Does communication mean email or human collaboration?

Here it means computer data movement and coordination, including transfers inside a single machine.

Can an algorithm do more arithmetic and still be faster?

Yes, if the saved communication time outweighs the additional arithmetic and other costs.

Is communication avoidance always numerically safe?

No. Stability depends on the reformulation, problem and parameters, so it must be checked rather than inferred from reduced traffic.

AI Glossary / Mathematics and optimization / Intermediate

Communication-avoiding algorithm

Definition

A communication-avoiding algorithm reorganizes computation to reduce costly data movement or communication events. Communication includes transfers between memory levels within one computer and exchanges between processors or machines. The goal is to improve total performance while preserving the required mathematical result or an explicitly acceptable accuracy level.

What it means

A processor may perform arithmetic quickly yet spend much of its time waiting for data. Adding more processors does not necessarily solve this: those processors can then spend more time exchanging information or synchronizing.

Communication-avoiding design treats those transfers as a central algorithmic cost. It may group operations, reuse data already nearby, replicate selected information or reformulate a sequence of updates. Sometimes extra arithmetic is worthwhile if it removes more expensive transfers. “Avoiding” normally means reducing communication relative to a comparison method, not eliminating every exchange.

How it works

First identify where data moves and where workers must wait. Distinguish latency, the overhead of initiating an exchange or synchronization, from bandwidth cost, which depends on the amount transferred. Main-memory traffic and network traffic may require different analyses.

Then rearrange the dependency structure so more useful computation occurs between transfers. Blocking can improve reuse in fast memory. Some iterative methods unroll several dependent updates into an equivalent formulation that communicates less frequently. The permitted group size depends on the mathematics, available memory and numerical stability.

Analyze arithmetic, bytes transferred and message counts separately. A method that reduces synchronizations can still increase total bytes or floating-point operations. Finally verify accuracy and measure end-to-end runtime on the intended hardware, because a favorable communication count alone does not establish a practical speedup.

Three practical examples

1. Matrix calculations: organize work into blocks that reuse a loaded data tile before replacing it, reducing slow-memory transfers when the layout and capacity permit.

2. Iterative linear solvers: use a suitable communication-avoiding formulation to perform several local mathematical steps between global exchanges, with stability checks appropriate to the variant.

3. Distributed learning: reorganize a supported optimization procedure, such as a particular logistic-regression update scheme, so it communicates less frequently without casually changing the intended iteration semantics.

Think of it this way

Think of a cook fetching ingredients from a distant store. Planning several dishes around ingredients already in the kitchen can save trips, even if it requires extra preparation or storage.

The analogy distinguishes trip overhead from the amount carried. It also has limits: computational updates may depend on freshly computed global information. You cannot simply postpone every exchange without changing the result. A valid reformulation must respect those dependencies.

Worked example

Consider an original simplified runtime model. A baseline requires 100 sequential iterations. Each performs 0.2 milliseconds of arithmetic and one communication event. Assume each event costs 1 millisecond of latency plus 0.1 milliseconds for its payload. Ignore overlap and other overheads.

Baseline time is 100×(0.2+1+0.1)=130 milliseconds. Now suppose a mathematically valid reformulation groups five iterations per event. There are 20 events. Each grouped event transfers five times the original payload, costing 0.5 milliseconds of bandwidth time. Additional local work increases total arithmetic from 20 to 30 milliseconds.

The redesigned time is 30+20×(1+0.5)=60 milliseconds. The illustrative speedup is 130/60, approximately 2.17. The total bandwidth time stays at 10 milliseconds, while latency falls from 100 to 20 milliseconds and arithmetic rises by 10 milliseconds.

If latency were only 0.01 milliseconds, the baseline would take 31 milliseconds and the redesign 40.2 milliseconds. It would be slower. These hand-checked numbers are invented to isolate the tradeoff; they are not measured results and do not prove that any specific algorithm permits the assumed grouping.

Illustrative case study

Fictional case: a data-science team finds that a distributed fitting job spends more time in repeated synchronizations than in local arithmetic. Engineers prototype a supported communication-avoiding variant and test several grouping sizes.

The largest grouping reduces message counts most, but it also raises memory use and worsens numerical behavior. A smaller grouping produces a better overall result on the team's system. The report includes accuracy, elapsed time and memory alongside communication counts, so a narrow improvement is not mistaken for a complete performance gain.

Common misconceptions and mistakes

Do not equate fewer messages with fewer bytes. Batching can reduce latency while enlarging payloads.

Do not assume this is the same as asynchronous execution. Asynchrony may overlap work and communication; communication avoidance changes how much or how often communication is needed. The techniques can interact but answer different questions.

Do not skip mathematically required exchanges and assume the original convergence proof still applies. Distinguish exact-arithmetic equivalence, floating-point behavior and approximate variants. Also separate measured speedups from theoretical bounds or predictions for hypothetical hardware.

Business use

This approach is relevant when profiling identifies data movement as a meaningful bottleneck in analytics, simulation or model training. It can reduce expensive waiting, but redesign and validation have costs of their own.

Evaluate it against a well-tuned baseline at the same accuracy target. Record problem size, data layout, number of workers, memory capacity and communication system. Monitor whether improvements persist across realistic workloads. A technique effective on a high-latency cluster may offer little benefit on a smaller machine where computation or storage access dominates.

Check your understanding

In the example, why does grouping five iterations not reduce total bandwidth time?

Answer: Each of the 20 messages carries five times as much data. The total payload remains equivalent to 100 original messages, while the number of latency overheads falls.

Related terms

Latency
Parallel computing
Synchronization
bandwidth
data locality
cache blocking
Krylov method
numerical stability

Learn next

profile a workload and separate arithmetic time, transfer volume and synchronization count. Build a simple latency-plus-bandwidth cost model, then test where additional local work becomes worthwhile under different hardware assumptions.

Sources

Sources: Devarakonda, “Avoiding Communication in First Order Methods for Optimization,” primary thesis abstract and tradeoffs read: https://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-92.html . Devarakonda and Demmel, “Avoiding Communication in Logistic Regression,” primary abstract read: https://arxiv.org/abs/2011.08281 . No published benchmark speedup is generalised here. Runtime arithmetic and fictional case are original teaching material, not performance measurements.

Previous: Communicability Betweenness Next: Communication network