Predicting Speedup for Distributed Computing on a Token Ring Network

Before a conventional applications is converted into a distributed one (typically a costly process), it is prudent to estimate the improvement in run time that will be achieved. Previous research has tended to ignore communications delays in order to facilitate analysis. However, such models lead to optimistic predictions and may be grossly inaccurate for problems involving fine-grained parallelism. In this paper, the authors consider distributed computation on a token ring local area network. They obtain exact analytical results for the mean speedup, both for small n and for asymptotically large n. For large n, they show that under very general conditions speedup tends to a limiting value with increasing numbers of processors: i.e., there is a communications speedup limit that cannot be exceeded regardless of the number of processors. Because the token ring represents a limiting case for the effects of communication delays, results obtained thus provide an upper bound for speedup on Ethernets and other bus-type networks. Analytical results were verified by simulation.