Gerard Baudet

The Design and Analysis of Algorithms for Asynchronous Multiprocessors Degree Type: Ph.D. in Computer Science
Advisor(s): H. T. Kung
Graduated: May 1978

Abstract:

The characteristic of an asynchronous multiprocessor is that it is composed of several processors capable of carrying out the execution of their own programs in a completely independent fashion. As a consequence, parallel algorithms for asynchronous multiprocessors present some unique aspects in both their design and their analysis. This thesis explores the issues raised by the design and the analysis of parallel algorithms for asynchronous multiprocessors and illustrates the various notions and concepts involved with these algorithms by considering problems in diverse areas.

The thesis demonstrates that asynchronous multiprocessors can be used efficiently in different problem domains, provided that appropriate algorithms are used. It also illustrates various techniques useful in the analysis of such algorithms. As evidenced by a series of experimental results, the computation time required by a process to execute several instances of the same task on an asynchronous multiprocessor cannot be regarded as constant and is actually subject to important fluctuations.

These fluctuations in computation times have a negative effect on the performance of parallel algorithms when several processes cooperating in the solution of a problem communicate extensively among themselves. In this case, when synchronization is used, it tends to introduce a prohibitive overhead which decreases the parallelism. On the other hand, an algorithm is presented to illustrate that the fluctuations are not always a negative factor but can also be utilized advantageously.

Thesis Committee:
H. T. Kung (Chair)

Joseph Traub, Head, Computer Science Department