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).
Abstract
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.
Comments
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