Effective MPI: User-defined Datatypes and Cartesian Communicators for Zero-copy All-to-all Communication in Multidimensional Tori

Jesper Larsson Träff · 2026

Read Effective MPI: User-defined Datatypes and Cartesian Communicators for Zero-copy All-to-all Communication in Multidimensional Tori by Jesper Larsson Träff (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29970.txt.

Introduction

Jesper Larsson Träff implements all-to-all communication on arbitrary multidimensional tori in MPI. Given a factorization matching a torus, a Cartesian communicator splits the set into per-dimension pieces per process, cached to dodge repeated splitting. The all-to-all itself runs as per-dimension all-to-all calls, with data rearrangement left implicit through derived datatypes. That makes the code formally zero-copy, with no explicit local reordering, plus double buffering with modest scratch needs. Tests show competitive speed against native all-to-all calls.

Catalog record

CREATORJesper Larsson Träff
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33690
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.29970

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Effective MPI: User-defined Datatypes and Cartesian Communicators for Zero-copy All-to-all Communication in Multidimensional Tori Jesper Larsson Träff Abstract We present and show how to implement a non-trivial all-to-all communication algorithm for arbitrary d d -dimensional tori effectively in MPI. Given a factorization of the number of processes p p into d d factors that can be mapped onto a d d -dimensional torus, we first utilize a Cartesian communicator to split a given p p -process MPI communicator into, for each MPI process, d d smaller communicators spanning each of the dimensions of the torus to which the process belongs, and cache these communicators in order to avoid expensive splitting at each all-to-all operation. The all-to-all operation itself is decomposed into a sequence of d d MPI_Alltoall operations on the dimension-wise communicators. The non-trivial data rearrangement before and after each MPI_Alltoall call is implicit only and effected by MPI derived datatypes. This makes the implementation of the algorithm formally zero-copy , meaning that no explicit process-local reordering of data blocks ever has to be performed. In order to achieve this, the algorithm employs a double-buffering scheme with modest temporary buffer requirements. By choosing the factorization of p p and selecting appropriate implementations for the component MPI_Alltoall operations, the presented implementation gives ample opportunities for algorithm tuning and adaptation to the particular high-performance system. A few, select experimental results show competitive performance with native MPI_Alltoall implementations and illustrate problems that common MPI_Alltoall implementations may have. 1 Introduction The all-to-all personalized communication problem, in which each process in a set of processes has an individual block of data (of some given number of elements) to each of the other processes, arises naturally in many important applications, but is also the most communication intensive and expensive collective data exchange problem. The operation should therefore be used judiciously, while at the same time efficient and well-implemented algorithms are needed. All-to-all communication is standardized in MPI as the regular MPI_Alltoall collective and the irregular MPI_Alltoallv and MPI_Alltoallw collectives [ 7 ] . We present a paradigm for potentially efficient implementations of the all-to-all operation in terms of smaller component all-to-all operations, which shows how such a collective operation can be expressed in terms of more specialized uses of the same collective operation. Such a decomposition is possible with MPI functionality and highlights how MPI can be used effectively to efficiently implement non-trivial algorithms. Such implementations of MPI functionality in terms of other MPI functionality naturally poses upper bounds on the concrete performance of, in the case here, the MPI_Alltoall collective in any given MPI library as so-called self-consistent performance guidelines [ 12 ] . Such performance guidelines can be automatically checked and strengthen ones confidence in the performance and quality of a given MPI library [ 5 ] . Essentially, a performance guideline states that for a given collective operation, there is no immediate better implementation in terms of MPI itself. We can view the all-to-all algorithm that we present here in three different ways. 1. As a dedicated algorithm for a torus communication network of any number of dimensions, in which communication is restricted to be between processes (or nodes of processes) that are neighbors along one of the dimensions in the torus. With d dimensions, the algorithm takes d communication rounds. 2. As an algorithm for the all-to-all problem for any given or desired factorization of the number of processes p . Viewed in this way, the algorithm can be adopted to the given communication network and partition by choice of factorization and choice of implementations for the all-to-all problems to be solved on the factors. With d factors, the algorithm takes d communication rounds. For a power of two number or processes, p=2^{d} , this is \log_{2}p , and the resulting algorithm can be seen as a natural generalization of well-known hypercube algorithms. 3. As message-combining performance guideline implementations of the all-to-all operation against which the MPI library native MPI_Alltoall function can be judged by comparative benchmarking [ 5 ] . All three viewpoints entail combining of blocks of elements from and to different processes. In each round different combinations of blocks are needed. We show how such composite blocks can be put together implicitly, at the corresponding component MPI_Alltoall call, by expressing the sequences of blocks as derived datatypes. The communicators for the component MPI_Alltoall operations are created in advance and cached so that the expensive creation of the needed subcommunicators can be amortized over many all-to-all operations. The paper has the didactic purpose of showing the effectiveness of MPI mechanisms (Cartesian communicators, communicator splitting, attribute caching and derived datatypes) for the implementation of non-toy examples. 2 Related Work Standard all-to-all algorithms for two- and three-dimensional meshes and hypercubes are explained in [ 4 ] , see also [ 9 ] and [ 1 ] for full-ported hypercubes. Message combining all-to-all algorithms like Bruck [ 2 ] , and for more general circulant graphs [ 11 ] , are well-known and used in many different forms, also in MPI libraries. Message-combining can reduce the number of communication rounds d down to the optimal d=\lceil\log_{2}p\rceil , but at an inherent cost of (re)sending roughly half the data blocks in each round [ 2 ] . An implementation of the Bruck algorithm using MPI derived datatypes to reorganize and pipeline data blocks was given in [ 17 ] . Multidimensional torus all-to-all algorithms with one-ported communication were presented and implemented in [ 18 , 19 , 10 ] , and elsewhere, and use links along only one dimension at a time. The simple d=2 algorithm for the BlueGene/L system in [ 20 ] attempts to use multiple links simultaneously. Two-level decompositions of the MPI_Alltoall operation, also relying on MPI derived datatypes were given in [ 16 , 13 ] ; in the latter the decomposition in particular follows the compute node structure of the given cluster and performs the all-to-all communication as concurrent intra-node all-to-all operations followed by concurrent inter-node all-to-all operations (or the other way round). The algorithm of this paper extends this implementation to arbitrary number of dimensions and deeper processor hierarchies. A somewhat similar algorithm, for two levels only, viewing the MPI all-to-all problem as a matrix transposition problem, was given in [ 3 ] . Our implementation precomputes and uses information stored with communicators to decide on the details of the algorithms to be executed. This viewpoint was discussed in more detail specifically for MPI in [ 14 ] . Some problems related to MPI_Dims_create that also appear in this paper were discussed and solved in [ 15 ] , see also [ 8 ] . 3 A d -dimensional Torus All-To-All Algorithm Assume that a p -process(or) communication structure (network, system, artifact), say a d -dimensional torus, is given and can be described as a Cartesian graph product M^{D}_{d}=G_{0}\Box\allowbreak G_{1}\Box\ldots\Box\allowbreak G_{d-1} with graph factors G_{i}=(V_{i},E_{i}) and p=\Pi_{i=0}^{d-1}D[i]=|V_{0}|\times|V_{1}|\times\ldots|V_{d-1}| . When M^{D}_{d} is a torus with dimension orders D[i],i=0,1,\ldots,d-1 , the factors G_{i} are ring communication structures, when M^{D}_{d} is a mesh, the factors are linear processor arrays; but the factors could be (isomorphic to) other graphs (like fully connected networks) as fitting to the actual hardware communication capabilities of

Read the complete text