Problem 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 framework.

Top of Page