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

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

Read More

Access further information on this document at

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.

Our mission to help improve policy and decisionmaking through research and analysis is enabled through our core values of quality and objectivity and our unwavering commitment to the highest level of integrity and ethical behavior. To help ensure our research and analysis are rigorous, objective, and nonpartisan, we subject our research publications to a robust and exacting quality-assurance process; avoid both the appearance and reality of financial and other conflicts of interest through staff training, project screening, and a policy of mandatory disclosure; and pursue transparency in our research engagements through our commitment to the open publication of our research findings and recommendations, disclosure of the source of funding of published research, and policies to ensure intellectual independence. For more information, visit

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.