一种新的片上网络拥塞感知容错路由算法

2017-05-18吴凤阳刘勤让

重庆邮电大学学报(自然科学版) 2017年2期

关键词：路由器数据包路由

吴凤阳，刘勤让

(国家数字交换系统工程技术研究中心，河南郑州 450002)

一种新的片上网络拥塞感知容错路由算法

吴凤阳，刘勤让

(国家数字交换系统工程技术研究中心，河南郑州 450002)

提出一个有效的路由通道选择机制，实现了基于片上网络(networks on chips,NoC)的拥塞感知的自适应容错路由算法(congestion-aware adaptive fault-tolerant routing algorithm, CAFR)。该算法基于Up*/Down*路由算法得出源节点到目的节点每条路径的转向概率，再根据每条链路的两端路由器剩余内存时隙得出一个加权链路，最后由每条路径权重值和其路径的转向概率计算出源地址到目的地址各条路径的总权重值。实验结果表明，在无故障条件下，该算法的平均延迟和平均吞吐率都能维持较好水平。在故障条件下，该算法相对其他算法在吞吐量衰减方面有很大改善，尤其在故障率达到20%时，该算法吞吐量只有44.32%的衰减，而其他有容错性能的算法衰减达到48%～70%。

片上网络；拥塞感知；Up*/Down*路由算法；加权链路

0 引言

随着技术的发展，硅元件的特征尺寸已发展到亚纳米阶段，同时元件的可靠性也越来越低。另外，数字系统复杂度的增加很可能会造成在它们的使用过程中要经历永久性故障。为了克服这个问题，片上网络在设计时不仅要满足性能的需要，而且在面对许多故障发生时还得具有较强的鲁棒性。

当代复杂的片上系统引入新的互连策略，如允许可扩展芯片上多种处理单元之间通信的片上网络(network on chips,NoC)。当前NoCs中，通信延迟和容错对于复杂性和高概率应用映射结构的片上多处理器是个挑战[1]。在经常发生故障的工艺制造中，先前工艺制造处理和物理缺陷的增加对于实际NoC可靠性是关键挑战。NoC通信延迟主要由路由算法决定。自适应路由算法需要解决有繁忙/拥塞争论的流量监测，同时还要解决可靠性问题和提供容错[2]。目前算法不仅需要考虑链路的流量，而且还有在NoC中产生的永久和暂时性故障。特殊永久故障的存在对于动态系统是不可逆的；额外的敏感电流和辐射能造成短暂的故障，同时不稳定的硬件能造成间歇的故障，如卡壳、桥接、窜扰、单事件更新和传输的故障。根据国际半导体技术发展路线图(international technology roadmap semicoductors,ITRS)报道，在日常运作期间，每天将有1%的芯片产生故障。在不久的将来，工艺制造的缺陷概率将达到每平方米大约有1 000个缺陷[3-4]。测试结果表明在NoC中，即使很小数量的故障，如逻辑门开关故障，都能造成5～50的链路故障，这极大损害NoC网络系统[5]。当一条链路发生故障，自适应路由算法应该选择一条无故障路径发送数据包，避免数据包传输的瘫痪。因此，确保NoCs模块能够容纳故障和维持标准工艺的运行需要，自动化系统应能够根据真实的通信流量条件作出决定。解决这种情况首先要提出一个路径选择优化方案让系统能够在当前故障下运行。

目前，国内外学者对此展开大量的研究。文献[6]在XY和Odd-Even 算法基础上进行改进，提出了一种能在拥塞条件下进行确定性和自适应路由算法之间转化的DyXY路由算法，该算法较单独的XY和Odd-Even 算法在平均延迟上具有较好的特性，但在故障条件下吞吐量、平均延迟等性能急剧下降。文献[7]提出了一种在每条链路增加2条专用线路来指示与当前路由器有相同行或列路由节点的通信状态以避免拥塞路径的方案。但是这种增加专用线路的方案需要较大的资源开销，如有网路发生故障时，网络吞吐量衰减较大。文献[8-9]提出了一种集中自适应路由机制，它采用路由表和一个负反馈模块检测全局网络通信状态来选择一条拥塞程度低的路径转发数据包。但是该类算法在故障条件下无法保持网络性能。文献[10]采用一个可重构路由算法，当检测到故障或失效路由器时，该算法通过绕开故障路由器来达到容错的性能。但是该算法仅能容忍节点故障。陈庆强等人提出了一种邻居节点感知和端口优先级选择方案[11-12]，该方案可以自适应选择无故障路径转发数据微片，但是该算法在端口优先级划分上略显欠缺，控制拥塞也不明显，而且在发生区域故障时平均延迟较高。

