Source-linked AI summary
Blink: Fast and Generic Collectives for Distributed ML
Guanhua Wang, Shivaram Venkataraman, Amar Phanishayee, Jorgen Thelin, Nikhil Devanur, Ion Stoica
TL;DR
Large-scale data-parallel training is limited by parameter-synchronization overhead and communication libraries’ inability to use heterogeneous GPU topologies and links. Blink dynamically generates topology-specific collectives by packing spanning trees and exploiting heterogeneous channels, achieving up to 8× faster model synchronization and up to 40% lower end-to-end training time than NCCL.
Problem
Parameter synchronization can consume 50% to 90% of communication overhead, while existing protocols underutilize heterogeneous GPU topologies and links.
Method
Blink probes link availability, packs spanning trees to generate topology-specific collectives, minimizes tree count, and transfers data across PCIe and NVLink.
Results
Up to 8× faster model synchronization and up to 40% lower end-to-end DNN training time were achieved compared with NCCL2 and ring-based protocols.
Takeaways & Limitations
Blink provides a fast, generic collective communication library for distributed machine learning across heterogeneous GPU hardware.
Takeaways & Limitations
In commodity networks, low inter-server AllReduce throughput limits further gains because Blink cannot substantially reduce the cross-server communication stage.
Abstract
from arXiv · showhide
Model parameter synchronization across GPUs introduces high overheads for data-parallel training at scale. Existing parameter synchronization protocols cannot effectively leverage available network resources in the face of ever increasing hardware heterogeneity. To address this, we propose Blink, a collective communication library that dynamically generates optimal communication primitives by packing spanning trees. We propose techniques to minimize the number of trees generated and extend Blink to leverage heterogeneous communication channels for faster data transfers. Evaluations show that compared to the state-of-the-art (NCCL), Blink can achieve up to 8x faster model synchronization, and reduce end-to-end training time for image classification tasks by up to 40%.
1 Introduction
Distributed training requires multi-GPU parameter synchronization, but communication can consume 50%–90% of training time and remains bottlenecked by heterogeneous GPU topologies and links.
- 50% to 90% of training overhead can come from parameter synchronization communication for popular ML models.
- Modern communication libraries still underutilize inter-GPU links because they cannot fully mitigate topology heterogeneity.The paper identifies link under-utilization as the central hurdle for peak inter-GPU collective performance.
- Different DGX-1P and DGX-1V server configurations require topology-aware protocols to use their available hardware effectively.
- Ring-based collectives fail to exploit heterogeneous NVLink and PCIe links because throughput is limited by the lowest-bandwidth link.NCCL and Horovod use ring-based protocols; PCIe provides 8-12GB/s versus 20-25GB/s for NVLink.
- NCCL may fall back to PCIe when NVLink-only rings cannot be constructed, leaving NVLink capacity unused.Even when NVLink rings are possible, the paper reports additional link under-utilization for some allocations.
- Fragmented scheduler allocations can produce 3, 5, 6, or 7 GPUs within individual 8-GPU servers, creating irregular topologies.The finding comes from an analysis of over 40,000 multi-GPU jobs on Cloud-X over three months.
PCIe
Blink dynamically generates topology-specific collective implementations, using spanning trees, automatic chunking, and CUDA-stream pipelining to exploit heterogeneous links.
- Blink dynamically probes available links and generates communication primitives for each job’s topology.It builds a topology with appropriate link capacities at runtime.
- Packing spanning trees lets Blink utilize more links than ring-based protocols for collective communication.The paper applies a multiplicative-weight update approximation and minimizes the number of generated trees.
- Blink extends spanning-tree communication to Broadcast, Gather, and AllReduce while using bidirectional links and hardware capabilities.
- Generated code automatically chunks data and uses CUDA streams to pipeline transfers and computation.
- Blink provides an NCCL-compatible API and integrates with TensorFlow and PyTorch without user-program modifications.Integration relies on preloading through LD_PRELOAD.
- Up to 8× faster all-to-all collective communication and up to 40% shorter end-to-end training were observed relative to NCCL.On DGX-1V, Blink achieved up to 8× speed-up for AllReduce and reduced end-to-end training time by up to 40%.
2 Motivation
Communication overhead remains substantial because fixed ring-based collectives underuse heterogeneous GPU links and topologies. Blink addresses this by dynamically packing spanning trees and generating topology-specific primitives, with micro-benchmarks supporting the feasibility of deep, concurrent, reduction-capable transfers.
- Motivation: Communication can consume 50% to 90% of runtime in popular ML models, even on fast multi-GPU servers using modern libraries and optimizations.The motivation identifies communication as increasingly prominent as GPU computation accelerates and model sizes grow.
- The case for packing trees: Ring-based protocols underutilize heterogeneous links because each ring restricts every node to one input and one output, while throughput is limited by the lowest-bandwidth link.NCCL and Horovod therefore cannot fully exploit topologies combining NVLink and PCIe or partial GPU allocations.
- The case for packing trees: Packing spanning trees achieves maximum flow from a root to all other vertices, motivating spanning-tree protocols for broadcast and reduce-and-forward communication.AllReduce can be modeled as reduce-and-forward toward a root followed by broadcast away from it.
- Micro Benchmarks: For 1000MB transfers over chains, reduce+forward throughput decreases from around 21 GB/s to around 19 GB/s as chain length increases, while smaller datasets perform worse.Small data sizes are harder to usefully saturate because CUDA invocation overheads become significant.
- Micro Benchmarks: For datasets larger than 10MB, MIMO and MCA achieve around 18 GB/s, with MIMO about 15% below maximum NVLink Gen2 throughput and MCA roughly matching MIMO.These tests show support for concurrent transfers, aggregation, and forwarding on modern GPUs.
- Blink Approach: Blink probes the allocated GPUs’ topology, computes weighted spanning-tree packings, generates NCCL-compatible CUDA code, and loads it through LD_PRELOAD without program modification.Its approach targets topology-specific utilization while minimizing the number of generated trees.
3 Design
Blink models GPU communication as capacity-constrained directed graphs and packs spanning trees to achieve high-rate collective operations. It then reduces tree count, supports many-to-many collectives, and balances heterogeneous PCIe/NVLink transfers.
- 3.1 Packing Spanning Trees: Blink models GPUs as vertices and NVLink or PCIe connections as directed, bandwidth-capacity edges inferred from allocated resources.This topology model supports communication protocols tailored to heterogeneous hardware and partial GPU allocations.
- 3.1 Packing Spanning Trees: For broadcast, Blink maximizes the total weight of directed spanning trees while ensuring each edge’s capacity constraint is respected.Each arborescence originates at the root and spans every other GPU.
- 3.1 Packing Spanning Trees: Because enumerating all arborescences can be exponentially large, Blink uses multiplicative weight updates to obtain a (1− ε)-approximate packing in O(mlnm/ε^2).The procedure iteratively selects minimum-weight trees and updates graph weights.
- 3.2 Approximate Packing: Blink refines the approximate packing with an ILP and relaxes integer constraints until its feasible rate is within a configured threshold of the optimum.The candidate-tree set is much smaller than all graph spanning trees, making the refinement tractable.
- 3.2.1 Minimizing Number of Trees: 181 to 6 trees: on an 8-GPU DGX-1V topology, refinement equalizes tree rates and changes a 1000MB transfer from uneven 0.33–148MB chunks to 166MB per tree.Fewer, more evenly weighted trees improve the amount of data transferred through each tree and link utilization.
- 3.4 Handling hybrid communication: For hybrid PCIe/NVLink communication, Blink minimizes max(TPCIe,TNVL) by splitting data so the two transfer times are equal.The split uses measured peer-access-disable latency and the bandwidths of PCIe and NVLink trees.
4 Implementation
Blink’s implementation generates and executes weighted spanning-tree collectives with chunking and CUDA-stream pipelining. It adaptively selects chunk sizes and reuses streams to address hardware scheduling and link-sharing constraints.
- Blink parses weighted spanning trees, splits broadcast data across them, and uses CUDA copies, events, and per-link-per-tree streams for parallel transfers.
- Automatic chunk size selection: Chunk size balances pipelining and link utilization against the scheduling overhead of issuing at least three CUDA commands per chunk.Splitting data into two chunks reduced transfer time by one third in the cited four-GPU example.
- Automatic chunk size selection: Blink explores chunk sizes across initial iterations because the optimum depends on data size, tree count, and maximum tree depth.
- Automatic chunk size selection: MIAD increases chunk size multiplicatively while throughput rises and decreases it additively after throughput falls; a four-GPU broadcast stabilized after four iterations from a 1MB start with 2× increases.
- Link sharing: CUDA does not guarantee fair sharing when multiple trees use one link, so Blink reuses streams for similarly positioned links to preserve ordering.Uneven sharing can delay chunks, create forwarding gaps, and reduce effective throughput.
5 Evaluation
Blink is evaluated theoretically, through collective-throughput experiments on three GPU platforms, with hybrid transfers, and in end-to-end DNN training. Results show gains over NCCL, especially for irregular topologies, smaller DGX-2 messages, and single-server training.
- Theoretical comparison: Packing spanning trees is at least as fast as rings theoretically and can reach up to 6× speedup when rings traverse PCIe.The estimate may be higher in practice if PCIe performs worse than modeled, or lower because of chunking overheads.
- NVLink Broadcast: On DGX-1V, Blink achieves up to 6× Broadcast speedup over NCCL, with a 2× geometric mean across tested GPU-allocation topologies.NCCL loses throughput when it cannot form NVLink-only rings; Blink still gains 3–5 GB/s in some fully connected cases through optimized chunking.
- NVLink Broadcast: On DGX-1P, Blink achieves up to 3× Broadcast speedup over NCCL, with a 1.6× geometric mean across 14 topology configurations.
- NVLink AllReduce: Blink achieves up to 8× AllReduce throughput speedup over NCCL, with a 2× geometric mean, especially when NCCL cannot form NVLink rings or must drop links.
- DGX-2: On DGX-2, Blink’s single-hop trees provide up to 3.32× lower latency and 3.5× higher AllReduce throughput than NCCL for the evaluated setting.The advantage is reported for smaller data sizes, compared with NCCL’s double-binary trees and rings.
- Hybrid transfers: Hybrid NVLink-plus-PCIe broadcast adds 2–5 GB/s over NVLink-only transfers, but the gain falls from about 5 GB/s at 3–4 GPUs to about 2 GB/s at 7–8 GPUs.The channel-switching cost increases with the number of GPUs.
- End-to-end training: Blink reduces end-to-end DNN training iteration time by up to 40% and communication time by up to 87% on single-server ImageNet-1K training.The geometric means are 6.3% for iteration time and 31% for communication time; multi-server training improves by up to 11% over Horovod with NCCL/MPI.
- Multi-server training: As cross-machine bandwidth increases, Blink’s simulated end-to-end benefits become more pronounced until intra-server NVLinks become the bottleneck.
6 Related Work
Prior collective-communication work includes topology-fixed algorithms for regular or fixed networks and topology-aware methods that exploit hierarchy or locality. Blink targets dynamically changing, irregular topologies rather than assuming a fixed communication structure.
- Topology-fixed schemes: Earlier collective algorithms primarily optimize regular structures such as hypercubes, full meshes, and other topology-fixed networks.
- Topology-fixed schemes: Ring-based collectives are bandwidth-optimal in homogeneous networks but assume a fixed topology, limiting their fit for cloud environments where topology may change dynamically.
- Blink’s position: Blink is designed for irregular topologies and dynamically yields optimal communication solutions.
- Topology-aware protocols: Topology-aware protocols reduce transfers over slow links or use pairwise bandwidth measurements to exploit locality in wide-area, cloud, or NUMA settings.
7 Conclusion
Blink is a fast, generic collective communication library that accelerates distributed machine learning by dynamically packing spanning trees to maximize link utilization.
- Blink dynamically packs spanning trees to maximize link utilization across heterogeneous GPU topologies.
- Compared with NCCL2, Blink achieves up to 8× faster model synchronization.
- Blink reduces end-to-end DNN training time by up to 40%.
A.1 Micro Benchmarks (DGX-1V)
The microbenchmarks examine forwarding on chain and fan-in/fan-out topologies.
- The microbenchmarks highlight forwarding results on chain and fan-in/fan-out topologies.
A.1.1 Depth Test
The depth test varies tree depth using a chain topology and evaluates forward, reduce+forward, and reduce-broadcast traffic. Throughput generally declines with longer chains and smaller datasets.
- A.1.1 Depth Test: The depth test varies tree depth using a simple chain topology.
- A.1.1 Depth Test: The benchmark measures data forward, reduce+forward, and reduce-broadcast traffic patterns.
- A.1.1 Depth Test: Forward throughput decreases from around 22 GB/s with 3GPU to around 20 GB/s with 8 GPU for 1000MB data.
- A.1.1 Depth Test: Reduce+forward throughput remains around 18GB/s as chain length increases.
- A.1.1 Depth Test: Throughput drops with smaller datasets because fast links are harder to saturate and CUDA-operation overheads become more significant.
A.1.2 Breadth Test
The breadth test evaluates fan-in and fan-out forwarding and reduction across varying numbers of GPUs and data sizes. Forwarding approaches peak throughput for data sizes above 50MB, while reduction adds latency and large fan-in can exceed available memory.
- A.1.2 Breadth Test: The breadth test evaluates fan-in forward, fan-in reduce+forward, and fan-out forward topologies.
- A.1.2 Breadth Test: For DGX-1 systems, maximum fan-in and fan-out degrees are limited to three.
- A.1.2 Breadth Test: With data size >50MB, fan-in and fan-out forward achieve near maximum throughput.
- A.1.2 Breadth Test: Fan-in reduce+forward throughput decreases 1-2 GB/s on average because reduction-kernel launches add latency at the center node.
- A.1.2 Breadth Test: Running 1000MB with fan-in of 3 requires memory for each incoming link and exceeds available memory.
- A.1.2 Breadth Test: Fan-out forward throughput is close to peak link bandwidth.