Hardware implementation of a tournament tree sort algorithm using an external memory

1. A method for executing a tournament tree sort algorithm on a hardware accelerator that includes an external memory, the method comprising:

receiving, at the hardware accelerator, a plurality of keys;

sequentially assigning key numbers to the plurality of keys;

performing pairwise comparisons of at least a subset of the plurality of keys to determine, a first set of losing keys and a first set of winning keys;

storing each losing key in the first set of losing keys in a first section of the external memory;

storing each winning key in the first set of winning keys in a second section of the external memory;

performing pairwise comparisons of the winning keys to determine a second set of losing keys and a second set of winning keys

storing each losing key in the second set of losing keys in a third section of the external memory;

storing each winning key in the second set of winning keys locally on the hardware accelerator;

comparing a first locally-stored winning key and a second locally-stored winning key to determine a winner key; and

emitting the winner key as an output of the tournament tree sort algorithm.

2. The method of claim 1 , wherein storing each losing key in the first set of losing keys in a first section of the external memory corresponds to populating a first set of nodes at a first level of a tournament tree with the first set of losing keys, wherein storing each winning key in the first set of winning keys in a second section of the external memory corresponds to populating second set of nodes at a second level of the tournament tree with the first set of winning keys, and wherein the second level is closer in hierarchy to a root node of the tournament tree that the first level.

3. The method of claim 1 , wherein each losing key in the first set of losing keys is stored in a respective location in the first section of the external memory that is based on a respective sequential key number assigned to the losing key.

4. The method of claim 1 , further comprising assigning a color value to a particular key of the plurality of keys, wherein the color value indicates a tournament tree sort run associated with the particular key.

5. The method of claim 1 , further comprising:

receiving, at the hardware accelerator, a new key;

assigning a key number previously assigned to the outputted winner key to the new key;

initializing a tree level variable;

setting a global winner to the new key;

retrieving a first stored key stored at a first level of the tournament tree corresponding to the tree level variable;

comparing the global winner to the retrieved first stored key to determine that the retrieved first stored key wins the comparison;

writing the global winner to an external memory address at which the first stored key is stored;

updating the global winner by setting the global winner to the retrieved first stored key; and

incrementing the tree level variable.

6. The method of claim 5 , further comprising:

retrieving a second stored key stored at a second level of the tournament tree corresponding to the incremented tree level variable;

comparing the global winner to the retrieved second stored key to determine that the global winner wins the comparison;

incrementing the tree level variable;

determining that a current value of the tree level variable corresponds to a highest tree level of the tournament tree;

determining that a top key of the tournament tree wins a comparison with the global winner;

emitting the top key; and

storing the global winner as a new top key.

7. The method of claim 1 , wherein storing each losing key in the first set of losing keys in a first section of the external memory comprises performing a batched write of the first set of losing keys to the first section of the external memory.

8. A system for executing a tournament tree sort algorithm, the system comprising:

a hardware accelerator that includes an external memory and that is configured to receive a plurality of keys; and

a processor configured to execute stored instructions to:

sequentially assign key numbers to the plurality of keys;

perform pairwise comparisons of at least a subset of the plurality of keys to determine, a first set of losing keys and a first set of winning keys;

store each losing key in the first set of losing keys in a first section of the external memory;

store each winning key in the first set of winning keys in a second section of the external memory;

perform pairwise comparisons of the winning keys to determine a second set of losing keys and a second set of winning keys;

store each losing key in the second set of losing keys in a third section of the external memory;

store each winning key in the second set of winning keys locally on the hardware accelerator;

compare a first locally-stored winning key and a second locally-stored winning key to determine a winner key; and

emit the winner key as an output of the tournament tree sort algorithm.

9. The system of claim 8 , wherein storing each losing key in the first set of losing keys in a first section of the external memory corresponds to populating a first set of nodes at a first level of a tournament tree with the first set of losing keys, wherein storing each winning key in the first set of winning keys in a second section of the external memory corresponds to populating second set of nodes at a second level of the tournament tree with the first set of winning keys, and wherein the second level is closer in hierarchy to a root node of the tournament tree that the first level.

