Single Matrix Block Shift (SMBS) Dense Matrix Multiplication Algorithm

Many scientific and numeric computations rely on matrix-matrix multiplication as a fundamental component of their algorithms. It constitutes the building block in many matrix operations used in numeric solvers and graph theory problems. Several algorithms have been proposed and implemented for matrix-matrix multiplication, especially, for distributed-memory systems, and these have been greatly studied. In particular, the Cannon’s algorithm has been implemented for distributed-memory systems, mostly since the memory needs remain constant and are not influenced by the number of processors employed. The algorithm, however, involves block shifting of both matrices being multiplied. This paper presents a similar block-oriented parallel algorithm for matrix-matrix multiplication on a 2-dimensional processor grid, but with block shifting restricted to only one of the matrices. We refer to this as the Single Matrix Block Shift (SMBS) algorithm. The algorithm, we propose, is a variant of the Cannon’s algorithm on distributed architectures and improves upon the performance complexity of the Cannon and SRUMMA algorithms. We present analytic as well as experimental comparative results of our algorithm with the standard Cannon’s algorithm on 2-dimensional processor grids, showing over 4X performance improvement.