Design and simulation of a Torus topology for network on chip

Aiming at the applications of NOC （network on chip） technology in rising scale and complexity on chip systems, a Torus structure and corresponding route algorithm for NOC is proposed. This Torus structure improves traditional Torus topology and redefines the denotations of the routers. Through redefining the router denotations and changing the original router locations, the Torus structure for NOC application is reconstructed. On the basis of this structure, a dead-lock and live-lock free route algorithm is designed according to dimension increase. System C is used to implement this structure and the route algorithm is simulated. In the four different traffic patterns, average, hotspot 13%, hotspot 67% and transpose, the average delay and normalization throughput of this Torus structure are evaluated. Then, the performance of delay and throughput between this Torus and Mesh structure is compared. The results indicate that this Torus structure is more suitable for NOC applications.

Torus网络中分布式自适应路由算法

基于转向模型提出适用于Torus网络的3种分布式自适应路由算法.算法将物理网络逻辑上分为虚网络,分组路由按照预定的规则使用不同的虚网络,从而达到无死锁,无活锁的目的.在二维Torus网络中实现这3种算法,仅需3条虚信道,这是目前Torus网络中实现无死锁自适应路由所需虚信道数目的最小值.对所提算法的性能采用OPNET软件进行仿真,拓扑采用8×8 2D Torus.结果表明,与广泛用于实际系统的维序路由算法相比,这3种算法具备自适应性,在不同流量配置下都能提高网络的时延吞吐性能.

Torus连接Petersen图互连网络及路由算法

可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素。基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络。该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性。网络节点采用混合编码方法,使得路由算法设计简单。分别设计了基于混合编码的单播、广播路由算法。分析表明提出的互连网络具有较好的拓扑性质。

用Torus网络构建可扩展分组交换结构的设计方案

提出了一种采用Torus网络技术的模块化交换子网结构——可配置单板(CB),给出了应用CB模块构建可扩展交换结构的具体设计方案,并讨论了关键设计参数的取值。该方案支持交换端口数与交换容量数百倍的平滑扩展。仿真实验结果验证了该方案的可行性。

Torus网络中基于中心距离的完全自适应路由算法

Torus网络凭借其优越的结构特性,引起了工业界和学术界的广泛关注.高效、无死锁的路由算法设计是互连网络研究的一个重要方面.针对Torus网络实现自适应路由所需虚通道数目多的缺点,提出了自适应路由算法Gear,该算法基于中心距离的方法来限制虚通道的使用,在虚切通交换下仅需两条虚通道即可为Torus网络提供无死锁自适应路由.通过仿真对所提算法的有效性进行了验证,结果表明,在同等情况下算法Gear的性能较经典的维序路由和Duato协议具有非常明显的优势.

Torus网络中基于标志位的容错路由

针对Torus结构的多处理机系统中容错路由的问题,提出标志位概念,给出一个基于标志位的容错路由算法。存储于Torus网络中各节点的标志位记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路。标志位的赋值可以通过与邻节点间的信息交换完成。

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

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

基于FPGA的2D-Torus片上网络无死锁路由算法

片上网络的拓扑结构和路由算法直接影响片上网络的传输延迟和传输效率.基于2D-Torus拓扑结构,提出了一种新的片上网络无死锁路由算法.通过改变数据包在片上网络路由过程中受限制转弯的位置,保证片上网络的自适应路由条件,从而有效降低片上网络的延迟.在FPGA硬件平台上,设计并实现了基于该路由算法的2D-Torus片上网络,并对其进行测试.实验结果表明,基于该路由算法的片上网络,可以满足片上网络多方向数据通信及多路数据并行通信等性能要求.

Torus网络中容错路由算法的设计与概率分析

基于k-Torus子网的概念提出了一个简单的Torus网络容错路由算法。假设结点出错相互独立,计算出路由算法成功路由的概率。对于几十万个结点以上的Torus网络,提出的路由算法构造通路的概率可达99%,且所提出的路由算法具有线性的特点。

