Granted Patent B2

US 12,632,217 · App. 19/002,992 · Granted May 19, 2026

Inventor: Xuejun Liao (Cary, NC)

Assignee: SAS INSTITUTE INC.

G06F7/24G06F12/0284G06F16/2246G06F2207/222

Abstract

Claims (257)

1 . A non-transitory computer-readable medium storing computer-readable instructions that, when executed by one or more processors of a computing system comprising a main memory, an internal memory, and a memory controller, cause the computing system to perform operations for reducing auxiliary memory overhead and processor internal memory inefficiency during sorting of large datasets, the operations comprising:

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.

2 . The non-transitory computer-readable medium of claim 1 , wherein the LAHAS comprises a linked-array tournament tree (LATT) data structure.

3 . 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.

4 . The non-transitory computer-readable medium of claim 3 , wherein to create the LATT, the computer-readable instructions further cause the one or more processors to:

compute a number of the plurality of layers in the LATT;

compute a number of the one or more nodes in each of the plurality of layers;

create the LATT data structure with the computed number of the plurality of layers, with each layer of the plurality of layers having the computed number of the one or more nodes for that layer;

link each of the plurality of layers with an adjacent layer of the plurality of layers; and

store the LATT data structure in the allocated amount of auxiliary computer memory.

5 . The non-transitory computer-readable medium of claim 4 , wherein the computer readable instructions further cause the one or more processors to compute the number of the plurality of layers by computing [log 2 N].

6 . The non-transitory computer-readable medium of claim 4 , wherein the computer readable instructions further cause the one or more processors to compute the number of the one or more nodes in each of the plurality of layers by computing

n

h

⁢

=

⌈

n

h

-

1

2

⌉

where n h is a number of nodes in an h th layer of the plurality of layers, and h=1, 2, . . . [log 2 N] and h 0 =N.

7 . The non-transitory computer-readable medium of claim 4 , wherein the computer readable instructions further cause the one or more processors to compute the amount of auxiliary computer memory by computingN* sizeof (integer), where sizeof (integer) is the number of bytes of an integer.

