Predicting Speedup for Distributed Computing on a Token Ring Network
✍ Scribed by Phillip M. Feldman; Raisa E. Feldman; David B. Kim
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 145 KB
- Volume
- 45
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Before a conventional application 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, we consider distributed computation on a token ring local area network. We obtain exact analytical results for the mean speedup, both for small n and for asymptotically large n. For large n, we 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 communications delays, results obtained thus provide an upper bound for speedup on Ethernets and other bus-type networks. Analytical results were verified by simulation.