My diploma thesis 2001

Parallel matrix-matrix multiplication
Author: Ivan Šimeček
Keywords

Parallel computation, high-performance,  matrix-matrix computation, Strassen' algorithm, Fox's  algorithm, Canon' algorithm.


Abstract

The main goal of this thesis is to study algorithms for the parallel multiplication of renctangular matices on distributed memory computers
with focusing on using the Strassen algorithm to improve the performance (both on sequential and parallel machines).

I have studied and implemented 3 different sequential algorithms (classical (trivial), commutative and Strassen's)
and 4 different parallel algorithms (1D systolic, Cannon's, Fox's and parallel variant of Strassen's).
For these algorithms I have evaluated theoreticaly their scalability. Then I have measured their performance, effeciency and scalability for various
combination of number of procesors and orders of matrices. The target architecture were a LINUX cluster consisting of INTEL PENTIUM computers
and a IBM SP2 supercomputer.

The best sequential algorithm on the both architectures was hierarchical algorithm, which uses Strassen's algorithm on the first level and commutative
algorithm on the second level. The best parallel algorithm was Fox's independently on the number of procesors or the order of matrices. Another result is that
the parallel hierarchical algorithm with Strassen's algorithm on the first level gives no performance improvement.


Download:
final version of my diploma thesis (in Czech, in .PS format)

BibTex entry
@BOOK{JA_DIP,
AUTHOR    = {I. \v{S}ime\v{c}ek},
TITLE     = {Paraleln\'{\i} n\'asoben\'{\i} matic},
PUBLISHER = {Diploma thesis},
Address =   {Department of Computer Science and Engineering, CTU FEE, Prague},
YEAR      = {2001}
}

BACK