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}
}