10. The system of claim 8 , wherein each losing key in the first set of losing keys is stored in a respective location in the first section of the external memory that is based on a respective sequential key number assigned to the losing key.

11. The system of claim 8 , wherein the processor is further configured to execute the stored instructions to assign a color value to a particular key of the plurality of keys, wherein the color value indicates a tournament tree sort run associated with the particular key.

12. The system of claim 8 , wherein the hardware accelerator is further configured to receive a new key, and wherein the processor is further configured to execute the stored instructions to:

assign a key number previously assigned to the outputted winner key to the new key;

initialize a tree level variable;

set a global winner to the new key;

retrieve a first stored key stored at a first level of the tournament tree corresponding to the tree level variable;

compare the global winner to the retrieved first stored key to determine that the retrieved first stored key wins the comparison;

write the global winner to an external memory address at which the first stored key is stored;

update the global winner by setting the global winner to the retrieved first stored key; and

increment the tree level variable.

13. The system of claim 12 , wherein the processor is further configured to execute the stored instructions to:

retrieve a second stored key stored at a second level of the tournament tree corresponding to the incremented tree level variable;

compare the global winner to the retrieved second stored key to determine that the global winner wins the comparison;

increment the tree level variable;

determine that a current value of the tree level variable corresponds to a highest tree level of the tournament tree;

determining that a top key of the tournament tree wins a comparison with the global winner;

emitting the top key; and

storing the global winner as a new top key.

14. The system of claim 8 , wherein storing each losing key in the first set of losing keys in a first section of the external memory comprises performing a batched write of the first set of losing keys to the first section of the external memory.

15. A computer program product for executing a tournament tree sort algorithm on a hardware accelerator that includes an external memory, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:

receiving, at the hardware accelerator, a plurality of keys;

sequentially assigning key numbers to the plurality of keys;

performing pairwise comparisons of at least a subset of the plurality of keys to determine, a first set of losing keys and a first set of winning keys;

storing each losing key in the first set of losing keys in a first section of the external memory;

storing each winning key in the first set of winning keys in a second section of the external memory;

performing pairwise comparisons of the winning keys to determine a second set of losing keys and a second set of winning keys;

storing each losing key in the second set of losing keys in a third section of the external memory;

storing each winning key in the second set of winning keys locally on the hardware accelerator;

compare a first locally-stored winning key and a second locally-stored winning key to determine a winner key; and

emit the winner key as an output of the tournament tree sort algorithm.

16. The computer program product of claim 15 , wherein storing each losing key in the first set of losing keys in a first section of the external memory corresponds to populating a first set of nodes at a first level of a tournament tree with the first set of losing keys, wherein storing each winning key in the first set of winning keys in a second section of the external memory corresponds to populating second set of nodes at a second level of the tournament tree with the first set of winning keys, and wherein the second level is closer in hierarchy to a root node of the tournament tree that the first level.

17. The computer program product of claim 15 , wherein each losing key in the first set of losing keys is stored in a respective location in the first section of the external memory that is based on a respective sequential key number assigned to the losing key.

18. The computer program product of claim 15 , the method further comprising assigning a color value to a particular key of the plurality of keys, wherein the color value indicates a tournament tree sort run associated with the particular key.

19. The computer program product of claim 15 , the method further comprising:

receiving, at the hardware accelerator, a new key;

assigning a key number previously assigned to the outputted winner key to the new key;

initializing a tree level variable;

setting a global winner to the new key;

retrieving a first stored key stored at a first level of the tournament tree corresponding to the tree level variable;

comparing the global winner to the retrieved first stored key to determine that the retrieved first stored key wins the comparison;

writing the global winner to an external memory address at which the first stored key is stored;

updating the global winner by setting the global winner to the retrieved first stored key; and

incrementing the tree level variable.

20. The computer program product of claim 19 , the method further comprising:

retrieving a second stored key stored at a second level of the tournament tree corresponding to the incremented tree level variable;

comparing the global winner to the retrieved second stored key to determine that the global winner wins the comparison;

incrementing the tree level variable;

determining that a current value of the tree level variable corresponds to a highest tree level of the tournament tree;

determining that a top key of the tournament tree wins a comparison with the global winner;

emitting the top key; and

storing the global winner as a new top key.