Method and apparatus for partitioning and sorting the data sets on a multi-processor system

摘要

PROBLEM TO BE SOLVED: To provide a method and apparatus for partitioning and sorting a data set on a multiprocessor system.;SOLUTION: The method for partitioning a data set comprises: partitioning iteratively a data set into a plurality of buckets corresponding to different data ranges by using a plurality of accelerators in parallel, wherein each of the plurality of buckets could be stored in a local storage of the plurality of accelerators; wherein in each iteration, the method comprises: roughly partitioning the data set into a plurality of large buckets; determining a plurality of data ranges for the data set based on parameters of the data set that can indicate the distribution of data values in that data set; and partitioning the plurality of large buckets into a plurality of small buckets corresponding to the plurality of data ranges respectively by using the plurality of accelerators in parallel, wherein each of the plurality of accelerators, for each element in the large bucket it is partitioning, determines a data range to which that element belongs among the plurality of data ranges by computation.;COPYRIGHT: (C)2010,JPO&INPIT