# US 2025/0085860 A1 · Conflict-free parallel radix sorting device, system and method

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

- Number: US 2025/0085860 A1
- Document ID: US20250085860A1
- Status: Published application
- Kind: A1
- Application number: 18/954,624
- Filed: 2024-11-21
- Published: 2025-03-13
- Earliest claimed: 2022-06-17
- Assignees: Achronix Semiconductor Corporation
- Applicants: Achronix Semiconductor Corporation
- Inventors: Marcel Van der Goot; Raymond Nijssen; Christopher C. LaFrieda
- Web page: https://patentgrep.com/patent/US20250085860A1

## CPC

- G06F 3/0613: {in relation to throughput}
- 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 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0673: {Single storage device}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A conflict-free parallel radix sorting algorithm, and devices and systems implementing this algorithm, schedules memory copies of data elements of a large dataset so that there is always a single copy to each target memory each cycle of operation for the system implementing the algorithm. The conflict-free parallel radix sorting algorithm eliminates memory copying conflicts in copying data elements from different source memories to the same target memory and in this way maintains maximum throughput for the copying of data elements from source memories to target memories, reducing the time required to sort the data elements of the large dataset.

## Claims

### Claim 1

A method comprising:
generating a schedule table that provides a plurality of conflict-free mappings of data elements from a first bank comprising a first plurality of memories of a memory system to a second bank comprising a second plurality of memories of the memory system;
sorting the data elements locally in each of the first plurality of memories; and
performing, according to the schedule table, conflict-free copying in parallel of the sorted data elements from the first plurality of memories to the second plurality of memories.

### Claim 2 (depends on 1)

The method of claim 1, wherein the generating of the schedule table comprises executing a modified Edmonds' algorithm to find the conflict-free mappings.

### Claim 3 (depends on 2)

The method of claim 2, wherein the modified Edmond's algorithm comprises:
modifying a bipartite graph to remove edges with a weight of zero, the bipartite graph providing a perfect matching and having been generated in a prior iteration of Edmonds' algorithm; and
finding a subsequent perfect matching based on the modified bipartite graph.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
iteratively repeating the modifying of the bipartite graph and the finding of a subsequent perfect matching until the modified bipartite graph has no non-zero edges.

### Claim 5 (depends on 3)

The method of claim 3, wherein the generating of the schedule table further comprises generating a global copy queue including the plurality of conflict-free mappings, each conflict-free mapping corresponding to a perfect matching of the bipartite graph.

### Claim 6 (depends on 5)

The method of claim 5, wherein the performing, according to the schedule table, of the conflict-free copying in parallel of the data elements comprises copying the sorted data elements from the first plurality of memories to the second plurality of memories according to the plurality of conflict-free mappings of the global copy queue.

### Claim 7 (depends on 5)

The method of claim 5, wherein:
the first bank of memories and the second bank of memories each comprise a number M of memories; and
the method further comprises generating a boundary offset table including boundary offset for M−1 boundaries between the memories.

### Claim 8 (depends on 1)

The method of claim 1, wherein:
each of the data elements includes a key and data;
the sorting of the data elements locally in each of the memories in the first bank of memories comprises:
performing a counting sort on the data elements in each of the first plurality of memories, the counting sort including:
generating a count histogram for each of the first plurality of memories, each count histogram based on the keys of the data elements in the memory, and
sorting the data elements in each of the first plurality of memories based on the count histogram for the memory; and
the generating of the schedule table is based on the count histograms for each of first plurality of memories.

### Claim 9 (depends on 8)

The method of claim 8, wherein the sorting of the data elements in each of the memories in the first plurality of memories and the generating of the schedule table are executed in parallel.

### Claim 10

A system comprising:
at least one processor; and
at least one memory storing instructions that, when executed by the processor, cause the system to perform operations comprising:
generating a schedule table that provides a plurality of conflict-free mappings of data elements from a first bank comprising a first plurality of memories of a memory system to a second bank comprising a second plurality of memories of the memory system;
sorting the data elements locally in each of the first plurality of memories; and
performing, according to the schedule table, conflict-free copying in parallel of the sorted data elements from the first plurality of memories to the second plurality of memories.

### Claim 11 (depends on 10)

The system of claim 10, wherein the generating of the schedule table further comprises generating a global copy queue including the plurality of conflict-free mappings, each conflict-free mapping corresponding to a perfect matching of a bipartite graph.

### Claim 12 (depends on 11)

The system of claim 11, wherein the performing, according to the schedule table, of the conflict-free copying in parallel of the data elements comprises copying the sorted data elements from the first plurality of memories to the second plurality of memories according to the plurality of conflict-free mappings of the global copy queue.

### Claim 13 (depends on 10)

The system of claim 10, wherein:
the first bank of memories and the second bank of memories each comprise a number M of memories; and
the operations further comprise generating a boundary offset table including boundary offset for M−1 boundaries between the memories.

### Claim 14 (depends on 10)

The system of claim 10, wherein:
each of the data elements includes a key and data;
the sorting of the data elements locally in each of the memories in the first bank of memories comprises:
performing a counting sort on the data elements in each of the first plurality of memories, the counting sort including:
generating a count histogram for each of the first plurality of memories, each count histogram based on the keys of the data elements in the memory, and
sorting the data elements in each of the first plurality of memories based on the count histogram for the memory; and
the generating of the schedule table is based on the count histograms for each of first plurality of memories.

### Claim 15 (depends on 14)

The system of claim 14, wherein the sorting of the data elements in each of the memories in the first plurality of memories and the generating of the schedule table are executed in parallel.

### Claim 16

A non-transitory computer-storage medium that stores instructions that, when executed by one or more hardware processors, cause the one or more hardware processors to perform operations comprising:
generating a schedule table that provides a plurality of conflict-free mappings of data elements from a first bank comprising a first plurality of memories of a memory system to a second bank comprising a second plurality of memories of the memory system;
sorting the data elements locally in each of the first plurality of memories; and
performing, according to the schedule table, conflict-free copying in parallel of the sorted data elements from the first plurality of memories to the second plurality of memories.

### Claim 17 (depends on 16)

The non-transitory computer-storage medium of claim 16, wherein the generating of the schedule table further comprises generating a global copy queue including the plurality of conflict-free mappings, each conflict-free mapping corresponding to a perfect matching of a bipartite graph.

### Claim 18 (depends on 17)

The non-transitory computer-storage medium of claim 17, wherein the performing, according to the schedule table, of the conflict-free copying in parallel of the data elements comprises copying the sorted data elements from the first plurality of memories to the second plurality of memories according to the plurality of conflict-free mappings of the global copy queue.

### Claim 19 (depends on 16)

The non-transitory computer-storage medium of claim 16, wherein:
the first bank of memories and the second bank of memories each comprise a number M of memories; and
the operations further comprise generating a boundary offset table including boundary offset for M−1 boundaries between the memories.

### Claim 20 (depends on 16)

The non-transitory computer-storage medium of claim 16, wherein:
each of the data elements includes a key and data;
the sorting of the data elements locally in each of the memories in the first bank of memories comprises:
performing a counting sort on the data elements in each of the first plurality of memories, the counting sort including:
generating a count histogram for each of the first plurality of memories, each count histogram based on the keys of the data elements in the memory, and
sorting the data elements in each of the first plurality of memories based on the count histogram for the memory; and
the generating of the schedule table is based on the count histograms for each of first plurality of memories.
