二维DMesh网络中基于转弯模型的无死锁路由算法研究

王新玉

（东北财经大学 管理科学与工程学院，辽宁 大连 116025）

0 引 言

互连网络目前被广泛应用于各个领域，如超大规模集成电路、电话网络、计算机网络、多核系统、超级计算机、工作站、集群等。随着半导体工艺水平的发展，互连网络的应用领域持续拓展，如汽车的整车控制系统需要一个互连网络将车内的微处理器和设备连接起来。互连网络的性能需求和开销限制随着具体的应用而变化，如在多机系统中，互连网络的性能和可靠性至关重要，而在分布式共享存储器多机网络中，可扩展性被放在设计的首位［1］。

在许多的应用领域，互连网络上通信资源间的带宽需求持续增加，例如，在多媒体领域的视频应用中，处理器核之间的聚合通信带宽需求已经增加到G字节／秒的数量级，并且这种需求还在增加，相信在不久的将来，这种需求将会增加到更大的量级。随着操作频率的不断提高，计算机核的处理速度不断提高，互连网络的通信速度（而非计算速度）成为整个系统的性能瓶颈［2］。为了提高系统的性能，为互连网络设计一种低延迟、高吞吐量的路由算法是迫切并且有意义的［3－4］。

互连网络研究主要包括3个方面的内容：拓扑结构设计、路由算法设计和流控机制。在众多的网络拓扑结构中，Mesh／Torus网络具有很好的可扩展性，且符合平面特性、链路较短、易于实现，被广泛应用于实验机器系统和商用机器系统中，因此前人在低阶网络中的研究较多［12－14］。然而，随着通信需求的增加，路由器的阶数（Radix）直接决定了网络拓扑直径和平均距离的下界，此时传统的2DMesh和Torus网络不能满足要求需求，高阶网络被提出［5，15］，并成为互连网络研究的热点。

在增加路由器阶数的基础上，为了降低网络拓扑直径和平均距离，前人提出了许多不同的拓扑结构［6－11］。在众多的高阶网络拓扑结构中，与其他拓扑结构不同，DMesh结构保持了低阶Mesh网络的优势（物理链路短、易于布局布线），同时有效降低了网络的拓扑直径和平均距离。路由算法设计分为确定性路由和适应性路由两大类，其中，确定性路由机制简单，但是由于未考虑消息传输的灵活性，性能较差；而适应性路由算法路由过程中会考虑网络中负载的状况，为消息提供更多的可选择的路径，有利于减少报文之间的竞争，从而降低网络的平均延迟，提高吞吐量。文献［10］中只分析了确定性路由算法DXY，本文将基于转弯模型（turn model），设计出适用于DMesh网络的适应性路由算法，以提高网络的性能。

1 预备工作

在互连网络中，拓扑结构可以用图G（V，E）来表示，其中V代表节点的集合，E代表边的集合。对于∀v∈V，表示网络中的一个路由器，对于∀e∈E，表示网络中的一条物理链路，即它所连接的2个路由器之间有直接的物理链路相连。

1.1 定义与符号

定义1 一个n×n的二维DMesh网络中有n2个节点，本文将横轴称为X维，纵轴称为Y维，则该DMesh的图G（V，E）可以表示如下：

图1 一个8×8的DMesh网络拓扑结构

式（1）中可以看出，DMesh网络的节点集与Mesh网络中的节点集相同，而DMesh网络的边集是Mesh网络中边集的超集，其中，E1表示 Mesh网络中的边集，E2表示y＝x方向和y＝－x方向上的边集。图1给出了一个8×8的DMesh网络。

1.2 DMesh网络中的DXY算法

互连网络通信是通过发送消息来实现的。在DMesh网络中，DXY路由算法总是优先选择对角线方向上的输出通道，当且仅当对角线上的偏移为0时，此时消息至少在X或Y某一个方向上的偏移为0。之后，消息沿着偏移不为0的方向进行路由，当且仅当消息在X方向和Y方向上的偏移均为0时，消息到达目的节点，完成一次传输过程。由于该算法是本文所提出算法的比较对象，表1给出了具体的算法描述。

表1 DMesh网络中的DXY路由算法

2 基于转弯模型的路由算法设计

转弯模型最早是在Mesh网络中提出的，通过限制消息的转弯行为，达到死锁避免的目的。本文将其应用到DMesh网络中，设计出一种适应性路由算法，从而充分利用DMesh网络提供的路径多样性，最终提高互连网络的通信性能。

2.1 基于转弯模型的路由算法描述

