Source-linked AI summary
Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz
TL;DR
Parallel Strassen algorithms face a communication-cost gap relative to lower bounds. CAPS is a Strassen-based parallel algorithm designed to minimize communication, and it achieves asymptotic cost minima with reported practical speedups over prior algorithms.
Problem
Existing parallel Strassen algorithms reduce computation at the expense of higher communication, while communication can dominate computation in parallel matrix multiplication.
Source: §1.2 · p. 2, §1.1 · p. 2Method
CAPS uses lower-bound insights to minimize communication and computational costs across parallel Strassen-based algorithms.
Source: §1.3 · p. 2, §1.4 · p. 2Results
CAPS asymptotically minimizes computational and bandwidth costs across parallel Strassen-based algorithms and achieves 24%–184% speedups over the best previous parallel Strassen algorithms.
Source: §1.4 · p. 2, §5.2 · p. 9Takeaways & Limitations
The parallelization generalizes to other fast matrix multiplication algorithms, though communication optimality is not proved for all such algorithms.
Source: §6.6.2 · p. 11The implementation performs below the corresponding Strassen-Winograd peak, and the paper has not established whether machine parameters fully explain the gap.
Source: §6.3 · p. 11
Abstract
from arXiv · showhide
Parallel matrix multiplication is one of the most studied fundamental problems in distributed and high performance computing. We obtain a new parallel algorithm that is based on Strassen's fast matrix multiplication and minimizes communication. The algorithm outperforms all known parallel matrix multiplication algorithms, classical and Strassen-based, both asymptotically and in practice. A critical bottleneck in parallelizing Strassen's algorithm is the communication between the processors. Ballard, Demmel, Holtz, and Schwartz (SPAA'11) prove lower bounds on these communication costs, using expansion properties of the underlying computation graph. Our algorithm matches these lower bounds, and so is communication-optimal. It exhibits perfect strong scaling within the maximum possible range. Benchmarking our implementation on a Cray XT4, we obtain speedups over classical and Strassen-based algorithms ranging from 24% to 184% for a fixed matrix dimension n=94080, where the number of nodes ranges from 49 to 7203. Our parallelization approach generalizes to other fast matrix multiplication algorithms.
1. INTRODUCTION
The introduction motivates a Strassen-based parallel algorithm that addresses communication costs and matches communication lower bounds. It presents CAPS as asymptotically efficient and faster in practice, with an approach that extends to other fast matrix multiplication algorithms.
1.1 The communication bottleneck
- Communication can dominate computation, and even matrix multiplication becomes communication-bound when run on sufficiently many processors.The paper motivates matching communication lower bounds as a way to obtain communication-optimal algorithms.Source: §1.1 · p. 2
1.2 Communication costs of matrix multiplication
- Prior parallel Strassen algorithms reduced computation at the expense of higher communication, motivating a new algorithm rather than tighter lower bounds.The paper identifies a gap between existing algorithms’ communication costs and lower bounds, which it hypothesized could be closed by a new algorithm.Source: §1.2 · p. 2, §1.3 · p. 2
1.3 Parallelizing Strassen’s matrix multiplication in a communication efficient way
- The design uses lower-bound insights to develop CAPS, which achieves perfect load balance, minimizes communication, and asymptotically improves computation and communication over classical multiplication.The design observations include using a Strassen-specific communication pattern and as much local memory as possible.Source: §1.3 · p. 2
1.4 Our contributions and paper organization
- The paper names its algorithm Communication-Avoiding Parallel Strassen (CAPS) and reports that a 2.5D-Strassen combination improves on prior algorithms but remains inferior to CAPS.It also states that the parallelization method applies to other fast matrix multiplication algorithms.Source: §1.4 · pp. 2–3
- CAPS asymptotically minimizes computational and bandwidth costs across parallel Strassen-based algorithms, and latency cost up to a logarithmic factor in processor count.The introduction also says CAPS matches communication lower bounds and performs asymptotically better than prior classical or Strassen-based parallel algorithms.Source: §1.4 · p. 2
- 24%–184% speedups over classical and Strassen-based algorithms were measured at n = 94080 on 49 to 7203 nodes.The introduction reports benchmarking on a Cray XT4.Source: §1.4 · p. 3
2. PRELIMINARIES
The preliminaries define a distributed-memory communication model, review Strassen and prior parallelizations, and summarize communication lower bounds. The bounds depend on memory and rely on assumptions about recomputation, input storage, and load balance.
2.1 Communication model
- The model counts bandwidth in words, latency in messages, and computation in floating-point operations along the critical path, with message time modeled as α + βw.It assumes homogeneous processors and no communication resource contention; computation and communication cannot overlap in the stated model.Source: §2.1 · p. 3
2.2 Strassen’s algorithm
- Recursive Strassen multiplication uses 7 multiplications per 2 × 2 block and has O(n^ω0) work, where ω0 = log2 7 ≈ 2.81.Winograd reduces the base-case addition count from 18 to 15.Source: §2.2 · p. 3
2.3 Previous work on parallel Strassen
- Earlier parallel Strassen approaches combine classical communication patterns with Strassen locally or at the top recursion levels, while other schemes use only one or two Strassen steps.A shared-memory approach studied depth-first versus breadth-first evaluation and memory footprint but not communication costs.Source: §2.3 · p. 3
2.4 Strassen lower bounds
- Strassen communication lower bounds use expansion arguments; latency bounds follow from bandwidth bounds, with memory-dependent or memory-independent bounds dominant in different M regimes.The stated theorems assume no duplicated intermediate computations; the memory-independent bound also assumes one initial input copy and asymptotically load-balanced computation.Source: §2.4 · pp. 3–4
3. COMMUNICATION-AVOIDING PARALLEL STRASSEN
CAPS traverses Strassen’s recursion tree with breadth-first and depth-first steps, and the section presents it as communication-optimal. Its schemes trade memory against communication and use layouts that support local additions and load balance.
3. COMMUNICATION-AVOIDING PARALLEL STRASSEN
- CAPS has optimal computational and bandwidth costs, while its latency cost is at most log P away from optimal.The section presents CAPS and proves its communication optimality.Source: §3 · p. 4
3.1 Overview of CAPS
- BFS computes seven subproblems in parallel using 1/7 of the processors each, while DFS computes them sequentially using all processors; BFS uses more memory but reduces communication.The LM scheme uses the minimum number of DFS steps allowed by memory, followed by k BFS steps; it is optimal up to a constant factor, so interleaving offers no more than a constant-factor improvement.Source: §3.1 · p. 4, Figure 1 · p. 4
3.2 Data layout
- CAPS requires matching layouts for each set of four submatrices to permit local weighted additions, and equal distribution of each submatrix across processors for load balance.Block-cyclic layout is one option; Figure 2 shows an example with P = 49 and s = 2.Source: §3.2 · pp. 4–5, Figure 2 · p. 5
3.3 Unlimited Memory scheme
The unlimited-memory scheme takes k BFS steps, distributing subproblems among processors until each is computed locally. Its memory use, additions, and communication follow from this parallel traversal.
3.3 Unlimited Memory scheme
- After k = log7 P BFS steps, each subproblem is assigned to one processor and computed locally, with no further communication.The initial matrix layout has parameters (n, P, s); local additions produce the subproblem matrices without communication.Source: §3.3 · p. 5
3.3.1 Memory requirements
- Each BFS step allocates space for all seven triples S_j, T_j, Q_j, and the extra memory required grows by a factor of 7/4 per step.The memory analysis assumes local multiplications require no extra memory.Source: §3.3.1 · p. 6
3.3.2 Computational costs
- Each BFS step performs 18 additions and subtractions to compute the S_i and T_i and update C with the Q_i.The section gives a recurrence for the computational cost.Source: §3.3.2 · p. 6
3.3.3 Communication costs
- Redistribution uses all-to-all communication among groups of seven processors, with each processor sending and receiving six messages for each redistribution.Because each all-to-all involves only seven processors, the algorithm avoids scalability issues typically associated with all-to-all communication patterns.Source: §3.3.3 · p. 6, §3.3 · p. 6
3.4 Limited Memory scheme
The limited-memory scheme first uses depth-first steps to shrink subproblems, then applies the unlimited-memory scheme within the available memory. DFS reuses storage and requires no redistribution.
3.4 Limited Memory scheme
- The LM scheme takes ℓ DFS steps followed by k BFS steps, minimizing ℓ subject to memory constraints so UM can run on each resulting subproblem.The DFS steps reduce the problem size before the UM scheme is applied.Source: §3.4 · p. 6
- A DFS step stores only one subproblem at a time; after each product updates C, its storage is discarded and reused for the next subproblem.All processors participate in each product, and no redistribution occurs during DFS.Source: §3.4 · p. 6
- The LM scheme’s extra memory for a DFS step is one quarter of the space for A, B, and C, and the chosen requirements do not exceed available memory.The section assumes A, B, and C use only one third of available memory.Source: §3.4 · p. 6
- DFS steps have no communication cost; after ℓ steps, the algorithm computes 7^ℓ subproblems of size n/2^ℓ using k BFS steps.The DFS computation processes subproblems sequentially with all processors participating.Source: §3.4 · pp. 6–7
3.5 Communication optimality
The UM and LM schemes attain their respective communication lower bounds under the stated conditions. For LM, perfect strong scaling holds only up to the memory threshold where UM becomes possible.
3.5 Communication optimality
- The UM scheme matches the memory-independent communication lower bound, up to a logarithmic factor in latency, assuming the initial layout described in Section 3.2; LM matches the memory-dependent lower bound.The LM result applies when smaller M requires the limited-memory scheme.Source: §3.5 · p. 7
- For a fixed problem size, LM’s computational and communication costs decrease in proportion to processor count, with perfect strong scaling ending when memory suffices for UM.As P increases, global memory PM also increases.Source: §3.5 · p. 7
4. ANALYSIS OF OTHER ALGORITHMS
This section compares classical and Strassen-based parallel algorithms with communication lower bounds, including hybrid designs that trade computation, communication, and memory. CAPS is the reference for whether these alternatives attain the Strassen-based bounds.
4.1 Classical Algorithms
- Classical algorithms communicate asymptotically more than optimal Strassen-based algorithms; 2D and 3D methods suit particular memory regimes, while 2.5D interpolates across them.The 2.5D algorithm reduces to 2D or 3D at the memory extremes.Source: §4.1 · p. 7
4.2 2D-Strassen
- 2D-Strassen uses classical communication across processors and fast multiplication locally, but does not use Strassen on the largest matrices and exceeds CAPS’s communication costs.Its computational cost also exceeds the Strassen lower bound by a factor of P^(3−ω0)/2, approximately P^0.10.Source: §4.2 · pp. 7–8
4.3 Strassen-2D
- Strassen-2D applies ℓ Strassen steps before 2D multiplication, approaching Strassen’s computational lower bound at large ℓ but increasing communication costs.Packing messages can reduce latency to the 2D-Strassen cost in the best case, but requires more memory and remains above CAPS.Source: §4.3 · p. 8
4.4 2.5D-Strassen
- 2.5D-Strassen replaces 2D communication with 2.5D, reducing communication and computation when extra memory is available, but its bandwidth and latency costs remain above CAPS.With M = Θ(n²/P), it is exactly 2D-Strassen.Source: §4.4 · p. 8
4.5 Strassen-2.5D
- Strassen-2.5D applies ℓ communication-free Strassen steps, then 2.5D multiplication to each subproblem; at ℓopt, bandwidth remains above CAPS and computation is nonoptimal.For M ≥ n²/P^(2/3), zero Strassen steps minimize communication; extra steps reduce computation at higher communication cost, while message packing can reduce latency but not bandwidth.Source: §4.5 · pp. 8–9
5. PERFORMANCE RESULTS
On a Cray XT4, the paper benchmarks CAPS and other matrix multiplication algorithms for fixed-size square matrices. CAPS outperforms prior classical and Strassen-based algorithms, with stronger strong scaling than other algorithms except ScaLAPACK.
5.1 Experimental setup
- The Cray XT4 has 9,572 nodes, each with 8GB memory and a 36.8 GFLOPS peak rate; all Figure 3 runs multiply square matrices with n = 94080.The implementation treats each node as one processor and uses threaded BLAS for classical multiplication.Source: §5.1 · p. 9
5.2 Performance
- Effective GFLOPS gives classical algorithms their actual GFLOPS, but for fast algorithms measures performance relative to classical algorithms rather than their actual flop rate.The measure is calculated from execution time and 2n³ operations.Source: §5.2 · p. 9
5.3 Strong scaling
- CAPS exhibits better strong scaling than the other algorithms except ScaLAPACK, whose strong scaling is very good because its performance is poor at small processor counts.Perfect strong scaling appears as a horizontal line for a fixed problem size.Source: §5.3 · p. 9
5.4.1 CAPS
- The CAPS implementation switches to classical multiplication below a tuned size, supports P = c7^k processors for c ∈ {1, 2, 3, 6}, and uses Winograd Strassen.The plotted configurations tune BFS/DFS interleaving and total Strassen steps; the optimum is five or six steps.Source: §5.4.1 · p. 9
5.4.2 ScaLAPACK
- ScaLAPACK is Cray LibSci’s optimized SUMMA implementation; Figure 3 uses perfect-square processor counts for its square 2D grid.The passage says this arrangement should give its best performance.Source: §5.4.2 · p. 9
5.4.3 2.5D classical
- The 2.5D classical implementation chooses processor-grid parameters for best performance, with the number of matrix copies constrained by available memory.When c = 1, the code is an optimized SUMMA implementation.Source: §5.4.3 · p. 9
5.2 Performance
- 24%–184% speedups over the best previous parallel Strassen algorithms accompany 51%–94% over the best classical implementation; CAPS reaches 49.1 effective GFLOPS/node, 33% above the classical theoretical maximum.Figure 3 plots strong scaling for fixed n = 94080, with nodes on a log-scale horizontal axis and effective GFLOPS vertically.Source: §5.2 · p. 9, Figure 3 · p. 10
6. CONCLUSIONS/FUTURE WORK
The conclusion discusses stability and hardware demands, then identifies implementation limits and extensions of the parallelization approach. It generalizes beyond Strassen, while noting open questions about optimality and practical usefulness.
6.1 Stability of fast matrix multiplication
- Diagonal scaling makes Strassen error bounds comparable to LU and QR, so using it in larger computations will often not harm stability.Strassen has norm-wise rather than component-wise bounds before scaling.Source: §6.1 · p. 10
6.2 Hardware scaling
- Strassen needs γM^(ω0/2−1) ≥ c′β to be computation-bound, versus γM^1/2 ≥ cβ for classical multiplication.These conditions can guide hardware design for distributed local memory and network bandwidth, or cache and memory-cache bandwidth.Source: §6.2 · pp. 10–11
6.3 Optimizing on-node performance
- CAPS performs below the corresponding Strassen-Winograd peak, and the authors have not determined whether machine parameters fully explain the gap.A high-performance shared-memory Strassen implementation might provide substantial speedups for CAPS and for 2D-Strassen and 2.5D-Strassen.Source: §6.3 · p. 11
6.4 Testing on various architectures
- CAPS has been tested only on a Cray XT4; some architectures may require topology-aware redesign to minimize network contention.The authors have not yet done that redesign.Source: §6.4 · p. 11
6.5 Improvements to the algorithm
- For arbitrary P, CAPS can ignore at most six processors and incur constant-factor overhead, but attaining the computation lower bound exactly remains open.As presented, CAPS attains communication lower bounds when P is a power of seven; the arbitrary-P version attains both bounds up to a constant factor.Source: §6.5 · p. 11
6.6.1 Another optimal classical algorithm
- The parallelization approach also gives a recursive classical algorithm with the same asymptotic communication costs as 2.5D and comparable observed performance.Neither algorithm is optimized for contention in this comparison; 2.5D is very well optimized for contention on torus networks.Source: §6.6.1 · p. 11
6.6.2 Other fast matrix multiplication algorithms
- The DFS-sequential/BFS-parallel approach generalizes to bilinear fast multiplication: use P as a power of q, balanced block layouts, and traversal to choose product concurrency.The generalized communication costs use ω0 = log_n0 q.Source: §6.6.2 · p. 11
- For non-explicit fast algorithms, the generalization proves existence of communication-avoiding parallel algorithms, but practical usefulness is unclear and optimality remains conjectural unless lower bounds apply.Where the lower bounds apply, they match the generalized algorithm's performance.Source: §6.6.2 · p. 11
A. STRASSEN-WINOGRAD ALGORITHM
The appendix describes the Strassen-Winograd step used by CAPS, its recursion, and the computational cost associated with a cutoff.
A. STRASSEN-WINOGRAD ALGORITHM
- Strassen-Winograd forms seven linear combinations from each input’s four submatrices, multiplies them pairwise, then combines the products into output submatrices.The paper uses Strassen-Winograd because it usually requires fewer additions than Strassen’s algorithm.Source: A. STRASSEN-WINOGRAD ALGORITHM · p. 13
- Strassen-Winograd can be applied recursively to each of the 7 smaller matrix multiplications; although practice often uses only a few steps, attaining O(n^ω0) computational cost requires recursion down to O(1) × O(1) matrices.Source: A. STRASSEN-WINOGRAD ALGORITHM · p. 13
- At cutoff n0 = 8, the stated Strassen-Winograd computational cost is approximately 3.73n^ω0 − 5n^2.The constant cs depends on the cutoff point.Source: A. STRASSEN-WINOGRAD ALGORITHM · p. 13
B. COMMUNICATION-COST RATIOS
The appendix compares classical and Strassen-based bandwidth lower bounds across memory regimes. Their ratio depends on problem size and available memory.
B. COMMUNICATION-COST RATIOS
- When both bounds are memory-dependent, R = O(P^((3−ω0)/2)) and R = Ω(P^(3/ω0−1)).This case requires M = Ω(n^2/P) and M = O(n^2/P^(2/ω0)).Source: B. COMMUNICATION-COST RATIOS · p. 13
- When classical is memory-dependent and Strassen-based is memory-independent, R = O(P^(3/ω0−1)) and R = Ω(P^(2/ω0−2/3)).This case has M = Ω(n^2/P^(2/ω0)) and M = O(n^2/P^(2/3)).Source: B. COMMUNICATION-COST RATIOS · p. 13
- When M = O(P^(2/3)), both classical and Strassen-based bounds are in the memory-independent case.The overall ratio bounds vary with problem size relative to available memory.Source: B. COMMUNICATION-COST RATIOS · p. 13
- Depending on problem size relative to memory, classical bandwidth costs exceed Strassen-based bandwidth costs by a factor between Θ(P^(2/ω0−2/3)) and Θ(P^((3−ω0)/2)).Both lower bounds are attained by optimal algorithms.Source: B. COMMUNICATION-COST RATIOS · p. 13