Integrated search engine devices having pipelined search and tree maintenance sub-engines therein that support variable tree height
View Patent ↗A pipelined search engine device, such as a longest prefix match (LPM) search engine device, includes a hierarchical memory and a pipelined tree maintenance engine therein. The hierarchical memory is configured to store a b-tree of search prefixes (and possibly span prefix masks) at multiple levels therein. The pipelined tree maintenance engine, which is embedded within the search engine device, includes a plurality of node maintenance sub-engines that are distributed with the multiple levels of the hierarchical memory. The search engine device may also include pipeline control and search logic that is distributed with the multiple levels of the hierarchical memory.
1. A pipelined integrated circuit search engine device, comprising:
a hierarchical memory configured to (i) support a multi-way tree of search prefixes therein and (ii) support increases in the height of the multi-way tree across a plurality of levels of said hierarchical memory in response to search prefix insertions into the multi-way tree; and
a plurality of control modules distributed in a pipeline manner corresponding to the plurality of levels of said hierarchical memory;
wherein a first control module of the plurality of control modules is configured to pass root node level information downstream to a second control module during a search operation, and wherein the control modules are configured to perform a lookahead search by evaluating at least one span prefix mask associated with a search prefix within a search path of the multi-way tree to identify at least one search prefix outside the search path of the multi-way tree.
2. The device of claim 1 , wherein the first control module is associated with a highest one of the plurality of levels of said hierarchical memory and is configured to respond to a search request by determining whether the highest one of the plurality of levels of said hierarchical memory contains a root node of the multi-way tree.
3. The device of claim 2 , wherein the first control module is configured to inform the second control module, which is associated with a second highest one of the plurality of levels of said hierarchical memory, that the second highest one of the plurality of levels of said hierarchical memory is to participate in a search operation in the event the highest one of the plurality of levels of said hierarchical memory is determined to contain the root node of the multi-way tree.
4. The device of claim 3 , wherein the first control module is further configured to pass a node pointer, which identifies a location of a node to be searched in the second highest one of the plurality of levels of said hierarchical memory, downstream to the second control module in the event the highest one of the plurality of levels of said hierarchical memory is determined to contain the root node of the multi-way tree.
5. The device of claim 2 , wherein the first control module is configured to pass a node pointer, which identifies a location of a node to be searched in a second highest one of the plurality of levels of said hierarchical memory, downstream to a second control module associated with the second highest one of the plurality of levels of said hierarchical memory in the event the highest one of the plurality of levels of said hierarchical memory is determined to contain the root node of the multi-way tree.
6. The device of claim 5 , wherein the second control module is configured to pass handle data associated with a matching search prefix downstream to a third control module associated with a third highest one of the plurality of levels of said hierarchical memory in the event a search prefix within a node identified by the node pointer represents a best match to an applied search prefix associated with the search request.
7. A pipelined integrated circuit search engine device, comprising:
a hierarchical arrangement of a plurality of search and tree maintenance subengines that are configured to support a multi-way tree of search prefixes therein and further configured to perform a search operation by passing information identifying a location of a handle associated with a first search prefix within the multi-way tree that is a match to an applied search key, downstream through the plurality of search and tree maintenance sub-engines; and
a plurality of control modules distributed in a pipeline manner corresponding to the plurality of levels of said hierarchical memory;
wherein a first control module of the plurality of control modules is configured to pass root node level information downstream to a second control module during a search operation, and wherein the control modules are configured to perform a lookahead search by evaluating at least one span prefix mask associated with a search prefix within a search path of the multi-way tree to identify at least one search prefix outside the search path of the multi-way tree.
8. The search engine device of claim 7 , wherein said information operates as a pointer into a handle memory that is communicatively coupled to a last one of the plurality of search and tree maintenance sub-engines within said hierarchical arrangement.
9. The search engine device of claim 8 , wherein said information identifies at least a level within the multi-way tree and a node within that level that contain the first search prefix.
10. The search engine device of claim 7 , wherein said information identifies at least a level within the multi-way tree and a node within that level that contain the first search prefix.
11. The search engine device of claim 7 , wherein said information includes key position information and key offset information.
12. An integrated circuit search engine device, comprising:
a pipelined arrangement of a plurality of search and tree-maintenance subengines configured to support a multi-way tree of search prefixes therein and further configured to perform a longest prefix match (LPM) search operation by comparing an applied search key against a plurality of search prefixes within a search path of the multi-way tree and performing a lookahead search between the applied search key and at least one search prefix outside the search path of the multi-way tree, wherein said performing a lookahead search includes evaluating at least one span prefix mask associated with a search prefix within the search path of the multi-way tree to thereby identify the at least one search prefix outside the search path of the multi-way tree.