Systems and Methods for Implementing Low-Latency Lookup Circuits Using Sparse Hash Functions

摘要

A lookup circuit evaluates hash functions that map keys to addresses in lookup tables. The circuit may include multiple hash function sub-circuits, each of which applies a respective hash function to an input key value, producing a hash value. Each hash function sub-circuit may multiply bit vectors representing key values by a sparse bit matrix and may add a constant bit vector to the results. The hash function sub-circuits may be constructed using odd-parity circuits that accept as inputs subsets of the bits of the bit vectors representing the key values. The sparse bit matrices may be chosen or generated so that there are at least twice as many 0-bits per row as 1-bits or there is an upper bound on the number of 1-bits per row. Using sparse bit matrices in the hash function sub-circuits may allow the lookup circuit to perform lookup operations with very low latency.

主权项

1. A circuit configured to perform a table lookup operation, comprising:
an input configured to receive a representation of a key value; one or more hash function sub-circuits coupled to the input; and at least one memory; wherein the representation of the key value comprises a bit vector, wherein each of the hash function sub-circuits comprises a representation of a sparse bit matrix; and wherein each of the hash function sub-circuits is configured to:
apply a respective hash function to the key value to produce a respective hash value; andprovide the respective hash value to the at least one memory, wherein the respective hash values identifies a respective location in the at least one memory;wherein to apply the respective hash function to the key value, the hash function sub-circuit is configured to multiply the bit vector with the sparse bit matrix; and wherein the at least one memory is configured to:
receive the respective hash values provided by each of the hash function sub-circuits; andoutput a respective data value from each of the locations in the at least one memory identified by the received hash values.