Fault-tolerant wormhole routing in meshes
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 240-249
- https://doi.org/10.1109/ftcs.1993.627327
Abstract
It is shown how to modify the routing algorithms produced by the turn model to encompass dynamic faults. The authors describe how to modify the negative-first routing algorithm, which the turn model produces for n-dimensional meshes without virtual channels, to make it one-fault tolerant. Simulations of the one-fault-tolerant routing algorithms in a two-dimensional mesh indicate that misrouting increases communication latencies significantly at high throughputs. The conclusion is that misrouting should be used only for increasing the degree of fault tolerance, never for just increasing adaptiveness. Finally, the authors describe how to modify the negative-first routing algorithm to make it (n-1)-fault tolerant for n-dimensional meshes.Keywords
This publication has 10 references indexed in Scilit:
- High Performance Communications In Processor NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- The Turn Model for Adaptive RoutingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Virtual-channel flow controlPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A survey of wormhole routing techniques in direct networksComputer, 1993
- Planar-adaptive routingPublished by Association for Computing Machinery (ACM) ,1992
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- On the Design of Deadlock-Free Adaptive Routing Algorithms for Multicomputers: Design MethodologiesPublished by Springer Nature ,1991
- Adaptive, low latency, deadlock-free packet routing for networks of processorsIEE Proceedings E Computers and Digital Techniques, 1989
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- The torus routing chipDistributed Computing, 1986