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.3. Memory Subsystem MBL Operations

The multi-bin lookup (MBL) can perform ten different operations:
  1. Flush
  2. Key insertion
  3. Key lookup
  4. Modify result
  5. Key deletion
  6. Get handle
  7. Lookup using handle
  8. Modify result using handle
  9. Delete key using handle
  10. Insert key if not present, modify result if present

The following sections provide high-level descriptions of each MBL operation. Refer to the Performing MBL Operations section for detailed instructions on issuing MBL commands through the AXI Lite interface, and for waveform examples.

Flush

You must always issue a flush operation at the beginning of the traffic. The flush operation writes zeros to all locations of the hash table and reinitializes the free pointers list.

Key Insertion

The system performs the following sequence when a management system requests a key to be inserted:

  1. Key lookup is performed, as described below. The Lookup Core returns a match/no match result, and information needed in the insertion process (all bins from the row and HASH2 vector).
  2. All signatures in the selected row are compared with the signature of the candidate key:
    1. If there is no matching signature, then the signature is inserted to the first available bin in the row. If there are no free bins in the row, then the key cannot be inserted.
    2. If there is a matching signature already in the row, the signature rehashing is performed:
      1. All keys corresponding to this row are read from the key table.
      2. All signatures are re-calculated using the HASH2 polynomial that you can set as a parameter. All signatures are compared with each other to check if there are collisions. The first polynomial with no collisions is selected as the polynomial for this row.
  3. If the new key can be inserted, a free pointer to the key memory is obtained from a free pointers list.
    Note: When you have enabled SEMI_AUTO pointer management mode, the pointer must be provided by the software, based on MBL_GET_HANDLE command run prior to the insert.
  4. The key is written to the key memory, at the location indicated by the pointer.
  5. The hash table is written with the updated row.

Key Lookup

Key lookup can be requested from the control path. The sequence of operations is as follows:

  1. The key is hashed in HASH1 to produce a row number.
    Note: It is possible that different keys after going through HASH1 produce the same row number, this is referred to as row collision.
  2. The system uses the row number to read the corresponding row from the hash table.
  3. The key is hashed in HASH2 to generate a signatures.
  4. The system compares the signature with a signature in each active bin in the row.
  5. If the system detects a signature match, the pointer from the matching bin is used to read a key and result from the key memory.
  6. The system compares the key read from the memory to the key being looked up; if a match is detected, the result is sent to output as a valid lookup result.

Modify Result Using Key

  1. Key lookup sequence 1-5 is performed.
  2. The system compares the key read from the memory to the key being looked up; if a match is detected, the result is modified.

Key Deletion

When a management system requests a key to be deleted, the following sequence is performed in hardware:

  1. Key lookup sequence 1-6 is performed.
  2. If the key is found, then the corresponding bin is marked as free.
  3. If the bin is located in the middle of other used bins then the bin at the highest index is moved to fill the gap left after the bin corresponding to the deleted entry.
  4. The pointer from the deleted entry is returned to the free pointers list, if the hardware-based pointer management is enabled.

Get Handle

When the Semi-automatic pointer management option is enabled, you can request a number of free handles. Refer to Optimization Features and MBL Get Handle Operation for more information.

Lookup Using Handle

  1. The handle is used to access the indicated address.
  2. Key and result are read from the key table.
  3. The key and result is sent to output as a valid lookup result.

Modify Result Using Handle

  1. The handle is used to access the indicated address.
  2. The result is modified.

Key Deletion Using Handle

  1. The handle is used to read a key and result from the key table.
  2. If the key is found in hash table, then the corresponding bin is marked as free.
  3. If the bin is located in the middle of other used bins then the bin at the highest index is moved to fill the gap left after the bin corresponding to the deleted entry.
  4. The pointer from the deleted entry is returned to the free pointers list.

Insert Key if Not Present, Modify Result if Present

  1. Key lookup sequence 1-6 is performed.
  2. If a match is detected, modify operation is executed.
  3. If no match is detected, key insertion operation is performed.