# US 2023/0418555 A1 · Bitonic sorting accelerator

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0418555 A1
- Document ID: US20230418555A1
- Status: Published application
- Kind: A1
- Application number: 18/335,452
- Filed: 2023-06-15
- Published: 2023-12-28
- Earliest claimed: 2018-07-12
- Assignees: Texas Instruments Incorporated
- Applicants: Texas Instruments Incorporated
- Inventors: Indu Prathapan; Puneet Sabbarwal; Pankaj Gupta
- Web page: https://patentgrep.com/patent/US20230418555A1

## CPC

- G06F 7/24: Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence)
- G06F 5/065: {Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's}
- G06F 2207/228: Sorting or merging network
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The circuit of claim 1 further comprising:
a first multiplexer comprising an output coupled to the first input;
a second multiplexer comprising an output coupled to the second input;
a third multiplexer comprising an output coupled to the third input; and
a fourth multiplexer comprising an output coupled to the fourth input.

### Claim 3 (depends on 2)

The circuit of claim 2, further comprising:
a first accelerator coupled to the sixth output;
a second accelerator coupled to the eighth output;
a third accelerator coupled to the tenth output; and
a fourth accelerator coupled to the twelfth output.

### Claim 4 (depends on 3)

The circuit of claim 3, wherein:
an output of the first accelerator is coupled to a first input of the fourth multiplexer;
an output of the second accelerator is coupled to a first input of the second multiplexer;
an output of the third accelerator is coupled to a first input of the third multiplexer; and
an output of the fourth accelerator is coupled to a first input of the first multiplexer.

### Claim 5 (depends on 4)

The circuit of claim 4, wherein:
a second input of the first multiplexer is coupled to memory;
a second input of the second multiplexer is coupled to memory;
a second input of the third multiplexer is coupled to memory; and
a second input of the fourth multiplexer is coupled to memory.

### Claim 6 (depends on 3)

The circuit of claim 3, wherein each of the first accelerator, the second accelerator, the third accelerator, and the fourth accelerator are bitonic sorting accelerators.

### Claim 7 (depends on 1)

The circuit of claim 1, wherein each of the first, second, third, and fourth compare-exchange circuits comprises:
a comparator coupled to respective inputs of the respective compare-exchange circuit;
an XOR circuit coupled to an output of the comparator and to a respective input of the respective compare-exchange circuit;
an AND circuit coupled to an output of the XOR circuit coupled to another respective input of the respective compare-exchange circuit; and
a first multiplexer coupled to the respective inputs of the respective compare-exchange circuit, to an output of the AND circuit, and to a respective output of the respective compare-exchange circuit; and
a second multiplexer coupled to the respective inputs of the respective compare-exchange circuit, to the output of the AND circuit, and to another respective output of the respective compare-exchange circuit.

### Claim 8 (depends on 1)

The circuit of claim 1, wherein each of the first, second, third, and fourth compare-exchange circuits are coupled to a buffer.

### Claim 9 (depends on 8)

The circuit of claim 8, wherein the buffer is a first-in-first-out buffer.

### Claim 10

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.

### Claim 11 (depends on 10)

The method of claim 10, wherein the first compare-exchange circuit comprises:
a comparator coupled to a first input and a second input of the first compare-exchange circuit;
an XOR circuit coupled to an output of the comparator and to the input of the first compare-exchange circuit;
an AND circuit coupled to an output of the XOR circuit, coupled to the second input of the first compare-exchange circuit;
a first multiplexer coupled to the first input and the second input of the first compare-exchange circuit, to an output of the AND circuit, and to a first output of the first compare-exchange circuit; and
a second multiplexer coupled to the first input and the second input of the first compare-exchange circuit, to the output of the AND circuit, and to a second output of the first compare-exchange circuit.

### Claim 12 (depends on 10)

The method of claim 10, further comprising:
if the determined operation mode is a third 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 lesser value to the buffer of the first compare-exchange circuit; and
passing the greater value to the third compare-exchange circuit or the memory.

### Claim 13 (depends on 10)

The method of claim 10, further comprising:
during a first iteration, arranging a vector of input data into a bitonic sequence by a plurality of compare-exchange circuits, the plurality of compare-exchange circuit comprising the first compare-exchange circuit, the second compare-exchange circuit, and the third compare-exchange circuit.

### Claim 14 (depends on 13)

The method of claim 13, further comprising:
during a second iteration, arranging the bitonic sequence into a fully-sorted array by the plurality of compare-exchange circuits.

### Claim 15 (depends on 10)

The method of claim 10, wherein the control signal is stored in a control signal buffer.

### Claim 16 (depends on 10)

The method of claim 10, wherein the buffer of the first compare-exchange circuit is a first-in-first-out buffer.

### Claim 17 (depends on 10)

The method of claim 10, wherein the first compare-exchange circuit comprises a counter configured to increment a first counter based on each iteration and to increment a second counter based on each clock cycle.

### Claim 18 (depends on 17)

The method of claim 17, wherein the control signal is based on the first counter and the second counter.

### Claim 19

A method comprising:
determining an operation mode for a first compare-exchange circuit based on a control signal;
if the 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 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;
if the operation mode is a third 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 lesser value to the buffer of the first compare-exchange circuit; and
passing the greater value to the third compare-exchange circuit or the memory.

### Claim 20 (depends on 19)

The method of claim 19, wherein:
the first compare-exchange circuit comprises a counter configured to increment a first counter based on each iteration and to increment a second counter based on each clock cycle; and
the control signal is based on the first counter and the second counter.
