US 2016/0259724 A1 · Systems and Methods for Implementing Low-Latency Lookup Circuits Using Sparse Hash Functions

Abstract

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.

Claims20

Dependent claims

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;
and
provide 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;
and
output a respective data value from each of the locations in the at least one memory identified by the received hash values.

14 more elements

A method, comprising:

performing, by lookup circuit:
receiving a given key value;
for each of one or more hash functions:
applying the hash function to the given key value to produce a respective hash value, wherein said applying the hash function comprises multiplying a bit vector representation of the given key value with a sparse bit matrix;
providing the respective hash value to a memory, wherein the respective hash value identifies a location in the memory;
and
obtaining data stored in the identified location in the memory.

4 more elements

A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

receiving a plurality of keys for key-value pairs to be evaluated in a lookup circuit;
generating two or more hash functions that when applied to each of the keys produce respective hash values that map the key to respective index values in the lookup circuit, wherein said generating comprises generating two or more candidate sparse random bit matrices, and wherein each of the hash functions multiplies an input bit vector representing a key with a respective one of the candidate sparse random bit matrices;
determining whether the hash functions are suitable for mapping each of the keys to a respective location in the lookup circuit at which a data portion of its key-value pair can be stored;
and
in response to determining that the hash functions are suitable for mapping each of the keys to a respective location in the lookup circuit at which a data portion of the respective key-value pair can be stored:
transferring a representation of each of the hash functions to the lookup circuit;
and
loading at least the data portion of each of the key-value pairs into a respective entry of a lookup table in a memory in the lookup circuit such that retrieval of the data portion of each of the key-value pairs from the respective entry is dependent on at least one of the index values to which the key for the key-value pair is mapped by the hash functions.

5 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims20