Communication Avoiding Algorithm
Communication-Avoiding Algorithms are the algorithmic redesigns that minimize data movement between levels of the memory hierarchy or between processors — achieving provably optimal or near-optimal communication costs that can be asymptotically lower than traditional algorithms, because data movement (not arithmetic) is the dominant cost in modern computing where a FLOP costs ~100x less energy than a DRAM access and ~10,000x less than a network transfer.
Why Communication Dominates
| Operation | Energy (pJ) | Time (ns) |
|---|---|---|
| FP64 FMA | ~20 | ~0.5 |
| L1 cache access | ~50 | ~1 |
| L2 cache access | ~200 | ~5 |
| DRAM access | ~2,000 | ~50 |
| Network transfer (Ethernet) | ~10,000 | ~1,000 |
- Communication cost growing relative to compute: Memory bandwidth doubles every ~4 years, compute doubles every ~2 years.
- Bandwidth wall: Gap between compute and communication grows → data movement is THE bottleneck.
Communication Lower Bounds
- For matrix multiplication (C = A × B, N × N matrices):
- Arithmetic: O(N³) FLOPs — any algorithm.
- Sequential communication (between cache of size M and main memory): $\Omega(N^3 / \sqrt{M})$ words.
- Parallel communication (on P processors with M memory each): $\Omega(N^3 / (P \sqrt{M}))$ words + $\Omega(\sqrt{P})$ messages.
Communication-Optimal Matrix Multiply
| Algorithm | Communication (Sequential) | Optimal? |
|---|---|---|
| Naive (ijk loops) | O(N³) | No (N³/√M possible) |
| Blocked / Tiled | O(N³/√M) | Yes! |
| Recursive (divide & conquer) | O(N³/√M) | Yes! |
| Strassen (recursive) | O(N^(log₂ 7) / √M) | Yes (for Strassen arithmetic) |
3D Algorithm (Parallel Matrix Multiply)
- Traditional 2D: P processors, each holds ~N²/P of A, B, C.
- Communication: O(N² / √P) per processor.
- 3D Algorithm: Arrange P processors in P^(1/3) × P^(1/3) × P^(1/3) cube.
- Replicate inputs across layers → each processor computes N³/P of work.
- Communication: O(N² / P^(2/3)) — asymptotically less!
- Tradeoff: Uses 3x the memory (replicated inputs).
- 2.5D Algorithm: Interpolate between 2D and 3D — use available extra memory optimally.
CA-GMRES / CA-CG (Iterative Solvers)
- Traditional Krylov methods (GMRES, CG): Compute one vector per iteration → global synchronization per iteration.
- CA-Krylov: Compute s vectors at once (s-step method) → synchronize once per s iterations.
- s-step CG: Replace s iterations of CG with one block computation → reduce messages by factor s.
- Challenge: Numerical stability degrades with large s → requires careful basis selection.
CA-LU Factorization (Tournament Pivoting)
- Standard LU: Panel factorization requires N sequential pivoting steps → N synchronization points.
- CA-LU (CALU): Tournament pivoting selects pivots in parallel → reduces communication.
- Achieves communication lower bound for LU factorization.
Communication-avoiding algorithms represent a fundamental shift in algorithm design philosophy — by recognizing that data movement, not arithmetic, is the dominant cost, these algorithms achieve orders-of-magnitude speedups on modern hardware, proving that algorithmic innovation remains as important as hardware improvement for advancing computational performance.