Sorting/merging tree for determining a next tournament champion in each cycle by simultaneously comparing records in a path of the previous tournament champion
US5287494A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Oct 18, 1990 |
| Grant date | Feb 15, 1994 |
| Priority date | — |
| Expiry date | Oct 18, 2010 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.