Overlapping Communication and Computation to Hide Latency

49 concepts37 papers1 proposal

In distributed computing, performance is dictated by a fundamental tension: processors compute data in nanoseconds, but networks move data in milliseconds. As hardware accelerators grow exponentially faster, the interconnects linking them have failed to keep pace. Duanmu et al. describe this bottleneck as the "Bandwidth Wall" in modern large language model inference, where accelerators spend more time idling for data than executing arithmetic operations.

Historically, distributed algorithms have been structured in discrete, alternating phases: a computation phase followed by a communication phase. However, Ding et al. note that this strict separation acts as a heavy tax, forcing processors to sit completely idle during data redistribution. To maximize throughput, modern distributed systems must transition to a paradigm of communication-computation overlap. By interleaving data transfers with active processing, the time spent waiting on the network can be completely masked behind useful hardware cycles.

Traditional Sequential Execution:
[  Compute Tile 1  ][  Compute Tile 2  ][ Transfer 1 ][ Transfer 2 ]
                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^ Idle Compute Time

Overlapped Pipelined Execution:
[  Compute Tile 1  ][  Compute Tile 2  ]
                    [   Transfer 1     ][   Transfer 2     ]
                    ^^^^^^^^^^^^^^^^^^^^ Latency Hidden!

Tiling and Pipelining

The most intuitive way to hide latency is to break monolithic operations into smaller, independent units of work. Instead of processing an entire dataset and then transmitting the result, systems can use a tiling strategy to pipeline execution.

As soon as a single tile finishes computing, its data transfer is initiated asynchronously. While that tile travels across the network, the processor immediately begins working on the next tile. Ye et al. demonstrate the power of this approach in edge-based Transformer inference, where partitioning massive matrix operations into fine-grained tiles allows home networks with limited bandwidth to sustain high throughput.

This pipelining mechanism is highly effective across diverse domains:

  • Graph Processing: Chen et al. apply pipelined communication to massive subgraph counting, ensuring that distributed nodes remain fully utilized while waiting for graph chunks to arrive.
  • Bioinformatics: In genome assembly, Wright et al. greedily schedule tasks so that completed high-$k$ de Bruijn graphs are transmitted across nodes while low-$k$ graphs are still actively being processed.

Domain Decomposition and Non-Blocking Primitives

For spatial workloads, such as physical simulations or convolutional neural networks, communication patterns are dictated by geometric boundaries. When a grid is split across multiple GPUs, each processor needs data from its neighbor's edge—often called the "halo" or "ghost zone"—before it can proceed to the next step.

If an algorithm updates the entire grid before communicating, it stalls. To prevent this, Cao et al. leverage non-blocking communication protocols to split the computation into two distinct regions:

  1. Boundary Regions: The cells along the edge of a node's domain are computed first.
  2. Internal Regions: As soon as the boundary data is ready, a non-blocking network transfer is fired off. While that boundary data is in transit, the processor immediately transitions to updating the internal domain cells, which have no external dependencies.

By the time the internal updates finish, the boundary data has arrived from the network, hiding the communication latency entirely. Conversely, when these operations are kept separate, systems suffer severe performance penalties. Jin et al. and Azad et al. both observe that fusing kernel execution with data transfers is a critical requirement for scaling sparse matrix operations and spatially parallel convolutions. Similarly, Selvitopi et al. show that this pipelining can bridge heterogeneous boundaries, overlapping heavy GPU-based matrix calculations with CPU-managed network synchronization.

Intelligent Scheduling and Background Progress

Achieving optimal overlap requires orchestrating when tasks execute relative to when data moves. If a task is scheduled before its dependent data arrives, the pipeline stalls.

Guan et al. address this by using hypergraph-based task scheduling to order operations based on their file-sharing patterns, maximizing the mathematical probability of overlap. For Multiprocessor Systems-on-Chip (MPSoCs), Jiang et al. integrate communication pipelining directly into the scheduling logic, treating data transfer as a first-class execution constraint rather than an afterthought.

However, network protocols are not free; they require CPU cycles to handle events, manage message handshakes, and copy memory buffers. If the main application thread has to pause its calculations to manage a network event, the benefit of asynchronous communication is lost.

To solve this, Trahay demonstrates that systems can offload communication progress tasks—such as network event handling and message rendezvous processing—to idle CPU cores. This allows the main application threads to compute uninterrupted while background cores quietly advance the network state.

Without Background Progress Cores:
Main Thread: [ Compute Tile 1 ][ Handle Network ][ Compute Tile 2 ]
                               ^^^^^^^^^^^^^^^^^^ Stalled Compute

With Background Progress Cores:
Main Thread: [ Compute Tile 1 ][ Compute Tile 2 ]
Core 2 (BG):                   [ Handle Network ]
                               ^^^^^^^^^^^^^^^^^^ Handled in Background

Hiding Costs via Auxiliary Tasks and Redundant Compute

When a system cannot perfectly align its primary computation with data transfers, it can fill the idle time with auxiliary operations, or alter the computation itself to bypass the network.

Co-Optimizing Auxiliary Tasks

Instead of treating communication as dead time, systems can inject necessary overhead tasks into the communication window. For example, Huang et al. introduce a framework that meticulously overlaps error-bounded lossy compression, decompression, and kernel launching directly with data transfers, maximizing GPU throughput. In fault-tolerant computing, Liang et al. execute online soft-error detection logic during periods of data transposition and inter-node communication, achieving hardware resilience without increasing the application's total runtime.

Trading Computation for Communication

Sometimes, the fastest way to hide communication latency is to avoid it altogether by performing redundant work. Asquini et al. demonstrate this in Processing-in-Memory (PIM) architectures, where isolated cores perform overlapping, redundant calculations and apply a mathematical correction later, bypassing expensive inter-core synchronization. In task scheduling, Maiti et al. prove mathematically that strategically duplicating jobs across multiple processors masks communication delays, significantly reducing overall execution makespan.

The Path to Automation

Despite the clear performance benefits of communication-computation overlap, implementing it manually remains incredibly difficult. Developers must carefully balance tile sizes, manage asynchronous pointers, and avoid race conditions.

Lockhart et al. point out that traditional performance models often isolate communication costs from the broader application context, failing to accurately predict how well an application will hide latency in production. To bridge this gap, Yoo et al. emphasize the need for standardized execution trace representations. By capturing both deep learning workloads and collective communication algorithms in a unified graph, the industry can pave the way for automated compilers and schedulers to discover and exploit overlap opportunities automatically.


Referenced Papers

Key Foundational Work

Transposition Table Driven Work Scheduling in Distributed Search (1999) — contributed 1 concept elements to this direction.
Design of Multithreaded Estimation of Distribution Algorithms (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_communication_computation_overlap_latenc_ad50cf5c,
  title = {communication-computation overlap (latency hiding)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/communication-computation-overlap-latency-hiding/rdr_ad50cf5c1c204789b2086e67f0b27477},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_communication_computation_overlap_latenc_ad50cf5c_v1,
  title = {communication-computation overlap (latency hiding)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/communication-computation-overlap-latency-hiding/rdr_ad50cf5c1c204789b2086e67f0b27477/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake