Parallelized in-place radix sorting

Patent metadata

Field	Value
Publication number	US-9892149-B2
Application number	US-201514750363-A
Country	US
Kind code	B2
Filing date	Jun 25, 2015
Priority date	Jan 29, 2014
Publication date	Feb 13, 2018
Grant date	Feb 13, 2018

Abstract

Methods for sorting a data set. A data storage is divided into a plurality of buckets that is each associated with a respective key value. A plurality of stripes is identified in each bucket. At least one data stripe set is defined that has one stripe within each respective bucket. An in-place partial bucket radix sort is performed on data items contained within one data stripe set with a first processor using an initial radix. Incorrectly sorted data items are then grouped in each bucket into a respective incorrect data item group within each bucket. A radix sort is then performed using the initial radix on the items within the respective incorrect data item group. A first level sorted output is produced.

First claim

What is claimed is:

1. A method comprising:
dividing a plurality of data items stored in a data storage into a plurality of buckets, each bucket being associated with a respective key value;
identifying, within each bucket of the plurality of buckets, a respective plurality of stripes;
defining a plurality of data stripe sets, each data stripe set in the plurality of data stripe sets comprising one respective stripe within each respective bucket of the plurality of buckets, the plurality of data stripe sets comprising at least a first data stripe set and a second data stripe set that is separate from the first data stripe set;
performing, with a first processor, a first in-place partial bucket radix sort using an initial radix value on data items contained within the first data stripe set;
performing, with a second processor while performing the first in-place partial bucket radix sort, a second in-place partial bucket radix sort using the initial radix value on data items contained within the second data stripe set, the second processor being different from the first processor;
grouping, in each bucket after performing the first in-place partial bucket radix sort and the second in-place partial bucket radix sort, incorrectly sorted data items into a respective incorrect data item group within each bucket, the incorrectly sorted data items comprising data items within a first bucket but having a respective radix value associated with a different bucket;
performing a radix sort using the initial radix value on the items within the respective incorrect data item group; and
producing a first level sorted output comprising the plurality of data items within the data storage sorted according to the initial radix value.

2. The method of claim 1 ,
wherein the dividing comprises defining a plurality of data pointers into the data storage, each data pointer indicating a separation between two adjacent buckets, and
wherein the defining the plurality of data stripe sets comprises:
defining a respective stripe head pointer for each respective stripe, each respective stripe head pointer indicating a first element of each respective stripe; and
defining a respective stripe tail pointer for each respective stripe, each respective stripe tail pointer indicating a last element of each respective stripe.

3. The method of claim 1 , wherein each stripe in a particular data stripe set contains an equal number of data items.

4. The method of claim 1 , wherein at least one stripe within a data stripe set contains a first number of data elements unequal to a second number of data elements within stripes of the data stripe set that are other than the at least one stripe.

5. The method of claim 4 , wherein the first number of data elements and the second number of data elements are based upon value distribution characteristics of the plurality of data items.

6. The method of claim 1 , further comprising:
dividing, subsequent to performing the radix sort using the initial radix value on the items within the respective incorrect data item group, at least one bucket within the plurality of buckets into a plurality of second level buckets, each second level bucket being associated with a respective second level key value;
identifying, within at least one second level bucket, a plurality of respective second level stripes;
defining at least one second level data stripe set comprising one respective second level stripe within each second level bucket of a respective at least one bucket; and
performing, with the first processor, a partial bucket radix sort on the first level sorted output using a second level radix on data items contained within the at least one second level data stripe set.

7. The method of claim 6 , further comprising selecting the at least one second level bucket based upon a number of data elements in the at least one second level bucket relative to a number of data elements in other second level buckets within the plurality of buckets.

8. The method of claim 1 , wherein at least a portion of the first data stripe is stored a local cache memory of the first processor while the first processor performs the first in-place partial bucket radix sort, and
wherein at least a portion of the second data stripe is stored a local cache memory of the second processor while the second processor performs the second in-place partial bucket radix sort.

Assignees

• IBM

Inventors

• Bordawekar Rajesh
• Brand Daniel
• Cho Minsik
• Finkler Ulrich
• Puri Ruchir

Classifications

• G06F16/23 Primary

  Updating · CPC title

• G06F16/2237 Primary

  Vectors, bitmaps or matrices · CPC title

• G06F17/30445

  Physics · mapped topic

• G06F17/30324

  Physics · mapped topic

• G06F17/30345 Primary

  Physics · mapped topic