A Tight Lower Bound on the Number of Channels Required for Deadlock-Free Wormhole Routing

Authors

Ran Libeskind-Hadas, Harvey Mudd CollegeFollow

Document Type

Article

Department

Computer Science (HMC)

Publication Date

1998

Abstract

Wormhole routing is widely employed in current generation multicomputers and the design of deadlock-free wormhole routing algorithms is an important problem. In this note, we prove a tight lower bound on the number of channels required by a broad class of deadlockfree wormhole routing algorithms. This result has applications in proving that certain topologies do not admit deadlock-free wormhole routing algorithms, as well as applications in the design and analysis of fault-tolerant wormhole routing algorithms.

Rights Information

© 1998 Institute of Electrical and Electronics Engineers

DOI

10.1109/12.729799

Recommended Citation

R. Libeskind-Hadas, “A Tight Lower Bound on the Number of Channels Required for Deadlock-Free Wormhole Routing,” IEEE Transactions on Computers, Vol. 47, No. 10, October 1998, pp. 1158 -1160. DOI: 10.1109/12.729799