Sorting using pipelined compare units
AssigneeInternational Business Machines Corporation
InventorsJörg-Stephan Vogt, Norbert Hagspiel, Christian Jacobi, Matthias Klein
Life of this patent
Estimating the term…
Abstract
A compare unit includes an array including a plurality of buffer pairs to receive records on one level of a plurality of levels of a hierarchical structure. A comparator is coupled to the array, and the comparator includes one input to receive one beat of one record from one buffer of a selected buffer pair of the plurality of buffer pairs coupled to the comparator. The comparator further includes another input to receive another beat of another record from another buffer of the selected buffer pair, and logic coupled to the one input and the other input to compare the one beat and the other beat to obtain a winner beat of the compare.
Claims20
A compare unit comprising:
- an array comprising a plurality of buffer pairs to receive records on one level of a plurality of levels of a hierarchical structure;
- a hardware comparator coupled to the array, the hardware comparator comprising:
- one input to receive one beat of one record from one buffer of a selected buffer pair of the plurality of buffer pairs coupled to the hardware comparator;
- another input to receive another beat of another record from another buffer of the selected buffer pair;
- and
- logic coupled to the one input and the another input to compare the one beat and the another beat to obtain a winner beat of the compare, wherein the logic outputs the winner beat form the one buffer or the another buffer that includes the winner beat;
- and
- request logic to request from anther selected buffer air re-fill beat to be input to the one buffer or the another buffer from which the winner beat is output, the another selected buffer pair being on another level of the plurality of levels of the hierarchical structure.
An integrated circuit comprising:
- a field programmable gate array, the field programmable gate array comprising:
- an array comprising a plurality of buffer pairs to receive records on one level of a plurality of levels of a hierarchical structure;
- a comparator coupled to the array, the comparator comprising:
- one input to receive one beat of one record from one buffer of a selected buffer pair of the plurality of buffer pairs coupled to the comparator;
- another input to receive another beat of another record from another buffer of the selected buffer pair;
- and
- logic coupled to the one input and the another input to compare the one beat and the another beat to obtain a winner beat of the compare, wherein the logic outputs the winner beat from the one buffer or the another buffer that includes the winner beat;
- and
- request logic to request from another selected buffer pair a re-fill beat to be input to the one buffer or the another buffer from which the winner beat is output the another selected buffer pair being on another level of the plurality of levels of the hierarchical structure.
A method of facilitating sorting of records, the method comprising:
- receiving, by a comparator, one beat of one record from one buffer of a selected buffer pair of an array of a plurality of buffer pairs coupled to the comparator, the plurality of buffer pairs to receive records on one level of a plurality of levels of a hierarchical structure;
- receiving, by the comparator another beat of another record from another buffer of the selected buffer pair;
- comparing, by the comparator, the one beat and the another beat to obtain a winner beat of the compare, wherein the comparing outputs the winner beat from the one buffer or the another buffer that includes the winner beat;
- and
- requesting from another selected buffer pair a re-fill beat to be input to the one buffer or the another buffer from which the winner beat is output, the another selected buffer pair being on another level of the plurality of levels of the hierarchical structure.
Dependencies are inferred from the claim text.