Systems and methods for implementing dynamically configurable perfect hash tables

Patent metadata

Field	Value
Publication number	US-9384145-B2
Application number	US-201314010183-A
Country	US
Kind code	B2
Filing date	Aug 26, 2013
Priority date	Aug 26, 2013
Publication date	Jul 5, 2016
Grant date	Jul 5, 2016

Abstract

Hardware circuitry may evaluate minimal perfect hash functions mapping keys to addresses in lookup tables. The circuitry may include primary hash function sub-circuits that apply linear hash functions to input key values (using carry-free arithmetic) to produce primary hash values. Each sub-circuit may multiply bit vectors representing key values by a bit matrix and add a constant bit vector to the result. The circuitry may include a secondary hash function sub-circuit that generates secondary hash values by aggregating values associated with multiple primary hash values using signed, unsigned, or modular integer addition, or bit-wise XOR operations. Secondary hash values may be usable to access data values in the lookup table that are associated with particular input key values. The circuitry may determine the validity of input keys and may alter the configuration or contents of the lookup tables. The hash function sub-circuits may include programmable hash tables.

First claim

What is claimed:

1. A circuit configured to evaluate at least one perfect hash function, comprising:
an input configured to receive a key value;
two primary hash function sub-circuits coupled to the input;
a secondary hash function sub-circuit; and
at least one memory;
wherein each of the primary hash function sub-circuits is configured to perform carry-free arithmetic that applies a respective linear hash function to the key value to produce a respective primary hash value, and
wherein the secondary hash function sub-circuit is configured to:
receive the respective primary hash values from the two primary hash function sub-circuits; and
generate a secondary hash value dependent on the received primary hash values, wherein the secondary hash value is usable to access a data value stored in the at least one memory that is associated with the key value.

2. The circuit of claim 1 ,
wherein the at least one memory stores a representation of each of the respective linear hash functions; and
wherein to apply the respective linear hash function to the key value, each of the primary hash function sub-circuits is configured to access the representation of the respective linear hash function stored in the at least one memory.

3. The circuit of claim 1 ,
wherein the at least one memory stores a representation of a secondary hash function; and
wherein to generate the secondary hash value, the secondary hash function sub-circuit is configured to access the representation of the secondary hash function stored in the at least one memory.

4. The circuit of claim 3 ,
wherein to generate the secondary hash value, the secondary hash function sub-circuit is configured to:
obtain a respective value associated with each of the received primary hash values from the at least one memory; and
aggregate the respective values associated with each of the received primary hash values using unsigned integer addition, signed integer addition, modular integer addition, or a bit-wise XOR operation.

5. The circuit of claim 1 ,
wherein the circuit further comprises an input configured to receive a hash function selection value;
wherein the at least one memory stores a plurality of representations of linear hash functions;
wherein the at least one memory stores a plurality of representations of secondary hash functions; and
wherein the hash function selection value induces selection of at least one of: a representation of a linear hash function to be accessed by one of the primary hash function sub-circuits, or a representation of a secondary hash function to be accessed by the secondary hash function sub-circuit.

6. The circuit of claim 5 ,
wherein the hash function selection value induces selection of one of a plurality of sets of configuration parameter values, each set of configuration parameter values being associated with a respective one of a plurality of lookup tables stored in the at least one memory;
wherein the secondary hash function sub-circuit is configured to generate the secondary hash value dependent on the selected one of the plurality of sets of configuration parameter values; and
wherein the secondary hash value is usable to access the data value in one of the plurality of lookup tables in the at least one memory dependent on the selected one of the plurality of sets of configuration parameter values.

7. The circuit of claim 1 ,
wherein the circuit further comprises an input configured to receive a word selection parameter value; and
wherein the word selection parameter value induces selection of the data value stored in the at least one memory from among a plurality of data values stored in the at least one memory that are associated with the key value.

8. The circuit of claim 1 ,
wherein the at least one memory is configured to store, for each of a plurality of key values, one or more data values that are associated with the key value;
wherein at least one of the number of data values stored in the at least one memory that are associated with each key value or the size of the data values stored in the at least one memory is configurable without a hardware modification to the circuit.

9. The circuit of claim 1 ,
wherein the data value is stored in the at least one memory in an entry of a lookup table;
wherein the at least one memory further comprises a table configured to store a value for each of one or more configuration parameters of the lookup table; and
wherein the configuration parameters of the lookup table specify one or more of: a key size for the lookup table, a number of key values for the lookup table, a size for data values stored in the lookup table, a number of data values associated with each key value in the lookup table, or a value of a signal indicating whether received key values are to be validated by the evaluation circuit.

10. The circuit of claim 1 ,
wherein the data value is stored in the at least one memory in an entry of a lookup table;
wherein the lookup table further stores a key value that is associated with the data value; and
wherein the circuit further comprises a validation sub-circuit configured to:
compare the key value stored in the at least one memory that is associated with the data value and the key value received by the input;
determine whether the key value stored in the at least one memory that is associated with the data value matches the key value received by the input; and
output an indication of a result of the determination.

11. The circuit of claim 1 ,
wherein the key value is represented by a bit vector comprising plurality of bits; and
wherein to apply a respective linear hash function to the key value to produce a respective primary hash value, each of the primary hash function sub-circuits is configured to multiply the bit vector by a pre-defined bit matrix.

12. The circuit of claim 11 , wherein to apply a respective linear hash function to the key value to produce a respective primary hash value, each of the primary hash function sub-circuits is further configured to add a pre-defined constant bit vector to a result of the multiplication.

13. The circuit of claim 1 , wherein to perform carry-free arithmetic that applies a respective linear hash function to the key value, each of the primary hash function sub-circuits is configured to perform polynomial arithmetic over a Galois field.

14. A method for evaluating a perfect hash function, comprising:
performing, by an evaluation circuit:
receiving a given key value;
applying a first primary hash function to the given key value to produce a first primary hash value;
applying a second primary hash function to the given key value to produce a second primary hash value;
generating a secondary hash value dependent on the first and second primary hash values; and
accessing a data value in a lookup table that is associated with the given key value, wherein said accessing is dependent on the secondary hash value;
wherein at least one of said applying a first primary hash function and said applying a second primary hash function comprises performing carry-free arithmetic to produce a respective primary hash value dependent on the given key value.

15. The method of claim 14 , further comprising:
prior to said receiving:
generating a representation of the first primary hash function;
generating a representation of the second primary hash function;
generating a representation of the secondary hash function; and
transferring the representations of the first primary hash function, the second primary hash function, and the secondary hash function to the evaluation cir

Assignees

• Oracle Int Corp

Inventors

• Gura Nils
• Steele Jr Guy L
• Chase David R

Classifications

• G06F12/1018 Primary

  involving hashing techniques, e.g. inverted page tables · CPC title