US 12,141,544 B2 · Bitonic sorting accelerator

Abstract

An accelerator for bitonic sorting includes a plurality of compare-exchange circuits and a first-in, first-out (FIFO) buffer associated with each of the compare-exchange circuits. An output of each FIFO buffer is a FIFO value. The compare-exchange circuits are configured to, in a first mode, store a previous value from a previous compare-exchange circuit or a memory to its associated FIFO buffer and pass a FIFO value from its associated FIFO buffer to a subsequent compare-exchange circuit or the memory; in a second mode, compare the previous value to the FIFO value, store the greater value to its associated FIFO buffer, and pass the lesser value to the subsequent compare-exchange circuit or the memory; and in a third mode, compare the previous value to the FIFO value, store the lesser value to its associated FIFO buffer, and pass the greater value to the subsequent compare-exchange circuit or the memory.

Claims20

Dependent claims

A circuit, comprising:

a first input;
a second input;
a third input;
a fourth input;
a first compare-exchange circuit comprising:
a fifth input coupled to the first input;
a sixth input coupled to the second input;
a first output;
and
a second output;
a second compare-exchange circuit comprising:
a seventh input coupled to the third input;
an eighth input coupled to the fourth input;
a third output;
and
a fourth output;
a third compare-exchange circuit comprising:
a ninth input coupled to the first output;
a tenth input coupled to the third output;
a fifth output coupled to a sixth output of the circuit;
and
a seventh output coupled to an eighth output of the circuit;
and
a fourth compare-exchange circuit comprising:
an eleventh input coupled to the second output;
a twelfth input coupled to the fourth output;
a ninth output coupled to a tenth output of the circuit;
and
an eleventh output coupled to a twelfth output of the circuit.

26 more elements

A method comprising:

receiving a control signal;
determining an operation mode for a first compare-exchange circuit based on the control signal;
if the determined operation mode is a first mode:
storing a first data value from a second compare-exchange circuit or memory to a buffer of the first compare-exchange circuit;
and
passing a second data value from the buffer of the first compare-exchange circuit to a third compare-exchange circuit or the memory;
and
if the determined operation mode is a second mode:
comparing the first data value from the second compare-exchange circuit to the second data value from the buffer of the first compare-exchange circuit for a greater value and for a lesser value;
storing the greater value to the buffer of the first compare-exchange circuit;
and
passing the lesser value to the third compare-exchange circuit or the memory.

9 more elements

Dependencies are inferred from the claim text.

Bitonic sorting accelerator

Life of this patent

Bitonic sorting accelerator

Life of this patent

Abstract

Claims20