High performance sort hardware for a database accelerator in a data processing system
AssigneeInternational Business Machines Corporation
InventorJerry E. Hendricks
Life of this patent
Estimating the term…
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.
Claims8
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.
Dependencies are inferred from the claim text.