基于PRDT的16节点NoC路由算法

网络结构对于片上网络系统的性能和功耗发挥着重要作用，PRDT(2,1)有着较低的网络直径和平均距离、常数的节点度以及良好的可扩展性，这些特点使其非常适于NoC。为了提高小规模PRDT的路由性能，该文提出了一种binary路由算法，当网络规模不大于16时，该算法无须使用虚拟通道即可实现无死锁路由，通过增加少量虚拟通道，可改进为完全自适应路由算法。对所提出的路由算法与原有的向量路由算法进行仿真比较，结果显示binary算法在硬件成本较低的同时，性能更为优异，完全可以应用于基于PRDT的小规模NoC网络。     

Torus网络自适应容错路由算法

在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。     

一类自选网络的容错直径与容错路由算法

作为加利图的一种,自选图AGn相对于其它网络结构,在并行计算及分布式计算领域有着更好的特性,因而受到广泛的重视.ANn是由翼有虎提出的基于AGn的一类新的网络结构.这个新的网络结构在直径、容错度、容错直径和汉密尔顿连通性上都优于网络AGn.虽然该网络结构已经有了较好的非容错路由算法,但是依然没有一种针对这个结构的容错路由算法以完善其实际应用.文中通过研究ANn的性质,得出了容错直径,然后基于该容错直径,设计并实现了ANn容错路由算法,最后验证了该算法的正确性.     

Mesh网络容错广播路由算法的概率分析

One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. This paper proposes a fault tolerant, local-irdormation-based, and distributed broadcast routing algorithm based on the concept of k-submesh-cormectivity in all-port mesh networks.The paper analyzes the fault tolerance of the algorithm in terms of node failure probability. Suppose that every nodehas independent failure probability, and deduce the success probability of the broadcast routing, which successfully routes a message from a source node to all non-faulty nodes in the networks. The paper strictly proves that the broadcast routing algorithm with the success probability of 99％ to route among all non-faulty nodes on mesh networks with forty thousand nodes, in case that the node failure probability is controlled within 0.12％ Simulation results show that the algorithm is practically efficient and effective, and the time steps of the algorithm are very closeto the optimum.     

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

为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法。该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up^*/down^*算法确定路由路径。此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁。在6×6 Mesh网络中,RFTR算法能减少25%的路由表资源用量。仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up^*/down^*算法和segment算法相当甚至更优的性能。     

一种适用于2D Mesh片上网络的可重构容错路由算法

适用于2D Mesh片上网络的可重构容错路由算法,在芯片某些区域由于制造缺陷、使用老化等原因拓扑结构变得不再规整的时候,可以对网络节点重新进行配置,从而保证健康节点间的正常通信.基于SystemC的平台仿真表明该算法相对于传统算法可以获得更佳的网络性能.该算法是免于死锁的,同时对其可重构机制也给出了详细的论述.它还具有良好的扩展性,当系统规模增大的时候每个路由器的硬件开销保持恒定,而其容错能力也得到了增强.     

一种适于最佳双环网的容错路由算法

本文提出了一种新的适用于C.S.Raghavendra等人提出的最佳双环网的容错路由算法,并证明了该算法总能导致信包传递沿着一条最优的路径。     

二维mesh上的自适应容错路由算法

基于故障块模型提出了二维ｍｅｓｈ上的自适应无死锁容错路由算法。该算法将网络分为两个虚拟网络ＶＩＮ０和ＶＩＮ１。消息根据源与目的节点的相对位置判断进入哪一个虚拟网络。消息在没有遇上故障时经由最短路径路由。算法的容错技术是基于故障环和故障链的概念。最后,将该算法与另一个二维ｍｅｓｈ上的容错路由算法ｆ－ｃｕｂｃ２进行性能比较。     

VTFTR：高维胖树中的无死锁容错路由算法

