Optimized in-place sorting using additional memory

A non-transitory computer-readable medium storing instructions that, when executed by one or more processors of a computing system, cause the computing system to perform operations comprising:

• receiving, by a memory controller, a plurality of elements to be sorted, the plurality of elements comprising N elements stored in a first portion of a computer memory;
• computing, by the one or more processors, a required amount of auxiliary memory less than N based on characteristics of the plurality of elements and available internal memory;
• allocating, within the computer memory, a second portion corresponding to the computed amount of auxiliary memory, the second portion being contiguous with the first portion of the computer memory;
• constructing, within the second portion of the computer memory, a linked-array tournament tree (LATT) data structure comprising a plurality of layers of nodes, each node storing an index corresponding to an element of the plurality of elements;
• initializing, by the one or more processors, the LATT data structure by populating each node of each layer with a node value determined from an executed pairwise comparison between respective elements of the plurality of elements;
• executing, by the one or more processors, a plurality of tournament rounds within the computer memory, each round comprising:
• determining, for each of a plurality of games executed in the computer memory, a winning element based on the pairwise comparison between at least two elements;
• determining, across the plurality of games, a champion element as a winning element for the round;
• and
• swapping, within the first portion of the computer memory, the champion element with an unsorted element to store the champion element in a sorted position;
• updating, after each tournament round, at least one node value of the LATT data structure based on the champion element to maintain consistency between the layers of the LATT data structure and the memory locations of the plurality of elements;
• and
• outputting, from the first portion of the computer memory, the plurality of elements in a sorted order without requiring transfer of the plurality of elements to an external storage medium.

A computing system, comprising:

• a main memory having computer-readable instructions stored thereon;
• an internal memory;
• a memory controller;
• and
• one or more processors that execute the computer-readable instructions to perform operations for reducing auxiliary memory overhead and processor internal memory inefficiency during sorting of large datasets, wherein the one or more processors executing the computer-readable instructions to perform the operations comprises the one or more processors executing the computer-readable instructions to:
• storing, in the main memory, a plurality of unsorted data elements, each data element of the plurality of unsorted data elements associated with a respective index value, the plurality of unsorted data elements comprising N data elements;
• detecting, by the one or more processors, a memory-constrained sorting condition in which an available auxiliary memory capacity of the computing system is less than N;
• computing, by the one or more processors, based on the detected memory-constrained sorting condition, an auxiliary memory quantity to be used for sorting that is dynamically adjusted according to an internal utilization parameter of the computing system;
• allocating, by the memory controller, a contiguous auxiliary memory region within the main memory corresponding to the computed auxiliary memory quantity;
• constructing, within the contiguous auxiliary memory region, a linked-array hierarchical assessment structure (LAHAS), the LAHAS comprising a plurality of interconnected layers of nodes, each node of the plurality of interconnected layers of nodes associated with an index value of a corresponding data element of the plurality of unsorted data elements stored in the main memory;
• initializing, by the one or more processors, the LAHAS by performing processor-executed pairwise assessment operations between data elements of the plurality of unsorted data elements and populating each node of the plurality of interconnected layers of nodes with an identifier of an assessment result data element determined from the pairwise assessment operations;
• executing, by the one or more processors, within the main memory, a multi-stage assessment sequence, each stage of the multi-stage assessment sequence comprising:
• performing, by the one or more processors, parallel pairwise assessment operations at one or more nodes of the plurality of interconnected layers of nodes of the LAHAS to generate updated assessment result data elements;
• identifying, by the one or more processors, from the updated assessment result data elements, a terminal assessment result data element representing an extreme value relative to a predetermined assessment criterion;
• and
• replacing, by the one or more processors, within the main memory, a memory position of the terminal assessment result data element with a memory position of an unsorted data element of the plurality of unsorted data elements to store the terminal assessment result data element in a sorted location in the main memory without invoking external memory transfers;
• updating, by the one or more processors, after completion of each stage of the multi-stage assessment sequence, node values of the plurality of interconnected layers of nodes of the LAHAS to maintain consistency between the index values and corresponding memory locations of the data elements stored in the main memory;
• and
• outputting, by the one or more processors, from the main memory, the plurality of data elements in a sorted order, wherein execution of the multi-stage assessment sequences and the updates to the node values of the plurality of interconnected layers of nodes of the LAHAS collectively reduce sorting time, recursion depth, and auxiliary memory consumption relative to conventional heapsort implementations, thereby improving processor internal memory efficiency and computational throughput of the computing system.

A system, comprising:

