Predicting Speedup for Distributed Computing on a Token Ring Network

Published in: Journal of Parallel and Distributed Computing, v. 45, no. 1, 1997, p. 53-62

Posted on RAND.org on December 31, 1996

by Phillip M. Feldman, Raisa E. Feldman, David B. Kim

Read More

Access further information on this document at www.elsevier.com

This article was published outside of RAND. The full text of the article can be found at the link above.

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.

This report is part of the RAND Corporation external publication series. Many RAND studies are published in peer-reviewed scholarly journals, as chapters in commercial books, or as documents published by other organizations.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.