2022/04/10 by Wentao Yang, Yang, Wentao, Vipul Harsh +3
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Distributed #F.2.2 #FOS: Computer and information sciences #Machine Learning and Algorithms #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2204.04599
openalex publication_date 2022/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
State-of-the-art parallel sorting algorithms for distributed-memory architectures are based on computing a balanced partitioning via sampling and histogramming. By finding samples that partition the sorted keys into evenly-sized chunks, these algorithms minimize the number of communication rounds required. Histogramming (computing positions of samples) guides sampling, enabling a decrease in the overall number of samples collected. We derive lower and upper bounds on the number of sampling/histogramming rounds required to compute a balanced partitioning. We improve on prior results to demonstrate that when using p processors, O(log^* p) rounds with O(p/log^* p) samples per round suffice. We match that with a lower bound that shows that any algorithm with O(p) samples per round requires at least Ω(log^* p) rounds. Additionally, we prove the Ω(p log p) samples lower bound for one round, thus proving that existing one round algorithms: sample sort, AMS sort and HSS have optimal sample size complexity. To derive the lower bound, we propose a hard randomized input distribution and apply classical results from the distribution theory of runs.