大数据 (Jul 2024)
A scalable parallel sorting algorithm by regular sampling for big data
Abstract
Sorting is one of the basic algorithms in computer science, and has been extensively used in a variety of applications.In the big data era, as the volumes of data increase rapidly, parallel sorting has attracted much attention.Existing parallel sorting algorithms suffered from excessive communication overhead and load imbalance, making it difficult to scale massively.To solve above problems, a scalable parallel algorithm sorting by regular sampling (ScaPSRS) was proposed, which sampled the p-1 pivot elements to divide the entire data set into p disjoint subsets by all parallel processes, rather than by only one given process as PSRS did.Furthermore, ScaPSRS adopted a novel iterative update strategy of selecting pivots to guarantee that the workloads and data were evenly scheduled among the parallel processes, thus ensuring superior overall performance.A variety of experiments conducted on the Tianhe-Ⅱ supercomputer demonstrated that ScaPSRS succeeded in scaling to 32 000 cores and outperformed state-of-the-art works significantly.
