Parallelized in-place radix sorting
US10831738B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 22, 2017 |
| Grant date | Nov 10, 2020 |
| Priority date | — |
| Expiry date | Sep 22, 2038 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/285
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Apparatuses and 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. A plurality of data stripe sets is defined that has one stripe within each respective bucket. A first and a second in-place partial bucket radix sort are performed on data items contained within the first and second data stripe sets, respectively, using an initial radix. Incorrectly sorted data items in the first bucket are grouped by a first processor and incorrectly sorted data items in the second bucket are grouped by a second processor 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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.