ON THE SCALABILITY OF ASYNCHRONOUS PARALLEL COMPUTATIONS

This paper investigates the time lost in a parallel computation due to sequential and duplicated work, communication, and blocking, and prop oses characterizations of parallel algorithms based upon the communica tion complexity and the blocking model. It discusses the impact of the processor's architecture upon the measured speedup. It shows that a l arge speedup may be due to an inefficient sequential computation, rath er than to an efficient parallel computation. A model of parallel comp utation which takes into account sequential and duplicated work, commu nication and control, and blocking is presented. It parametrizes scala bility using three functions of the number P of processors: E (P) = th e number of communication events, f(P) = the fraction of sequential an d duplicated work plus the algorithmic blocking, I(P) = the instructio n execution rate. The characteristic function E(P) is the most importa nt as in many computations f(P) and I(P) are nearly constant. The mode l is used to predict the asymptotic behavior, the maximum speedup, and the optimal number of processors. A 3-D FFT algorithm and a Chebyshev iterative algorithm are used to illustrate the concepts introduced. ( C) 1994 Academic Press, Inc.