A Fault-Tolerant and Deadlock-Free Routing Protocol in 2D Meshes Based on Odd-Even Turn Model
A Fault-Tolerant and Deadlock-Free Routing Protocol in 2D Meshes Based on Odd-Even Turn Model
复制标题
DOI：
10.1109/tc.2003.1228511
复制
发表时间：
2003-09
期刊：
影响因子：
--
通讯作者：
Jie Wu
中科院分区：
文献类型：
--
作者：
Jie Wu
提出了一种基于维序路由和奇偶转弯模型的确定性容错无死锁路由协议。建议的协议，称为扩展的X-Y路由，不使用任何虚拟通道，禁止某些位置的故障和目的地。断层包含在一组不相连的矩形区域中，称为断层块。要容忍的故障的数量是无限的，只要故障块外部的节点连接在2D网状网络中。扩展的X-Y路由也可以用于一个特殊的凸故障区域称为正交故障块，它可以从一个给定的故障块，通过激活一些非故障节点的块。扩展部分自适应路由，流量和自适应平衡使用虚拟网络，路由使用虚拟通道和虚拟网络没有约束。
We propose a deterministic fault-tolerant and deadlock-free routing protocol in two-dimensional (2D) meshes based on dimension-order routing and the odd-even turn model. The proposed protocol, called extended X-Y routing, does not use any virtual channels by prohibiting certain locations of faults and destinations. Faults are contained in a set of disjointed rectangular regions called faulty blocks. The number of faults to be tolerated is unbounded as long as nodes outside faulty blocks are connected in the 2D mesh network. The extended X-Y routing can also be used under a special convex fault region called an orthogonal faulty block, which can be derived from a given faulty block by activating some nonfaulty nodes in the block. Extensions to partially adaptive routing, traffic and adaptivity-balancing using virtual networks, and routing without constraints using virtual channels and virtual networks are also discussed.