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;
- and
- 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 other input to compare the one beat and the other beat to obtain a winner beat of the compare.
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;
- and
- 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 other input to compare the one beat and the other beat to obtain a winner beat of the compare.
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;
- and
- comparing, by the comparator, the one beat and the other beat to obtain a winner beat of the compare.
The method of claim 116, wherein the comparing outputs the winner beat from the one buffer or the other buffer that includes the winner beat, and wherein the method further comprises requesting from another selected buffer pair a re-fill beat to be input to the one buffer or the other buffer from which the winner beat is output, the other selected buffer pair being on another level of the plurality of levels of the hierarchy.
Dependencies are inferred from the claim text.