Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-03
2002-11-26
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06487550
ABSTRACT:
TECHNICAL FIELD
The invention relates to digital electronic circuitry and algorithms for searching. More particularly, the invention relates to digital electronic circuitry and algorithms for quickly and efficiently finding a first element having a predetermined state among an ordered set of elements.
BACKGROUND ART
Data structures in an ordered relationship, such as queues, buffers and stacks, are common in software and digital electronics. Known techniques for finding a first element meeting a specified condition in an ordered data structure are serial in nature. That is, known techniques proceed element-by-element from the beginning end of the data structure towards the opposite end, testing each element in turn for the specified condition until the specified condition is met. The time required to perform such a serial find operation on a data structure having N elements is on the order of N (i.e., O(N)) in the worst case and on the order of N/2(i.e., O(N/2)) on average. The execution time is measured in gate delays for a hardware implementation of the technique or in terms of processor cycles for a software implementation. The execution time can be prohibitively large when N is large.
SUMMARY OF INVENTION
In one respect, the invention is a method 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. As necessary, the method can process other of the M subsets in a similar manner. Preferably, all of the M subsets are processed in parallel. Thus, the method decomposes the problem of finding a first one in a set of N into M much more manageable problems. The same basic method can then optionally be applied to the outputs of the basic method to further simplify the problem.
In another respect, the invention is an apparatus for use with a structure having N ordered locations. Each location is capable of storing a variable that can be in a plurality of states including a predetermined state. The apparatus comprises a plurality of first level circuit blocks. Each first level circuit block is connected to a subset of the N ordered locations, and each first level circuit block comprises a first logic gate and a first logic network. The first logic gate has a plurality of inputs, each of which is connected to an element of the subset of the N ordered locations. The first logic gate output is the predetermined state if at least one of the inputs is in the predetermined state. The first logic network also has a plurality of inputs, each of which is connected to an element of the subset of the N ordered locations. The first logic network outputs one or more signals indicative of the first location among the subset of the N ordered locations to be in the predetermined state. Optionally, the apparatus includes second and subsequent level logic blocks as necessary in a modular design.
In yet another respect, the invention is an apparatus for use with a structure having N ordered locations. Each location is capable of storing a variable that can be in a plurality of states including a particular state. The apparatus comprises a plurality of first presence determining means and a plurality of first indicating means. Each first presence determining means performs the function of determining if a subset of the N ordered locations contains an element having the predetermined state. Each of the first indicating means performs the function of indicating which element in a subset of the N ordered locations is the first element having the predetermined state in the subset. Each subset contains at least two of the N ordered locations.
In comparison to known methods and apparatus for finding a first element in an ordered data structure, certain embodiments of the invention are capable of achieving certain advantages, including the following:
(1) Certain embodiments of the invention are capable of much faster execution. In particular, the speed of execution can be made less dependent on the size of the data structure.
(2) Certain embodiments of the invention can be performed recursively or designed using modular hardware components.
Those skilled in the art will appreciate these and other advantages and benefits of various embodiments of the invention upon reading the following detailed description of a preferred embodiment with reference to the below-listed drawings.
REFERENCES:
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 6266375 (2001-07-01), Chang et al.
Wolfe, A., “Patents shed light on Merced's Innards”, Electronic Engineering Times, Feb. 15, 1999.
Hewlett--Packard Company
Mizrahi Diane D.
Mofiz Apu M
LandOfFree
Method and apparatus for finding a first element does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for finding a first element, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for finding a first element will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2962410