Communication Complexity of PRAMs

By Alok Aggarwal, A. K. Chandra, M. Snir. 1990

Subfields: Algorithms & Complexity

How researchers see this paper

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

In Algorithms & Complexity

1. Sang-Yun Oh
2. Sivan Toledo
3. J. Demmel
4. K. Yelick
5. Leonid Oliker
6. A. Tiskin
7. Dmitriy Morozov
8. Aydin Buluç

Citations in the corpus

• Mesh-TensorFlow: Deep Learning for Supercomputers (2018, background): “Mesh-TensorFlow can express a wide range of uniform partitionings of the iteration space and therefore can adopt many best known mappings, e.g., 3D [3, 1] and 2.5D [8] algorithms for square matrices, CARMA [13] for rectangular matrices, 1.5D [18] algorithm for matrices with different sparsities,…”
• Communication-Avoiding Optimization Methods for Distributed Massive-Scale Sparse Inverse Covariance Estimation (2017, methodology): “The most popular algorithm uses a 2D layout [2, 41], treating the processors as a square grid and making each processor responsible for all computations associated with one submatrix of the output matrix.”
• Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms (2011, background): “For matrix multiplication, Algorithm 1 [8, 1, 2, 16] achieves the 3D bandwidth and latency lower bounds.”
• Communication-Avoiding Parallel Sparse-Dense Matrix-Matrix Multiplication (2016, background): “Allowing different replication factors for each matrix would change the lower bounds, which is the subject of future work.”
• A massively parallel tensor contraction framework for coupled-cluster computations (2014, background): “Given an unlimited amount of memory, it is possible to replicate the data to reduce the communication cost, which is realized by a 3D matrix multiplication algorithm [32, 12, 1, 2, 23] with a resulting bandwidth cost of”
• Communication lower bounds for distributed-memory matrix multiplication (2004, methodology): “Essentially the same algorithm as in[5] was proposed again later, independently, by Gupta and Kumar [14], and by Johnsson [19].”
• Communication lower bounds and optimal algorithms for programs that reference arrays - Part 1 (2013, methodology): “For example, for matrix multiplication (d = 3, sHBL = 3/2, and dmax = 2) we get the familiar constraints N(2)/P 2/3 ≥M ≥ N(2)/P and N(2)/P 2/3 ≤ (N(3)/P )/M ≤ N(2)/P 1/2 [3, 1, 13, 20].”