Tunable hardware sort engine for performing composite sorting algorithms

Patent metadata

Field	Value
Publication number	US-2016110390-A1
Application number	US-201514977832-A
Country	US
Kind code	A1
Filing date	Dec 22, 2015
Priority date	Aug 7, 2013
Publication date	Apr 21, 2016
Grant date	—

Abstract

Embodiments include methods, systems and computer program products for performing a composite sort on a tunable hardware sort engine includes determining desired sort performance parameters, configuring a composite sort engine based on the desired sort performance parameters, and receiving a plurality of keys having a payload associated with each of the plurality of keys. The method also includes reserving DRAM storage for each of the payloads, generating a tag for each of the plurality of keys, the tag identifying the DRAM storage reserved for each of the payloads, and storing the payloads in the portions of the DRAM storage. The method further includes generating a composite key for each of the plurality of keys, sorting the composite keys by the composite sort engine, and retrieving the payloads associated with the sorted composite keys from the DRAM storage. The method also includes outputting the payloads associated the sorted composite keys.

First claim

What is claimed is:

1 . A method for performing a composite sort on a tunable hardware sort engine comprises:
determining one or more desired sort performance parameters; configuring a composite sort engine of the tunable hardware sort engine based on the one or more desired sort performance parameters; receiving, by the tunable hardware sort engine, a plurality of keys having a payload associated with each of the plurality of keys; generating a tag for each of the plurality of keys, the tag identifying a portion of a DRAM storage reserved for each of the payloads; storing the payloads in a DRAM storage; generating a composite key for each of the plurality of keys; sorting the composite keys by the composite sort engine; retrieving the payloads associated with the sorted composite keys from the DRAM storage; and outputting the payloads associated the sorted composite keys.

2 . The method of claim 1 , wherein the composite key generated for each of the plurality of keys consists of the tag generated for each of the plurality of keys and a value associated with each of the plurality of keys.

3 . The method of claim 1 , wherein sorting the composite keys by the composite sort engine comprises distributing each of the composite keys to one of a plurality of sorting engines and merging the output of the plurality of sorting engines.

4 . The method of claim 3 , wherein a quantity and a type of the plurality of sorting engines is selected based on the one or more desired sort performance parameters.

5 . The method of claim 4 , wherein the one or more desired sort performance parameters include at least one of the following: a number of keys in a sorted run; a consumption rate of arriving keys; an available chip area; and a rate of producing sorted keys.

6 . The method of claim 4 , wherein the type of the sorting engines is a tournament tree sort.

7 . The method of claim 1 , wherein the tag consists of a starting address of a location of the DRAM storage and a size of the payload.

Assignees

• IBM

Inventors

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

Classifications

• G06F17/30312 Primary

  Physics · mapped topic

• G06F7/22

  Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc · CPC title

• G06F17/30495

  Physics · mapped topic

• G06F16/22 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/24558

  Binary matching operations · CPC title