A study of average-case speedup and scalability of parallel computations on static networks

A parallel system consists of a parallel algorithm and a parallel machine t hat supports the implementation of the algorithm. The scalability of a para llel system is a measure of its capability to increase speedup in Proportio n to the number of processors, or its capability to keep a constant efficie ncy as the number of processors increases. The present paper is devoted to the investigation of the average-case scalability of parallel algorithms ex ecuting oil multicomputers with symmetric static networks, including the co mpletely connected network, ring, hypercube, and torus. In particular, we c haracterize the communication overhead such that the expected efficiency ca n be kept at certain constant level, and that the number of tasks grows at the rate Theta(P log P). (C) 1999 Elsevier Science Ltd. All rights reserved .