Data sort using memory-intensive exosort
AssigneeEmpire Technology Development LLC
InventorFarid A. Chouery
Life of this patent
Estimating the term…
Abstract
Technologies are generally described to implement exosort in computing devices. In some examples, elements in a list to be sorted may be mapped to respective list positions based on some relationship. Collisions that occur at particular list positions may be resolved by allocating list space at those particular list positions based on the number of collisions and mapping collided elements to the respective allocated list space. Each allocated list space may then be further sorted, either by recursively using exosort or by using another sorting algorithm such as quicksort.
Claims29
A method to generate a sorted list in a memory, the method comprising:
- identifying a list including a plurality of elements and stored at a first location in the memory;
- mapping at least one element in the plurality of elements to a respective list position;
- determining, for each mapped element, a collision parameter;
- allocating, for each mapped element, space in the memory based on the collision parameter;
- determining, for each element in the plurality of elements, a respective memory location in the memory based on the allocated space and the collision parameter;
- transferring each element in the plurality of elements to its respective memory location;
- determining, for each mapped element, a colliding element selected from the plurality of elements;
- combining each mapped element and its respective colliding element into a subarray using a sorting algorithm;
- and
- storing the subarray in the space in the memory allocated for each respective mapped element by determining the respective memory location in the memory for each element in the plurality of elements.
(canceled)
(canceled)
A computing device configured to generate a sorted list, the computing device comprising:
- a memory;
- and
- a processing block configured to:
- identify a list including a plurality of elements and stored at a first location in the memory;
- map at least one element in the plurality of elements to a respective list position based on a linear relationship;
- determine, for each mapped element, a collision parameter;
- allocate, for each mapped element, space in the memory based on the collision parameter;
- determine, for each element in the plurality of elements, a respective memory location in the memory based on the allocated space and the collision parameter;
- transfer each element in the plurality of elements to its respective memory location;
- determine, for each mapped element, at least one colliding element selected from the plurality of elements;
- combine each mapped element and its respective at least one colliding element into a respective subarray using one of an exosort algorithm and a quicksort algorithm;
- and
- store the respective subarray in the space in the memory allocated for each respective mapped element by determining the respective memory location in the memory for each element in the plurality of elements.
(canceled)
(canceled)
(canceled)
A processor configured to execute an application module to generate a sorted list, the processor comprising:
- an on-chip memory;
- and
- one or more cores coupled to the on-chip memory, wherein at least one of the cores is configured to execute the application module, the application module configured to:
- identify a list including a plurality of elements and stored at a first location in the memory;
- map at least one element in the plurality of elements to a respective list position based on a linear relationship, wherein the linear relationship is computed based on at least one of a largest element in the list, a smallest element in the list, and a size of the list;
- determine, for each mapped element, a collision parameter;
- allocate, for each mapped element, space in the memory based on the collision parameter;
- determine, for each element in the plurality of elements, a respective memory location in the memory storing the list based on the allocated space and the collision parameter;
- transfer each element in the plurality of elements to its respective memory location;
- determine, for each mapped element, at least one colliding element selected from the plurality of elements;
- combine each mapped element and its respective at least one colliding element into a respective subarray using one of an exosort algorithm and a quicksort algorithm;
- and
- store the respective subarray in the space in the memory allocated for each respective mapped element by determining the respective memory location in the memory for each element in the plurality of elements.
(canceled)
(canceled)
(canceled)
(canceled)
Dependencies are inferred from the claim text.