Patent US5265260A successfully refreshed from Google Patents.
US5265260A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High performance sort hardware for a database accelerator in a data processing system
Assignee: International Business Machines Corp
•
Filing: 1991-06-26
•
Granted: 1993-11-23
•
Expires: 2011-06-26
Abstract
Abstract A database accelerator that uses the Van Voorhis sort network is implemented as a state machine using the same hardware in succeeding cycles. The database accelerator comprises high performance sort (HPS) hardware that includes working store elements for storing data records to be sorted, a plurality of comparator modules, control read only memories (ROMs), and storage control elements (SCEs). The SCEs direct respective pointer arrays and storage elements, and the storage elements provide addresses to the working store elements, which in turn feed data to the comparator modules. The control ROMs provide control signals to each comparator module as well as global control for the HPS hardware.
Inventors
- 👤 Jerry E. Hendricks
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 12:08
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/24; G06F2207/00; G06F2207/22; G06F2207/228; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
328 words
High performance soft hardware for a database accelerator, comprising: working store means for storing data records to be sorted; a plurality of comparator modules, said plurality of comparator modules each including cache storing means for storing records from said working store means and providing high speed access to stored records, data in said cache storing means of each of said plurality of comparator modules being identical, said plurality of comparator modules each further including comparator means for selecting records stored in said cache storing means in a predetermined ascending or descending order and generating comparator outputs according to said predetermined order; and control means for loading said comparator outputs of said plurality of comparator modules in said working store means in a sequence of cycles which implements a sort algorithm as a state machine, said plurality of comparator modules comprising eight comparator modules operating in nine cycles, wherein said sort algorithm is a Van Voorhis n=16 sort network, where n is a number of elements to be sorted, and wherein each of said plurality of comparator modules comprises: first and second imbedded logical arrays functioning as a high-speed cache and storing data to be compared, said identical data in the logical arrays of each of said comparator modules requiring only addresses of data to be transferred between comparator modules; comparator means connected to receive data read out of said first and second imbedded logical arrays and generating comparator output indicative of a comparator operation on said data; first and second address register means for addressing data in said first and second imbedded logical arrays, respectively, addressed data being read out of said first and second logical arrays to said comparator means; and first and second multiplexer means each receiving addresses from said first and second address register means and responsive to said comparator output of said comparator means for respectively outputting one of said addresses as a high output and one of said addresses as a low output.
Claim 2
Dependent Claim
328 words
High performance soft hardware for a database accelerator, comprising: working store means for storing data records to be sorted; a plurality of comparator modules, said plurality of comparator modules each including cache storing means for storing records from said working store means and providing high speed access to stored records, data in said cache storing means of each of said plurality of comparator modules being identical, said plurality of comparator modules each further including comparator means for selecting records stored in said cache storing means in a predetermined ascending or descending order and generating comparator outputs according to said predetermined order; and control means for loading said comparator outputs of said plurality of comparator modules in said working store means in a sequence of cycles which implements a sort algorithm as a state machine, said plurality of comparator modules comprising eight comparator modules operating in nine cycles, wherein said sort algorithm is a Van Voorhis n=16 sort network, where n is a number of elements to be sorted, and wherein each of said plurality of comparator modules comprises: first and second imbedded logical arrays functioning as a high-speed cache and storing data to be compared, said identical data in the logical arrays of each of said comparator modules requiring only addresses of data to be transferred between comparator modules; comparator means connected to receive data read out of said first and second imbedded logical arrays and generating comparator output indicative of a comparator operation on said data; first and second address register means for addressing data in said first and second imbedded logical arrays, respectively, addressed data being read out of said first and second logical arrays to said comparator means; and first and second multiplexer means each receiving addresses from said first and second address register means and responsive to said comparator output of said comparator means for respectively outputting one of said addresses as a high output and one of said addresses as a low output.
Claim 3
Dependent Claim
69 words
High performance sort hardware as recited in claim 1 further comprising third and fourth multiplexer means connected to receive high and low outputs from each of said plurality of comparator modules and responsive to said control means for supplying one of said high and one of said low outputs to said first and second address register means as next-state addresses according to the Van Voorhis state for a cycle.
Claim 4
Dependent Claim
28 words
High performance sort hardware as recited in claim 2 further comprising means for loading said first and second imbedded arrays with data records from said working store means.
Claim 5
Dependent Claim
59 words
High performance sort hardware as recited in claim 3 wherein said control means comprises: means for generating microcode control signals to said plurality of comparator modules; and store control element means for receiving outputs from said comparator modules and generating addresses to said working store means to output appropriate data records to each of said plurality of comparator modules.
Claim 6
Dependent Claim
74 words
High performance sort hardware as recited in claim 4 wherein said working store means comprises four working stores, each supplying data records to two of said plurality of comparator modules, said means for generating microcode control signals comprises two microcode storage means, each supplying control signals to four of said plurality of comparator modules, and said storage control element means comprises two storage control elements, each supplying addresses to two of said working stores.
Claim 7
Dependent Claim
63 words
High performance sort hardware as recited in claim 5, said hardware being fault tolerant and wherein each of said microcode storage means stores a plurality of separate microprogram sequences, said microprogram sequences including a sequence for all components of said sort hardware being functional and microprogram sequences for various conditions of one or more of the components of said sort hardware being non-functional.
Claim 8
Dependent Claim
112 words
High performance sort hardware as recited in claim 4 wherein said storage control element means comprises: storage element means for storing address values which are output to said working store means; pointer array means for receiving data elements which are physical addresses of data records in said working store means, said data elements being stored in said storage element means; arithmetic logic means for translating addresses output from said plurality of comparator modules to said physical addresses which are received by said pointer array means; and result register means for holding indices of data records in sorted order, said indices corresponding to data records whose addresses are in said pointer array means.
Claim 9
Dependent Claim
63 words
High performance sort hardware as recited in claim 7 wherein said means for generating microcode control signals is incorporated in said storage control element means, said storage control element means further including bidirectional bus means for allowing global simultaneous loading of data records from said working store means to said plurality of comparator modules and any-to-any connectivity of said plurality of comparator modules.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-22 | 1997-05-24 | 1997-11-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-22 | 2001-05-24 | 2001-11-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-22 | 2005-05-24 | 2005-11-23 | $7700.00 | Window Closed / Lapsed |