随着近年来高性能计算系统规模的急剧扩大,高性能互连网络的可靠性成为愈发重要的问题。高维胖树是一种结合了胖树与多维环网优点的网络拓扑结构,凭借其良好的可扩展性与网络性能在E级时代具有广阔的应用前景。然而,目前关于高维胖树中容错路由算法的相关研究较为有限,其可靠性问题亟待解决。为提高高维胖树拓扑在高性能互连网络中的容错能力,进一步提高对应超算系统的运行效率,提出一种用于高维胖树中叶交换机故障的容错路由算法VTFTR。该算法结合转向模型与虚通道切换的思想,通过严格控制报文在无故障路径与容错路径中的转向,使用少量的容错虚通道与额外跳步实现高维胖树中的无死锁容错。实验结果表明,在单点故障情况下,VTFTR算法的容错路径较对比算法有2~4个跳步的减少,在4 096个节点规模的网络中,当叶交换机故障数量为10时,在故障叶交换机不同的分布情况下,该算法能够以1.4%~2.0%的吞吐率下降作为代价来保持全网无故障节点之间的互连。     

基于前缀的片上网络容错源路由算法

为克服片上网络链路永久性错误带来的路由问题,提出一种基于前缀的片上网络容错源路由算法PFTSR。该算法适用于二维mesh片上网络,采用预测路径并根据反馈信息调整路径的方法进行路由探测。在仿真平台NIRGAM上进行仿真,实验结果表明,与传统片上网络容错源路由算法SRN相比,PFTSR极大降低了片上系统的功耗,并且在大多数情况下能减少探测到第一条路径的时间。     

A survey of routing algorithm for mesh Network-on-Chip

With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on-chip interconnection. Under such background, Network-on-Chip (NoC) is proposed and gradually replacing the traditional on-chip interconnections such as sharing bus and crossbar. For the convenience of physical layout, mesh is the most used topology in NoC design. Routing algorithm, which decides the paths of packets, has significant impact on the latency and throughput of network. Thus routing algorithm plays a vital role in a wellperformed network. This study mainly focuses on the routing algorithms of mesh NoC. By whether taking network information into consideration in routing decision, routing algorithms of NoC can be roughly classified into oblivious routing and adaptive routing. Oblivious routing costs less without adaptiveness while adaptive routing is on the contrary. To combine the advantages of oblivious and adaptive routing algorithm, half-adaptive algorithms were proposed. In this paper, the concepts, taxonomy and features of routing algorithms of NoC are introduced. Then the importance of routing algorithms in mesh NoC is highlighted, and representative routing algorithms with respective features are reviewed and summarized. Finally, we try to shed light upon the future work of NoC routing algorithms.     

双层二维网格结构间的Wormhole路由算法

二维网格结构由于其较好的可扩 展性而被越来越广泛地应用,因此对于二维网格结构多处理机间的数据通信,寻找一个好的路由算法也越来越重要。以Intel公司的Option Red机器为背景,分析了双层二维网格结构多处理机间的通信机制,并且针对该实际结构,根据单层二维网格结构中以Wormhole原理为基础的Unicast自适应路由算法,提出了适用于双层二维网格结构的无死锁的Wormhole路由算法。根据该算法得出的数据传输路径是无死锁的最短传输路径。     

面向农业应用的WSNs路由恢复算法

无线传感器网络(WSNs)作为现代重要的信息技术之一,在农业生产领域具有广阔的前景.以灌溉系统为具体应用场景,提出一种基于WSNs的农业应用设计方案,设计方案包括灌溉系统的总体设计、硬件设计和软件设计.还针对因节点故障导致的路由链路中断问题设计了WSNs的路由恢复算法,并对这种路由恢复算法进行了仿真.仿真表明:这种路由恢复算法传输的包数量比动态源路由(DSR)协议更少,可以有效降低节点的能耗.     

基于混合遗传算法的QoS多播路由算法

具有多QoS约束的多播路由问题具有NP完全的复杂度。基于延时、延时抖动、带宽、丢包率等QoS约束,描述了一种适应于研究QoS多播路由的网络模型,提出了基于遗传算法和禁忌搜索混合策略的具有多QoS约束的多播路由算法。该算法充分利用了遗传算法和禁忌搜索的优点。克服了遗传算法在求解多QoS约束多播路由问题中的爬山能力差以及不成熟收敛等问题。仿真实验结果表明,该算法为多QoS约束多播路由问题的求解提供了一种有效的新途径。     

