Integrated search engine devices having pipelined search and tree maintenance sub-engines therein that maintain search coherence during multi-cycle update operations
View Patent ↗A search engine includes a pipelined arrangement of a plurality of search and tree maintenance sub-engines therein, which are configured to support the performance of search operations on exclusively valid multi-way trees of search prefixes concurrently with the performance of update operations on the multi-way trees as they are being searched.
1. An integrated circuit device, comprising:
a search engine having a pipelined arrangement of a plurality of search and tree maintenance sub-engines, wherein the search engine is configured to: (i) perform search operations on multi-way trees of search prefixes, (ii) concurrently perform update operations on the multi-way trees as they are being searched, and (iii) perform an update operation on a first multi-way tree by generating a modified copy of a first branch of the first multi-way tree, wherein the modified copy comprises a plurality of temporary node pointers associated with copies of nodes of the first branch of the first multi-way tree, wherein the plurality of temporary node pointers are generated by extracting the plurality of temporary node pointers from a free list within the search engine, and wherein the modified copy of the first branch does not comprise all nodes of the first multi-way tree.
2. The integrated circuit device of claim 1 , wherein the search engine is further configured to perform an insert-type update operation on the first multi-way tree by searching the first multi-way tree to identify the first branch thereof that is to receive a search prefix to be inserted.
3. The integrated circuit device of claim 1 , wherein the modified copy of the first branch is generated by (a) copying a portion of the first branch and (b) modifying the copied portion after a request to perform the update operation is received.
4. The integrated circuit device of claim 2 , wherein the search engine is further configured to update the first multi-way tree by removing the first branch from the first multi-way tree and substituting the modified copy of the first branch therefor.
5. The integrated circuit device of claim 4 , wherein the search engine is configured to return node pointers within the first branch to the free list in response to removing the first branch from the first multi-way tree.
6. The integrated circuit device of claim 4 , wherein the search engine is configured so that operations to generate a modified copy of the first branch can be performed concurrently with operations to search the first branch of the first multi-way tree.
7. An integrated circuit device, comprising:
a search engine configured to support search operations on multi-way trees of search prefixes concurrently with tree update operations that comprise replacing branches of the multi-way trees with modified copies of the branches that reflect updates to the multi-way trees, wherein the modified copies of the branches are generated by generating a plurality of temporary node pointers associated with copies of nodes of the branches of the multi-way trees, wherein the plurality of temporary node pointers are generated by extracting the plurality of temporary node pointers from a free list within the search engine, and wherein each of the modified copies of the branches do not comprise all nodes of the tree to which the modified copy of the branch belongs.
8. The integrated circuit device of claim 7 , wherein the tree update operations further comprise a search operation using a search prefix to be inserted into or deleted from the multi-way tree.
9. The integrated circuit device of claim 8 , wherein the tree update operations further comprise replacing a first branch of the multi-way tree with a modified copy of the first branch that reflects an update to the first branch using a branch replacement operation having a latency equivalent to a latency of the search operations.
10. The integrated circuit device of claim 7 , wherein the tree update operations further comprise replacing a first branch of the multi-way tree with a modified copy of the first branch that reflects an update to the first branch using a branch replacement operation having a latency equivalent to a latency of the search operations.
11. The integrated circuit device of claim 8 , wherein the tree update operations are variable-latency operations.
12. An integrated search engine device, comprising:
a pipelined arrangement of a plurality of search and tree maintenance sub-engines configured to: (i) support corresponding levels of a b-tree of search prefixes therein, and (ii) insert search prefixes into the b-tree by modifying copies of a plurality of nodes within the b-tree and by generating updated pointers to the modified copies of the plurality of nodes before reclaiming the plurality of nodes as free nodes, wherein generating updated pointers comprises generating a plurality of temporary node pointers associated with the copies of the plurality of nodes within the b-tree, wherein the plurality of temporary node pointers are generated by extracting the plurality of temporary node pointers from a free list within the search engine, and wherein the plurality of nodes does not comprise all nodes of the b-tree.
13. An integrated search engine device, comprising:
a pipelined arrangement of a plurality of search and tree maintenance sub-engines configured to: (i) support corresponding levels of a b-tree of search prefixes therein and (ii) 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 by modifying copies of a plurality of nodes within the b-tree and by generating updated pointers to the modified copies of the plurality of nodes before reclaiming the plurality of nodes as free nodes, wherein generating updated pointers comprises generating a plurality of temporary node pointers associated with the copies of the plurality of nodes within the b-tree, wherein the plurality of temporary node pointers are generated by extracting the plurality of temporary node pointers from a free list within the search engine, and wherein the plurality of nodes does not comprise all nodes of the b-tree.
14. A method of updating an integrated circuit search engine device, comprising:
searching a multi-way tree within the search engine device to identify a first branch of the tree that is to receive a first search prefix, in response to an insert instruction;
generating a modified copy of the first branch that includes the first search prefix concurrently with searching at least a portion of the first branch of the tree with a second search prefix associated with a search instruction, wherein generating a modified copy of the first branch comprises generating a plurality of temporary node pointers associated with copies of nodes of the first branch, wherein the plurality of temporary node pointers are generated by extracting the plurality of temporary node pointers from a free list within the search engine, and wherein the modified copy of the first branch does not comprise all nodes of the multi-way tree; and
replacing the first branch of the tree with the modified copy of the first branch.
15. The method of claim 14 , wherein a latency associated with replacing the first branch of the tree is equivalent to a latency associated with the search instruction.
16. The method of claim 15 , wherein a latency associated with the insert instruction is variable; and wherein the latency associated with the search instruction is fixed.
17. The method of claim 14 , wherein replacing the first branch of the tree comprises replacing the first branch of the tree with the modified copy of the first branch, in response to treating a no-op instruction received by the search engine device as a branch replacement instruction.
18. The method of claim 14 , wherein generating the modified copy of the first branch comprises generating the modified copy of the first branch using operations having lower priority to memory resources within the search engine device relative to operations to search the multi-way tree in response to the search instruction.
19. An integrated circuit device, comprising:
a search engine having a pipelined arrangement of a plurality of search and tree maintenance sub-engines, wherein the search engine is configured to: (i) perform fixed-latency search operations on multi-way trees of search prefixes concurrently with variable-latency tree update operations, and (ii) perform an update operation on a first multi-way tree by generating a modified copy of a first branch of the first multi-way tree, wherein the modified copy comprises a plurality of temporary node pointers associated with copies of nodes of the first branch of the first multi-way tree, wherein the plurality of temporary node pointers are generated by extracting the plurality of temporary node pointers from a free list within the search engine, and wherein the modified copy of the first branch does not comprise all nodes of the first multi-way tree.