Search engine devices that support high speed parallel decoding of digital search tries

A search engine device that supports a Patricia trie arrangement of search keys includes an array of comparator cells that supports parallel decoding of the Patricia trie. This array of comparator cells processes a plurality of distinguishing bit identifiers for nodes in the Patricia trie in parallel with a corresponding plurality of bits of an applied search key during a search operation. In response to this processing, the array generates a match signal that identifies a location of a matching search key candidate within the Patricia trie.

TECHNICAL FIELD

The disclosure herein relates to integrated circuit devices and, more particularly, to search engine devices.

BACKGROUND

A path-compressed digital search trie (DST) that supports branching decisions based on single binary digits is often referred to as a Patricia trie.FIG. 1Aillustrates a conventional digital search trie10athat supports eight 8-bit search keys A-H andFIG. 1Billustrates a conventional Patricia trie10bthat is achieved by removing all unary branches from the trie10aand labeling all remaining nodes with the distinguishing bit positions from the search keys A-H. Conventional search techniques include using selected bits from an applied search key to traverse the trie10band locate a result by a process of elimination.

FIGS. 2A-2Billustrate conventional multiple steps used to construct a Patricia trie20that supports N=8 keys of size W=16-bits. These eight keys are illustrated in the top left corner ofFIG. 2A. In step1, the leftmost bit (bit15) is identified as a bit that can split the set of eight keys into two groups. The first group includes a single key (key7), which has a leftmost bit equal to 1, and the second group includes the seven remaining keys having leftmost bits equal to 0. In step2, the seven keys in the second group can be further split into a group of six keys and a group of one key based on the 12thbit. In step3, the group of six keys identified in step2can be split into a group of two keys and a group of four keys based on the 10thbit. In step4, the group of two keys identified in step3can be further split into two groups of one key each (keys4and5), based on the 9thbit. In step5, the group of four keys identified in step3can be split into a group of one key and a group of three keys based on the 8thbit. In step6, the group of three keys identified in step5can be split into a group of two keys and a group of one key based on the 6thbit. Finally, in step7, the group of two keys identified in step6is evenly split based on the 3rdbit. Thus, as illustrated byFIG. 2B, the nodes of the Patricia trie are labeled with the distinguishing bit positions (e.g., bits15,12,10,9,8,6and3). In particular, the trie20consists of nodes that identify a set of bit positions that are examined in an applied search key, and left and right branches (pointers) to follow based on the value of each examined bit.

As will be understood by those skilled in the art, the construction of the trie20requires log2W bits to encode each bit position, log2N bits to encode each of the left or right pointers and a bit to indicate whether a branch leads to another intermediate node or a leaf node. There are always N−1 branch nodes in a trie with N keys. Moreover, for N<W, all N−1 nodes must be visited in the worst case (skewed). For N>W, the number of nodes traversed is bounded by W (i.e., examine all bits in an applied key). In the best case, which occurs when the search trie is balanced, only log2N nodes are visited.

Searching the Patricia trie20ofFIG. 2Busing distinguishing bit values extracted from the applied search key results in the identification of a candidate key in a leaf node (or possibly pointed to by the leaf node) that may (or may not) exactly match the applied search key. To determine whether an exact match is present, the candidate key must be compared to the applied search key. For example, searching the trie20with an applied search key equal to 0001000111000000 will terminate at the leaf node containing key6, which represents an exact match. However, searching the same trie20with a key equal to 0111111000111111 will also terminate at the leaf node containing key6, but this key clearly does not match the applied search key.

In order to modify the trie20with the insertion of a new key, it is necessary to find a predecessor key (i.e., a key in the trie with the highest ordinal value less than the new key) or a successor key (i.e., a key in the trie with the lowest ordinal value greater than the new key). This may be accomplished by finding where a distinguishing bit is missing that would have led to the new key had the new key been present in the trie. One conventional technique to find the distinguishing bit includes finding a longest common prefix (LCP) between the new key (S) and a candidate key (K) and adjusting all bits following the LCP. A new pseudo-key P may be created consisting of the concatenation of the LCP and a string of all 0's or 1's, depending on whether the bit following the LOP in the new key is a 0 or 1. For example, if the new key (S) equals 0110100011000001, then a search of the trie20results in an identification of key2(0000001001100011) as the candidate key, which does not equal to the new key. The LOP between the new key and the candidate key (key2) is LCP=0***************. This LCP value indicates that the first distinguishing bit should have been bit14of the new key S, which equals 1. The pseudo-key is therefore P=0111111111111111. Performing a search of the trie20using the pseudo-key P results in an identification of key6. Because bit14of the new key S is 1, key6must be a predecessor of the new key S. This confirms the following relationship: key6<new key S<key7. Based on this relationship, the new key S is identified as key7and original key7is renumbered as key8in the conventional trie20′ inFIG. 2C.

