PARALLEL EXECUTION OF A SEQUENCE OF TASKS ON A ASYNCHRONOUS MULTIPROCESSOR.

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 speed-up achievable with the parallel algorithm. When the execution times are exponentially distributed, and no critical section is used, the algorithm with k processes yields a speed-up of order k** one-half . Show more