Back to results
US 9,858,179 B2Granted
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.
Claims18
A method performed by a processor to increase a speed of sorting a plurality of elements stored in a memory, the method comprising:
- identifying a list that includes the plurality of elements and that is stored at a first location in the memory;
- mapping at least one element in the plurality of elements to a respective list position;
- storing the mapped at least one element at another location, different from the first location, in the memory;
- determining, for the mapped at least one element, a respective collidine element selected from the plurality of elements, wherein the respective colliding element is stored at a second location in the memory;
- determining, for the mapped at least one element, a collision parameter, wherein the collision parameter includes at least one of a collision count for the mapped at least one element and a collision location for the respective colliding element, wherein the collision count is stored at a third location in the memory and the collision location is stored at a fourth location in the memory, and wherein the first location, the second location, the third location, the fourth location, and the another location are different from each other;
- allocating, for the mapped at least one element, a space in the memory based on the collision parameter,
- determining, for the mapped at least one element, a respective memory location in the memory based on the allocated space and the collision parameter,
- transferring the mapped at least one element to the respective memory location;
- combining the mapped at least one element and the respective colliding element into a subarray using a sorting algorithm;
- storing the subarray in the space in the memory allocated for the mapped at least one element by determining the respective memory location in the memory for the mapped at least one element;
- combining a plurality of mapped elements and respective colliding elements into a plurality of respective subarrays;
- and
- sorting the plurality of respective subarrays to generate a sorted list of the plurality of elements, wherein storing the mapped at least one element, the respective colliding element the collision count for the mapped at least one element, the collision location for the respective colliding element, and the subarray, at different locations in the memory, facilitates an increase in the speed of sorting to generate the sorted list of the plurality of elements.
10 more elements
A computing device configured to increase a speed of sorting a plurality of elements stored in a memory, the computing device comprising:
- a processor block coupled to the memory, the processor block configured to:
- identify a list that includes the plurality of elements and that is stored at a first location in the memory;
- map at least one element in the plurality of elements, to a respective list position by storage of the mapped at least one element at another location, different from the first location, in the memory;
- determine, for the mapped at least one element, a respective at least one colliding element selected from the plurality of elements, wherein the respective at least one colliding element is stored at a second location in the memory;
- determine, for the mapped at least one element, a collision parameter, wherein the collision parameter includes at least one of a collision count for the mapped at least one element and a collision location for the respective at least one colliding element, wherein the collision count indicates a number of elements mapped to the respective list position, wherein the collision count is stored at a third location in the memory and the collision location is stored at a fourth location in the memory, and wherein the first location, the second location, the third location, the fourth location, and the another location are different from each other;
- allocate, for the mapped at least one element, space in the memory based on the collision parameter;
- determine, for the mapped at least one element, a respective memory location in the memory based on the allocated space and the collision parameter;
- transfer the mapped at least one element to the respective memory location;
- combine the mapped at least one element and the respective at least one colliding element into a respective subarray by use of at least one of an exosort algorithm and a quicksort algorithm;
- store the respective subarray in the space in the memory allocated for the mapped at least one element by determination of the respective memory location in the memory for the mapped at least one element;
- combine a plurality of mapped elements and respective colliding elements into a plurality of respective subarrays;
- and
- sort the plurality of respective subarrays to generate a sorted list of the plurality of elements, wherein the storage of the mapped at least one element, the respective at least one colliding element, the collision count for the mapped at least one element, the collision location for the respective at least one colliding element, and the subarray, at different locations in the memory, facilitates an increase in the speed of sorting to generate the sorted list of the plurality of elements.
10 more elements
A processor configured to execute an application module to increase a speed of sorting a plurality of elements stored in an on-chip memory, the processor comprising:
- one or more cores operatively coupled to the on-chip memory, wherein at least one of the one or more cores is configured to execute the application module, and wherein the application module is configured to:
- identify a list that includes the plurality of elements and that is stored at a first location in the on-chip memory;
- map at least one element in the plurality of elements, to a respective list position by storage of the mapped at least one element at another location, different from the first location, in the on-chip memory, 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 the mapped at least one element, a respective at least one colliding element selected from the plurality of elements, wherein the respective at least one colliding element is stored at a second location in the on-chip memory;
- determine, for the mapped at least one element, a collision parameter, wherein the collision parameter includes at least one of a collision count for the mapped at least one element and a collision location for the respective at least one collidine element, wherein the collision count is stored at a third location in the on-chip memory and the collision location is stored at a fourth location in the on-chip memory, and wherein the first location, the second location, the third location, the fourth location, and the another location are different from each other;
- allocate, for the mapped at least one element, a space in the on-chip memory based on the collision parameter;
- determine, for the mapped at least one element, a respective memory location in the on-chip memory based on the allocated space and the collision parameter,
- transfer the mapped at least one element to the respective memory location;
- combine the mapped at least one element and the respective at least one colliding element into a respective subarray by use of at least one of an exosort algorithm and a quicksort algorithm;
- store the respective subarray in the space in the memory allocated for the mapped at least one element by determination of the respective memory location in the on-chip memory for the mapped at least one element;
- combine a plurality of mapped elements and respective colliding elements into a plurality of respective subarrays;
- and
- sort the plurality of respective subarrays to generate a sorted list of the plurality of elements, wherein the storage of the mapped at least one element, the respective at least one colliding element, the collision count for the mapped at least one element, the collision location for the respective at least one colliding element, and the subarray, at different locations in the on-chip memory, facilitates an increase in the speed of sorting to generate the sorted list of the plurality of elements.
10 more elements
Dependencies are inferred from the claim text.