2D Mesh片上网络分区容错路由算法  

Region-based fault tolerant routing algorithm for 2D mesh network on chip

作　　者：胡哲琨[1] 杨升春[1] 陈杰[2] 

机构地区：[1]武汉数字工程研究所研发部,武汉430205 [2]中国科学院微电子研究所通信与多媒体技术研究室,北京100029

出　　处：《计算机应用》2016年第5期1201-1205,共5页journal of Computer Applications

摘　　要：为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法。该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up*/down*算法确定路由路径。此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁。在6×6 Mesh网络中,RFTR算法能减少25%的路由表资源用量。仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up*/down*算法和segment算法相当甚至更优的性能。In order to reduce the entries of routing tables and avoid using large numbers of Virtual Channels（ VC）,a Region-based Fault Tolerant Routing（ RFTR） algorithm was proposed for wormhole switching 2D Mesh Network on Chip（ No C） 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 deadlock-free using only two VCs. In a6 × 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 segment-based routing algorithms.

关 键 词：片上网络 容错路由 死锁避免 路由表 通道依赖图 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]