Speedup, communication complexity and blocking-a La Recherche du Temps Perdu

The paper investigates the time lost in a parallel computation due to sequential and duplicated work, communication and control, and blocking. It introduces the concept of relative speedup and proposes characterizations of parallel algorithms based upon the communication complexity and the blocking model. The paper discusses the impact of the processor´s architecture upon the measured speedup. It shows that a large speedup may be due to an inefficient sequential computation, e.g. due to the cache management, rather than to an efficient parallel computation. A model of parallel computations which takes into account sequential and duplicated work, communication and control and blocking is presented. The paper shows that the scalability of a parallel computation is determined by the communication complexity. The model is used to predict the asymptotic behavior, the maximum speedup and the optimal number of processors. An incore 3D FFT algorithm for distributed memory MIMD systems and a Chebyshev iterative algorithm for solving a linear system of equations are used to illustrate the concepts