Patent ID: 7653619
Filing Date: 2010-01-26
Classification: G06F

Abstract:
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.