Method and apparatus for finding a first element
AssigneeHewlett-Packard Company
InventorDouglas J Cutter
Life of this patent
Estimating the term…
Abstract
Disclosed are methods and apparatus for finding an element meeting a predetermined condition among an ordered set of N elements. The method subdivides the ordered set of N elements into M subsets, wherein 1<M<N. A particular one of the M subsets contains K elements. The method determines if the particular subset contains an element meeting the predetermined condition. The method also identifies which of the K elements in the particular subset is the first element meeting the predetermined condition.
Claims15
A method for finding an element meeting a predetermined condition among an ordered set of N elements, the method comprising:
- subdividing the ordered set of N elements into M subsets, wherein 1>M>N and wherein a particular subset contains K elements;
- determining if the particular subset contains an element meeting the predetermined condition;
- identifying which element in the particular subset is the first element meeting the predetermined condition in the particular subset;
- performing the determining step for all other of the M subsets besides the particular subset;
- performing the identifying step for all other of the M subsets besides the particular subset;
- and
- wherein the steps of determining, identifying, performing the determining step for all other of the M subsets, and performing the identifying stop for all other of the M subsets are performed in parallel.
An apparatus for use with a structure having N ordered locations, each location capable of storing a variable that can be in a plurality of states including a predetermined state, the is apparatus comprising:
- a plurality of first level circuit blocks, each first level circuit block connected to a subset of the N ordered locations, each first level circuit block comprising:
- a first logic gate having a plurality of inputs, each input connected to an element of the subset of the N ordered locations, wherein the output of the first logic gate is the predetermined state if at least one of the inputs is in the particular state;
- and
- a first logic network having a plurality of inputs, each input connected to an element of the subset of the N ordered locations, wherein the first logic network outputs one or more signals indicative of the first among the subset of the N ordered locations to be in the predetermined state.
Dependencies are inferred from the claim text.