Communication-Efficient Matrix Multiplication on Hypercubes

By H. Gupta, Ponnuswamy Sadayappan. 1996

In this paper we present an efficient dense matrix multiplication algorithm for distributed memory computers with a hypercube topology. The proposed algorithm performs better than all previously proposed algorithms for a wide range of matrix sizes and number of processors, especially for large matrices. We analyze the performance of the algorithms for two types of hypercube architectures, one in which each node can use (to send and receive) at most one communication link at a time and the other in which each node can use all communication links simultaneously.

Citations in the corpus

• Mesh-TensorFlow: Deep Learning for Supercomputers (2018, neutral): “…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, best…”