具有失效结点2D-Torus网络可靠性研究

结合2D-Torus网络的特点,以3×3Torus为例采用markov过程建立结点失效独立和结点失效相关条件下的网络可靠性模型.通过建立markov状态空间图并进行求解得出可靠性模型的数学表达式,计算出网络的可靠度.通过对模型的仿真表明:网络规模越大,可靠性越低;结点失效相关时的网络可靠性要比结点失效独立时的网络可靠性低.

Torus拓扑结构的双端口NoC模型与性能分析

为了充分利用片上网络的并行通信能力,挖掘网络带宽利用率,设计了一种高性能的双端口片上网络。该网络中每个路由节点提供两个本地端口,每个资源节点采用对角线的方式接入到网络中两个路由节点上,并针对这种接入结构提出一种目的节点切换方法用于提高网络的并行通信能力。同时,为进一步提高新路由结构的性能,将双端口路由节点引入Torus结构,构造了基于Torus的双端口网络的模型,并对其进行性能评估。实验结果表明,基于Torus结构的对角线双端口NoC在单目事物实验中较单端口网络平均吞吐量和平均包延迟最大改善了83.3%和55.9%,在双目事物实验中较同一维序双端口网络平均吞吐量和平均包延迟最大改善了91.1%和54.3%。

基于递推分解的Torus网络可靠性研究

为解决大规模Torus网络可靠度计算中遇到的NP难问题,引入递推分解和组合模型的思想对Torus网络的可靠性进行分析研究。递推分解的算法降低了计算网络可靠度的复杂性,组合模型的方法则降低了网络的结构复杂度。对于大规模的Torus网络,通过采用可靠度上下界逐步逼近的方法,可以得到较高精度的可靠度近似值。实验结果表明,在结点失效概率均小于0.10%时,对多达上千个结点的Torus网络仍超过90%的可靠度,而且提出的方法也适合其它并行体系结构网络的可靠度计算。

基于SD-Torus网络的分布式IP地址查找

针对IP路由器的FIB(Forwarding Information Base)极限问题和分布式IP地址查找中的通信延迟问题,提出了SD-Torus(Semi-Diagonal Torus)直连网络。按照"临近存储"的原则,将路由表划分后存储在每个节点及其邻居节点上,以减少分布式IP地址查找中的通信延迟,提高整体的查找性能。在分析SD-Torus网络拓扑性质的基础上,提出了一种负载均衡的路由算法。基于SystemC的仿真结果表明,使用该结构可以大大降低分布式IP地址查找的通信延迟,提高系统的扩展性。该研究结果可以应用于高性能的分布式IP地址查找。

基于Petri网多核映射任务分析及在torus架构中的应用

多核任务映射是高性能计算领域的研究热点。基于torus互连的多核架构,本文提出了行资源映射和行优化资源映射两种算法,行资源映射算法首先以torus的最左边位置作为起点映射,然后按入度值从大到小的次序依次映射其后继,每映射完一个后继就映射其相应的前驱,以此类推,映射完所有的节点。行优化资源映射首先把出度最大的点放在torus最左边位置,把入度最大的点放在torus同一行最右边位置,然后映射出度最大的点的其他后继和入度最大的点其他前驱,以此类推,映射完所有的节点。利用时延petri网软件工具包对两种映射方法进行了分析和比较,实验结果表明,基于相同的循环任务数据流图和硬件架构,行优化资源映射算法获得的吞吐量是行资源映射算法的2倍,并且每个映射块运行时间减少近似一半,行优化资源映射算法具有合理性和可行性。

直线引导的Torus结构路由算法

为了提高片上网络在Torus拓扑结构下的路由通信效率,提出了一种基于直线引导思想的路由算法Tline。该路由算法将Torus拓扑结构的片上网络拓展为类似Mesh结构的坐标平面,以数据包的源节点和目的节点构成的直线为路由转发方向,并根据周围邻近节点的拥塞状况选择传输路径方向实现部分自适应路由。实验结果表明,与XY、OE路由算法相比,在热点流量模式下Tline路由算法具有较好的路由性能,且平均能耗降低约8%。

