Data-centric workloads with MPI_Sort

• Published in: Journal of parallel and distributed computing 2024-05, Vol.187, p.104833, Article 104833
• Main Authors: Zulian, P., Ben Bader, S., Fourestey, G., Krause, R., Rossinelli, D.
• Format: Article
• Language: English
• Subjects: Distributed sorting; Parallel algorithms; Supercomputers
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2023.104833

Sorting is a fundamental task in computing and plays a central role in information technology. The advent of rack-scale and warehouse-size data processing shaped the architecture of data analysis platforms towards supercomputing. In turn, established techniques on supercomputers have become relevant to a wider range of application domains. This work is concerned with multi-way mergesort with exact splitting on distributed memory architectures. At its core, our approach leverages a novel and parallel algorithm for multi-way selection problems. Remarkably concise, the algorithm relies on MPI_Allgather and MPI_ReduceScatter_block, two collective communication schemes that find hardware support in most high-end networks. A software implementation of our approach is used to process the Terabyte-size Data Challenge 2 signal, released by the SKA radio telescopes organization. On the supercomputer considered herein, our approach outperforms the state of the art by up to 2.6X using 9,216 cores. Our implementation is released as a compact open source library compliant to the MPI programming model. By supporting the most popular elementary key types, and arbitrary fixed-size value types, the library can be straightforwardly integrated into third-party MPI-based software. •Novel distributed multi-way selection algorithm.•Novel approach to multiway merge sort with exact splitters, on supercomputers.•GPU-friendly algorithms.•Outperforming factors up to 2.6X against the state of the art, on a supercomputer featuring about 10,000 cores.•Release of a concise, distributed sorting library compliant to the MPI programming model.