Report Number: CSL-TR-78-158
Institution: Stanford University, Computer Systems Laboratory
Title: Performance characterization of parallel computations
Author: Lee, Ruby Bei-Loh
Date: September 1978
Abstract: This paper defines and interprets quantitative measures by which we may characterize the absolute and relative performance of a parallel computation, compared with an equivalent serial computation. The absolute performance measures are the Parallelism Index, PI(P), the Utilization, U(P), and the maximum Quality, Q(P). The corresponding relative performance measures are the Speedup, S(P,1), the Efficiency, E(P,1), and the Quality, Q(P,1). We show how the corresponding absolute and relative performance measures are related via the Redundancy measure, R(P,1). We also examine the range of permissible values for each performance measure. Ideally, we would like to compare an optimal parallel computation with an optimal equivalent serial computation, in order to determine the performance improvements due solely to parallel versus serial processing. Toward this end, we define optimal parallel and serial computations, and show such optimality may be approximated in practice. In order to facilitate the calculation of the above performance measures, we show how the complexity of modelling an arbitrary parallel computation may be reduced substantially to two simple canonical forms, which we denote the computation's Parallelism Profile and TOP-form. Finally we show how all the canonical forms and performance measures may be generalized from one computation to a set of computations, to arrive at aggregate canonical and performance descriptions.
http://i.stanford.edu/pub/cstr/reports/csl/tr/78/158/CSL-TR-78-158.pdf