面向非规则三维片上网络的自适应可靠路由方法  

Adaptive Reliable Routing Scheme for Irregular 3D No Cs

作　　者：周君[1,2] 李华伟[1] 王天成[1,2] 李晓维[1] 

机构地区：[1]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190 [2]中国科学院大学,北京100049

出　　处：《计算机辅助设计与图形学学报》2016年第2期345-354,共10页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61432017;61176040;61221062);国家"九七三"重点基础研究发展计划项目(2011CB302501)

摘　　要：面向存在永久性链接故障的非规则三维片上网络,提出一种低成本自适应可靠路由方法.首先根据非规则三维片上网络的拓扑结构,优先选择一条汉密尔顿路径进行容错路由,在没有汉密尔顿路径的情况下,则执行生成树容错路由算法绕过故障链接;然后将基于动态规划的端口选择机制拓展到三维空间,结合前述路由算法来避开网络冲突区域,完成将数据包由源路由器节点传输至目的路由器节点的路由过程.实验结果表明,与之前的AFRA方法和基于生成树的可靠路由方法相比,该方法具有较高的通信性能和可靠性,同时所需的网络开销较低.In this paper, we propose a low-cost adaptive reliable routing scheme for the faulty links in the ir-regular 3D networks-on-chip (NoCs). Firstly, according to the topology of the irregular 3D NoC, fault-tol-erant routing is preferably conducted on a Hamiltonian path; if there is no Hamiltonian path in the network, the spanning-tree-based routing algorithm is applied to route the packets to bypass the invalid links. Secondly, in order to avoid the congestion area of the network, the dynamic-programming-based port selec-tion strategy is extended to the 3D scenarios, and adopted together with the aforementioned routing algo-rithm to implement the routing process from the source router nodes to the destination ones. Experimental results show that the proposed scheme has higher performance, better reliability, and lower overhead in comparison with the previous AFRA and the spanning-tree-based reliable routing scheme.

关 键 词：三维片上网络 非规则拓扑 自适应路由 永久性故障 容错 

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