Agilex™ 7 F-Series and I-Series FPGA Memory Subsystem IP User Guide

ID 789389
Date 7/15/2024
Public
Document Table of Contents

3.2.3.5. Signature Collisions

To achieve one access to the key memory per lookup, all signatures within a row must be unique; this guarantees that during search only one signature will match the incoming key’s signature and only one key will have to be read from the key memory for final comparison.

Signature collisions may be addressed through signature rehashing or increased signature width.

Signature Rehashing

If a collision occurs between the signatures inside a row, all signatures stored in this row are automatically recalculated using a different polynomial.

The system supports a configurable number of polynomials. For each rehashing attempt, the system goes through all polynomials in sequence, recalculating all signatures in the row and checking for collisions. The first polynomial which results in all existing signatures to be collision-free is selected as the signature polynomial for the row.

Increased Signature Width

Increasing the signature width can reduce the probability of signature collisions.

Reliable results, with keys ranging from incrementing patterns and pseudo-random, have been achieved with a signature width of 8 bits and the signature rehashing in operation. Signatures with a broader width should further reduce collisions.