Classification and Tools for Efficient Parallel Algorithm Design
A parallel algorithm is represented by three important items: (a) initial
data distribution, (b) communication schedule, and (c) local computational
tasks. Depending on the constraints imposed on these three factors,
different problems arise which might require distinct approaches to
handle them. In this talk, we will discuss the issues involved in determining
and designing optimal and/or efficient parallel numerical algorithms
based on problem classification of these three criteria.
One goal of utilizing such a classification is to determine ways to
optimize existing algorithms for specified parallel machines and/or
general models and to provide software tools to automatically perform
the optimization. Working with general models may further aid algorithm
designers by taking into account issues such as portability.
In this talk, we shall present a mathematical framework for classifying
parallel algorithms and its application to parallel numerical computing.
We shall also discuss results we have obtained working based on this