Multi-level compressed look-up tables formed by logical operations to compress selected index bits

Abstract

A lookup is performed using multiple levels of compressed stride tables in a multi-bit Trie structure. An input lookup key is divided into several strides including a current stride of S bits. A valid entry in a current stride table is located by compressing the S bits to form a compressed index of D bits into the current stride table. A compression function logically combines the S bits to generate the D compressed index bits. An entry in a prior-level table points to the current stride table and has a field indicating which compression function and mask to use. Compression functions can include XOR, shifts, rotates, and multi-bit averaging. Rather than store all 2 S entries, the current stride table is compressed to store only 2 D entries. Ideally, the number of valid entries in the current stride table is between 2 D-1 and 2 D for maximum compression. Storage requirements are reduced.

1 . A computing device configured to:
 store a plurality of stride tables arranged into a plurality of levels that form a multi-bit Trie structure, the plurality of stride tables including a compressed stride table pointed to by a table pointer in a prior-level selected entry in a prior stride table at a prior level in the plurality of levels, the prior-level selected entry being selected by a prior stride;   receive an input lookup key dividable into a plurality of strides corresponding to the plurality of levels, wherein at least one of the strides has multiple bits and the compressed stride table includes a plurality of valid entries selected with compressed index bits, the compressed index bits having fewer bits than a current stride for the compressed stride table; and   receive current stride bits for the current stride of the input lookup key and logically combine the current stride bits to generate logically combined compressed index bits.   
     
     
         2 . The computing device of  claim 1  further configured to:
 logically combine the current stride bits using a logical function specified by a function identified by a compression field stored in the prior level selected entry. 
 
     
     
         3 . The computing device of  claim 2  further configured to:
 logically combine the current stride bits using a logical function specified by a compression function type identified in the compression field. 
 
     
     
         4 . The computing device of  claim 3  wherein the compression function type specifies an exclusive-OR (XOR) logical function, an AND logical function, or an OR logical function,
 whereby stride bits are compressed to form the compressed index bits with the XOR, AND, or OR function. 
 
     
     
         5 . The computing device of  claim 4  wherein the compression function type specifies a conditional operation to be performed when the current stride bits match a condition value. 
     
     
         6 . The computing device of  claim 5  wherein the conditional operation is a shift or a rotate of at least a subset of the current stride bits,
 whereby conditional shifts or conditional rotates are supported as compression function types. 
 
     
     
         7 . The computing device of  claim 3  further configured to:
 logically combine input bits to generate logically-combined bits; and 
 select bits from the current stride bits for use in the compressed index bits. 
 
     
     
         8 . The computing device of  claim 7  further configured to:
 specify a mask indicating which of the current stride bits and which of the logically-combined bits to select to form the compressed index bits. 
 
     
     
         9 . The computing device of  claim 3  further further configured to:
 generate merged bits by logically combining current stride bits using an XOR logical function; and 
 select a subset of the merged bits for inclusion in the compressed index bits, 
 whereby current stride bits are first merged by the XOR logical function, and then masked to form the compressed index bits. 
 
     
     
         10 . A table lookup method comprising:
 receiving an input lookup key and dividing the input lookup key into a first stride and a second stride;   using the first stride to locate a first entry in a first-level stride table;   locating a second-level stride table using a table pointer in the first entry;   compressing stride bits in the second to generate compressed second stride bits;   using the compressed second stride bits to locate a second entry in the second-level stride table;   determining that the second entry is not a final entry and using a table pointer in the second entry as a pointer to a next-level stride table; and   using table pointers in additional entries as pointers to additional stride tables until a final entry in a final-level stride table is located.   
     
     
         11 . The table lookup method of  claim 10  further comprising
 comparing a second tag value stored in the second entry to determine when a valid match has occurred. 
 
     
     
         12 . The table lookup method of  claim 11  further comprising
 masking uncompressed stride bits in the second stride when comparing the second tag value and a second mask stored in the second entry is set. 
 
     
     
         13 . The table lookup method of  claim 12  further comprising:
 in response to said comparison, generating a partial stride mask in a current-level stride table at a current level using the current-level stride table as the final-level stride table; and 
 returning the lookup result stored in or pointed to by the final entry in the final-level stride table. 
 
     
     
         14 . A compressed-lookup-table computing device configured to:
 receive an input key;   extract a multi-bit stride from the input key;   compress the multi-bit stride to form a compressed index having fewer bits than the multi-bit stride;   use the compressed to locate a selected entry within a stride table; and   reading a result pointer from the selected entry and locate a lookup result.   
     
     
         15 . A table compression method comprising:
 dividing an input lookup key into one or more strides of stride bits populated into stride tables at one or more levels;   receiving uncompressed stride bits in a current stride for valid entries in a current stride table and placing the valid entries into an initial group;   determining a set of candidate bit-positions of uncompressed stride bits for the current stride table;   (a) for each candidate bit-position in the set of candidate bit-positions, finding a splitting value that indicates a degree of evenness of splitting groups into pairs of groups using the candidate bit-position;   selecting as a current discriminate bit-position a candidate bit-position that generated a smallest value for the splitting value;   removing the current discriminate bit-position from the set of candidate bit-positions and adding the current discriminate bit-position to bit-positions of compressed stride bits for the current stride;   splitting each group of valid entries into a pair of groups using a value of the current discriminate bit-position;   repeating from step (a) for groups having two or more valid entries until all groups have no more than one valid entry;   forming a compressed stride table from the valid entries by using the compressed stride bits to locate valid entries,   whereby bit-positions of compressed stride bits are determined by successively splitting groups of valid entries.   
     
     
         16 . A table lookup method comprising:
 dividing an input lookup key into a plurality of strides of stride bits including a first stride, a second stride, and a third stride;   using the first stride to locate a first entry in a first-level stride table;   locating a second-level stride table in a plurality of second-level stride tables using a table pointer in the first entry;   compressing stride bits in the second stride using a function indicated by a compression-type field in the first entry to generate compressed second stride bits;   using the compressed second stride bits to locate a second entry in the second-level stride table;   locating a third-level stride table in a plurality of third-level stride tables using a table pointer in the second entry;   compressing stride bits in the third stride using a second function indicated by a compression-type field in the second entry to generate compressed third stride bits;   using the compressed third stride bits to locate a third entry in the third-level stride table;   continuing for other strides in the input lookup key until a final entry in a final-level stride table is located; and   returning a lookup result stored in or pointed to by the final entry in the final-level stride table.   
     
     
         17 . The table lookup method of  claim 16 , further comprising:
 comparing a second tag value stored in the second entry with the second stride to determine that a valid match has occurred; and   comparing a third tag value stored in the third entry with the third stride to determine that the valid match has occurred, whereby stored tags are compared to uncompressed stride bits to determine when valid matches occur.   
     
     
         18 . The table lookup method of  claim 17 , further comprising:
 masking uncompressed stride bits in the second stride when comparing the second tag and a second mask stored in the second entry is set; and   masking uncompressed stride bits in the third stride when comparing the third tag when a third mask stored in the third entry is set, whereby masked comparisons allow for a partial stride match to determine when a valid mask has occurred.   
     
     
         19 . A table lookup method comprising:
 dividing an input lookup key into a plurality of strides of stride bits, including a first stride, a second stride, and a third stride;   using the first stride to locate a first entry in a first-level stride table;   locating a second-level stride table in a plurality of second-level stride tables using a table pointer in the first entry;   compressing stride bits in the second stride using a function indicated by a compression-type field in the first entry to generate compressed second stride bits;   using the compressed second stride bits to locate a second entry in the second-level stride table;   locating a third-level stride table in a plurality of third-level stride tables using a table pointer in the second entry;   compressing stride bits in the third stride using a second function indicted by a compression-type field in the second entry to generate compressed third stride bits;   using the compressed third stride bits to locate a third entry in the third-level stride table;   continuing for other strides in the input lookup key until a final entry in a final-level stride table is located;   returning a lookup result stored in or pointed to by the final entry in the final-level stride table;   compressing a stride table by:
 receiving uncompressed stride bits in a current stride for valid entries in the current stride table; and 
 determining a set of candidate bit-positions of the uncompressed stride bits for the current stride table by:
 generating merged stride bits by performing an XOR function on the uncompressed stride bits for the current stride; and 
 adding the merged stride bits to the set of candidate bit-positions of the uncompressed stride bits for the current stride table; 
 
   (a) selecting as a current discriminate bit-position a candidate bit-position that discriminates between valid entries in the current stride table;   removing the current discriminate bit-position from the set of candidate bit-positions and adding the current discriminate bit-position to bit-positions of compressed stride bits for the current stride;   repeating from step (a) for two or more valid entries until the bit-positions of compressed stride bits for the current stride discriminate between valid entries in the current stride table; and   forming a compressed stride table from the valid entries by using the bit-positions of compressed stride bits to locate valid entries.   
     
     
         20 . The table lookup method of  claim 19 , further comprising:
 generating merged stride bits by performing functions on the uncompressed stride bits for the current stride; and   when a merged stride bit is selected as the current discriminate bit-position, determining a current function used to generate the merged stride bit and storing an indication of the current function in the compression-type field.