SUMMARY

Embodiments disclosed herein include search engine devices configured to support Patricia tries of search keys. According to some of these embodiments, a search engine device includes an array of comparator cells. This array is configured to support a search operation by processing a plurality of distinguishing bit identifiers for nodes in a Patricia trie in parallel with a corresponding plurality of bits of an applied search key. In response to this processing, a match signal is generated that identifies a location of a matching search key candidate within the Patricia trie.

In some embodiments, the array of comparator cells includes cells that are configured to perform a comparison between two of the distinguishing bit identifiers. The array also includes diagonal and non-diagonal cells of different configuration. A priority encoder and a search key memory are also provided. The priority encoder is configured to generate a match index in response to the match signal and the search key memory is configured to generate the matching search key candidate in response to the match index. An exact match determination is made using a comparator that is configured to compare the matching search key candidate against the applied search key.

Still further embodiments include a search engine device having a match circuit and a search key memory therein. The match circuit is configured to support parallel decoding of a Patricia trie of search keys and the search key memory is configured to store search keys (and possibly corresponding key indexes) that are accessible using a result generated from the parallel decoding of the Patricia trie by the match circuit. The search engine device may also include a tree node memory, which is configured to store distinguishing bit identifiers for nodes in the Patricia tree. According to these embodiments, the search engine device performs the operations of decoding a plurality of distinguishing bit identifiers for nodes in a Patricia trie in parallel with a corresponding plurality of bits of an applied search key during a search operation and generating a match signal that identifies a location of a matching search key candidate within the Patricia trie.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

FIG. 3illustrates a block diagram of a search engine device30that supports a plurality of Patricia trie databases. The search engine device30includes a tree node memory32having a plurality of rows of memory cells therein. This tree node memory32is responsive to a row address (ROW), which specifies the location (e.g., memory row) of the distinguishing bit positions for a selected database (or portion of a database) of search keys, which is arranged as a Patricia trie. In particular, each row of the tree node memory32is illustrated as having a width equal to: (M−1)×log2W, where the value M−1 designates the number of nodes within the selected trie and W designates the width of the search keys supported by the tree. Using the trie20′ ofFIG. 2Cas an example, the output of the tree node memory32in response to a read operation equals 8×4=32 bits, with each of the eight 4-bit groupings designating a value of a distinguishing bit corresponding to a node within the trie20′. Thus, node0within the trie20′ would be represented by its distinguishing bit equal to 3 (i.e., 0011) and node1would be represented by its distinguishing bit equal to 6 (i.e., 0110). The remaining nodes2-7would be similarly designated.

An applied search key (S) of W bits is provided to a 2:1 routing multiplexer34. The output of the multiplexer34is forwarded to a bank of W:1-bit multiplexers36. This bank, which is shown as having a size equal to M−1, receives the output of the tree node memory32as a control signal (i.e., multiplexer select signal). Based on this configuration, the bank of multiplexers36selects M−1 distinguishing bits from an applied search key (S). Using the trie20′ ofFIG. 2Cagain as an example, the bank of multiplexers36would select the following distinguishing bits:3,6,8,9,10,12,14and15, from the applied search key (S) when performing a search operation. These M−1 distinguishing bits and the output of the tree node memory32are provided in parallel as inputs to a match block40. As described more fully hereinbelow with respect toFIGS. 4A-4C, the match block40includes an array of comparator cells. This array is configured to process a plurality of distinguishing bit identifiers for nodes in a Patricia trie (e.g., the row output of the tree node memory32) in parallel with a corresponding plurality of M−1 distinguishing bits of an applied search key during each search operation.

