Parallel programming paradigms
Philip A. Nelson · 1987
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-broadcast 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. An optimal contraction is given for algorithms using the tree interconnection structure. For other contractions, a method for comparing them is given. This dissertation also presents two new parallel algorithms. The first algorithm is a divide-and-conquer matrix multiplication algorithm with time complexity of $O(n)$ using $O(n\sp2)$ processors and $O(log n)$ using $O(n\sp3)$ processors. The second algorithm is a compute-aggregate-broadcast topological sort with time complexity of $O(n {\rm log} n)$ using $O(n\sp2)$ processors and $O(log\sp2 n)$ using $O(n\sp3)$ processors.