Torus结构的芯片上光互连网络损耗分析和优化

基于硅基波导、十字状波导交叉和基于波导微环的光交换器件的损耗特性,对Torus结构的芯片上光互连网络建立了损耗模型,利用该模型来对芯片上光互连网络进行光器件级、光路由器级和网络级的损耗特性分析,同时建立芯片上光互连网络损耗自动分析系统.依据该系统可以得到不同网络规模下的最大损耗,并分别分析了基于Crossbar、Cygnus和Crux路由器的torus结构网络的损耗特性.传输损耗随着网络规模的扩展而增加,最小的传输损耗出现在M=N时.同时,可以得到采用Crux路由器构成的芯片上光互连网络的传输损耗最小,小于Cygnus构成的芯片上光互连网络约5 dB.

一种混合Ring-Torus层次化片上网络拓扑结构

针对大规模平面片上网络延迟急剧增加的问题,提出一种混合Ring-Torus(RT)拓扑结构。RT结构融合环形结构和Torus结构的特点,簇内采用环形连接,用于临近通信;簇间采用Torus结构连接,用于远端节点通信,有效降低平面片上网络的延迟。同时提出适用于RT结构的基于方位判断的最短路径算法,解决拓扑结构中的死锁问题。通过仿真验证,RT结构的延迟在16点和64点网络规模低于Mesh结构,仅在64点低注入率下略高于CMesh结构,同时RT结构的饱和点分别比Mesh和CMesh结构右移11.1%和47.1%。

恰有2个内度的2维Torus网络的定向图

设G是一个简单图且D是G的一个定向图.若对D中任意顶点x,d-(x)=a或b,则称G是[a,b]可实现的.主要研究了2维Torus网络中[a,b]可实现的充要条件.设H=Torus(p,k)是一个2维Torus网络,其中p和k是2个不小于3且奇偶性相同的正整数.设0≤a,b≤4,则H是[a,b]可实现的当且仅当存在非负整数s和t使得s+t=kp且as+bt=2kp.

基于OPNET的分级扭Torus结构的设计与实现

对互连网络中Torus拓扑结构的链路利用率低和负载不匀衡问题,本文提出了一种新的分级互连网络结构——RTTM网络拓扑结构。该拓扑结构分为N级,第1级由2m×2m个节点的Mesh拓扑结构构成,第2级到第N级由a×2a个节点的长方形扭Torus拓扑结构以递归方式连接而成。本文在OPNET的建模环境下分别完成了RTTM网络拓扑结构的两级建模,第一级由4×4个节点的Mesh拓扑结构构成,第二级由4×8个节点的扭Torus拓扑结构构成。仿真结果表明RTTM网络拓扑结构链路利用率高,端到端延迟小,吞吐量大。

一种基于Torus网络的高效随机Oblivious路由算法

一个好的路由算法应同时满足:最小的路由跳数以减小传输延时,保持通讯的局域性;最大的平均情况和最坏情况吞吐率;简单的路由器结构。随机Oblivious路由算法在低功耗并行计算机互联网络以及片上网络中得到广泛应用。针对Torus网络下已提出的Oblivious路由算法所需虚通道数目多的缺点,提出了随机Oblivious路由算法WRD,该算法仅使用两条虚拟通道即可实现算法的无死锁性。通过仿真对所提算法的性能进行了验证,结果表明,该算法与使用两条虚拟通道的O1TURN路由算法相比,WRD路由算法在所有通讯模式下的网络吞吐率均有所提升。与使用四条虚拟通道的RLB算法相比,新提出的WRD路由算法性能接近于RLB算法,甚至在多个通讯模式下的网络吞吐率要好于RLB算法,而且WRD路由算法仅使用两条虚拟通道,降低了网络系统成本和功耗。