Brief Announcement: Scalable Distributed String Sorting
Florian Kurpicz, Pascal Mehnert, Peter W. Sanders, Matthias Schimek · 2024
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.