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 that supports the implementation of the algorithm. The scalability of a parallel system is a measure of its capability to increase speedup in Proportion to the number of processors, or its capability to keep a constant efficiency as the number of processors increases. The present paper is devoted to the investigation of the average-case scalability of parallel algorithms executing oil multicomputers with symmetric static networks, including the completely connected network, ring, hypercube, and torus. In particular, we characterize the communication overhead such that the expected efficiency can 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.
speedup scalability efficiency completely connected network ring hypercube torus communication cost execution time performance analysis random parallel program