Skip to main content Link Search Menu Expand Document (external link)
Florian Kurpicz

Brief Announcement: Scalable Distributed String Sorting

DOI pdf code

Abstract

String sorting is an important part of tasks such as building index data structures. Unfortunately, current string sorting algorithms do not scale to massively parallel distributed-memory machines since they either have latency (at least) proportional to the number of processors p or communicate the data a large number of times (at least logarithmic). We present practical and efficient algorithms for distributed-memory string sorting that scale to large p. Similar to state-of-the-art sorters for atomic objects, the algorithms have latency of about p^{1/k} when allowing the data to be communicated k times. Experiments show good scaling behavior on a wide range of inputs on up to 49,152 cores. We achieve speedups of up to 5 over the current state-of-the-art distributed string sorting algorithms.

BibTeX 

@inproceedings{Kurpicz2024SPAA,
  author    = {Florian Kurpicz and Pascal Mehnert and Peter Sanders and Matthias Schimek},
  title     = {Brief Announcement: Scalable Distributed String Sorting},
  booktitle = {SPAA},
  pages     = {375--377},
  publisher = {ACM},
  doi       = {10.1145/3626183.3660256},
  year      = {2024}
}

PDF