• a memory having computer-readable instructions stored thereon;
• a memory controller;
• and
• one or more processors that execute the computer-readable instructions to:
• receiving, by the memory controller, a plurality of elements to be sorted, the plurality of elements comprising N elements stored in a first portion of a computer memory;
• computing, by the one or more processors, a required amount of auxiliary memory less than N based on characteristics of the plurality of elements and available internal memory;
• allocating, within the computer memory, a second portion corresponding to the computed amount of auxiliary memory, the second portion being contiguous with the first portion of the computer memory;
• constructing, within the second portion of the computer memory, a linked-array tournament tree (LATT) data structure comprising a plurality of layers of nodes, each node storing an index corresponding to an element of the plurality of elements;
• initializing, by the one or more processors, the LATT data structure by populating each node of each layer with a node value determined from an executed pairwise comparison between respective elements of the plurality of elements;
• executing, by the one or more processors, a plurality of tournament rounds within the computer memory, each round comprising:
• determining, for each of a plurality of games executed in the computer memory, a winning element based on the pairwise comparison between at least two elements;
• determining, across the plurality of games, a champion element as a winning element for the round;
• and
• swapping, within the first portion of the computer memory, the champion element with an unsorted element to store the champion element in a sorted position;
• updating, after each tournament round, at least one node value of the LATT data structure based on the champion element to maintain consistency between the layers of the LATT data structure and the memory locations of the plurality of elements;
• and
• outputting, from the first portion of the computer memory, the plurality of elements in a sorted order without requiring transfer of the plurality of elements to an external storage medium.

A method for reducing auxiliary memory overhead and processor internal memory inefficiency during sorting of large datasets, the method comprising:

• storing, in a main memory of a computing system, a plurality of unsorted data elements, each data element of the plurality of unsorted data elements associated with a respective index value, the plurality of unsorted data elements comprising N data elements;
• detecting, by one or more processors, a memory-constrained sorting condition in which an available auxiliary memory capacity of the computing system is less than N;
• computing, by the one or more processors, based on the detected memory-constrained sorting condition, an auxiliary memory quantity to be used for sorting that is dynamically adjusted according to an internal utilization parameter of the computing system;
• allocating, by a memory controller of the computing system, a contiguous auxiliary memory region within the main memory corresponding to the computed auxiliary memory quantity;
• constructing, within the contiguous auxiliary memory region, a linked-array hierarchical assessment structure (LAHAS), the LAHAS comprising a plurality of interconnected layers of nodes, each node of the plurality of interconnected layers of nodes associated with an index value of a corresponding data element of the plurality of unsorted data elements stored in the main memory;
• initializing, by the one or more processors, the LAHAS by performing processor-executed pairwise assessment operations between data elements of the plurality of unsorted data elements and populating each node of the plurality of interconnected layers of nodes with an identifier of an assessment result data element determined from the pairwise assessment operations;
• executing, by the one or more processors, within the main memory, a multi-stage assessment sequence, each stage of the multi-stage assessment sequence comprising:
• performing, by the one or more processors, parallel pairwise assessment operations at one or more nodes of the plurality of interconnected layers of nodes of the LAHAS to generate updated assessment result data elements;
• identifying, by the one or more processors, from the updated assessment result data elements, a terminal assessment result data element representing an extreme value relative to a predetermined assessment criterion;
• and
• replacing, by the one or more processors, within the main memory, a memory position of the terminal assessment result data element with a memory position of an unsorted data element of the plurality of unsorted data elements to store the terminal assessment result data element in a sorted location in the main memory without invoking external memory transfers;
• updating, by the one or more processors, after completion of each stage of the multi-stage assessment sequence, node values of the plurality of interconnected layers of nodes of the LAHAS to maintain consistency between the index values and corresponding memory locations of the data elements stored in the main memory;
• and
• outputting, by the one or more processors, from the main memory, the plurality of data elements in a sorted order, wherein execution of the multi-stage assessment sequences and the updates to the node values of the plurality of interconnected layers of nodes of the LAHAS collectively reduce sorting time, recursion depth, and auxiliary memory consumption relative to conventional heapsort implementations, thereby improving processor internal memory efficiency and computational throughput of the computing system.

A method, comprising:

• receiving, by a memory controller, a plurality of elements to be sorted, the plurality of elements comprising N elements stored in a first portion of a computer memory;
• computing, by one or more processors, a required amount of auxiliary memory less than N based on characteristics of the plurality of elements and available internal memory;
• allocating, within the computer memory, a second portion corresponding to the computed amount of auxiliary memory, the second portion being contiguous with the first portion of the computer memory;
• constructing, within the second portion of the computer memory, a linked-array tournament tree (LATT) data structure comprising a plurality of layers of nodes, each node storing an index corresponding to an element of the plurality of elements;
• initializing, by the one or more processors, the LATT data structure by populating each node of each layer with a node value determined from an executed pairwise comparison between respective elements of the plurality of elements;
• executing, by the one or more processors, a plurality of tournament rounds within the computer memory, each round comprising:
• determining, for each of a plurality of games executed in the computer memory, a winning element based on the pairwise comparison between at least two elements;
• determining, across the plurality of games, a champion element as a winning element for the round;
• and
• swapping, within the first portion of the computer memory, the champion element with an unsorted element to store the champion element in a sorted position;
• updating, after each tournament round, at least one node value of the LATT data structure based on the champion element to maintain consistency between the layers of the LATT data structure and the memory locations of the plurality of elements;
• and
• outputting, from the first portion of the computer memory, the plurality of elements in a sorted order without requiring transfer of the plurality of elements to an external storage medium.