Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Proposes CAPS, a parallel Strassen implementation that provably matches communication lower bounds by interleaving breadth- and depth-first recursion and using extra local memory when available; shows strong-scaling runs on IBM Blue Gene/P and Cray where CAPS exceeds classical peak performance and outperforms 2D/2.5D and naive Strassen parallelizations, giving up to ~2–3x speedups on communication-bound sizes and better scaling on large problems; recommends using about 4–5 Strassen steps to limit numerical loss (roughly two digits) while retaining gains.
AI-written summary · about
chapters (15)
- 0:00Start
- 1:20Outline
- 3:15Motivation communication costs
- 4:36Communication lower bounds for matrix multiplication
- 8:13Lessons from lower bounds
- 10:11Simple "D" Classical Algorithm
- 11:32Previous parallel Strassen-based algorithms
- 16:53Tuning the choices of BFS and DFS Steps
- 18:10Asymptotic costs analysis
- 19:05Performance of CAPS on large problems
- 21:29Performance: Model vs Actual
- 23:38Performance of CAPS on small (comm-bound) problems
- 25:12Practical Considerations for Strassen
- 25:26Stability - why you shouldn't worry
- 27:06Summary
related talks
43mCoded matrix computation: numerical stability, partial stragglers and sparse input matrices
19mSTRADS-AP: Simplifying Distributed Machine Learning Programming without Introducing a New Programming Model
32mApproximate coding computing
58mThe Communication Complexity Landscape of Information-theoretic MPC
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
01h 05mGraph Algorithms in the MPC Model
43mConstruction And Decoding Of Short Codes
15mA General Framework for Communication-Efficient Distributed...