High throughput sort
AssigneeInfineon Technologies AG
InventorsDavid Addison, Dyson Wilkes
Life of this patent
Estimating the term…
Abstract
Systems, methods, and circuitry are provided for a sorting array. In one example, a sorting array element includes an output register and control circuitry. The output register is configured to store an output value. In response to a cell under test (CUT) load signal the output register stores a CUT value and in response to a first register shift signal from a previous sorting array element the output register stores contents of an output register of the previous sorting array element. The control circuitry is configured to generate the CUT load signal and a second register shift signal for a subsequent sorting array element based on relative magnitudes of the CUT value, the output value, and an output value stored in the output register of the previous sorting array element.
Claims19
A sorting array element, comprising:
- an output register configured to store an output value, wherein in response to a cell under test (CUT) load signal the output register stores a CUT value and wherein in response to a first register shift signal received from a previous sorting array element, the output register stores a previous sorting array element output value comprising an output value stored in an output register of the previous sorting array element;
- and
- control circuitry configured to
- receive a first comparison signal from the previous sorting array element, the first comparison signal indicative of a result of a comparison between the CUT value and the previous sorting array element output value;
- and
- generate a second comparison signal indicative of a result of a comparison of the CUT value to the output value;
- and
- generate the CUT load signal and a second register shift signal for a subsequent sorting array element based on the first comparison signal and the second comparison signal.
A sorting array for sorting a plurality of sorting values by magnitude, comprising:
- a plurality of sorting array elements;
- wherein each of the sorting array elements comprises
- an output register configured to store an output value,
- wherein in response to a cell under test (CUT) load signal the output register stores a CUT value, and
- wherein in response to a first register shift signal being received from a previous sorting array element in the plurality of sorting array elements, the output register stores a previous sorting array element output value comprising an output value stored in an output register of the previous sorting array element;
- and
- control circuitry configured to
- receive a first comparison signal from the previous sorting array element, the first comparison signal indicative of a result of a comparison between the CUT value and the previous sorting array element output value;
- and
- generate a second comparison signal indicative of a result of a comparison of the CUT value to the output value;
- and
- generate the CUT load signal and a second register shift signal for a subsequent sorting array element in the plurality of sorting array elements based on the first comparison signal and the second comparison signal.
A method, comprising:
- in a first comparison, comparing a cell under test (CUT) value with a first output value stored in an output register of a first sorting array element;
- in a second comparison, comparing the CUT value with a second output value stored in an output register of a second sorting array element, wherein the second sorting array element is disposed before the first sorting array element in a sorting array;
- and
- when the CUT value falls between the first output value and the second output value, storing the CUT value in the output register of the first sorting array element;
- when the CUT value is less than or equal to the second output value, storing the second output value in the output register of the first sorting array element;
- and
- when the CUT value is greater than the first output value, maintaining the first output value in the output register of the first sorting array element.
A sorting array element, comprising:
- a cell under test (CUT) register configured to store a CUT value;
- an output register coupled to the CUT register and an output register of a previous sorting array element, the output register comprising
- a validity bit, CUT register load input, and a register shift input, wherein the CUT register load input, when enabled, causes a CUT value to be loaded into the output register and the register shift input, when enabled, causes an output value stored in the output register of the previous sorting array element to be loaded into the output register;
- comparison circuitry comprising
- respective inputs coupled to the CUT register and the output register, and
- an output coupled to an output register of a subsequent sorting array element;
- CUT load circuitry comprising
- respective inputs coupled to the output of the comparison circuitry and an output of comparison circuitry of the previous sorting array element, and
- an output coupled to the CUT register load input of the output register;
- and
- register shift circuitry comprising
- respective inputs coupled to the validity bit and the output of the comparison circuitry, and
- an output coupled to an adjacent register shift input of an output register of the subsequent sorting array element.
Dependencies are inferred from the claim text.