Pipelined hash table with reduced collisions

Abstract

Apparatuses and methods for pipelined hashing are described herein. An example apparatus to perform a pipelined hash function may include a first memory to store a first plurality of bucket records, a second memory to store a second plurality of bucket records, and a hash circuit to receive a key and to perform a pipelined hash function using the key to provide a hash value. The hash circuit further to select a first bucket record of the first plurality of bucket records from the first memory based on a first subset of bits of the hash value. The hash circuit further to provide a location of a particular entry of an entry record of the plurality of entry records based on contents of the first bucket record and a second subset of bits of the hash value.

What is claimed is: 
     
         1 . A pipelined hash circuit comprising:
 a hash module that performs a hash function on a received key based on contents of a packet to provide a hash value having a first subset of bits and a second subset of bits, the first subset of bits indicating a location of a first bucket record of a plurality of bucket records stored in a first portion of memory; and   bucket logic circuitry that processes the second subset of bits and data stored in the first bucket record to identify a particular location of an entry record of a plurality of entry records in a second portion of memory, the bucket logic circuitry identifying, based on contents of the first bucket record identifying bits of the second subset of bits of the hash value, a particular entry of the entry record of the plurality of entry records in the second portion of memory that is associated with the received key.   
     
     
         2 . The pipelined hash circuit of  claim 1 , wherein the first bucket record comprises a select field that includes a plurality of select values and the bucket logic circuitry includes an entry selection module to select an individual bit of the second subset of bits of the hash value corresponding to each of the plurality of select values to provide an entry select value. 
     
     
         3 . The pipelined hash circuit of  claim 2 , wherein the first bucket record comprises a mask field to identify one or more entries currently stored in an entry record of the plurality of entry records in the second portion of memory and the bucket logic circuitry further includes a previous array identifier to identify which of the mask field bits less than the entry select value have a first logical value to provide a previous set array. 
     
     
         4 . The pipelined hash circuit of  claim 3 , wherein the first bucket record comprises a bucket pointer field to indicate a location of a first entry of the entry record of the plurality of entry records in the second portion of memory and the bucket logic circuitry further includes an entry pointer generator to identify the particular entry of the one or more entries of the entry record of the plurality of entry records in the second portion of memory by adding a count of the first logical values in the previous set array multiplied by an entry size to a bucket pointer of the first bucket record to generate an entry pointer to the particular entry of the entry record of the plurality of entry records in the second portion of memory that is associated with the received key. 
     
     
         5 . A network device to perform a pipelined hash function, comprising:
 a pipelined hash circuit comprising a hash module that performs a hash function on a received key based on contents of a packet to provide a hash value having a first subset of bits and a second subset of bits, the first subset of bits indicating a location of a first bucket record of a plurality of bucket records stored in a first portion of memory and bucket logic circuitry that processes the second subset of bits and data stored in the first bucket record to identify a particular location of an entry record of a plurality of entry records in a second portion of memory, the bucket logic circuitry identifying, based on contents of the first bucket record identifying bits of the second subset of bits of the hash value, a particular entry of the entry record of the plurality of entry records in the second portion of memory that is associated with the received key; and   an output logic circuit that provides a hit indication in response to a match between the key and a key value stored in the particular entry of the entry record of the plurality of entry records in the second portion of memory.   
     
     
         6 . The network device of  claim 5 , wherein the output logic circuit further provides an output action stored in the particular entry of the entry record of the plurality of entry records in the second portion of memory in response to a miss associated with an entry of a second plurality of entry records of a third portion of memory. 
     
     
         7 . The network device of  claim 6 , wherein the output logic circuit further provides a hit indication in response to a hit in an entry of an entry record of the second plurality of entry records in the third portion of memory. 
     
     
         8 . The network device of  claim 7 , wherein the output logic circuit further provides an output action stored in an entry of the second plurality of entry records of the third portion of memory in response to a hit associated with the entry of the second plurality of entry records of the third portion of memory. 
     
     
         9 . A method of performing a pipelined hash function, comprising:
 receiving a packet;   providing a key based on contents included in the packet;   performing a pipelined hash function on the key to generate a hash value having a first subset of bits and a second subset of bits;   selecting a first bucket record of a plurality of bucket records stored in a first portion of memory based on the first subset of bits of the hash value; and   identifying a particular location of an entry record of a plurality of entry records in a second portion of memory based on contents of the first bucket record identifying bits of the second subset of bits of the hash value, wherein the particular location of the entry record of the plurality of entry records in the second portion of memory is associated with the key.   
     
     
         10 . The method of  claim 9 , further comprising providing a hit indication in response to a match between the key and a key value stored in the particular entry of the entry record of the plurality of entry records in the second portion of memory. 
     
     
         11 . The method of  claim 10 , further comprising providing, to an output, an action stored at the particular entry of the entry record of the plurality of entry records in the second portion of memory. 
     
     
         12 . The method of  claim 9 , wherein the first bucket record comprises a select field that includes a plurality of select values, further comprising selecting an individual bit of the second subset of bits of the hash value corresponding to each of the plurality of select values to provide an entry select value. 
     
     
         13 . The method of  claim 12 , wherein the first bucket record comprises a mask field to identify one or more entries currently stored in an entry record of the plurality of entry records in the second portion of memory, further comprising identifying which mask field bits less than the entry select value have a first logical value to provide a previous set array. 
     
     
         14 . The method of  claim 13 , wherein the first bucket record comprises a bucket pointer field to indicate a location of a first entry of the entry record of the plurality of entry records in the second portion of memory, further comprising identifying the particular entry of the one or more entries of the entry record of the plurality of entry records in the second portion of memory by adding a count of the first logical values in the previous set array multiplied by an entry size to a bucket pointer of the first bucket record to generate an entry pointer to the particular entry of the entry record of the plurality of entry records in the second portion of memory that is associated with the key. 
     
     
         15 . The method of  claim 9 , further comprising providing an output action stored in the particular entry of the entry record of the plurality of entry records in the second portion of memory in response to a miss associated with an entry of a second plurality of entry records of a third portion of memory. 
     
     
         16 . The method of  claim 15 , further comprising providing a hit indication in response to a hit in an entry of an entry record of the second plurality of entry records in the third portion of memory. 
     
     
         17 . The method of  claim 16 , further comprising providing an output action stored in an entry of the second plurality of entry records of the third portion of memory in response to a hit associated with the entry of the second plurality of entry records of the third portion of memory.