在DMesh网络中，每个路由器有9个输入输出端口，其中8个用来连接邻居路由器，1个用来连接本地的计算单元。根据方向的正负，可以将输出端口划分为2大类，分别为｛X＋，Y＋，C＋，T＋｝和｛X－，Y－，C－，T－｝。为了便于说明，本文将X＋，Y＋，X－，Y－方向的输出通道称为Regular通道，而C＋，T＋，C－，T－方向的输出通道称为Crossing通道。负向优先是一种应用较为普遍的基于转弯模型的死锁避免机制，由于C和T方向的输出通道直接影响X和Y方向上的偏移，负向优先思想不能直接在DMesh网络中应用，需要进行特殊处理。

表2 DMesh网络中基于转弯模型的路由算法

表2给出了基于转弯模型的路由算法 （Turn Model Based Routing，TMBR），当前路由器的坐标（cx，cy）和目的路由器的坐标（dx，dy）作为算法的输入，而一条可选择的输出通道作为算法的输出。首先计算消息在2个方向上的偏移，分别记为offx和offy。若offx和offy重只有一个偏移为0，则消息沿着偏移不为0的方向进行路由（算法中的步骤3，步骤9，步骤11，步骤12）。若offx和offy都大于0，则消息可以沿着X＋，Y＋和C＋3个方向进行路由（算法中的步骤2）；类似地，若二者都小于0，则消息可以沿着X－，Y－和C－3个方向进行路由（算法中的步骤10）。若offx大于0而offy小于0，则消息沿着Y－和T－方向进行路由，遵循负向优先原则，不能走X＋方向（算法中的步骤4）。若offx小于0而offy大于0，为了保证消息的正常传输，需要考虑2个方向上剩余跳步数，若X方向上的剩余跳步数大于Y方向＞），消息沿着X－方向路由；若2个方向上的剩余跳步数相同，消息沿着T＋方向路由；若Y方向上的剩余跳步数大于X方向，消息可以沿着T＋和Y＋两个方向路由（算法中的步骤5～8）。若2个方向的偏移均为0，消息到达目的节点，通过本地输出通道传送给上层应用的计算单元，标志着一次通信的结束。

在表中给出了一个Select函数，该函数是从可选择的多个输出通道中为消息选择一条空闲的输出通道。为了充分利用C和T通道降低消息传输的跳步数，当空闲的输出通道中同时包含通道Regular和Crossing通道时，Crossing通道的优先级要高于Regular通道。

2.2 路径多样性分析

在互连网络中，拓扑结构为计算单元之间的通信提供了一个基础框架，而路由算法则决定了消息在网络中传输行为。一个好的路由算法能够在无死锁和无活锁的约束下，充分挖掘消息传输路径的多样性，本节将对DXY和TMBR两种路由算法中的路径多样性进行分析。

从单个路由器上来看（见表2），2类消息有3条可选择的输出通道，6类消息有1条可选择的输出通道，2类消息有2条可选择的输出通道。从整个网络来看，消息可选择的路径数是消息在每一步骤上可选择输出通道数目的积。以8×8的DMesh网络为例，假设消息M1的源节点为（0，0），目的节点为（1，5），则TMBR为该消息M1提供9条可选择的路由路径；另外，假设消息M2的源节点为（4，4），目的节点为（6，0），则TMBR为该消息M2提供5条可选择的路径；不论何种情况下，DXY总是为消息提供唯一的一条路径。

上述分析可知，TMBR为消息路由提供了更多的灵活性，当网络中的负载量较高时，有利于消息绕开拥塞区域和热点路由器，降低消息传输的等待延迟，从而提高网络的通信性能。

2.3 无死锁证明

死锁避免是互连网络设计中是一个非常棘手的问题。因此，在设计一个网络之后，必须为该网络设计相应的无死锁路由算法。本节将给出TMBR路由算法在无死锁方面的证明。

定理1 针对DMesh网络提出的TMBR路由算法是无死锁的。

证明 在DMesh网络中，通道划分为2类，分别为S1＝｛X＋，Y＋，C＋，T＋｝和S2＝｛X－，Y－，C－，T－｝。从表2可以知道，从S1中通道到S2中通道的依赖关系是不存在的。根据转弯模型理论［16］，笔者分别证明顺时针方向和逆时针方向的环形通道依赖不存在，从而证明TMBR算法无死锁。

图2 TMBR算法中产生的通道依赖转弯

根据Mesh网络中负向优先算法可知，TMBR路由算法中，通道集｛X＋，Y＋，X－，Y－｝不会形成死锁。在Crossing通道之间不会产生通道依赖关系，因此，通道集｛C＋，T＋，C－，T－｝内部也不会形成死锁。假设TMBR中存在死锁，则必然在图2a中有Crossing通道实现X＋到Y－的转弯（有T－通道参与），或者在图2b中有Crossing通道实现Y＋到X－的转弯（有T＋通道参与）。