对于以上多数容错方案，在复杂的通信条件下做出拥塞控制和选择优先路径方面普遍存在不足；而且在大量通信状态和发生区域性故障条件下，不能很好地维持网络的性能。因此提出了一种具有拥塞感知的容错路由算法(congestion-adaptive fault-tolerant routing algorithm，CAFR)。

容错NoC路由算法通过灵活地均衡它内在的路由解决了这个难题。也就是说，CAFR路由算法通过限制通信在无故障路径中传输来应对故障发生。本文中，虽然一些不可知的拓扑结构路由算法提供了较高灵活性的路径，甚至在目前存在许多故障情况下保持网络的连通性。尽管如此，当在芯片上不断地配置不能实现的故障时，它们也经常在很少的故障下导致系统的服务性能退化。例如，在文献[13]中，在仅有10个故障下一个8×8 mesh网络的吞吐量下降20%。这不合理的损失主要是由于在剩下健康路径中通信拥塞的增加。因此，运行时通信流量的控制对故障网络的性能具有重要的影响。

本文中，采用CAFR算法的目的是在当前故障下通过动态路由最小化NoC吞吐量的退化。它采用一个在有效的区域中基于权重端口选择机制定义可靠的、低拥塞的路由通道。CAFR算法对于多种通信流量条件(如繁忙/拥塞/故障)定义不同的权重值，在算法中繁忙和故障条件下被分别定义成最大和最小权重值。每个NoC路由器端口被设定权重值，最大的权重端口作为优先转发数据包。通过计算端口的权重，在路由器端口之间做路由选择时，能够避免故障或拥塞的链路。因此，在NoC系统中CAFR算法能够绕开故障，并有能力根据复杂的通信流量条件做出优化路由抉择。通过定义好的端口，在给定的流量模式和故障条件下使全局NoC吞吐量最大，获得优秀的系统性能。

1 CAFR路由算法描述

1.1 路径边权重计算

路径计算的主要思路为：① 将设计一个关联的有向图G(V，E)；②根据当前网路通信状态按比例分配边权重；③基于ball-string模型，设计一种自检测机制，该机制可以在已知的源节点与目的节点坐标的条件下得出权重值最大的路径[6]。可以把链路的状态分别定义成：空闲(权重：6～9)、繁忙(权重：3～5)、拥塞(权重：1～2)和故障(权重：0)。

本节根据当前系统缓存占用率的信息来计算边权重，如图1所示。具体来说，就是计算上一跳路由节点输出缓存与下一跳路由节点输入缓存中所剩余内存时隙的总个数。图1a阐述了一条链路的边权重计算算法。图1b给出了3×2 NoC关联图的边权重。最优路径中的边权重wij(i=1,2,3…,|V|;j=1,2,3…,|V|)计算为

(1)

算法在部署时利用了网络图的邻接矩阵[A]n×n，因为每个元素存储了相应的边权重(即aij=wij) ，所以将其称为网络矩阵。图1c给出了[A]3×2网路矩阵。

为了减小额外的硬件开销，本文采取一种分布式、自适应路由策略。NoC拓扑网络被划分成多个区，在每个分区设置一个本地监测模块(local monitoring module，LMM)[13]。LMM模块作为一种检测器，负责检测该区域节点连接链路的拥塞状态。如图2中划分的区域大小相等，实际中对区域大小不做要求。

每个LMM模块主要工作是将当前链路的状态信息分发到其领域所有路由器中以及其领域一阶(first-order )相邻的路由器。LMM模块还要计算出连接不同领域的链路权重，它们之间通过互连来实现信息共享。

1.2 转向概率

研究中数据资料均采用统计学软件SPSS20.0构建的数据库检验，其中患者不良反应、依从及满意率、检查图像质量分析均百分率表示，卡方检验。当数据差异P＜0.05，视为统计学价值存在。

CAFR算法基于Up*/Down*路由算法建立一个链路生成树。链接到根节点被标记为Up链路，而链接向叶节点被标记为Down链路。Up*/Down*路由算法不允许Down-Up转向：一旦数据包到达一个Down链路，它就不能被允许转到一个Up链路。

图1 边权重计算示例Fig.1 Link weights

