一种基于2D-mesh的片上网络无死锁容错路由算法

为解决片上网络中的永久性故障问题，提出一种基于2D-mesh拓扑结构的无死锁容错路由算法.定义了新的故障块生成规则，减小了故障节点的区域和受影响的健康节点数目，设计了一种故障节点探测和绕道路径生成算法，通过递归式消息传递实现了故障块区域的建立和绕道路径列表的生成.在绕道容错路由算法中，采用部分路由表与路由规则相结合的方法，通过在报头中加入绕道路径列表的方式引导报文绕过故障区域.结果表明，与现有算法相比，所提出的容错路由算法在随机均衡负载和热点负载2种情况下的延时都有所降低.

A Fault-Tolerant and Deadlock-Free Routing Algorithm in 2D-Mesh for Network on Chip

A fault-tolerant and deadlock-free routing algorithm applied in 2D-mesh was proposed to solve the problem of the permanent and unpredictable failure occurrence in network on chip. Firstly a new definition of fault block is proposed to reduce the region of fault and the affected healthy node, and then a detour-path construction algorithm is designed to implement the construction of fault block and the generation of detour-path list by recursive of message deliver. The detour-path routing algorithm combines the detour-path list and routing rules, makes a detour to avoid the fault block by adding detour-path list into the header flit. The experimental results show that the proposed algorithm achieves a reduction of average delay under uniform random distribution and hotspot distribution.