Matrix multiplication on a toroidal parallel architecture
Wayne Patterson · 2003
Matrix multiplication is one of the class of algorithms which have considerable application and which may provide substantial increase in efficiency when implemented on an appropriate parallel machine. In particular, the author presents an algorithm for dense matrix multiplication on a toroidal architecture with n/sup 2/ processors, which has a runtime of h+nm+(n-1)a, where the matrices to be multiplied are square of order n; and where h=the time to transmit one word between adjacent processors; m=the time to multiply two words in a processor; a=the time to add two words in a processor; with a local storage requirement of 2n+2 words. Furthermore, the coefficients of the product are stored in the local memory of the same processors as the corresponding coefficients of the factors.>