Performance evaluation of mesh-based NoCs: Implementation of a new architecture and routing algorithm

This paper presents the result of experiments conducted in mesh networks on different routing algorithms, traffic generation schemes and switching schemes. A new network on chip (NoC) topology based on partial interconnection of mesh network is proposed and a routing algorithm supporting the proposed architecture is developed. The proposed architecture is similar to standard mesh networks, where four extra bidirectional channels are added which remove the congestion and hotspots compared to standard mesh networks with fewer channels. Significant improvement in delay (60% reduction) and throughput (60% increase) was observed using the proposed network and routing when compared with the ideal mesh networks. An increase in number of channels makes the switches expensive and could increase the area and power consumption. However, the proposed network can be useful in high speed applications with some compromise on area and power.     

基于量子遗传算法的QoS路由算法

多约束的QoS路由问题是NP完全问题.量子遗传算法是基于量子计算理论的新遗传算法,具有种群多样性、收敛速度快和全局寻优的特点.将量子遗传算法引入多约束QoS路由计算,提出了一种基于量子遗传算法的QoS路由算法,给出了算法实现的方法和具体流程.实验结果表明,通过该算法得到的QoS路由不但能满足QoS约束要求,同时可以均衡链路负载,减少路由拥塞.     

拥塞敏感的无线传感器网络路由算法

如何延长无线传感器网络的生命周期是一个重要的挑战.提出了一种新的拥塞敏感的路由算法,该算法充分考虑了路由选择过程中的数据负载与邻节点的缓存、信道竞争等状态的关系,每个节点以此计算一个能反映本地拥塞状态的权值,节点选择权值最高的下游节点作为下一跳来平衡下游节点的能耗和数据负载,同时降低下游节点的拥塞可能性.模拟实验表明:...     

基于遗传策略的过多指定点路由算法的研究

提出了一种求解移动IP中过多指定节点的最短路由问题的分层遗传算法。通过对已有的求解路由模型进行分析,建立了通过多个指定节点的网络模型;根据所给的指定节点来划分解的可行域的层次,来求解移动IP的最短路由问题;该算法采用了可变长度染色体的编码方法,并使用了随机遍历抽样的选择方法,根据网络的拓扑信息进行交叉和变异操作,同时使用修正函数以消除遗传操作中产生的不可行解。各个子种群间独立地并行运行遗传算法,最后得到一条经过多个指定节点的最短路由。并建立随机网络拓扑对该算法进行仿真,实验结果表明,该算法能够有效地求出通过多个指定节点的最短路由,并且受网络规模和问题的复杂性影响比较小。     

基于用户体验评价模型的最优路由选择算法

网络视音频业务的兴起使网络运营商和服务提供商更加关注视音频的用户体验（QoE）,而传统的路由算法只能保证所选路径的服务质量（QoS）参数,如延迟、抖动等满足QoS约束的需求,并不能直接反映QoE的信息,从而不能保证所选路径满足QoE需求。基于QoE评价模型,给出以QoE为目标的最优路由选择算法。通过分析QoE表征参数与传统QoS参数的关系,利用QoE表征参数可分解性和QoE表征值非递减性两个性质,给出多项式时间复杂度为O(V log V+E)的QoE_DSP算法。实验和分析表明,该算法能保证所得路径满足QoE需求,同时具有良好的计算扩展性。     

一种抗干扰半静态分簇路由算法

针对无线传感器网络( WSNs)分簇路由算法中的能量洞、热点和抗干扰问题,设计一种抗干扰半静态分簇( AlSSC)路由算法,给无线传感器网络提供能量多、距离短、链路质量好的路径来传输数据.该算法利用节点定位获取节点地理位置,综合考虑传感器节点剩余能量和干扰信噪比,通过节点距离度量、节点聚簇、簇间融合、簇头选举和簇头轮换五个步骤进行无线传感器网络节点的分簇.仿真结果表明:这种路由算法可以提高无线传感器网络通信链路质量,均衡网络能量消耗.