clarke@csri.toronto.edu (Jim Clarke) (02/07/89)
NUMERICAL ANALYSIS SEMINAR - Friday, February 24, 10 a.m. in Room SF 4102
(SF = Sandford Fleming Building, 10 King's College Road)
Israel Nelken
Rutgers University
"Parallelization for MIMD Multicomputers with
Applications to Linear Algebra Algorithms"
It has become obvious in recent years that parallel computers offer high
computational power at a relatively small cost. For example, multiple
instruction multiple data (MIMD) message passing architectures, such as the
hypercube, have been shown to be useful for many types of problems. Smart
parallelizing compilers are required to fully utilize the potential of
these machines. It is known, however, that NP-complete problems are associ-
ated with the optimal parallelization of a general algorithm.
We will demonstrate that for an important class of algorithms encountered
in linear algebra, a simple methodology is sufficient to produce very effi-
cient parallel codes. This methodology has several stages: identification
of parallelism at the statement level, partitioning the operations into
indivisible tasks and the data into corresponding data units and, finally,
scheduling these tasks in the processors.
A new scheduling scheme which is suitable for message passing architectures
will be described. It incorporates the Critical Path/ Most Immediate Suc-
cessors First (CP/MISF) strategy of Kasahara and Narita. A feature of the
new method is that it exhibits an interesting time space tradeoff. An
increase of the available memory results in a decrease of the parallel
time.
Applying this methodology to the Gaussian elimination algorithm and several
of its variants results in very efficient parallel programs. Computational
results from a 128 node NCUBE hypercube as well as from simulators serve to
verify the results.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke