Analysis of Asynchronous Multiprocessor Algorithms with Applications to Sorting,

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1977
Accession Number
ADA046742

Entities

People

  • John T. Robinson

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Networks
  • Computer Science
  • Computers
  • Data Science
  • Decomposition
  • Distribution Functions
  • Information Science
  • Military Research
  • Multiprocessors
  • Network Protocols
  • Order Statistics
  • Probability
  • Probability Distributions
  • Queueing Theory
  • Random Variables
  • Standards

Fields of Study

  • Computer science

Readers

  • Computer Vision.
  • Mathematical Modeling and Probability Theory.
  • Software Engineering.