communication avoiding algorithms
**Communication-Avoiding Algorithms** are **reformulations of classical numerical and data-intensive algorithms that minimize data movement (between memory hierarchy levels or between processors) at the cost of additional computation**, based on the principle that communication costs (latency + bandwidth) grow faster than computation costs and increasingly dominate execution time on modern hardware.
The energy cost of moving a double-precision number from DRAM to a CPU register (~100 pJ) is 100x the cost of a floating-point multiply (~1 pJ). Between nodes across a network, the ratio is 10,000x. Communication-avoiding algorithms reduce data movement by the maximum amount information-theoretically possible.
**Communication Lower Bounds**: For matrix-matrix multiplication of n x n matrices, the I/O lower bound (minimum data movement between fast memory of size M and slow memory) is Omega(n^3 / sqrt(M)). Classical algorithms perform O(n^3) communication — sqrt(M) times more than necessary. **Communication-optimal algorithms** match the lower bound.
**Key Communication-Avoiding Algorithms**:
| Algorithm | Classical Communication | CA Communication | Savings |
|----------|----------------------|-----------------|----------|
| **CA-LU/QR/Cholesky** | O(n^3/P^(2/3)) messages | O(n^3/P^(2/3) / P^(1/3)) | P^(1/3)x fewer |
| **Tall-Skinny QR (TSQR)** | O(n log P) messages | O(log P) messages | n/log(P) fewer |
| **2.5D matrix multiply** | O(P^(1/2)) memory traffic | O(P^(1/3)) with c copies | P^(1/6) reduction |
| **s-step Krylov** | O(s*n) global syncs | O(n) global syncs | s-fold reduction |
**s-Step Krylov Methods**: Classical Krylov solvers (CG, GMRES) perform one matrix-vector multiply and one or two global reductions (dot products, norms) per iteration — the global reductions synchronize all processes and become the bottleneck at scale. s-step variants compute s iterations' worth of basis vectors before orthogonalizing, reducing global synchronizations by a factor of s. The trade-off: numerical stability decreases with larger s, requiring careful implementation with Newton or Chebyshev polynomials for basis generation.
**2.5D Algorithms**: Classical 2D parallel algorithms distribute an n x n matrix across P processors in a P^(1/2) x P^(1/2) grid. 2.5D algorithms use c redundant copies of the data, organized in a P^(1/2) x P^(1/2) x c processor grid, reducing communication bandwidth by a factor of c^(1/2) at the cost of c-fold memory overhead. For c = P^(1/3), this achieves the communication lower bound — optimal data movement at the cost of extra memory and redundant computation.
**Cache-Oblivious Algorithms**: Achieve near-optimal cache behavior without knowing cache sizes, using recursive divide-and-conquer that naturally fits data into any level of the memory hierarchy. Cache-oblivious matrix multiplication recursively divides matrices into quadrants until they fit in L1 cache, achieving O(n^3 / sqrt(M)) cache misses at every cache level simultaneously — communication-optimal without cache-size tuning parameters.
**Communication-avoiding algorithms represent a fundamental shift in algorithm design priorities — from minimizing arithmetic operations (the classical optimization metric) to minimizing data movement (the actual performance limiter on modern hardware), yielding speedups that increase as the computation-to-communication gap continues to widen with each hardware generation.**