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

Patent metadata

Field	Value
Publication number	US-2016188644-A1
Application number	US-201514741490-A
Country	US
Kind code	A1
Filing date	Jun 17, 2015
Priority date	Dec 29, 2014
Publication date	Jun 30, 2016
Grant date	—

Abstract

Embodiments include methods, systems and computer program products for performing a tournament tree sort on a hardware accelerator having an external memory. The method includes receiving a plurality of key values by the hardware accelerator, assigning each of the plurality of key values a sequential key number as the plurality of key values are received and performing pairwise comparisons of each of the plurality of key values to identify a winning key and a losing key. The method also includes storing the losing key of each pairwise comparison in a first section of the external memory, wherein a location in the first section is based on the key number of the losing key and storing the winning key of each pairwise comparison in a second section of the external memory, wherein a location in the second section is based on the key number of the winning key.

First claim

What is claimed is:

1 . A method of performing a tournament tree sort on a hardware accelerator having an external memory, comprising:
receiving a plurality of key values by the hardware accelerator; assigning each of the plurality of key values a sequential key number as the plurality of key values are received; performing pairwise comparisons of each of the plurality of key values to identify a winning key and a losing key; storing the losing key of each pairwise comparison in a first section of the external memory, wherein a location in the first section is based on the key number of the losing key; and storing the winning key of each pairwise comparison in a second section of the external memory, wherein a location in the second section is based on the key number of the winning key.

2 . The method of claim 1 , further comprising:
performing a subsequent pairwise comparisons of the winning keys and storing each of the plurality of keys in locations in the external memory based on the results of the subsequent pairwise comparisons and the key number of the keys.

3 . The method of claim 1 , wherein the hardware accelerator includes an embedded memory configured to store one or more key values that are not stored in the external memory.

4 . The method of claim 2 , further comprising emitting a winning key.

5 . The method of claim 4 , further comprising:
receiving a new key; and setting the key number of the new key to the key number of the winning key previously emitted.

6 . The method of claim 5 , further comprising:
fetching one or more keys from the external memory for comparison to the new key.

7 . The method of claim 6 , wherein the location of the one or more keys fetched from the external memory is based on the key number of the new key.

Assignees

• IBM

Inventors

• Sukhwani Bharat
• Thoennes Mathew S

Classifications

• G06F17/30327 Primary

  Physics · mapped topic

• 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

• G06F17/30495

  Physics · mapped topic

• G06F16/24558

  Binary matching operations · CPC title