US5287494A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Sorting/merging tree for determining a next tournament champion in each cycle by simultaneously comparing records in a path of the previous tournament champion
Assignee: International Business Machines Corp
•
Filing: 1990-10-18
•
Granted: 1994-02-15
•
Expires: 2010-10-18
Abstract
Abstract A tree sorter having hardware logic node registers and output selectors plus comparators enables a vector processor to perform sort and merge operations. A system and method of providing one output record each cycle provides performance enhancement over similar scalar operation. Storage to storage traffic is drastically reduced because the hardware tree and update logic is implemented in the Vector Processor. Vector registers provide input data to the hardware tree structure. Output records sorted by key together with address ID are placed in storage. Multiple Vector count and multiple Vector Interruption Index (VIX) operation, string length and merge masks are used in conjunction with a vector merge instruction. The data input record key field has both long and short formats. Actual key data or codewords may be used. The vector merge forms a new codeword when compare equal codewords are encountered. By storing sorted keys (codewords) plus the address ID, reuse of codewords (in formation of longer strings, etc.) is made possible.
Inventors
- 👤 Leslie C. Garcia
- 👤 David B. Lindquist
- 👤 Gerald F. Rollo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 18:54
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/76; G06F15/80; G06F15/8053; G06F7/00; G06F7/22; G06F7/24; G06F7/36; G06F2207/00; G06F2207/22; G06F2207/222; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
238 words
An apparatus for sorting and merging database records, whereby a tournament champion is determined in each cycle, the apparatus comprising: a root register; a plurality of node registers coupled to the root register in a logical tree configuration so as to form a plurality of data paths; a plurality of base registers, each of the base registers being coupled to one of the node registers; a champion key register, coupled to the root register, having a first field for holding a key and a second field for holding address data identifying one of said base registers from which the key originated; path selection means, coupled to the champion key register, for selecting one of the data paths, responsive to the address data held in the champion key register for a current tournament champion; simultaneous compare means operating with the node registers in a currently selected path of the tree and the champion key register for determining in a single cycle of comparison, a next tournament champion among data represented in the node registers which form the currently selected data path selected by the path selection means, and for writing the key of the next tournament champion and the address data identifying the base register of origin into the champion key register; and update means, coupled to the path selection means, for updating the data in the node registers forming the data path selected by the path selection means.
Claim 2
Independent Claim
238 words
An apparatus for sorting and merging database records, whereby a tournament champion is determined in each cycle, the apparatus comprising: a root register; a plurality of node registers coupled to the root register in a logical tree configuration so as to form a plurality of data paths; a plurality of base registers, each of the base registers being coupled to one of the node registers; a champion key register, coupled to the root register, having a first field for holding a key and a second field for holding address data identifying one of said base registers from which the key originated; path selection means, coupled to the champion key register, for selecting one of the data paths, responsive to the address data held in the champion key register for a current tournament champion; simultaneous compare means operating with the node registers in a currently selected path of the tree and the champion key register for determining in a single cycle of comparison, a next tournament champion among data represented in the node registers which form the currently selected data path selected by the path selection means, and for writing the key of the next tournament champion and the address data identifying the base register of origin into the champion key register; and update means, coupled to the path selection means, for updating the data in the node registers forming the data path selected by the path selection means.
Claim 3
Dependent Claim
76 words
The apparatus of claim 1, wherein the base registers are vector registers having a plurality of elements, each of the vector registers holding a contending key, each one of the vector registers further comprising: index means, coupled to the champion key register, for containing a pointer to one of the elements and for incrementing the pointer responsive to an indication by the second field that the tournament champion originated from the one of the vector registers.
Claim 4
Dependent Claim
37 words
The apparatus of claim 1 in which the update means updates data in the registers in the currently selected data path during the cycle of comparison after a next path is determined in the path selection means.
References Cited (Backward Citations)
US3713107A
Cited
US4295206A
Cited
US4945471A
Cited
US4497039A
Cited
US4567572A
Cited
US4791555A
Cited
US4644471A
Cited
US4779192A
Cited
US4799152A
Cited
US4734877A
Cited
JPS6478369A
Cited
US5121493A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-02-14 | 1997-08-16 | 1998-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-02-14 | 2001-08-16 | 2002-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-02-14 | 2005-08-16 | 2006-02-15 | $7700.00 | Window Closed / Lapsed |