Method and system for an algorithm and circuit for a high performance exact match lookup function

摘要

In one aspect, a device is configured to provide a lookup operation for looking up a data value stored in a result table. The device includes several data tables for storing keys, or compressed representations of keys, associated with data values stored in the result table. During an example lookup operation, storage locations included within the data tables are searched for a particular key, or compressed representations of the key. If the key is found, the storage location is used to identify a memory address associated with the result table. In some implementations, the data tables are accessed in parallel to provide a lookup operation having a fixed latency. Storage locations within the data tables also are arranged to reduce the amount of memory used to implement each data table. In some implementations, the data tables are configured to use no more than one result table access per lookup operation.

主权项

1. An apparatus comprising:
a first storage device implementing a first data table including a plurality of storage locations, each storage location capable of storing a compressed key generated by applying a first hash function to a key, each storage location having a respective address in the first data table, each address being associated with one or more indexes, each index capable of being generated by applying a second hash function to a key, wherein:
each of the addresses of a first group of the storage locations is associated with a compressed index, each compressed index being a compressed representation of two or more indexes; andwhen provided with a compressed representation of a key during a lookup operation, the first storage device provides the address where the compressed representation of the key is stored if the compressed representation of the key is stored in the first data table; a second storage device implementing a second data table including a plurality of storage locations, each storage location capable of storing a key, each storage location having a respective address in the second data table, each address being associated with one or more indexes, each index capable of being generated by applying a third hash function to a key, wherein:
when provided with a key during a lookup operation, the second storage device provides the address where the key is stored if the key is stored in the second data table; and one or more processing devices for performing a lookup operation including:
receiving a key;generating a compressed representation of the received key using the first hash function;providing the compressed representation of the received key to the first storage device;providing the received key to the second storage device;receiving an address associated with the compressed representation of the received key from the first storage device;receiving an address associated with the received key from the second storage device;selecting an address received from the first and second storage devices, wherein when an address is received from the first storage device and an address is received from the second storage device, the address from the second storage device is selected; andproviding the selected address to a result table that provides a data value based on the selected address.