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.