假设有T－通道参与，则需要两种通道依赖关系的支持，分别为Y＋→T－和T－→X－，根据前面的结论（S1中通道到S2中通道的依赖关系是不存在的），前一种通道依赖关系不存在，因此相应的环也不存在。同样地，可以证明有T＋通道参与时，相应的环也不会存在。假设不成立，即TMBR中不存在死锁。

综上，本文中提出的针对DMesh网络基于转弯模型的路由算法TMBR是无死锁的。

3 实验结果分析

为了验证本文提出的TMBR路由算法的性能，实验基于C＋＋软件模拟一个微片级的二维互连网络仿真平台，搭建了一个8×8的DMesh拓扑结构，作为互连网络中不同计算单元通信的基础架构。

3.1 实验配置

采用文献［17］中的方法，将消息长度设置为5。在路由器建模方面，采用四级流水线结构，分别为缓冲区写操作、路由计算、交换开关分配、交换单元内部传输等，微片每经过一个流水线需要一个时钟周期。为了更加直观地评价TMBR算法，选择DXY算法作为比较的对象，通过比较二者在同一个模拟器下的性能，来验证TMBR算法在高效利用路由路径的灵活性实现高性能路由方面的改进与提高。

模拟器中的路由器采用虫孔交换机制，因为该机制所需要的虚拟通道的数目最少，硬件开销最小。在未特殊说明的情况下，虚拟通道数目为2，缓冲区的深度为2flits，采用先进先出机制。为了更加准确的收集结果信息，模拟开始的20 000个时钟被忽略，目的是将网络引导到一个稳定的状态，接下来的80 000个时钟周期用于结果收集。

实验中采用平均延迟（average latency）来衡量算法性能。延迟是指从消息开始发送开始、直到被目的节点接收为止所经历的时间。在一定的消息注入率（packet injection rate）条件下，较低的延迟意味着该算法具有更好的性能。

实验采用置换通信模型（permutation traffic pattern）来检验算法的性能：在置换通信模型中，节点A只能与某个特定的节点B进行通信，其中A和B的节点坐标满足某个特定的函数，最为常用的一种置换通信模型有对位传输通信模型（transpose traffic pattern），文献［18］中有对于这种通信模型的具体描述。

3.2 实验结果及讨论

图3 在4×4的DMesh网络中TMBR与DXY性能比较

本节中从网络规模和虚拟通道数目等2个不同的方面对2个算法进行比较。图3给出的是网络规模为4×4的情况下TMBR与DXY的延迟曲线。从图中可以看出，当消息注入率低于0.28（flits／node／cycle）时，二者的网络平均延迟相当，当消息注入率继续增加时，TMBR的性能要优于DXY，从网络饱和点来看，TMBR的网络饱和点较DXY提高了21.4%。

当网络规模增加至8×8时，比较2类算法的平均延迟，如图4和图5所示。当虚拟通道数目为2，缓冲区深度为2时，图4给出了延迟随消息注入率的变化曲线，显然，当消息注入率低于0.15（flits／node／cycle）时，二者相当，高于0.15（flits／node／cycle）时，TMBR的性能要优于 DXY。当消息注入率为0.16（flits／node／cycle）时，DXY 和 TMBR的平均延迟分别为109.18和28.15（cycles），此时TMBR将网络平均延迟降低了74.2%。

图4 在8×8的DMesh网络中TMBR与DXY性能比较

图5 虚拟通道数目增加至4时DMesh网络中TMBR与DXY性能比较

图5给出了虚拟通道数目为4，缓冲区深度为1时的性能比较，当消息注入率低于0.17（flits／node／cycle）时，采用2个算法的网络中平均延迟不相上下，当消息注入率持续增加时，显然TMBR的性能优于DXY，以消息注入率为0.18的网络状态为例，TMBR和DXY的网络平均分别为32.11和43.91，网络性能提高了约26.9%。

与DXY路由算法相比，本文中提出的基于转弯模型的TMBR算法能够很好地适应网络规模和虚拟通道数目的变化。

4 结 论

