Minimizing Communication in Numerical Linear Algebra

Grey Ballard, James Demmel, Olga Holtz, Oded SchwartzSIAM J. Matrix Anal. Appl 2011 · OpenReview

TL;DR

This paper generalizes fundamental communication lower bounds from matrix multiplication to a vast array of linear algebra operations, including LU, Cholesky, QR factorization, and eigenvalue/singular value problems. The authors establish that for many algorithms, the communication cost (both data movement and message count) is intrinsically linked to the number of arithmetic operations and the size of the fast memory, providing a theoretical ceiling for optimization.

What Problem Does This Paper Address?

Modern computing architectures feature a hierarchy of memory (e.g., caches, main memory, disk). Moving data between these levels is a significant bottleneck, often dominating the cost of computation. The problem this paper tackles is understanding and quantifying the minimum amount of data that must be moved between memory levels (bandwidth) and the minimum number of messages required (latency) for a wide range of fundamental linear algebra algorithms. This is crucial for designing algorithms that are not only computationally efficient but also perform well on real-world hardware by minimizing this communication overhead. The paper builds upon seminal work by Hong and Kung (1981) and Irony, Toledo, and Tiskin (2004) which established these bounds for matrix multiplication.

Methods

The core of the paper's contribution lies in generalizing the proof techniques used for matrix multiplication. The authors extend the "geometric argument on the lattice of indices" and the "segment-based analysis" from prior work.

  • Generalizing the Lower Bound: The key insight is that many linear algebra operations can be expressed in a form similar to matrix multiplication (e.g., $C_{ij} = \sum_k A_{ik} B_{kj}$), allowing the application of the same lower bound framework. This framework relates the number of data transfers to the total number of arithmetic operations ($G$) and the size of the fast memory ($M$) as $\Omega(G/\sqrt{M})$.
  • Bandwidth and Latency: The paper derives lower bounds for both bandwidth (total data moved) and latency (number of messages). The latency bound is derived from the bandwidth bound by considering the maximum message size.
  • Composition of Operations: A novel aspect is extending these bounds to sequences of operations (e.g., computing matrix powers). The authors show how to analyze these compositions by either imposing communication to make them fit the model or by directly bounding the interleaved operations.
  • Handling S2/D2 Operands: A crucial technical detail is handling "S2/D2 operands" – data that is computed and then discarded without necessarily touching slow memory. The authors develop techniques to bound these, ensuring the lower bounds remain valid.
  • Specific Algorithms: The framework is applied to dense and sparse LU factorization, Cholesky factorization, QR factorization, eigenvalue and singular value decomposition (SVD), and even some graph algorithms. For algorithms like QR, which don't fit the standard model as neatly, a modified argument is developed.

Datasets

Not discussed in the paper. The paper focuses on theoretical lower bounds for general algorithms and matrix structures, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Universality of the $\Omega(G/\sqrt{M})$ Bound: The most striking insight is how broadly the communication lower bound derived for matrix multiplication applies. It's not just for multiplication but extends to a vast family of direct linear algebra methods, suggesting a fundamental limit imposed by memory hierarchy.
  • Bandwidth vs. Latency Trade-offs: The paper clearly distinguishes between bandwidth and latency costs and shows how to derive bounds for both. This is important because different hardware architectures might be more sensitive to one over the other.
  • Composition Matters: Simply optimizing individual operations isn't always enough. The paper demonstrates that for sequences of operations, interleaving computations can sometimes yield better communication performance than a naive "phased" approach (executing each operation optimally in isolation).
  • "Making Progress" is Key: For algorithms like QR, the proof relies on the idea that the algorithm "makes progress" by preserving previously created zeros. This structural property is essential for bounding communication.
  • Attainability is Not Trivial: While the paper establishes lower bounds, it also highlights that achieving them in practice, especially for sparse matrices or with specific constraints like partial pivoting, is a significant algorithmic challenge.

Key Results

  • General Lower Bound: A general lower bound of $\Omega(\#\text{arithmetic operations} / \sqrt{M})$ for bandwidth is established for a wide class of linear algebra algorithms, where $M$ is the fast memory size.
  • Latency Bounds: Corresponding lower bounds for latency are also derived.
  • Specific Algorithm Bounds: The paper provides specific lower bounds for:
  • Dense LU, Cholesky, QR, Eigenvalue, SVD: $\Omega(n^3/\sqrt{M})$ for bandwidth.
  • Matrix Multiplication: $\Omega(n \cdot r \cdot m / \sqrt{M})$ for an $n \times r$ times $r \times m$ multiplication.
  • Sparse Cholesky on Meshes: $\Omega(n^3)$ for an $n^2 \times n^2$ matrix.
  • Compositional Bounds: For computing matrix powers $A^t$, the bandwidth lower bound is shown to be $\Omega(G/\sqrt{M})$, where $G$ is the total number of multiplications, indicating that simply calling an optimal matrix multiplication routine repeatedly is often communication-optimal.
  • Attainability: The paper notes that for dense matrices, many of these lower bounds are indeed attainable by recently developed algorithms, though these are not always found in standard libraries.

Limitations and Future Work

  • Sparse Matrices: While the framework is extended to sparse matrices, the attainability of the derived lower bounds for sparse cases is largely an open problem.
  • Rectangular and Sparse Matrices: For sufficiently rectangular dense matrices or sufficiently sparse matrices, the derived lower bound can be lower than the trivial lower bound of (#inputs + #outputs). The paper poses the question of whether the maximum of these two bounds is attainable in such cases.
  • Parallel Architectures: While parallel algorithms are discussed, the paper notes that optimal algorithms for architectures mixing parallelism and multiple memory hierarchies are still an open area.
  • Strassen-like Algorithms: The derived bounds do not apply to algorithms like Strassen's matrix multiplication, which have different computational structures.
  • Numerical Stability: The paper touches upon numerical stability issues, particularly for SVD, and notes that achieving communication optimality might require sacrificing conventional pivoting strategies.
  • Open Problems: The authors explicitly list several open problems, including finding optimal sparse algorithms, understanding attainability for rectangular/sparse matrices, and developing communication-optimal algorithms for complex parallel architectures.

Summary updated

Abstract

In 1981 Hong and Kung proved a lower bound on the amount of communication (amount of data moved between a small, fast memory and large, slow memory) needed to perform dense, -by- matrix multiplication using the conventional algorithm, where the input matrices were too large to fit in the small, fast memory. In 2004 Irony, Toledo, and Tiskin gave a new proof of this result and extended it to the parallel case (where communication means the amount of data moved between processors). In both cases the lower bound may be expressed as , where is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization, Cholesky factorization, factorization, QR factorization, the Gram–Schmidt algorithm, and algorithms for eigenvalues and singular values, i.e., essentially all direct methods of linear algebra. The proof works for dense or sparse matrices and for sequential or parallel algorithms. In addition to lower bounds on the amount of data moved (bandwidth cost), we get lower bounds on the number of messages required to move it (latency cost). We extend our lower bound technique to compositions of linear algebra operations (like computing powers of a matrix) to decide whether it is enough to call a sequence of simpler optimal algorithms (like matrix multiplication) to minimize communication, or whether we can do better. We give examples of both. We also show how to extend our lower bounds to certain graph-theoretic problems. We point out recently designed algorithms that attain many of these lower bounds.
BibTeX
@article{ballard2011minimizing,
  author = {Grey Ballard and James Demmel and Olga Holtz and Oded Schwartz},
  title = {{Minimizing Communication in Numerical Linear Algebra}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2011},
  url = {https://openreview.net/forum?id=s88MHpCHIPb},
}

Loading related content...

Figure