| 主权项 |
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 log2N bits, the parallel comparison result corresponding to log2N 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; andcomparison circuitry coupled to receive the log2N 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 log2N 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. |
