Accession Number:

ADA207792

Title:

A Model of Parallel Performance

Descriptive Note:

Final rept. Jul-Dec 1988

Corporate Author:

AIR FORCE WEAPONS LAB KIRTLAND AFB NM

Personal Author(s):

Report Date:

1989-04-01

Pagination or Media Count:

50.0

Abstract:

This report introduces a general model of parallel performance. With the goal of developing conceptual and empirical methods for characterizing and understanding parallel algorithms, new definitions of speedup and efficiency have been formulated. These definitions take into account the effects that problem size and the number of processors have on efficiency and speedup, and provide a natural and quantifiable measure of parallel performance. The terms introduced in the definitions provide new and improved interpretations of the serial and parallel fraction parameters commonly used in the literature i. e., Amdahls Law to explain the behavior of parallel algorithms. The model provides a more complete characterization of parallel algorithm behavior and is used to correct apparent deficiencies in the formulation of speedup as expressed by Amdahls Law. Chapter of this report reviews the basic definitions of speedup and efficiency and introduces new definitions of these quantities in terms of work units and presents two illustrative examples. Chapter 3 discusses two models of parallel performance which appear in the parallel computing literature. The two formulations of speedup and efficiency are based on the notion of serial and parallel fractions and present an apparent dichotomy which must be resolved. Then, the serial and parallel fractions are expressed terms of the new work quantities introduced in Chapter 2, providing a natural interpretation of the serial and parallel fractions of a task. The resulting equations are used to reconcile the apparent dichotomy between Amdahls Law and the more recent formulation of speedup.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE