Optimal Round and Sample-Size Complexity for Partitioning in Parallel Sorting

Wentao Yang, Vipul Harsh, Edgar Solomonik

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 [2] and HSS [16] 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.

Original languageEnglish (US)
Title of host publicationSPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages467-478
Number of pages12
ISBN (Electronic)9781450395458
DOIs
StatePublished - Jun 17 2023
Externally publishedYes
Event35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023 - Orlando, United States
Duration: Jun 17 2023Jun 19 2023

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023
Country/TerritoryUnited States
CityOrlando
Period6/17/236/19/23

Keywords

  • communication cost
  • communication lower bounds
  • parallel algorithms
  • parallel sorting

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Optimal Round and Sample-Size Complexity for Partitioning in Parallel Sorting'. Together they form a unique fingerprint.

Cite this