2DMesh片上网络分区容错路由算法
2016-05-14胡哲琨杨升春陈杰
胡哲琨 杨升春 陈杰



Abstract: In order to reduce the entries of routing tables and avoid using large numbers of Virtual Channels (VC), a Regionbased Fault Tolerant Routing (RFTR) algorithm was proposed for wormhole switching 2D Mesh Network on Chip (NoC) to reduce the amount of hardware resources. According to the positions of faulty nodes and links, the 2D Mesh network was divided into several rectangular regions. Within each region the packet could be routed by deterministic or adaptive routing algorithms, while among these regions the routing path was determined by up*/down* routing algorithm. Besides, with the Channel Dependency Graph (CDG) model, the proposed algorithm was proved to be deadlockfree using only two VCs. In a 6×6 Mesh network, the RFTR algorithm can reduce the amount of routing table resources by 25%. Simulation results show that, with the same amount of buffer resources, the RFTR algorithm can achieve an equivalent or even higher performance compared to up*/down* and segmentbased routing algorithms.
Key words:Network on Chip (NoC); fault tolerant routing; deadlock avoidance; routing table; Channel Dependency Graph (CDG)
0 引言
随着集成电路工艺技术的发展,芯片内部可集成的IP核数目不断增加,出于对可扩展性、连线延时和功耗等因素的考虑,片上网络(Network on Chip, NoC)逐渐成为多核间通信的主流方式。2D Mesh是一种常用的片上网络结构,具有规则的平面布局,且易于实现高效无死锁的数据包路由。然而,集成电路制造过程中产生的缺陷和工艺变化等因素可能导致芯片中的部分节点或链路不能正常工作,从而打破了Mesh结构的规则性,且随着工艺尺寸的进一步缩小,该现象会更加明显。为了有效利用芯片中剩余的资源进行计算,片上网络需具有一定的容错特性,而其中一个重要方面就是容错路由算法的设计。
目前针对2D Mesh网络已存在多种容错算法。传统的基于故障块模型的容错路由算法[1-2]需要3至4个虚通道(Virtual Channels, VC)才能避免死锁,然而在片上网络中,较多的虚通道不仅会占用大量的缓存资源,还会导致路由器工作频率降低,因此这类算法并不适用于片上网络。拓扑无关的路由算法[3]也能用于容错路由,如up*/down*路由算法[4-5]和segment路由算法[6]。这些算法在不使用虚通道的情况下就能避免死锁,但需依赖路由表才能实现路由计算,而路由表的总项数与网络节点数的平方成正比,当片上网络的规模增大时,会导致芯片面积和功耗的急剧增加,因此这类算法缺乏良好的可扩展性。文献[7]提出了一种基于逻辑运算的分布式容错路由机制,无需虚通道就能避免死锁,但只能针对某些特定的拓扑结构(如“P”型、“+”型网络)适用。……