图2 NoC被分割为4个分区的示意图Fig.2 NoC segmentation image

对于路径的每个部分，我们分3个步骤估算数据包从源节点到目的节点所有可能链路。

Step 1 估算不同路径。计算出从源节点到达下一跳所有不同路由节点链路总数。例如，在图3a中节点13可从2个不同路由器到达节点10的东边链路：13→9→10和13→14→10，然而只有一个路由器能够通向节点10的北边链路：13→14→10。在这个处理中，只允许在有限的转向约束下以最短跳步的路由路径转发数据。

Step 2 链路负载估计。根据Step 1的结果估算出基于多种可利用路径中每条链路上来自上一跳的通路负载基数。节点输入端口概率等于输入端口链路的通路基数除去用相同跳数到达该节点的所有路由器总通路数。图3b展示了连接节点10的每条输入端口链路的概率。

Step 3 转向负载估计。为了估计每个转向负载概率，我们拿来自源方向输入端口负载概率除去源方向允许输出的端口总数。图3c展示了连接节点10路由器的输出端口概率。

图3 链路负载和转向概率示例Fig.3 Link load and turn probability

最优路径选择

(2)

(2)式中：yii是一个二进制变量，表示链路ch(vi，vj) 是否可以被采用；pi是转向概率，表示路由器j选择下一链路的几率。计算最短路径的方法是基于并行最短路径搜索[14]原理，该方法是通过检测当前网络通信状态来计算出多条路径权重，最终比较得出一条最优路径。如图4展示了源节点13到目的节点4的各条链路权重和转向概率。

1.3 死锁避免

网络通信中死锁的产生是由于网络中存在多个数据包同时转发任务，每个转发任务包都占据了一些链路或缓存资源，又同时请求被其他任务包所占据的通信资源，而形成依赖环。如果此时外界对网络没有给予一定处理，数据包将处于无限时间的等待中，不能得到有效地传送。

图4 最优路径Fig.4 Optimal path

如果节点端口的缓冲区或路由器内部通道资源被占用，都将会造成数据包不能立即转发而处于循环等待，最后形成死锁。第1种情况(第1类)发生在路由器端口用于存储转发的Buf中，称之为缓冲区死锁(buffer deadlock)。当4个相邻的环形节点之间相互连接的链路端口上的缓冲区分别被不同的数据包占用，就会形成第1类死锁，除非丢弃某个数据包或者其中1个任务包转发路径出错，否则死锁一直存在。第2种情况(第2类)发生在采用虫孔交换技术的Mesh型的网络通道中，称之为通道死锁(channel deadlock)。因为虫孔交换技术会把数据包切分成不同的微片以流水线的形式在网络中向前“蠕动”，所以大多时间一个数据包的头微片(head flit)、数据微片(body flit)和尾微片(tail flit)分别存在于不同路由器通道中。如图5所示，有4个数据包的微片同时分别占用了对方的转发通道，形成一个依赖环就会产生第2类死锁。当前避免死锁的技术主要有虚通道技术和转向模型2种。

图5 通道死锁Fig.5 Channel deadlock

死锁预防算法主要针对不同方向的数据包而提供不同的路由性能。此算法优点是逻辑简单、易于实现，而缺点是却存在极大地不公平现象。为了解决此类问题，Chiu提出的Odd-Even转向模型，分别禁止奇数列通信节点上的EN(ES)转向和偶数列上的NW(SW)转向，从而解开依赖环。Odd-Even转向模型解决了在死锁预防算法中禁止同类节点的相同转向而带来不公平。

Up*/Down*路由算法是一种典型的禁止拐弯的模型,它首先是为DEcAutonet网络提出的，是一种适用于规则或不规则拓扑网络的无死锁路由算法，可用源或分布式方式实现,当采用分布式方式实现时,提供了部分自适应性，它给每条链路指派Up或Down方向,把网络配置成无圈的有向图,然后通过禁止消息经过Down方向到Up方向的拐弯(turn),来保证算法无第1类死锁。

