Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms

By Edgar Solomonik, J. Demmel. 2011

262 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Hardware and Architecture, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Hardware and Architecture

In Optimization & Training

Citations in the corpus

Mesh-TensorFlow: Deep Learning for Supercomputers (2018, methodology): “This technique is sometimes called iteration space tiling [2], replication [6], or task parallelism [11].”
Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding (2018, background): “Hence, deploying matrix computation tasks on large-scale distributed systems has received wide interests [1]–[4].”
Communication lower bounds and optimal algorithms for programs that reference arrays - Part 1 (2013, methodology): “In some cases algorithms are known that attain these smaller lower bounds (e.g., matrix multiplication in [20]), i.e., replicating data can reduce communication.”
Communication optimal parallel multiplication of sparse random matrices (2013, methodology): “As in [27, 26], we assume the data initially resides only on the one of the c layers and gets replicated along the third dimension before the multiplications start.”
Overlap Communication with Dependent Computation via Decomposition in Large Deep Learning Models (2022, background): “5D [47, 50] algorithms were further proposed for different applications by trading memory for communication.”
Scalable task-based algorithm for multiplication of block-rank-sparse matrices (2015, background): “5D and 3D MM algorithms [29] that trade off memory to increase concurrency.”
Communication-Avoiding Optimization Methods for Distributed Massive-Scale Sparse Inverse Covariance Estimation (2017, methodology): “3D [1] and 2.5D [46] algorithms are provably communication-optimal in certain cases, and instead divide up the 3D iteration space, by essentially making c copies of the output matrix, and having a square group of processors responsible for a subset of updates to that copy; the copies are eventually…”
Communication-Avoiding Parallel Sparse-Dense Matrix-Matrix Multiplication (2016, background): “3D algorithms, however, further minimize the cost of communication relative to 2D algorithms, at the expense of more memory usage [22].”
Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication (2013, unknown): “Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication James Demmel∗, David Eliahu†††, Armando Fox‡††, Shoaib Kamil§, Benjamin Lipshitz¶††, Oded Schwartz‖††, and Omer Spillinger∗∗†† Abstract—Communication-optimal algorithms are known for square matrix multiplication.”