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.