Conflict-free parallel radix sorting device, system and method
AssigneeAnchronix Semiconductor Corporation
InventorsMarcel Van der Goot, Raymond Nijssen, Christopher C. LaFrieda
Life of this patent
Estimating the term…
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.
Claims24
A method of performing a conflict-free parallel radix sorting of data elements of a dataset stored in a memory system, the method including scheduling a copying of the data elements between storage locations of the memory system to enable the copying of the data elements to be conflict-free and to be performed at a maximum throughput of the memory system.
A system comprising:
- at least one processor;
- and
- at least one memory storing instructions that, when executed by the processor, configure the system to perform operations comprising:
- performing a conflict-free parallel radix sorting of data elements of a dataset stored in a first bank of memories, the conflict-free parallel radix sorting including;
- generating a schedule table providing a plurality of conflict-free mappings of data elements from the first bank of memories to a second bank of memories;
- and
- performing, according to the schedule table, conflict-free copying in parallel of the locally sorted data elements from each of the memories in the first bank of memories to the memories in the second bank of memories.
A method of performing a parallel radix sort, comprising:
- storing a plurality of data elements in a plurality of storage locations of a memory system, each of the plurality of data elements including a key and data;
- counting the keys of the plurality of data elements for a first iteration of the parallel radix sort as the data elements are initially stored in the storage locations in the memory system;
- generating an offset histogram based upon the counted keys;
- copying the plurality of data elements between storage locations of the memory system based on the offset histogram to sort the plurality of data elements according to the keys;
- repeating the operations of generating and copying for each radix of the key, wherein the counting of the keys for the first iteration of the parallel radix sort occurs as the data elements are initially being stored in data locations in the memory;
- and
- wherein the counting of the keys for subsequent iterations of the parallel radix sort occurs during copying of the data elements between storage locations of the memory system.
A distributed computer network, comprising:
- a network;
- and
- a plurality of computer systems coupled to the network, each computer system including at least one processor and at least one memory storing instructions that, when executed by the at least one processor, configure the computer system to perform operations comprising:
- executing a portion of a conflict-free parallel radix sorting on a portion of data elements of a dataset stored in the corresponding memory of the computer system;
- and
- communicating information for the executed portion of the conflict-free parallel radix sorting over the network to a designated one of the plurality of computer systems, the designated one of the plurality of computer systems utilizing the communicated information from each of the other computer systems to schedule communications over the network of data elements among the computer systems, the scheduled communications over the network being conflict-free and at a maximum throughput of the network.
Dependencies are inferred from the claim text.