Hardware implementation of a tournament tree sort algorithm
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.
1. A method of performing a tournament tree sort on a hardware accelerator, 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 a first array stored by 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 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 wherein the sorting identifies a winning key from the plurality of keys in the memory; and
outputting the winning key.
2. The method of claim 1 , wherein the hardware accelerator is a field programmable gate array (FPGA) or an application-specific integrated circuit (ASIC).
3. The method of claim 1 , wherein sorting the plurality of keys includes performing a speculative comparison of two of the plurality of keys.
4. The method of claim 3 , 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 method of claim 1 , wherein the winning key corresponds to the key with a highest key value.
6. The method of claim 1 , wherein the winning key corresponds to the key with a lowest key value.
7. The method 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.
8. The method 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.
9. A method of performing a tournament tree sort on a hardware accelerator, 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 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 wherein the sorting identifies a winning key from the plurality of keys in the memory; and
outputting the winning key.
10. The method of claim 9 , wherein the hardware accelerator is a field programmable gate array (FPGA) or an application-specific integrated circuit (ASIC).
11. The method of claim 9 , wherein sorting the plurality of keys includes performing a speculative comparison of two of the plurality of keys.
12. The method of claim 11 , 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.
13. The method of claim 9 , wherein the winning key corresponds to the key with a highest key value.
14. The method of claim 9 , wherein the winning key corresponds to the key with a lowest key value.
15. The method of claim 9 , 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.
16. The method of claim 9 , 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.