Parallel Programming Paradigms
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1987
- Accession Number
- ADA196931
Entities
People
- Philip A. Nelson
Organizations
- University of Washington