Data-centric workloads with MPI_Sort

Patrick Zulian

doi:10.1016/j.jpdc.2023.104833

Data-centric workloads with MPI_Sort

2024-05-01

0

PRE

AI

DOI：10.1016/j.jpdc.2023.104833

Original

Original request for help

Save

Abstract

En 中文

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

Keywords:

Distributed sorting

Parallel algorithms

Supercomputers

Data-centric workloads with MPI_Sort

Abstract

Journal

Organization