Communication Avoiding Algorithms for Linear Algebra and Beyond
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
A model counts flops, words moved and messages and proves a flops/√M bandwidth lower bound for many nested-loop array codes; a 2.5D replicated matrix multiply that stores C copies hits the bound, cuts communication by ~95%, gives perfect strong scaling in time and energy and shows 12× speedup on 64k-core Blue Gene for an 8k×8k matrix (2.7× for larger problems). Theory uses an HBL-based linear program to give optimal blocking exponents, yields 12× n‑body speedups, 13× GPU gains for tall‑skinny QR, and is being integrated into libraries and tensor frameworks.
AI-written summary · about
chapters (9)
- 0:00The case for communication
- 2:20Direct linear algebra goals
- 3:46Lower bounds in linear algebra
- 7:29Two-and-a-half-D algorithms
- 11:31Strong scaling and performance
- 13:27Ongoing research applications
- 15:16Generalizing the theory
- 20:13Mathematical foundation
- 24:25Iterative methods and outlook
related talks
48mC++ Algorithmic Complexity, Data Locality, Parallelism, Compiler Optimizations, & Some Concurrency
43mCoded matrix computation: numerical stability, partial stragglers and sparse input matrices
32mApproximate coding computing
01h 04mCompile-time sparse matrices
01h 04mDesign for Performance
23mPattern-Based Optimization (...)
31mSome Novel Computational Models to Think About
01h 02mSqueezing the Hardware to Make Performance Juice