Patent Document ID: 8954661
Application ID: 12944350
Patent Flag: 1

Claim One:
1. A circuit configured to perform a search for a key in a sorted list of entries using a plurality of binary search iterations, the circuit comprising: a parallel comparison stage comprising N registers each storing a different respective one of the entries, and parallel comparison circuitry configured to compare the key to each of the entries in the N registers in parallel and generate a parallel comparison result including log 2 N bits, the parallel comparison result corresponding to log 2 N binary search iterations to search for the key in the sorted list of entries, wherein N is an integer greater than 1; and a plurality of pipeline stages configured in a pipeline, each of the plurality of pipeline stages comprising: memory storing an orthogonal subset of the entries relative to the subsets of the entries in memories of all others of the plurality of pipeline stages, the memory in each successive pipeline stage having exponentially more storage capacity than an immediately previous pipeline stage and including entries corresponding to a particular one of the binary search iterations; and comparison circuitry coupled to receive the log 2 N bits from the parallel comparison stage, the comparison circuitry configured to select an entry of the memory of the pipeline stage based on a respective index including the log 2 N bits, to generate a comparison result indicating whether the key is greater than or equal to or less than the selected entry of the memory of the pipeline stage and to pass the key and the comparison result to a subsequent pipeline stage, wherein the respective index also includes a bit based on a comparison result received from a previous pipeline stage.