Integrated search engine devices that support multi-way search trees having multi-column nodes
View Patent ↗An integrated circuit search engine device supports a multi-way tree of search keys therein. The search engine device includes at least one multi-node sub-engine. The multi-node sub-engine includes a node processor and a plurality of columns of sub-nodes containing search keys. The node processor is configured to distribute an applied search key in parallel to each of the plurality of columns of sub-nodes in response to a search request. The node processor is also configured to receive and resolve corresponding sub-node search results from the plurality of columns of sub-nodes.
1. An integrated circuit device, comprising:
a search engine configured to store a multi-way tree of search keys using a hierarchy of node sub-engines, wherein the hierarchy of node sub-engines each comprise a node processor and a plurality of columns of sub-nodes containing search keys associated with a corresponding level of the multi-way tree, wherein each node processor, of the hierarchy of node sub-engines, is configured to distribute an applied search key in parallel to each of a corresponding plurality of columns of sub-nodes in response to a search request and is further configured to receive sub-node search results from the corresponding plurality of columns of sub-nodes, and wherein each of the corresponding plurality of columns of sub-nodes is configured to perform a, sub-node search by identifying a respective branching key stored therein and returning a relative relationship between the applied search key and the branching key to the node processor in the same node sub-engine as the corresponding plurality of columns of sub-nodes.
2. The device of claim 1 , wherein said node processor is configured to store child pointers associated with the search keys stored in the corresponding plurality of columns of sub-nodes.
3. The device of claim 1 , wherein each of the corresponding plurality of columns of sub-nodes is configured to perform a sub-node search by identifying a respective branching key stored therein and returning to the node processor: (a) an indicator of position of the branching key within the sub-node and (b) a relative relationship between the applied search key and the branching key as sub-node branching results.
4. The device of claim 3 , wherein said node processor is further configured resolve a node branching result from the plurality of sub-node branching results returned from the corresponding plurality of columns of sub-nodes.
5. The device of claim 4 , wherein said node processor is configured to store child pointers associated with the search keys stored in the corresponding plurality of columns of sub-nodes; and wherein resolving a node branching result from the plurality of sub-node branching results includes identifying a stored child pointer associated with a branching key identified by one of the corresponding plurality of columns of sub-nodes.
6. The device of claim 4 , wherein each of the corresponding plurality of columns of sub-nodes is further configured to perform a sub-node search by passing a best match prefix length to said node processor in the event a first search key in the sub-node matches the applied search key.
7. The device of claim 6 , wherein each of the corresponding plurality of columns of sub-nodes is further configured to perform a sub-node search by passing an indicator of position of the first search key to said node processor.
8. The device of claim 6 , wherein said node processor is configured to store child pointers associated with the search keys stored in the corresponding plurality of columns of sub-nodes.
9. An integrated search engine device, comprising:
a pipelined arrangement of search and tree maintenance sub-engines configured to store corresponding levels of a multi-way tree of search keys therein, said pipelined arrangement of search and tree maintenance sub-engines comprising a node sub-engine associated with a non-leaf level of the multi-way tree, said node sub-engine comprising a node processor and a plurality of columns of sub-nodes containing search keys, said node processor configured to distribute an applied search key in parallel to each of the plurality of columns of sub-nodes in response to a search request received by said node sub-engine and further configured to receive corresponding sub-node search results from the plurality of columns of sub-nodes, wherein each of the plurality of columns of sub-nodes is configured to perform a sub-node search by identifying a respective branching key therein and returning a relative relationship between the applied search key and the branching key to the node processor.
10. The device of claim 9 , wherein said node processor is configured to store child pointers associated with the search keys stored in the plurality of columns of sub-nodes.
11. The device of claim 9 , wherein each of the plurality of columns of sub-nodes is configured to perform a sub-node search by identifying a respective branching key therein and returning an indicator of position of the branching key within the sub-node and a relative relationship between the applied search key and the branching key as sub-node branching results, to the node processor.
12. The device of claim 11 , wherein said node processor is further configured resolve a node branching result from the plurality of sub-node branching results returned from the plurality of columns of sub-nodes.
13. The device of claim 12 , wherein said node processor is configured to store child pointers associated with the search keys stored in the plurality of columns of sub-nodes; and wherein resolving a node branching result from the plurality of sub-node branching results includes identifying a stored child pointer associated with a branching key identified by one of the plurality of columns of sub-nodes.
14. The device of claim 12 , wherein each of the plurality of columns of sub-nodes is further configured to perform a sub-node search by passing a best match prefix length to said node processor in the event a first search key in the sub-node matches the applied search key.
15. An integrated search engine device, comprising:
a pipelined arrangement of search and tree maintenance sub-engines configured to store corresponding levels of a multi-way tree of search keys therein, said pipelined arrangement of search and tree maintenance sub-engines comprising a multi-node sub-engine having a node processor and a plurality of columns of sub-nodes therein, said node processor configured to distribute an applied search key in parallel to each of the plurality of columns of sub-nodes in response to a search request and further configured to receive corresponding sub-node search results from the plurality of columns of sub-nodes, wherein each of the plurality of columns of sub-nodes is configured to perform a sub-node search by identifying a respective branching key therein and returning a relative relationship between the applied search key and the branching key to the node processor.
16. The device of claim 15 , wherein each of the plurality of columns of sub-nodes comprises sub-node memory configured to store search keys associated with multiple nodes of the multi-way tree.
17. The device of claim 15 , wherein said node processor is configured to store child pointers associated with the search keys stored in the plurality of columns of sub-nodes.
18. The device of claim 15 , wherein each of the plurality of columns of sub-nodes is configured to perform a sub-node search by identifying a respective branching key therein and returning an indicator of position of the branching key within the sub-node and a relative relationship between the applied search key and the branching key as sub-node branching results, to the node processor.