Integrated search engine devices having pipelined search and b-tree maintenance sub-engines therein
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 search engine device, comprising:
a hierarchical memory configured to store a b−tree of search prefixes at multiple levels therein that reside at corresponding stages of the pipelined search engine device and are sequentially accessed during a search operation;
a pipelined tree maintenance engine embedded within the search engine device, said pipelined tree maintenance engine comprising a plurality of node maintenance sub-engines distributed with the multiple levels of said hierarchical memory; and
a pipeline control and a search logic distributed with the multiple levels of said hierarchical memory;
wherein the pipelined control and search logic is configured to search the b−tree of search prefixes in said hierarchical memory by evaluating at least one search prefix and corresponding span prefix mask at a first node of the b−tree within a search path of the b−tree during the search operation to thereby identify any prefixes that match the applied search key yet reside at a second node of the b−tree that is lower in the b−tree relative to the first node and outside the search path of the b−tree when the b−tree is traversed during the search operation.
2. The device of claim 1 , further comprising a handle memory pipeline stage having a handle update interface electrically coupled to the plurality of node maintenance sub-engines and a primary pipeline interface communicatively coupled to the pipeline control and search logic associated with a lowest level of said hierarchical memory.
3. The device of claim 1 , wherein the plurality of node maintenance sub-engines include a root level maintenance sub-engine associated with a root level of said hierarchical memory, an intermediate level maintenance sub-engine associated with an intermediate level of said hierarchical memory and a leaf level maintenance sub-engine associated with a leaf level of said hierarchical memory; and wherein the leaf node maintenance sub-engine is configured to perform an insert overflow operation at the leaf level of said hierarchical memory by requesting a first search prefix to be dropped down from the intermediate node maintenance sub-engine.
4. The device of claim 3 , wherein the leaf node maintenance sub-engine is further configured to push a second search prefix up to the intermediate node maintenance sub-engine during the insert overflow operation.
5. The device of claim 3 , wherein the leaf node maintenance sub-engine is further configured to push second and third search prefixes up to the intermediate node maintenance sub-engine during the insert overflow operation.
6. The device of claim 5 , wherein the intermediate node maintenance sub-engine is further configured to issue a child modification message that travels upstream in said pipelined tree maintenance engine, in response to receipt of the third search prefix from the leaf node maintenance sub-engine.
7. The device of claim 5 , wherein the intermediate node maintenance sub-engine is further configured to issue a child modification message that travels upstream in said pipelined tree maintenance engine.
8. The device of claim 1 , wherein said hierarchical memory is configured to store a plurality of search prefixes and corresponding span prefix masks at the multiple levels therein, said span prefix masks having values that are evaluated during the search operation to identify one or more search prefixes that match an applied search key yet reside at least one node of the b−tree that is not traversed during the search operation.
9. An integrated search engine device, comprising:
a pipelined arrangement of a plurality of search and tree maintenance sub-engines configured to support corresponding levels of a b−tree of search prefixes therein;
a handle memory lookup engine having a primary pipeline interface communicatively coupled to a last one of the plurality of search and tree maintenance sub-engines in said pipelined arrangement and a handle update interface communicatively coupled to each of the plurality of search and tree maintenance sub-engines in said pipelined arrangement;
wherein said hierarchical memory is configured to store a plurality of search prefixes and corresponding span prefix masks at the multiple levels therein, said span prefix masks having values that are evaluated during the search operation to identify one or more search prefixes that match an applied search key yet reside at least one node of the b−tree that is not traversed during the search operation.
10. The search engine device of claim 9 ,
wherein said pipelined arrangement of the plurality of search sub-engines are configured to search the b−tree of search prefixes by evaluating at least one search prefix and corresponding span prefix mask at a first node of the b−tree within a search path of the b−tree during the search operation, to thereby identify any prefixes that match the applied search key yet reside at a second node of the b−tree that is lower in the b−tree relative to the first node and outside the search path of the b−tree when the b−tree is traversed during the search operation.
11. A pipelined search engine device, comprising:
a hierarchical memory configured to store a multi-way tree of search prefixes at multiple levels therein; and
a pipelined tree maintenance engine embedded within the search engine device, said pipelined tree maintenance engine comprising an intermediate node maintenance sub-engine associated with an intermediate level of said hierarchical memory and a leaf node maintenance sub-engine configured to push a search prefix and an associated span prefix mask up to the intermediate node maintenance sub-engine during the insert operation, said span prefix mask having a value that is evaluated during a search operation of said hierarchical memory to identify one or more search prefixes within the multi-way tree that match an applied search key yet reside at least one node of the multi-way tree that is not traversed during the search operation.
12. An integrated search engine device, comprising: a pipelined arrangement of a plurality of search and tree maintenance sub-engines configured to support corresponding levels of a b−tree of search prefixes therein and further configured to support upstream and downstream communications between the plurality of search and tree maintenance sub-engines during operations to insert search prefixes into the b−tree;
wherein the upstream and downstream communications include upstream transfers of span prefix masks during the operations to insert search prefixes into the b−tree, said span prefix masks having values that are evaluated during a search operation of said hierarchical memory to identify one or more search prefixes within the b−tree that match an applied search key yet reside at least one node of the b−tree that is not traversed during the search operation.
13. The search engine device of claim 12 , wherein the upstream and downstream communications include upstream and downstream transfers of search prefixes during the operations to insert search prefixes into the b−tree.
14. The search engine device of claim 13 , wherein the upstream and downstream communications include upstream messaging of child modification information during the operations to insert search prefixes into the b−tree.
15. The search engine device of claim 12 , wherein the upstream and downstream communications include upstream messaging of child modification information during the operations to insert search prefixes into the b−tree.
16. The search engine device of claim 12 , further comprising:
a handle memory lookup engine having a primary pipeline interface communicatively coupled to a last one of the plurality of search and tree maintenance sub-engines in said pipelined arrangement and a handle update interface communicatively coupled to each of the plurality of search and tree maintenance sub-engines in said pipelined arrangement.
17. The search engine device of claim 12 , wherein the plurality of search and tree maintenance sub-engines are configured to support respective levels of a an SPM b−tree of search prefixes, said b−tree of search prefixes containing span prefix masks having values that are evaluated during a search operation of said hierarchical memory to identify one or more search prefixes within the b−tree that match an applied search key yet reside at least one node of the b−tree that is not traversed during the search operation.