# Bandwidth Optimal Pipeline Schedule for Collective Communication

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 29 May 2023.

## Builds on (most cited first, 3 of 3)

- [TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches](https://mlsanity.com/paper/2111.04867/) (2021)
- [Blink: Fast and Generic Collectives for Distributed ML](https://mlsanity.com/paper/1910.04940/) (2019)
- [Collective phototactic robotectonics](https://mlsanity.com/paper/2208.12373/) (2022)

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

- [Rail-only: A Low-Cost High-Performance Network for Training LLMs with Trillion Parameters](https://mlsanity.com/paper/2307.12169/) (2023)

## Abstract (arXiv)

We present a strongly polynomial-time algorithm to generate bandwidth optimal allgather/reduce-scatter on any network topology, with or without switches. Our algorithm constructs pipeline schedules achieving provably the best possible bandwidth performance on a given topology. To provide a universal solution, we model the network topology as a directed graph with heterogeneous link capacities and switches directly as vertices in the graph representation. The algorithm is strongly polynomial-time with respect to the topology size. This work heavily relies on previous graph theory work on edge-disjoint spanning trees and edge splitting. While we focus on allgather, the methods in this paper can be easily extended to generate schedules for reduce, broadcast, reduce-scatter, and allreduce.