Efficient Pipelined Binary Search
An apparatus and machine readable storage medium for performing a binary search of an ordered list containing 2 N values, where N is an integer greater than one. The apparatus may include a pipeline having N stages numbered 1 to N in sequence. Stage M of the pipeline, where M is in integer from 1 to N, may include a memory storing 2 M-1 values from the ordered list, a comparator to compare the key to a value read from the memory based on comparison results from previous stages in the pipeline, and a result storage register to store a comparison result from the comparator and the comparison results from the previous stages in the pipeline.
1 . An apparatus for performing a binary search of an ordered list containing 2 N values, where N is an integer greater than one, the apparatus comprising:
a pipeline having N stages numbered 1 to N in sequence;
stage 1 including:
a stage 1 memory storing a single value from the ordered list,
a stage 1 comparator to compare a key to the value stored in the stage 1 memory, and
a stage 1 storage register to store a comparison result from the stage 1 comparator;
each subsequent stage comprising:
a stage M memory storing 2 M-1 values from the ordered list, where M is the stage number from 2 to N;
a stage M comparator to compare the key to a value read from the stage M memory based on comparison results from previous stages in the pipeline; and
a stage M result storage register to store a comparison result from the stage M comparator and the comparison results from the previous stages in the pipeline.
2 . The apparatus of claim 1 , wherein
the comparison result from the stage 1 comparator indicates whether the key falls within a lower half or an upper half of the ordered list.
3 . The apparatus of claim 2 , wherein
the comparison result from the comparator within each stage of the pipeline subsequent to stage 1 divides the portion of the ordered list being searched in half.
4 . The apparatus of claim 1 , each stage from stage 1 to stage N− 1 further comprising:
a respective key storage register to store the key for use by subsequent stages of the pipeline.
5 . The apparatus of claim 4 , wherein all of the result storage registers and the key store registers are responsive to a common clock.
6 . The apparatus of claim 1 , further comprising:
write logic to selectively store the values of the ordered list in the respective memories of the N stages.
7 . The apparatus of claim 1 , further comprising:
preset logic to select a portion of the ordered list in accordance with list select data.
8 . The apparatus of claim 7 , wherein the preset logic sets the content of at least the stage 1 result storage register independent of the output from the stage 1 comparator.
9 . A machine readable storage medium containing data that, when used to configure a programmable device, configures the device to include a pipelined search engine for performing a binary search of an ordered list containing 2 N values, where N is an integer greater than one, the pipelined search engine comprising:
a pipeline having N stages numbered 1 to N in sequence;
stage 1 including:
a stage 1 memory storing a single value from the ordered list,
a stage 1 comparator to compare a key to the value stored in the stage 1 memory, and
a stage 1 storage register to store a comparison result from the stage 1 comparator;
each subsequent stage comprising:
a stage M memory storing 2 M-1 values from the ordered list, where M is the stage number from 2 to N;
a stage M comparator to compare the key to a value read from the stage M memory based on comparison results from previous stages in the pipeline; and
a stage M result storage register to store a comparison result from the stage M comparator and the comparison results from the previous stages in the pipeline.
10 . The machine readable storage medium of claim 9 , wherein
the comparison result from the stage 1 comparator indicates whether the key falls within a lower half or an upper half of the ordered list.
11 . The machine readable storage medium of claim 10 , wherein
the comparison result from the comparator within each stage of the pipeline subsequent to stage 1 divides the portion of the ordered list being searched in half.
12 . The machine readable storage medium of claim 9 , each stage from stage 1 to stage N− 1 further comprising:
a respective key storage register to store the key for use by subsequent stages of the pipeline.
13 . The machine readable storage medium of claim 12 , wherein all of the result storage registers and the key store registers are responsive to a common clock.
14 . The machine readable storage medium of claim 9 , the pipelined search engine further comprising:
write logic to selectively store the values of the ordered list in the respective memories of the N stages.
15 . The machine readable storage medium of claim 9 , the pipelined search engine further comprising:
preset logic to select a portion of the ordered list in accordance with list select data.
16 . The machine readable storage medium of claim 15 , wherein the preset logic sets the content of at least the stage 1 result storage register independent of the output from the stage 1 comparator.