Performance models for scalable cluster computing

In this paper, we make a thorough study of scalable parallel computing performance models, point out some of the weaknesses of existing performance models, and discuss how one can improve and generalize them. We start with analyzing and accurately defining several kinds of serial and parallel execution times, discuss parallel speedup models, and present a generalized speedup model. We propose a formal definition of scalability, and discuss scalability of cluster systems from three aspects. As an extension to the isoefficiency metric and isospeed metric, we propose and define scalability of parallel algorithm-architecture combinations based on the fixed ratio of computation time to communication overhead, analyze some relevant theoretical perspectives, and compare scalability with speedup.