This processing results in the generation of a match signal that identifies a location of a matching search key candidate within the Patricia trie. This candidate represents a possible “match” to the applied search key. This match signal is illustrated as a M-bit match vector (with one bit set), which is provided to a priority encoder38. This priority encoder38encodes the match signal into a match index by finding the ordinal position of the single set bit in the match signal, for example. This match index is provided as a row address offset, which is combined with the row address (ROW) (designating a particular database) to access a key memory42. This access of the key memory42results in the generation of a candidate key (C) corresponding to the bit set within the M-bit match vector. The access of the key memory42may also result in the generation of additional data (e.g., associated data, which may include a key index, etc.) stored with the candidate key.

The candidate key C and the applied search key S are then compared to determine whether the candidate key C matches the applied search key S. This comparison is performed in a longest common prefix (LCP) determination circuit44, which determines a number of matching leading bits between the candidate key C and the applied search key S. When the number of matching leading bits is equivalent to W, then the search is complete and a matching index, which was returned with the candidate key during a read of the key memory42, is output from the search engine device30.

However, if the comparison performed by the LCP determination circuit44identifies a mismatch, then a pseudo key P is generated in order to support operations to insert the applied search key S into the Patricia trie. This pseudo key is generated as the longest common prefix identified by the LCP determination circuit44concatenated with a string of bits equal to the W-nth bit in the applied search key S, where n equals the length of the longest common prefix between the applied search key S and the candidate key C. After generation by the LCP determination circuit, the pseudo key P is passed through the 2:1 routing multiplexer34to the W:1-bit multiplexers36. The M−1 distinguishing bits (e.g., bits3,6,8,9,10,12,14and15) within the pseudo key P are then passed to the match block40in order to identify a location of a matching key. The match vector generated by the match block40is then passed to the priority encoder38, which is illustrated as generating a predecessor/successor index. This index specifies a location of a predecessor of the original applied search key S for the case where the W-nth bit appended to pseudokey is 1 or a location of a successor of the original applied search key S for the case where the W-nth bit appended to the pseudokey is 0. This predecessor index is then used to specify the location to which the applied search key S is to be inserted into the Patricia trie during a learn operation.

FIGS. 4A-4Cillustrate a match block40according to embodiments of the present invention, which includes a folded array of comparator cells (42aand42b). This exemplary array, which includes both diagonal cells42a(cells (0,0), (1,1), (2,2), . . . (7,7)) and non-diagonal cells42b(cells (1,0), (2,0), (3,0), . . . (7,0), (2,1), (3,1), . . . , (7,6)), is illustrated as supporting a small trie having eight nodes and nine leaves representing the nine stored keys. The size of this array varies with the capacity of the Patricia trie used in a particular application. This match block40is illustrated as being responsive to a plurality of distinguishing bit identifiers, which are provided by the tree node memory32, and a corresponding M−1 bits of an applied search key (KeyValue0-KeyValue7) or pseudo key, which are selected by the bank of multiplexers36. These distinguishing bit identifiers are illustrated as 4-bit identifiers: DB0<3:0>, DB1<3:0>, DB7<3:0>, for the case where the Patricia trie has eight nodes (see, e.g.,FIG. 2C) and W=16. In response to these inputs, the match block40generates a multi-bit match signal (MATCH0-MATCH8) having a single set bit (i.e., single bit remaining at logic 1 level). This match signal identifies a location of a matching search key candidate within the selected Patricia trie.

The compare operations begin with the diagonal cells and proceed downward and to the right across the array. In particular, the diagonal cells42agenerate logic 1 CARE signals (i.e., CARE=Vdd), which extend downward and to the right across the array, in addition to MATCH and MISMATCH signals. These logic 1 CARE signals indicate the cells located below and to the right of the corresponding diagonal cell are to participate in a matching operation. The diagonal cells42aeliminate many keys from the search path because whenever a KVi value equals 0, then the MATCH line to the right of the diagonal cell will be pulled low thereby eliminating a key. Alternatively, whenever the KVi value equals 1, the match line to the left of the diagonal cell receiving the KVi value will be pulled low to eliminate another key.