DMesh网络是在Mesh网络的基础上，每个路由器上端口数增加了一倍而得到的一种新的网络拓扑结构。路由算法是决定网络性能的关键因素之一，设计好一种网络拓扑结构之后，为之设计高效无死锁自适应路由算法是提高网络性能的重要方面。本文基于转弯模型的理论，通过限制部分通道转弯方法，为DMesh网络设计了无死锁自适应路由算法TMBR，这种新的路由算法充分考虑了DMesh网络提供的路由路径的多样性，在为消息提供路由路径时加入了适应性因素，能够有效地避开拥塞区域。仿真实验表明，在同等条件下，与DXY相比，算法TMBR取得了较好的性能改善，且具有更低的网络平均延迟，以及更高的网络饱和点。

在虫孔交换网络中，由于一个消息可以同时占用多条连续的通道，从而使得无死锁路由算法的设计更加困难。在后续工作中，将负载均衡因素考虑到算法设计中，如何进一步整个网络中路由器资源和物理链路资源的使用仍然是一个值得继续研究的课题。

［1］GROT B，WECKLER S W.Scalable On－Chip Interconnect Topologies［C］∥Proceedings of 2nd Workshop on Chip Multiprocessor Memory Systems and Interconnects.New York：Institute of Electrical and Electronics Engineers Incorporation，2008：1－11.

［2］FLICH J，BERTOZZI D.Designing network－on－chip architectures in the nanoscale era［M］.Boca Raton：Chapman and Hall／CRC，2011.

［3］FU Binzhang，HAN Yinhe，MA Jun，et al.An abacus turn model for time／space efficient reconfigurable routing［C］∥Proceedings of International Symposium on Computer Architecture.New York：Institute of Electrical and Electronics Engineers Incorporation，2011：259－270.

［4］YU Zhigang，XIANG Dong，WANG Xinyu.VCBR：virtual channel balanced routing in torus networks［C］∥Proceeding of International Conference on High Performance Computing and Communications.Piscataway NJ：IEEE Computer Society，2013：1359－1365.

［5］SCOTT S，ABTS D，DALLY W.High－radix interprocessor communications system and method：U.S.Patent 8，184，626［P］.2012－05－22.

［6］KIM J，BALFOUR J，DALLY W J.Flattened butterfly topology for on－chip networks［C］∥Proceedings of International Symposium on Microarchitecture.Piscataway NJ：IEEE Computer Society，2007：172－182.

［7］KIM J，DALLY W J，ABTS D.Adaptive routing in high－radix clos network［C］∥Proceedings of International Conference for High Performance Computing，Networking，Storage，and Analysis.New York：Association for Computing Machinery，2006：7－13.

［8］朱晓静，胡伟武，马可，等.Xmesh：一个 mesh－like片上网络拓扑结构［J］.软件学报，2007，18（9）：2194－2204.

［9］KIM J，DALLY W，SCOTT S，et al.Technology－driven，highly－scalable dragonfly topology［C］∥Proceedings of International Symposium on Computer Architecture.New York：Institute of Electrical and Electronics Engineers Incorporation，2008：77－88.

［10］欧阳一鸣，朱兵，梁华国，等.基于对角互连网格拓扑结构的片上网络［J］.计算机工程，2009，35（22）：100－104.

［11］WANG Xinyu，XIANG Dong.Multi－mapping meshes：a new communicating fabric for networks－on－chip［C］∥Proceedings of International Conference on Parallel and Distributed Systems.Piscataway NJ：IEEE Computer Society，2010：438－445.

［12］XIANG Dong，YU Zhigang，WU Jie.Deadlock－free fully adaptive routing in irregular networks without virtual channels［C］∥Proceedings of International Symposium on Parallel and Distributed Processing with Application.Piscataway NJ：IEEE Computer Society，2013：983－990.

［13］GROT B，HESTNESS J，KECKLER S，et al.Express cube topologies for on－chip interconnects［C］∥Proceedings of International Conference on of High Performance Computer Architecture.Piscataway NJ：IEEE Computer Society，2009：163－174.

［14］虞志刚，向东，王新玉.Torus网络中基于中心距离的完全自适应路由算法［J］.电子学报，2013，41（11）：2113－2119.

［15］KIM J，DALLT W，TOWLES B，et al.Microarchitecture of a high－radix router［C］∥Proceedings of International Symposium on Computer Architecture.New York：Institute of Electrical and Electronics Engineers Incorporation，2005：420－431.

［16］GLASS C，NI L.The turn model for adaptive routing［J］.Journal of the ACM，1994，41（5）：874－902.

［17］XU Yi，ZHAO Bo，ZHANG Youtao，et al.Simple virtual channel allocation for high throughput and high frequency on－chip routers［C］∥Proceedings of International Symposium on Computer Architecture.Piscataway NJ：IEEE Computer Society，2010：1－11.

［18］DALLY W，TOWLES B.Principles and practices of interconnection networks［M］.San Francisco：Morgan Kaufmann，2004.