Accession Number:

ADA046742

Title:

Analysis of Asynchronous Multiprocessor Algorithms with Applications to Sorting,

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1977-07-01

Pagination or Media Count:

21.0

Abstract:

Efficient algorithms for asynchronous multiprocessor systems must achieve a balance between low process communication and high adaptability to variations in process speed. Algorithms which employ problem decomposition can be classified as static and dynamic. Static and dynamic algorithms are particularly suited for low process communication and high adaptability, respectively. In order to find the best method, something about mean execution times must be known. Techniques for the analysis of the mean execution time are developed for each type of algorithm, including applications of order statistics and queueing theory. These techniques are applied in detail to 1 static generalizations of quicksort, 2 static generalizations of merge sort, and 3 a dynamic generalization of quicksort. Author

Subject Categories:

  • Theoretical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE