Parallel execution of a sequence of tasks on an asynchronous multiprocessor

58. G. M. Baudet, R. P. Brent and H. T. Kung, Parallel execution of a sequence of tasks on an asynchronous multiprocessor, Australian Computer Journal 12 (1980), 105-112. MR 81j:68036.

Paper: pdf (1368K).


Given a sequence of tasks to be performed serially, a parallel algorithm is proposed to accelerate the execution of the tasks on an asynchronous multiprocessor by taking advantage of fluctuations in the execution times of individual tasks.

A parallel program requiring no critical section is given to implement the algorithm, and its correctness is proved. A spacewise more efficient implementation which requires the use of critical sections is also given.

An analysis is presented (for both implementations) to estimate the speedup achievable with the parallel algorithm. When the execution times are exponentially distributed, and no critical section is used, the algorithm with k processors yields a speedup of order k1/2.


This paper might be regarded as a joke, since the useful work is only done by one processor and the speedup is due to the assumptions regarding execution times on different processors. However, it also has a serious aspect, if only as a warning against taking analyses of the speedup of parallel algorithms at face value.

Go to next publication

Return to Richard Brent's index page