The horizontal MISMATCH signal is generated by an inverter I2, which receives a corresponding key value (KeyValue=KV) as an input signal. This key value is also provided as vertical MISMATCH signal. A non-inverting buffer B1(with open collector (OC) configuration) generates a right MATCH signal and an inverting buffer I1(with open collector (OC) configuration) generates a left MATCH signal. As illustrated best byFIG. 4A, the MATCH signals are weakly held at logic 1 values (i.e., precharged) by a pull-up resistor network that is connected to a power supply voltage (shown as “+”). During a search operation, all but one (or possibly all) of these weak logic 1 values is pulled low by operation of the cells42aand42bwithin the folded array.

The non-diagonal cells42bare illustrated as including a log2W comparator C1, which generates a logic 1 output signal when DB[X] is greater than DB[Y] and a logic 0 output signal when DB[X] is less than DB[Y]. This output signal is passed through an inverter I3to an input of a first AND gate AND1. The output signal from the comparator C1is also passed directly to an input of a second AND gate AND2. Vertical and horizontal CARE signals are also provided to inputs of the first and second AND gates AND1, as illustrated. The CARE signals generated by the first and second AND gates are provided to first and second NAND gates (ND1and ND2), which have an open collector (OC) output configuration. These first and second NAND gates ND1and ND2are also responsive to vertical and horizontal MISMATCH signals. The output terminals of the first and second NAND gates ND1and ND2are connected to a vertical MATCH line and a horizontal MATCH line, respectively.

Operations of the match block40and the folded array of comparator cells42aand42btherein will now be described using a search example as applied to the Patricia trie20′ ofFIG. 2C. In this example, an applied search key S<15:0> equal to 1000001111111111 will result in the generation of a M−1 bit key value equal to: KeyValue<0:7>=KV<0:7>=11101001 for the following distinguishing bits: DB0<3:0>=3=(0011), DB1<3:0>=6 (0110), DB2<3:0>=8 (1000), DB3<3:0>=10 (1010), DB4<3:0>=9 (1001), DB5<3:0>=12 (1100), DB6<3:0>=14 (1110) and DB7<3:0>=15 (1111). Applying these values to the folded array ofFIG. 4Awill cause the diagonal cells (0,0), (1,1), (2,2), (4,4), and (7,7) to pull down the match line to the left of their cells, match0,1,2,6, and7since the KV input to these cells is 1. Similarly, diagonal cells (3,3), (5,5) and (6,6) pull the match lines to their right down, namely match lines4,6, and7. This process alone eliminates 6 of the 9 possible matching candidates. Moreover, the above specified values will also cause the comparator C1in the non-diagonal cell (4,3) to generate a logic 1 voltage at its output (because DB3<3:0>=10 (1010) is greater than DB4<3:0>=9 (1001). This generation of a logic 1 voltage will cause the first AND gate AND1to block vertical transfer of a logic 1 CARE signal through the cell (4,3) and cause the second AND gate AND2to pass a horizontal CARE signal through the cell (4,3). In addition, the application of these distinguishing bit and key values to the folded array ofFIG. 4Awill cause the comparator C1in all non-diagonal cells, except cell (4,3), to generate a logic 0 voltage at its output. This generation of a logic 0 voltage will cause the first AND gate AND1to enable vertical transfer of CARE signals through these non-diagonal cells and cause the second AND gate AND2to block transfer of horizontal CARE signals across these cells. Based on these operations and the generation of the MATCH and MISMATCH signals derived from the following key values: KeyValue<0:7>=KV<0:7>=11101001, a 9-bit match signal MATCH<0:8> equal to 000000001 will be generated.

Referring again toFIG. 3, this match signal MATCH<0:8> equal to 000000001 is passed to the priority encoder38, which converts the match signal to a 4-bit match index. For this example, the match index is set to 8 (i.e., 1000). This match index and row address (ROW), which designates a starting row address for the trie20′ illustrated byFIG. 2C, are combined to result in the generation of a candidate key C equal to: 1000011111111111 and the generation of a corresponding key index (and possibly additional associated data) from the key memory42. This candidate key is illustrated as Key8inFIG. 2C.

This candidate key C and the applied search key S are then compared to determine whether the candidate key C matches the applied search key S. This comparison is performed in the longest common prefix (LCP) determination circuit44. In particular, a length vector L is generated by determining whether a bit-to-bit equivalency is present between the candidate key C and the applied search key S. Because a bit-to-bit equivalency does exist in this example, the LCP determination circuit44outputs the key index associated with the matching key.