在Odd-Even 转向模型的基础上进行改进，当LMM模块检测到4个环形结点的4个缓冲区剩余的内存时隙总数量小于等于阀值权重8时进行转向控制：无故障NoC模块采用Odd-Even的禁止转向；当在故障NoC模块禁止min:wij×pj最小那一转向。本文基于Odd-Even转向模型进行的改进，传统的Odd-Even转向模型是对奇数列和偶数列上路由节点设定了一些特定方向的禁止转向，主要应用于无故障网络和单故障节点无死锁路由中，对区域故障和多故障网络会加大网络拥塞概率，相应的通信延迟也会增加。而本文利用LMM模块对网络通信状况进行检测，无故障区域可以利用Odd-Even 转向模型；在多故障区域发生死锁，可以禁止通信量相对较小的转向，从而减小拥塞程度，预防发生死锁。图6所示10-11-15-14环路链路的总权重值为8，将产生死锁，利用禁止转向方案在有故障节点下禁止最小的SW转向使能。

图6 死锁避免Fig.6 Deadlock free

2 实验与分析

本节概述实验所使用的方法和呈现的性能结果都是在无故障条件下使用CAFR算法得出的。

2.1 衡量性能分析的系数和实验平台

本文评估系数标准采用文献[16]的方法。例如数据包的注入率(packet injection rate ，PIR)指的是数据包注入NoC网路的概率。在NoC中对于给予的任何单节点路由器，每个时钟周期发送数据包的标准数量等于PIR(0

(3)

(3)式中：Rflits表示接收到微片的总数；Nnodes表示节点的总数；Nclk表示产生第一个微片到接收到最后一个微片总的时钟周期。因此，吞吐量是网络在物理处理给定路径的能力时衡量最大负载的一部分。延迟被定义为产生在头微片从源节点注入网路和产生在目标节点接收到最后尾微片两者之间流失的时钟周期数量。如(4)式定义的平均延迟D，它是总信息数量平均值；K是到达目标节点信息的总数量；Di是产生延迟的节点。

(4)

表1列出了评估环境。引用Noxim仿真器对CAFR路由算法性能进行评估。本文的CAFR路由算法使用的仿真平台基于一个2D-mesh系统。为了保证得到精确的结果，仿真在每个PIR点重复运行多次(此处运行5次)。准备阶段和执行阶段循环次数分别是1 000和20 000时钟周期。CAFR路由算法被评估是在各种流量模式下进行的包括①uniform，②transpose，③shuffle。算法的性能评估和数据对比按以下2步骤进行。第1步使用扩展的Noxim软件仿真评估CAFR拥塞感知能力。Noxim整合了DyAD，Odd-even，XY，Negative-first路由算法。标准的模拟器允许所研究的CAFR算法与整合的路由算法在相同的流量条件下进行性能比较。这种评估算法很实用，然而所整合的路由算法都是没有容错性能的。为了验证本算法的容错特性，第2步引进一些优秀的具有容错能力的路由算法进行比较，用来突出本算法在大量通信状态和发生区域性故障条件下，能更好地维持网络的性能，尤其在维持吞吐量方面更为突出。这些用来对比的算法有FoN,Cost，FTDR，FTDR-H，LAFT，HLAFT。

表1 仿真模型具体参数

2.2 网络性能

本节介绍关于CAFR算法与所列的基准算法的性能在不同的流量模式下的仿真结果。图7展示了在均匀分布(Uniform)的流量模式下CAFR算法与所有的基准算法仿真结果后的平均延迟D和吞吐量T数据。从图7a中可以看到CAFR算法和XY路由算法比较其他算法达到一个较低的延迟。图7b中DyAD，Odd-even，XY，Negative-first在注入率PIR分别为0.01，0.014，0.015，0.012处平均吞吐率开始饱和，可CAFR算法却一直保持较好的性能。

图8展示了在Transpose流量模式下的仿真结果。图8a中，在PIR=0.017以后，DyAD，XY和Negative-first算法平均延迟急剧增加。从图8b中可以看出XY和Negative-first算法在注入率PIR=0.07时平均吞吐率分别达到饱和，并且Odd-Even在PIR=0.1处达到饱和。Odd-Even和CAFR算法都在这个流量模式下平均延迟有所变动，但是较其他算法还是具有较高的性能。此外CAFR算法具有较少的拥塞链路和均衡了链路负载的性能。图9是对于在Shuffle流量模式下的平均延迟和吞吐量仿真结果。如图9a中，DyAD，Negative-first和XY算法的平均延迟分别在PIR=0.017和PIR=0.025之间开始增加，图9b吞吐率也在注入率为PIR=0.105和PIR=0.12达到饱和。然而Odd-Even和CAFR算法维持较低延迟和较高的吞吐量。我们应该注意到CAFR算法在各种流量模式下都具有较好的性能。

图7 Uniform流量模式下的性能Fig.7 Performance under Uniform traffic pattern

2.3 容错性能

实验设置了不同程度的故障链路来评估CAFR算法的性能。当系统有故障链路时，4个对比算法的吞吐量将会退减。吞吐量的衰减情况在表2中列出。从表2中可以看出系统在5%～20%故障链路下，所有的路由算法性能都有不同程度的退化。DyAD算法在5%-20%故障链路条件下有23.82%～61.90%的退化；Odd-Even算法有 21.78%～63.85%的退化；Negative-first和 XY算法分别有19.08～63.03%和20.75%～65.25%的退化。然而CAFR算法只有16.88%～44.32%的退化程度，较其他算法其退减较低。当故障率增加，CAFR算法吞吐量有较小衰减，如故障率是15%时衰减是36.04%，故障率为20%时衰减是44.32%。本算法的吞吐量性能较其他4个算法都获得了很大的提升。

图8 Transpose流量模式下的性能Fig.8 Performance under transpose Traffic pattern

图9 Shuffle流量模式下的性能Fig.9 Performance under Shuffle traffic pattern

本算法与其他具有较好容错性能的算法进行了比较。如FoN，Cost，FTDR，TDR-H，LAFT 和 HLAFT作为评估CAFR算法容错性能的基准比较算法。表3是分别来自于文献[16]和[17]中容错算法的吞吐量衰减数据。从表3中可以发现，在故障率为10%和20%时，FoN，Cost，FTDR 和FTDR-H容错算法有48%～70%吞吐量衰减。然而在同样的条件下本算法最高只达到45.12%吞吐量衰减。因此，该结果展现了CAFR算法优于这些基准容错算法。结果也证明了当故障发生时CAFR算法容错性能具有较小的衰减。

表2 在不同流量模式下吞吐量衰减度

表3 CAFR算法与其他容错算法对比

‘N/A’表示数据在作者论文没有呈现

3 结论

本文所提的CAFR拥塞感知容错算法在复杂通信条件下对NoC吞吐性能有很大的改进。该算法采用分布式策略将常规的片上网络架构分为多个由本地监测单元控制的区域，每个本地监控单元检测出所有路径最大权重值得出最优路径，以避免采用拥塞严重的路由器和故障链路，进而降低延迟。最后，算法在应用程序上能估算路由需求而且还能在可利用的资源下均衡通信路径。通过链路权重和节点转向概率方案定义一个最小延迟的输出端口方向；采用嵌入改进禁止转向模型保证了算法的无死锁性。实验结果表明，在无故障下，随着注入率增加该算法在平均吞吐率、平均延迟等性能上和Odd-Even等优秀算法保持在同一水平；在10%～20%故障条件下，其他具有容错能力的算法随着故障概率的提高吞吐量衰减达到48%～70%，而该算法最高只达到45.12%吞吐量衰减。总之，提出的算法在维持网络性能上就有很大的优势。未来研究工作的重点将探索对于可配置系统发生永久性故障后缓存资源如何再分配利用和如何提高路由算法的性能增益。

[1] AGARWAL A, SHANKAR R. Survey of Network on Chip (NoC) Architectures & Contributions[J]. Journal of Engineering Computing & Architecture, 2009, 3(1):1934-1938.

[2] LIU J, HARKIN J, LI Y, et al. Low cost fault-tolerant routing algorithm for Networks-on-Chip[J]. Microprocessors & Microsystems, 2015, 39(6):358-372.

[3] SHAFIK R A, MATHEW J, PRADHAN D K. Introduction to energy-efficient fault-tolerant systems[C]// Energy-Efficient Fault-Tolerant Systems. New York: IEEE,2014： 1-10.

[4] AISOPOS K, DEORIO A, PEH L S, et al. Agnostic Reconfiguration in a Disconnected Network Environment[C]// International Conference on Parallel Architectures & Compilation Techniques. New York:ACM, 2011:298-309.

[5] LI M, ZENG Q A, JONE W B. DyXY-A Proximity Congestion-Aware Deadlock-Free Dynamic Routing Method for Network on Chip[C]// DESIGN AUTOMATION CONFERENCE. New York: ACM/IEEE, 2006:849-852.

[6] LOTFI K P, RAHMANI A M, DANESHTALAB M, et al. EDXY-A low cost congestion-aware routing algorithm for network-on-chips[J]. Journal of Systems Architecture, 2010, 56(7):256-264.

[7] MANEVICH R, CIDON I, KOLODNY A, et al. Centralized Adaptive Routing for NoCs[J]. Computer Architecture Letters, 2010, 9(2):57-60.

[8] RAN M, CIDON I, KOLODNY A, et al. A Cost Effective Centralized Adaptive Routing for Networks-on-Chip[C]// Euromicro Conference on Digital System Design, IEEE Computer Society. New York:IEEE, 2011:39-46.

[9] WANG Y, ZHANG M, XIAO C W. A fault tolerant adaptive routing algorithm in 2D mesh network on chip[J]. Journal of Liaoning Medical University, 2011, 64(4):140-144.

[10] 陈庆强, 罗兴国, 陈韬,等. 一种邻节点状态感知的NoC可重构容错路由[J]. 小型微型计算机系统, 2013, 34(6):1365-1370. CHENG Qinqiang, LUO Xinguo, CHENG Tao.et al. A Reconfigurable Fault-tolerance Routing Algorithm of NoC Based on the Awareness of Status-on-neighbor [J]. Journal of Chinese Mini-Micro Computer Systems, 2013, 34(6): 1365-1370. [11] 张士鉴, 韩国栋, 沈剑良. 基于故障链路缓存再利用的NoC容错路由算法[J]. 计算机辅助设计与图形学学报, 2014, 26(1):131-137. ZHANG Shijian, HAN Guodong, SHEN Jianliang. A fault-tolerant algorithm of NoC based on buffer reuse[J]. Journal of Computer-Aided Design & Computer Graphics, 2014,26(1):131-137.

[12] WANG Y, ZHANG M, XIAO C W. A fault tolerant adaptive routing algorithm in 2D mesh network on chip[J]. Journal of Liaoning Medical University, 2011, 64(4):140-144.

[13] 孙利, 田进华. 片上网络中基于拥塞感知的自适应路由算法[J]. 计算机工程, 2015, 41(8):82-88. SUN Li, TIAN Jinhua. Adaptive Routing Algorithm Based on Congestion-aware in Network-on-Chip [J].Computer Engineering,2015, 41(8):82-88.

[14] LEE D, PARIKH R, BERTACCO V. Highly Fault-tolerant NoC Routing with Application-aware Congestion Management[C]//International Symposium on Networks-On-Chip. New York: ACM, 2015:1-8.

[15] AISOPOS K, DEORIO A, PEH L S, et al. Agnostic Reconfiguration in a Disconnected Network Environment.[C]// International Conference on Parallel Architectures & Compilation Techniques. New York: IEEE, 2011:298-309.

[16] FENG C, LU Z, JANTSCH A, et al. Addressing Transient and Permanent Faults in NoC With Efficient Fault-Tolerant Deflection Router[J]. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(6):1053-1066.

[17] AHMED A B, ABDALLAH A B. Graceful deadlock-free fault-tolerant routing algorithm for 3D Network-on-Chip architectures[J]. Journal of Parallel & Distributed Computing, 2014, 74(4):2229-2240.

(编辑：张诚)

A new congestion-aware fault-tolerant routing algorithm for networks-on-chips

WU Fengyang, LIU Qinrang

(National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450002, P.R. China)

We put forward an effective routing channel selection mechanism to realize the adaptive fault-tolerant routing algorithm with ability of congestion aware on NoC, called CAFR(congestion-aware adaptive fault-tolerant routing algorithm). CAFR algorithm gets the turning probability of each path from the source node to the destination node based on the Up*/Down*routing algorithm; secondly, it gets a weighted link according to the remaining memory time-slot of the endpoint router in each link; finally, the total weight value in each path from the source node to the destination node is calculated according to the weight value of each path and its path turning probability. Experimental results show that the algorithm can maintain a good level on the performance of average latency and average saturation throughput under the condition of trouble-free. Under fault conditions, the algorithm has greatly improved the attenuation of the throughput compared with other algorithms. Especially When the failure rate reach 20%, the algorithm only get 44.32% decay on the throughput, and other fault tolerant algorithms get 48%～70% decay.

networks-on-chips; congestion aware; Up*/Down*routing algorithm; weighted link

10.3979/j.issn.1673-825X.2017.02.005

2016-03-14

2016-06-18 通讯作者：吴凤阳 wufengyang666@163.com

国家自然科学基金(61572520)

Foundation Item：The National Nature Science Foundation of China(61572520)

TN914.53

1673-825X(2017)02-0167-09