Hardware implementation of a tournament tree sort algorithm

Patent metadata

Field	Value
Publication number	US-9619499-B2
Application number	US-201313961092-A
Country	US
Kind code	B2
Filing date	Aug 7, 2013
Priority date	Aug 7, 2013
Publication date	Apr 11, 2017
Grant date	Apr 11, 2017

Abstract

Embodiments include methods, systems and computer program products for performing a tournament tree sort on a hardware accelerator. The method includes receiving a plurality of key values by the hardware accelerator, storing each the plurality of keys into a location on a memory of the hardware accelerator, and creating a pointer to each of the locations of the plurality of keys. The method also includes storing the pointer to each of the plurality of keys into a first array stored by the hardware accelerator, sorting the plurality of keys by ordering the pointers in the first array and by using a second array for storing the pointers, wherein the sorting identifies a winning key from the plurality of keys in the memory, and outputting the winning key.

First claim

What is claimed is:

1. A computer program product, comprising:
a non-transitory computer readable storage medium having computer readable program code stored thereon that, when executed, performs a method, the method comprising:
receiving a plurality of key values;
storing each the plurality of keys into a location on a memory on a hardware accelerator;
creating a pointer to each of the locations of the plurality of keys;
storing the pointer to each of the plurality of keys into a first array on the hardware accelerator;
sorting the plurality of keys by ordering the pointers in the first array wherein the sorting includes performing a pairwise comparison of the key values associated the pointers having adjacent initial positions in the first array and storing the pointers of the loser of the pairwise comparison in a second array, wherein the sorting identifies a winning key from the plurality of keys in the memory, wherein a size of the second array is one quarter of a size of the first array to prevent corrupting the pointers to the plurality of keys being sorted; and
outputting the winning key.

2. The computer program product of claim 1 , wherein the hardware accelerator is a field programmable gate array (FPGA) or an application-specific integrated circuit (ASIC).

3. The computer program product of claim 1 , wherein sorting the plurality of keys includes performing a speculative comparison of two of the plurality of keys.

4. The computer program product of claim 2 , wherein the plurality of keys includes N keys and wherein the sorting identifies a subsequent winning key from the plurality of keys after every log N clock cycles.

5. The computer program product of claim 1 , wherein the winning key corresponds to the key with a highest key value.

6. The computer program product of claim 1 , wherein storing the pointer to each of the plurality of keys into the first array on the hardware accelerator includes determining a location in the first array based on the key value.

7. The computer program product of claim 1 , wherein ordering the pointers in the first array includes performing comparisons of the key values associated with adjacent pointers in the first array.

8. A hardware accelerator for performing a tournament tree sort, comprising: a memory configured to store each of a plurality of key values; a first array configured to store pointers to locations of each of the plurality of key values; a second array configured to store pointers to locations of a quarter or less of the plurality of key values; and a processor configured to sort the plurality of key values by ordering the pointers in the first array by performing a pairwise comparison of the key values associated the pointers having adjacent initial positions in the first array and the storing the pointers of the loser of the pairwise comparison in a second array, wherein the sorting identifies a winning key from the plurality of keys in the memory, wherein a size of the second array is one quarter of a size of the first array to prevent corrupting the pointers to the plurality of keys being sorted.

9. The hardware accelerator of claim 8 , wherein sorting the plurality of keys includes performing a speculative comparison of two of the plurality of keys.

10. The hardware accelerator of claim 9 , wherein the plurality of keys includes N keys and wherein the sorting identifies a subsequent winning key from the plurality of keys after every log N clock cycles.

11. A computer program product, comprising:
a non-transitory computer readable storage medium having computer readable program code stored thereon that, when executed, performs a method, the method comprising:
receiving a plurality of key values by the hardware accelerator;
storing each the plurality of keys into a location on a memory of the hardware accelerator;
creating a pointer to each of the locations of the plurality of keys;
storing the pointer to each of the plurality of keys into an initial position a first array stored by the hardware accelerator, wherein the initial position of each of the plurality of keys is determined based on a pairwise comparisons of the key values associated with adjacent locations in the memory of the hardware accelerator;
sorting the plurality of keys by performing a pairwise comparison of the key values associated the pointers having adjacent initial positions in the first array and by storing the pointers of the loser of the pairwise comparison in a second array, wherein the sorting identifies a winning key from the plurality of keys in the memory, wherein a size of the second array is one quarter of a size of the first array to prevent corrupting the pointers to the plurality of keys being sorted; and
outputting the winning key.

12. The computer program product of claim 11 , wherein the hardware accelerator is a field programmable gate array (FPGA) or an application-specific integrated circuit (ASIC).

13. The computer program product of claim 11 , wherein sorting the plurality of keys includes performing a speculative comparison of two of the plurality of keys.

14. The computer program product of claim 13 , wherein the plurality of keys includes N keys and wherein the sorting identifies a subsequent winning key from the plurality of keys after every log N clock cycles.

15. The computer program product of claim 11 , wherein the winning key corresponds to the key with a highest key value.

16. The computer program product of claim 11 , wherein the winning key corresponds to the key with a lowest key value.

17. The computer program product of claim 11 , wherein storing the pointer to each of the plurality of keys into the first array on the hardware accelerator includes determining a location in the first array based on the key value.

18. The computer program product of claim 11 , wherein reordering the pointers in the first array includes storing a winner of the pairwise comparison of the key values associated the pointers having adjacent initial positions in the first array in the second array.

Assignees

• IBM

Inventors

• Asaad Sameh W
• Min Hong
• Sukhwani Bharat
• Thoennes Mathew S

Classifications

• G06F7/24 Primary

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F17/30327 Primary

  Physics · mapped topic