# Sparbit: a new logarithmic-cost and data locality-aware MPI Allgather algorithm

arXiv: https://arxiv.org/abs/2109.08751 · HTML: https://mlsanity.com/paper/2109.08751/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2021.

## Built on by (most cited first, 1 of 1)

- [Bine Trees: Enhancing Collective Operations by Optimizing Communication Locality](https://mlsanity.com/paper/2508.17311/) (2025)

## Abstract (arXiv)

The collective operations are considered critical for improving the performance of exascale-ready and high-performance computing applications. On this paper we focus on the Message-Passing Interface (MPI) Allgather many to many collective, which is amongst the most called and time-consuming operations. Each MPI algorithm for this call suffers from different operational and performance limitations, that might include only working for restricted cases, requiring linear amounts of communication steps with the growth in number of processes, memory copies and shifts to assure correct data organization, and non-local data exchange patterns, most of which negatively contribute to the total operation time. All these characteristics create an environment where there is no algorithm which is the best for all cases and this consequently implies that careful choices of alternatives must be made to execute the call. Considering such aspects, we propose the Stripe Parallel Binomial Trees (Sparbit) algorithm, which has optimal latency and bandwidth time costs with no usage restrictions. It also maintains a much more local communication pattern that minimizes the delays due to long range exchanges, allowing the extraction of more performance from current systems when compared with asymptotically equivalent alternatives. On its best scenario, Sparbit surpassed the traditional MPI algorithms on 46.43% of test cases with mean (median) improvements of 34.7% (26.16%) and highest reaching 84.16%.