PROGRAM SPEEDUP IN A HETEROGENEOUS COMPUTING NETWORK

Program speedup is an important measure of the performance of an algor ithm on a parallel machine. Of particular importance is the near linea r or superlinear speedup exhibited by the most performance-efficient a lgorithms for a given system. We describe network and program models f or heterogeneous networks, define notions of speedup and superlinear s peedup, and observe that speedup consists of both heterogeneous and pa rallel components. We also consider the case of linear tasks, give a l ower bound for the speedup, and show that there is no theoretical uppe r limit on heterogeneous speedup. (C) 1994 Academic Press, Inc.