Parallel Execution of a Sequence of Tasks on an 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. A parallel program requiring no critical section is given to implement the algorithm and its correctness is proved. A spacewise more efficient implementation is also given but requires the use of critical sections. 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 sq rt of k. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1977
Accession Number
ADA042505

Entities

People

  • G. M. Baudet
  • H. T. Kung
  • R. P. Brent

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Asymptotic Series
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Distribution Functions
  • Military Research
  • Multiprocessors
  • Parallel Computing
  • Parallel Processing
  • Probability
  • Processing Equipment
  • Random Variables
  • Scheduling (Production)
  • Sequences
  • Time Intervals

Fields of Study

  • Computer science
  • Engineering

Readers

  • Computer Programming and Software Development.
  • Parallel and Distributed Computing.