Adaptive Space-efficient Collectives for Dynamic and Unstructured Sparsity on GPU Platforms
2026-07-06 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors focus on improving communication methods used in big computer tasks like high-performance computing and machine learning when the data contains lots of zeros (sparse data). They note that current top tools work well only with dense (mostly non-zero) data and have trouble efficiently handling sparse data. To fix this, they created new algorithms and a special data format called Pici that compresses sparse data quickly and changes its form based on how many zeros it has. Their approach speeds up key communication steps significantly compared to existing tools when data is very sparse.
collective communicationhigh-performance computingmachine learningsparse datadata compressionall-gatherreduce-scatterall-reduceNCCLbitvector
Authors
Lannie Dalton Hough, Emir Gencer, Hoffmann Muki, Abhinav Bhatele
Abstract
High-performance collective communication primitives are necessary for a variety of high performance computing (HPC) and machine learning (ML) workloads. State-of-the-art collective communication libraries such as NCCL optimize exclusively for dense data. However, when sending sparse data, we can reduce communication volume by not sending zeros. Unfortunately, explicitly handling sparsity introduces challenges such as format conversion overheads and densification during collectives that involve reductions. In this paper, we introduce sparsity-exploiting algorithms for three collectives that address these challenges: all-gather, reduce-scatter, and all-reduce. Our collective implementations are backed by a new bitvector-based format, Pici, designed for low overhead and fast (de)compression at moderate sparsities. Further, our algorithms adapt to the level of sparsity in data, modifying its representation during the course of the collective. At 99% input sparsity, our collectives achieve up to 5.25x, 2.5x, and 2.66x speedups over NCCL for all-gather, reduce-scatter, and all-reduce, respectively.