Communication costs of Strassen's matrix multiplication

Grey Ballard, James Demmel, Olga Holtz, Oded SchwartzCommunications of the ACM 2014 · OpenReview

TL;DR

This paper introduces CAPS, a new parallel algorithm for Strassen's matrix multiplication that is communication-optimal. It achieves this by carefully balancing computation and communication, outperforming all previous parallel matrix multiplication algorithms, both theoretically and in practice, by minimizing data movement between processors.

What Problem Does This Paper Address?

Modern high-performance computing relies heavily on parallel processing, but the efficiency of parallel algorithms is increasingly limited by the time it takes to move data between processors, rather than the time spent on computation itself. This is particularly true for fundamental operations like matrix multiplication. While Strassen's algorithm offers a theoretical speedup over classical matrix multiplication by reducing the number of arithmetic operations, its parallel implementations have historically struggled with high communication costs. This paper addresses the gap between the theoretical communication lower bounds for Strassen's algorithm and the actual communication costs incurred by existing parallel implementations, aiming to develop an algorithm that is both computationally efficient and communication-optimal.

Methods

The core of this paper is the development of the Communication-Avoiding Parallel Strassen (CAPS) algorithm. CAPS is designed to be communication-optimal by strategically interleaving "breadth-first-step" (BFS) and "depth-first-step" (DFS) operations.

  • BFS steps distribute subproblems across processors, reducing communication at the cost of higher memory usage.
  • DFS steps keep subproblems on the same processors, requiring less memory but incurring more communication.

CAPS intelligently uses these steps to minimize data movement. The algorithm is designed to maximize local memory usage, a key insight derived from analyzing communication lower bounds. The paper also introduces specific data layout requirements to enable communication-free DFS steps and efficient distribution of submatrices. The theoretical analysis of CAPS involves deriving its computational and communication costs and showing how they match the established lower bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and experimental evaluation using fixed-size matrix multiplication benchmarks.

Key Insights and Ideas

  • Communication is the Bottleneck: The paper strongly emphasizes that for parallel matrix multiplication, communication costs (moving data) are often far more significant than computational costs (performing calculations), and this trend is only increasing.
  • Communication Lower Bounds as a Guide: The authors leverage graph expansion properties to derive theoretical lower bounds on communication costs for Strassen's algorithm. These bounds serve as a target for designing optimal algorithms.
  • The Power of BFS/DFS Interleaving: The key innovation is the strategic use of BFS and DFS steps. By understanding the trade-offs between memory and communication for each, CAPS can adapt to available memory and minimize data transfers.
  • Maximizing Local Memory: A crucial insight is that to achieve communication optimality, algorithms must utilize as much local memory as possible. This is a direct consequence of the derived lower bounds.
  • Strassen's Advantage in Parallelism: CAPS demonstrates that Strassen's algorithm, when parallelized optimally, can significantly outperform classical algorithms not just in theory but also in practice, especially at scale.

Key Results

  • Communication-Optimal Algorithm: CAPS is proven to be communication-optimal, matching the theoretical lower bounds for both bandwidth and latency (up to a logarithmic factor for latency).
  • Superior Performance: Benchmarking on a Cray XT4 showed CAPS outperforming all other tested classical and Strassen-based algorithms.
  • Significant Speedups: For a fixed matrix dimension (n=94080) and varying processor counts (49 to 7203), CAPS achieved speedups of 24% to 184% over previous Strassen-based algorithms and 51% to 94% over classical algorithms.
  • Perfect Strong Scaling: CAPS exhibits perfect strong scaling within its achievable range, meaning that increasing the number of processors proportionally decreases computation and communication costs.

Limitations and Future Work

  • Hardware Dependence: The current implementation and benchmarking are limited to a Cray XT4. Testing on a wider variety of architectures is needed to confirm generalizability.
  • Network Topology: The current algorithm doesn't explicitly optimize for specific network topologies, which could be a factor in performance on certain supercomputers.
  • Generalizing Processor Counts: While CAPS is presented for P being a power of 7, extensions to arbitrary processor counts are discussed, but achieving exact optimality for all P remains an open question.
  • Constant Factors: While CAPS matches asymptotic lower bounds, there's potential for slight improvements in the constant factors within the analysis.
  • Other Fast Matrix Multiplication Algorithms: The paper suggests that the CAPS parallelization approach can be generalized to other fast matrix multiplication algorithms, but their practical utility and the optimality of such generalizations are still areas for exploration.
  • Stability: The paper briefly touches on the stability of fast matrix multiplication algorithms, noting that CAPS inherits the stability properties of Strassen's algorithm, which is generally comparable to classical methods with appropriate scaling.

Summary updated

Abstract

Algorithms have historically been evaluated in terms of the number of arithmetic operations they performed. This analysis is no longer sufficient for predicting running times on today's machines. Moving data through memory hierarchies and among processors requires much more time (and energy) than performing computations. Hardware trends suggest that the relative costs of this communication will only increase. Proving lower bounds on the communication of algorithms and finding algorithms that attain these bounds are therefore fundamental goals. We show that the communication cost of an algorithm is closely related to the graph expansion properties of its corresponding computation graph. Matrix multiplication is one of the most fundamental problems in scientific computing and in parallel computing. Applying expansion analysis to Strassen's and other fast matrix multiplication algorithms, we obtain the first lower bounds on their communication costs. These bounds show that the current sequential algorithms are optimal but that previous parallel algorithms communicate more than necessary. Our new parallelization of Strassen's algorithm is communication-optimal and outperforms all previous matrix multiplication algorithms.<!-- END_PAGE_1 -->
BibTeX
@article{ballard2014communication,
  author = {Grey Ballard and James Demmel and Olga Holtz and Oded Schwartz},
  title = {{Communication costs of Strassen's matrix multiplication}},
  journal = {Communications of the ACM},
  year = {2014},
  url = {https://openreview.net/forum?id=_8cxxbHi52},
}

Loading related content...

Figure