Method and apparatus for partitioning and sorting a data set on a multi-processor system
US8140585B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 24, 2009 |
| Grant date | Mar 20, 2012 |
| Priority date | — |
| Expiry date | May 14, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/5066
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention provides a method and apparatus for partitioning, sorting a data set on a multi-processor system. Herein, the multi-processor system has at least one core processor and a plurality of accelerators. The method for partitioning a data set comprises: partitioning iteratively said data set into a plurality of buckets corresponding to different data ranges by using said plurality of accelerators in parallel, wherein each of the plurality of buckets could be stored in local storage of said plurality of accelerators; wherein in each iteration, the method comprises: roughly partitioning said data set into a plurality of large buckets; obtaining parameters of said data set that can indicate the distribution of data values in that data set; determining a plurality of data ranges for said data set based on said parameters; and partitioning said plurality of large buckets into a plurality of small buckets corresponding to the plurality of data ranges respectively by using said plurality of accelerators in parallel, wherein each of said plurality of accelerators, for each element in the large bucket it is partitioning, determines a data range to which that element belongs …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.