Fault-tolerant wormhole routing in meshes without virtual channels
Fault-tolerant wormhole routing in meshes without virtual channels
复制标题
DOI：
10.1109/tpds.1996.10001
复制
发表时间：
1996
影响因子：
5.3
通讯作者：
C. Glass;L. Ni
中科院分区：
文献类型：
--
作者：
C. Glass;L. Ni
以前使虫洞路由网格具有容错能力的方法是基于向网络添加虚拟通道。本文提出了一种替代方法，一种基于轮流模型的虫洞路由算法设计方法。轮流模型产生的路由算法对于直接网络来说是无死锁的、非常自适应的、最小或非最小的、无活锁的——无论它们是否包含虚拟通道。本文说明了如何修改轮流模型生成的路由算法来处理动态故障。本文首先描述了如何修改轮流模型为没有虚拟通道的 n 维网格生成的负优先路由算法，使其具有单容错能力。在二维网格中对一容错路由算法和其他最小和非最小路由算法的模拟表明，错误路由在高吞吐量下会显着增加通信延迟。结论是错误路由只能用于提高容错程度，而不能仅仅用于提高适应性。最后，本文描述了如何修改负优先路由算法，使其对无虚拟通道的n维网格具有(n-1)容错能力。
Previous methods of making wormhole-routed meshes fault tolerant have been based on adding virtual channels to the networks. This paper proposes an alternative method, one based on the turn model for designing wormhole routing algorithms. The turn model produces routing algorithms that are deadlock free, very adaptive, minimal or nonminimal, and livelock free for direct networks--whether or not they contain virtual channels. This paper illustrates how to modify the routing algorithms produced by the turn model to handle dynamic faults. This paper first describes 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 algorithm and other minimal and nonminimal 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 paper describes how to modify the negative-first routing algorithm to make it (n - 1)-fault tolerant for n-dimensional meshes without virtual channels.