| 摘要 |
A method, apparatus, and system for improved high-performance parallel data sorting is provided. In a first phase, a plurality of unordered data elements to be sorted is divided into K unordered lists each preferably having approximately M elements. Each of these K unordered lists can be independently sorted in parallel using any algorithm, such as quicksort, to generate K ordered lists. In a second phase, N balanced workloads are determined from the K ordered lists by using an iterative converging process capped by a maximum number of iterations. Thus, any non-uniform or skewed data distribution can be load balanced with minimal processing time. Once the N balanced workloads are determined, they can be independently sorted in parallel, for example by using a merge sort, and then combined with a fast concatenation to provide the final sorted result. Thus, sorting operations are fully parallelized while avoiding any expensive data scanning steps. |
