Scalability of algorithms: an analytic approach

Abstract In this paper we discuss various scaling schemes for parallel applications where the parallel overhead is described by a fairly general class of overhead functions depending on the problem size N and the number of processors p which — as a structural requirement — display convexity with respect to p if multiplied by p . Our scaling schemes are derived from optimality criteria for speedup and speedup-efficiency-product respectively. These schemes are compared to the constant execution-time scheme of Gustafson and are related to iso-efficiency considerations.