TY - GEN
T1 - Scalability of parallel algorithms for matrix multiplication
AU - Gupta, Anshul
AU - Kumar, Vipin
PY - 1993/1/1
Y1 - 1993/1/1
N2 - A number of parallel formulations of dense matrix multiplication algorithm have been developed. For arbitrarily large number of processors, any of these algorithms or their variants can provide near linear speedup for sufficiently large matrix sizes and none of the algorithms can be clearly claimed to be superior than the others. In this paper we analyze the performance and scalability of a number of parallel formulations of the matrix multiplication algorithm and predict the conditions under which each formulation is better than the others. We present a parallel formulation for hypt.rcube and related architectures thai performs better than any of the schemes described in the literature so far for a wide range of matrtx sizes and number of processors. The superior performance and the analytical scalability expressions for this algorithm are verified through experiments on the Thinking Machines Corporation's CM-5TM' parallel computer for up to 512 processors.
AB - A number of parallel formulations of dense matrix multiplication algorithm have been developed. For arbitrarily large number of processors, any of these algorithms or their variants can provide near linear speedup for sufficiently large matrix sizes and none of the algorithms can be clearly claimed to be superior than the others. In this paper we analyze the performance and scalability of a number of parallel formulations of the matrix multiplication algorithm and predict the conditions under which each formulation is better than the others. We present a parallel formulation for hypt.rcube and related architectures thai performs better than any of the schemes described in the literature so far for a wide range of matrtx sizes and number of processors. The superior performance and the analytical scalability expressions for this algorithm are verified through experiments on the Thinking Machines Corporation's CM-5TM' parallel computer for up to 512 processors.
UR - http://www.scopus.com/inward/record.url?scp=84904335157&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904335157&partnerID=8YFLogxK
U2 - 10.1109/ICPP.1993.160
DO - 10.1109/ICPP.1993.160
M3 - Conference contribution
AN - SCOPUS:84904335157
T3 - Proceedings of the International Conference on Parallel Processing
SP - 115
EP - 123
BT - Algorithms and Applications
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1993 International Conference on Parallel Processing, ICPP 1993
Y2 - 16 August 1993 through 20 August 1993
ER -