PARALLEL MATRIX MULTIPLICATION ALGORITHMS ON HYPERCUBE MULTIPROCESSORS

In this paper, we present three parallel algorithms for matrix multipl ication. The first one, which employs pipelining techniques on a mesh grid, uses only one copy of data matrices. The second one uses multipl e copies of data matrices also on a mesh grid. Although data communica tion operations of the second algorithm are reduced, the requirement o f local data memory for each processing element increases. The third o ne, which uses a cubic grid, shows the trade-offs between reducing the computation time and reducing the communication overhead. Performance models and feasibilities of these three algorithms are studied. We an alyze the interplay among the numbers of processing elements, the comm unication overhead, and the requirements of local memory in each proce ssing element. We also present experimental results of these three alg orithms on a 32-node nCUBE-2 computer.