8 . The non-transitory computer-readable medium of claim 3 , wherein the plurality of layers comprises {l 1 , l 2 , . . . , l h } layers, where h= [log 2 N], wherein l 1 is a leaf layer, l h is a root layer, and {l 2 , . . . , l h−1 } are a plurality of additional layers between the leaf layer and the root layer, wherein the leaf layer has [N/2] nodes, the root layer has one node, and each of the plurality of additional layers has greater than one and less than [N/2] nodes determined based on a number of nodes in a next lower layer of the plurality of layers, and wherein each layer l x where x={[log 2 N], ([log 2 N]−1), ([log 2 N]−2, . . . , 2}, is linked to a next adjacent layer l x −1.

9 . The non-transitory computer-readable medium of claim 8 , wherein the plurality of elements comprises {D 0 , D 1 , . . . , D N−1 }, and wherein to initialize the LATT, the computer-readable instructions further cause the one or more processors to:

divide the plurality of elements {D 0 , D 1 , . . . , D N−1 } into a plurality of element pairs {D i , D min(i+1,N−1) }, where i=0,2,4, . . . ,2*[(N−1)/2];

compare element values of each element pair of the plurality of element pairs to determine the winner in each of the plurality of element pairs;

determine the index value of each of the winners;

populate the node value of each of the [N/2] nodes in the leaf layer with the index value of one of the winners; and

populate the node value of each of the one or more nodes in the layer l x based on the next adjacent layer l x−1 by:

dividing the one or more nodes in the next adjacent layer l x−1 into node pairs;

determining the element values corresponding to the index values in each of the node pairs;

comparing the element values in each of the node pairs to determine the winner in each of the node pairs; and

populating the node value of each of the one or more nodes in the layer l x with the index value of one of the winners of the node pairs.

10 . The non-transitory computer-readable medium of claim 8 , wherein the index value of the champion element corresponds to the node value in the root layer.

11 . The non-transitory computer-readable medium of claim 8 , wherein to update the value of at least one of the one or more nodes, the computer-readable instructions further cause the one or more processors to:

perform a remove operation to remove the champion element from the LATT; and

perform a replace operation to update the winners in the LATT.

12 . The non-transitory computer-readable medium of claim 11 , wherein to perform the remove operation, the computer-readable instructions further cause the one or more processors to:

designate the champion element after swapping as a child node;

determine a parent node of the child node in the leaf layer; and

update the node value of the parent node by removing the champion element as an opponent.

13 . The non-transitory computer-readable medium of claim 12 , wherein to update the node value of the parent node, the computer-readable instructions further cause the one or more processors to:

determine based on the node value of the parent node that the parent node has neither a left opponent nor a right opponent; and

responsive to determining that the parent node has neither the left opponent nor the right opponent, update the node value of an ancestor node of the child node.

14 . The non-transitory computer-readable medium of claim 11 , wherein to perform the remove operation, the computer-readable instructions further cause the one or more processors to:

check for satisfaction of a first exit or a second exit; and

responsive to satisfaction of either the first exit or the second exit, exit the remove operation and perform the replace operation.

15 . The non-transitory computer-readable medium of claim 14 , wherein the first exit occurs when a next sorted index position and a champion position have a same ancestor node in a non-root layer, and wherein the champion position is the index value associated with the champion element.

16 . The non-transitory computer-readable medium of claim 14 , wherein the second exit occurs when, before the swap, an

element

[

n

parent

th

⁢

(

next

⁢

sorted

⁢

index

⁢

position

)

]

has lost in a (n+1) th round of games of a previous iteration, where

0

parent

th

⁢

(

position

)

is the position self.

17 . The non-transitory computer-readable medium of claim 3 , wherein the node value of each of the one or more nodes further includes a one bit left child value indicating presence of a left opponent in the pairwise comparison and a one bit right child value indicating presence of a right opponent in the pairwise comparison.

18 . The non-transitory computer-readable medium of claim 3 , wherein the computer readable instructions further cause the one or more processors to:

initialize a next sorted index position in the first portion of the computer memory;

receive an indicator indicative of sorting the plurality of elements starting from a left side or a right side; and

responsive to determining that the indicator is to sort the plurality of elements starting from the left side, initialize the next sorted index position as the index value of a first element of the plurality of elements; or

responsive to determining that the indicator is to sort the plurality of elements starting from the right side, initialize the next sorted index position as the index value of a last element of the plurality of elements.

19 . The non-transitory computer-readable medium of claim 18 , wherein the computer readable instructions further cause the one or more processors to:

update the next sorted index position=next sorted index position+1 responsive to determining that the indicator is to sort the plurality of elements starting from the left side; or

update the next sorted index position=next sorted index position-1 responsive to determining that the indicator is to sort the plurality of elements starting from the right side.

20 . The non-transitory computer-readable medium of claim 3 , wherein the plurality of tournament rounds comprises N tournament rounds.

21 . 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.

22 . The system of claim 21 , wherein the LAHAS comprises a linked-array tournament tree (LATT) data structure.

23 . 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.

24 . The system of claim 23 , wherein to create the LATT, the computer-readable instructions further cause the one or more processors to:

compute a number of the plurality of layers in the LATT by computing [log 2 N];

compute a number of the one or more nodes in each of the plurality of layers by computing

n

h

⁢

=

⌈

n

h

-

1

2

⌉

where n h is a number of nodes in an h th layer of the plurality of layers, and h=1, 2, . . . [log 2 N] and h 0 =N;

create the LATT data structure with the computed number of the plurality of layers, with each layer of the plurality of layers having the computed number of the one or more nodes for that layer;

link each of the plurality of layers with an adjacent layer of the plurality of layers; and

store the LATT data structure in the allocated amount of auxiliary memory.

25 . The system of claim 23 , wherein the plurality of layers comprises {l 1 , l 2 , . . . , l h } layers, where h= [log 2 N], wherein l 1 is a leaf layer, l h is a root layer, and {l 2 , . . . , l h−1 } are a plurality of additional layers between the leaf layer and the root layer, wherein the leaf layer has [N/2] nodes, the root layer has one node, and each of the plurality of additional layers has greater than one and less than [N/2] nodes determined based on a number of nodes in a next lower layer of the plurality of layers, and wherein each layer l x where x={[log 2 N], ([log 2 N]−1), ([log 2 N]−2, . . . , 2}, is linked to a next adjacent layer l x −1.

26 . The system of claim 25 , wherein to initialize the LATT, the computer-readable instructions further cause the one or more processors to:

divide the plurality of elements {D 0 , D 1 , . . . , D N−1 } into a plurality of element pairs {Di, D min(i+1,N−1) }, where i=0,2,4, . . . ,2*[(N−1)/2];

compare element values of each element pair of the plurality of element pairs to determine the winner in each of the plurality of element pairs;

determine the index value of each of the winners;

populate the node value of each of the [N/2] nodes in the leaf layer with the index value of one of the winners; and

populate the node value of each of the one or more nodes in the layer l x based on the next adjacent layer l x−1 by:

dividing the one or more nodes in the next adjacent layer l x−1 into node pairs;

determining the element values corresponding to the index values in each of the node pairs;

comparing the element values in each of the node pairs to determine the winner in each of the node pairs; and

populating the node value of each of the one or more nodes in the layer l x with the index value of one of the winners of the node pairs.

27 . The system of claim 25 , wherein to update the value of at least one of the one or more nodes, the computer-readable instructions further cause the one or more processors to:

perform a remove operation to remove the champion element from the LATT by:

designating the champion element after swapping as a child node;

determining a parent node in the leaf layer of the child node;

updating the node value of the parent node to remove the champion element as an opponent; and

checking for satisfaction of a first exit or a second exit;

responsive to satisfaction of either the first exit or the second exit, exit the remove operation and perform a replace operation to update the LATT.

28 . The system of claim 27 , wherein the first exit occurs when a next sorted index position and a champion position have a same ancestor node in a non-root layer, and wherein the champion position is the index value associated with the champion element.

29 . The system of claim 27 , wherein the second exit occurs when, before the swap, an element

[

n

parent

th

⁢

(

next

⁢

sorted

⁢

index

⁢

position

)

]

has lost in a (n+1) th round of games of a previous iteration, where

0

parent

th

⁢

(

position

)

is the position self.

30 . The system of claim 23 , wherein the node value of each of the one or more nodes further includes a one bit left child value indicating presence of a left opponent in the pairwise comparison and a one bit right child value indicating presence of a right opponent in the pairwise comparison.

31 . The system of claim 23 , wherein the computer-readable instructions further cause the one or more processors to:

initialize a next sorted index position in the first portion of the computer memory;

receive an indicator indicative of sorting the plurality of elements starting from a left side or a right side; and

responsive to determining that the indicator is to sort the plurality of elements starting from the left side, initialize the next sorted index position as the index value of a first element of the plurality of elements; or

responsive to determining that the indicator is to sort the plurality of elements starting from the right side, initialize the next sorted index position as the index value of a last element of the plurality of elements.

32 . The system of claim 31 , wherein the computer-readable instructions further cause the one or more processors to:

update the next sorted index position=next sorted index position+1 responsive to determining that the indicator is to sort the plurality of elements starting from the left side; or

update the next sorted index position=next sorted index position −1 responsive to determining that the indicator is to sort the plurality of elements starting from the right side.

33 . 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.

34 . The method of claim 33 , wherein the LAHAS comprises a linked-array tournament tree (LATT) data structure.

35 . 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.

36 . The method of claim 35 , wherein for creating the LATT, the method further comprises:

computing, by the one or more processors, a number of the plurality of layers in the LATT by computing [log 2 N];

computing, by the one or more processors, a number of the one or more nodes in each of the plurality of layers by computing

n

h

⁢

=

⌈

n

h

-

1

2

⌉

where n h is a number of nodes in an h th layer of the plurality of layers, and h=1, 2, . . . [log 2 N] and h 0 =N;

creating, by the one or more processors, the LATT data structure with the computed number of the plurality of layers, with each layer of the plurality of layers having the computed number of the one or more nodes for that layer;

linking, by the one or more processors, each of the plurality of layers with an adjacent layer of the plurality of layers; and

storing, by the one or more processors, the LATT data structure in the allocated amount of auxiliary memory.

Assignments (1)

Continuity (2)

References Cited (12)