Accession Number:

ADA196931

Title:

Parallel Programming Paradigms

Descriptive Note:

Doctoral thesis

Corporate Author:

WASHINGTON UNIV SEATTLE DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1987-07-01

Pagination or Media Count:

142.0

Abstract:

Paradigms for the development of sequential algorithms, such as divide-and-conquer and the greedy method, are well known. Paradigms for the development of parallel algorithms, especially algorithms for non-shared memory MIMD machines, are not well known. These paradigms are important, not only as tools for the development of new algorithms, but also because algorithms using the same paradigm often have common properties that can be exploited by operations such as contraction. This dissertation identifies four primary paradigms used by non-shared memory MIMD algorithms. They are compute-aggregate- broadcast, divide-and-conquer, pipelining, and reduction. Compute-aggregate- broadcast is used, for example, in numerical approximation algorithms like the conjugate gradient iterations. Three variations of the compute-aggregate- broadcas t paradigm are studied. Divide-and-conquer is shown to be applicable to parallel algorithms. The relationship between divide-and-conquer algorithms and the n-cube is studied. Systolic techniques are known to be broadly applicable for the development of MIMD algorithms. Systolic algorithms are shown to be members of the more general pipelining paradigm. Finally, the reduction paradigm is briefly studied. The contraction problem, the problem arising when an algorithm requires more processors than are available on the execution machine, is studied. Special attention is given to common solutions to the contraction problem in each paradigm.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE