TLDR: Bine Trees are a new family of algorithms for high-performance computing (HPC) collective operations that significantly improve communication efficiency. By intelligently arranging communication partners using a negabinary approach, Bine trees reduce traffic on global network links by up to 33% and achieve up to 5x speedups on large-scale supercomputers with diverse network topologies, making collective operations more scalable and performant without requiring topology-specific knowledge.
High-performance computing (HPC) systems are constantly growing, and with their expansion, efficient communication between different parts of these massive systems becomes incredibly important. One of the biggest challenges in these large-scale networks is “communication locality,” which essentially means how close communicating nodes are to each other. When nodes that are far apart need to talk, it often involves sending data over “global links,” which are slower and more prone to congestion, especially in networks that are “oversubscribed” (meaning they have more potential traffic than they can handle at full speed).
A new research paper introduces an innovative solution to this problem called Bine Trees (short for binomial negabinary trees). These are a new family of algorithms designed to make collective operations – common tasks where many nodes work together, like sharing data or summing values – much more efficient by optimizing how and where data is communicated. The paper, titled “Bine Trees: Enhancing Collective Operations by Optimizing Communication Locality,” was authored by Daniele De Sensi, Saverio Pasqualoni, Lorenzo Piarulli, Tommaso Bonato, Seydou Ba, Matteo Turisini, Jens Domke, and Torsten Hoefler. You can find the full research paper here: Bine Trees Research Paper.
Understanding the Problem: Communication Locality
Imagine a large city with many neighborhoods. Communication within a neighborhood is fast, but sending a message across the city through main highways can be slow due to traffic. HPC networks are similar. Nodes within a local group can communicate quickly, but communication between different groups often has to go through shared, global links. These global links are typically longer, have higher latency, and can easily become congested, leading to slower performance and increased energy consumption. Existing collective algorithms, like standard binomial trees, don’t always prioritize keeping communication local, leading to unnecessary traffic on these critical global links.
Introducing Bine Trees: A Smarter Way to Communicate
Bine trees offer a novel way to construct communication patterns that are “topology-agnostic,” meaning they don’t need specific knowledge of the network layout, yet they inherently improve communication locality. The core idea is to arrange communicating nodes in a way that minimizes the “distance” between them. While standard binomial trees might send data to a node that is numerically distant, Bine trees use a clever mathematical trick called “negabinary representation” to ensure that communication partners are as “close” as possible, even when considering a circular arrangement of nodes.
This approach significantly reduces the volume of data that needs to traverse the slower global links. The researchers found that Bine trees can cut global-link traffic by up to 33% compared to standard binomial trees. This reduction is crucial for improving performance and scalability in modern supercomputers.
Real-World Performance Gains
The researchers implemented eight different collective algorithms based on Bine trees, including common operations like allgather, allreduce, broadcast, and scatter. They then rigorously tested these algorithms on four of the world’s largest supercomputers: LUMI (Dragonfly network), Leonardo (Dragonfly+ network), MareNostrum 5 (oversubscribed fat-tree), and Fugaku (torus topology). These systems represent a diverse range of network architectures, providing a comprehensive evaluation.
The results were impressive. Bine trees consistently outperformed state-of-the-art algorithms, achieving speedups of up to 5 times in some scenarios. For instance, on LUMI and MareNostrum 5, performance improved by up to 80%, on Leonardo by up to 50%, and on Fugaku, the gains were as high as 5 times. These improvements were observed across various data sizes and node counts, demonstrating the broad effectiveness of Bine trees.
Even when compared against highly optimized vendor-specific implementations, such as those on Fugaku’s torus network, Bine trees remained competitive, and often superior, especially for larger data sizes where reducing traffic on oversubscribed links is most beneficial. The paper also explored the impact of multiple processes per node and multi-GPU setups, showing that Bine trees can further enhance performance in these complex environments, even outperforming NVIDIA’s NCCL library in some GPU-aware allreduce tests.
Also Read:
- Scaling Large Language Model Inference on HPC Clusters with SLURM
- HyperFlexis: Optimizing LLM Serving for Diverse Performance Needs
A Step Towards More Efficient HPC
The main strength of Bine trees lies in their versatility and simplicity. They offer the generality of traditional binomial trees and butterflies but with an inherent optimization for communication locality. This means they can be easily adopted without needing complex knowledge of the underlying network topology or how jobs are allocated. By reducing network traffic and improving communication efficiency, Bine trees represent a significant advancement for high-performance computing, paving the way for more scalable and flexible collective algorithms in the future.
