# Bine Trees: Enhancing Collective Operations by Optimizing Communication Locality

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 55 references that are in the map.
- First posted on arXiv 24 Aug 2025.

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

- [Synthesizing Optimal Collective Algorithms](https://mlsanity.com/paper/2008.08708/) (2020)
- [An In-Depth Analysis of the Slingshot Interconnect](https://mlsanity.com/paper/2008.08886/) (2020)
- [LEONARDO: A Pan-European Pre-Exascale Supercomputer for HPC and AI Applications](https://mlsanity.com/paper/2307.16885/) (2023)
- [HammingMesh: A Network Topology for Large-Scale Deep Learning](https://mlsanity.com/paper/2209.01346/) (2022)
- [Swing: Short-cutting Rings for Higher Bandwidth Allreduce](https://mlsanity.com/paper/2401.09356/) (2024)
- [HiCCL: A Hierarchical Collective Communication Library](https://mlsanity.com/paper/2408.05962/) (2024)
- [Mitigating Network Noise on Dragonfly Networks through Application-Aware Routing](https://mlsanity.com/paper/1909.07865/) (2019)
- [Introducing MareNostrum5: A European pre-exascale energy-efficient system designed to serve a broad spectrum of scientific workloads](https://mlsanity.com/paper/2503.09917/) (2025)
- [Sparbit: a new logarithmic-cost and data locality-aware MPI Allgather algorithm](https://mlsanity.com/paper/2109.08751/) (2021)
- [A Locality-Aware Bruck Allgather](https://mlsanity.com/paper/2206.03564/) (2022)
- [A High-Performance Design, Implementation, Deployment, and Evaluation of The Slim Fly Network](https://mlsanity.com/paper/2310.03742/) (2023)
- [Modeling and Analysis of Application Interference on Dragonfly+](https://mlsanity.com/paper/2406.15097/) (2024)
- [PICO: Performance Insights for Collective Operations](https://mlsanity.com/paper/2508.16809/) (2025)

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

- [Maia 200: A Software Defined Dataflow System for Large-scale AI Acceleration](https://mlsanity.com/paper/2608.24664/) (2026)

## Abstract (arXiv)

Communication locality plays a key role in the performance of collective operations on large HPC systems, especially on oversubscribed networks where groups of nodes are fully connected internally but sparsely linked through global connections. We present Bine (binomial negabinary) trees, a family of collective algorithms that improve communication locality. Bine trees maintain the generality of binomial trees and butterflies while cutting global-link traffic by up to 33%. We implement eight Bine-based collectives and evaluate them on four large-scale supercomputers with Dragonfly, Dragonfly+, oversubscribed fat-tree, and torus topologies, achieving up to 5x speedups and consistent reductions in global-link traffic across different vector sizes and node counts.