Brief Announcement: Scalable Distributed String Sorting
Open Access
- 17 June 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 375-377
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 p1/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.Keywords
Funding Information
- Gauss Centre for Supercomputing
- European Research Council (882500)
This publication has 12 references indexed in Scilit:
- Brief Announcement: Scalable Distributed String Sorting2024
- KaMPIng: Flexible and (Near) Zero-overhead C++ Bindings for MPIarXiv, 2024
- Communication-Efficient String Sorting2020
- Lightweight Distributed Suffix Array Construction2019
- Robust Massively Parallel Sorting2017
- Practical Massively Parallel Sorting2015
- Communication efficient algorithms for fundamental big data problems2013
- Merging String Sequences by Longest Common PrefixesIPSJ Digital Courier, 2008
- Linear work suffix array constructionJournal of the ACM, 2006
- Optimal parallel string algorithms1994