1. 清华大学 软件学院, 北京 100084;
2. 国网湖南省电力公司 信息通信公司, 长沙 410004
收稿日期：2018-04-28
作者简介：蔡源(1992-), 女, 博士研究生
通信作者：向东, 教授, E-mail: dxiang@tsinghua.edu.cn
摘要：针对现有的判断片上网络路由算法是否含有死锁的方法都比较复杂，以及传统转弯模型存在不足的问题，提出了一种更简单更直观的判断路由算法是否包含死锁的算法，并证明了该算法的正确性，然后提出了一种列分转弯模型。列分转弯模型能实现针对二维mesh网络的基于虚跨步交换技术的无死锁、最短路径部分自适应路由，并且不需要额外的虚拟通道。该模型会在网络节点处限制某些转弯，从而避免死锁，类似于奇偶转弯模型。模拟实验结果表明：基于该模型的路由算法与基于奇偶转弯模型的路由算法相比，在不同的流量模式下平均延迟都有所降低，饱和点有所上升，从而提高了整个网络的性能。
关键词：转弯模型虚跨步交换二维mesh网络无死锁部分自适应路由
Routing algorithm based on a column-partition turn model for a network-on-chip
CAI Yuan1, LUO Wei2, XIANG Dong1
1.Software Department, Tsinghua University, Beijing 100084, China;
2.Information and Communication Company, State Grid Hunan Electric Power Company, Changsha 410004, China
Abstract: Existing methods cannot easily determine whether a routing algorithm for a network-on-chip contains a deadlock and the traditional turn model has serious limitations. This paper presents a simple, intuitive algorithm to determine whether the routing algorithm is deadlock-free. This paper gives a proof of the algorithm's correctness. Then, a column-partition turn model is given to implement deadlock-free minimal partially adaptive routing for a virtual cut-through (VCT)-switched 2-D mesh without extra virtual channels. This algorithm avoids deadlocks by restricting the locations for certain turns, which is similar to the odd-even turn method. Simulations show that this routing algorithm reduces the average latency and increases the saturation points compared to routing algorithms based on the odd-even turn model for various traffic patterns. Therefore, this column-partition turn model improves the performance of the whole network.
Key words: turn modelvirtual cut-through switching2-D meshdeadlock-freepartially adaptive routing
随着半导体技术的快速发展，在单一芯片上集成的IP(intellectual property)模块越来越多，并且IP模块之间的通信方式对系统的性能有着至关重要的影响。片上网络解决了基于总线的系统不可伸缩等问题，逐渐成为片上通信的主流方式，并得到了深入的研究。目前，学术界对于片上网络的研究主要分为以下3部分：拓扑结构、交换机制和路由算法。
片上网络的拓扑结构对片上多处理器的性能和功耗有重要影响[1]。虽然三维片上网络结构比二维片上网络结构集成度更高[2]，具有空间优势，但存在路由算法过于复杂、散热问题难以得到解决等问题，因此二维片上网络依然被普遍使用和研究[3-5]。二维mesh拓扑结构由于具有结构设计简单、节点之间通道短等特点已经被广泛应用于构造并行处理器系统[6-7]。基于此，本文针对二维mesh网络结构进行路由算法的研究。
片上网络的交换机制决定了消息通过网络时资源的分配方式[8]。典型的交换技术有：存储转发交换技术、虚跨步交换技术以及虫孔交换技术。
片上网络的路由算法决定了消息从源节点到目的节点要经过的通道序列。一个好的路由算法应该是无死锁的。本文根据Duato等[9]的无死锁定理和Verbeek等[10]提出的证明无死锁的算法，提出了一个判断路由算法是否包含死锁的方法，并证明了该方法的正确性。现在研究者们已经提出了许多针对二维mesh网络采用虚跨步交换技术的路由算法。根据消息路由时是否考虑网络状态，可以将路由算法分为2类：无关路由算法和自适应路由算法。对于mesh网络，实现无死锁的完全自适应路由算法必须要加入虚拟通道，但加入虚拟通道会增加路由器设计的复杂性，导致路由器延迟增加；除此之外，还会增大缓存区需求，从而使得网络的通信性能受到影响。因此，研究不使用虚拟通道的无死锁的部分自适应路由算法很有必要。转弯模型[11]的提出为在给定网络资源下开发部分自适应路由算法提供了一种系统方法。本文针对二维mesh网络提出了一种列分转弯模型，用于设计部分自适应路由算法。经过理论证明，该算法是无死锁的，并且不需要加入额外的虚拟通道。实验结果显示，该转弯模型在不同的流量模式下与奇偶转弯模型[12]相比具有更好的性能。
1 转弯模型Glass等[11]提出了一种模型用于设计不需要使用虚拟通道的部分自适应路由算法，称之为转弯模型。转弯模型将8种转弯分到顺时针和逆时针的2个环中，在每个环中禁止一个转弯来打破环，从而避免死锁。基于转弯模型，3种部分自适应路由算法被提出，分别是west-first、north-last和negative-first，但这3种路由算法的自适应度的分布是严重不均匀的，有一半的消息从源节点到目的节点只有一条最短路径，而其余的消息则按照完全自适应路由，这样使得网络更易发生拥塞而导致性能降低。
为了处理这个问题，Chiu[12]提出了奇偶(odd-even)转弯模型，仅仅限制了某些位置处的转弯。消息在奇数列不允许北西(NW)转弯和南西(SW)转弯；消息在偶数列时不允许东北(EN)转弯和东南(ES)转弯。基于奇偶转弯模型的路由算法提供了更加均匀的自适应度分布，但是没有源-目的节点对(源节点和目的节点之间的Manhattan距离长度大于2)拥有完全自适应路由。
2 判断无死锁路由的方法方法1??(无死锁判断)当消息按照给定的路由算法路由，如果网络中至少存在一条通道，使得任何消息只要通过该通道之后就能到达目的节点，那么此路由算法是无死锁的。
证明??任何消息通过某条通道就一定到达目的地，无法再继续转发，这是由于以下两点原因：1)路由算法的限制，规定不能输出到某条通道；2)到达网络边界或在方法1执行过程中通道被删除，没有通道可以路由。因此，不存在消息占有该条通道的同时申请另外的通道，即该条通道不可能对其他通道产生依赖关系。因为在有环的信道依赖图中，每个通道都会与另外一条通道存在依赖关系，所以那些与其他通道没有依赖关系的通道，显然不可能被包含在有环的信道依赖图中。将符合这样条件的通道加入到集合s中，并且将通道(单向的)从原来的网络拓扑图中删除，删除的目的是使这些通道在方法1之后的迭代过程中不能被消息路由使用。s被称为安全通道集合，其中的每条通道都无法与网络中其他任何通道由于依赖关系产生循环相关。对于此时不在s中的通道，若被消息占有，同时消息唯一等待在s中的通道，那么由于s中的通道不可能出现在环中，因此满足这样特征的通道也不可能出现在环中，从而说明这些通道也是安全的，可以被加入到s集合里面。若网络中的所有通道都加入到s中，那么说明网络中没有通道可以构成有环路的信道依赖图。
根据Duato[13]提出的在虚跨步网络中无死锁的充分必要条件，由此证明了判断路由算法是否为无死锁的方法1的正确性。
本文通过图 1算法isDeadlockFree()来描述该无死锁判断方法的流程。消息遵循给定的路由算法中的规则，遍历mesh网络中的每一条通道，若消息通过某条通道后到达目的节点或下一跳的通道在集合s中，那么就将该通道从网络中删除，并加入到集合s中。若最后网络中所有的通道都在集合s中，那么该算法就是无死锁的。
 |
| 图 1 算法isDeadlockFree |
| 图选项 |
以奇偶转弯模型为例，图 2显示了针对5×5 mesh网络使用方法1证明路由算法无死锁的过程。图 2中无箭头的通道表示双向链路，有箭头的通道表示单向链路，消息只能朝着箭头指向的方向路由，并且列是从0列开始计数。消息经过从节点23到节点24的链路后，在节点24一定到达目的节点，因为在节点24消息在X和Y方向都没有信道可以路由，所以根据图 1算法，可以将节点23到节点24这个方向的信道删除。并且，由于相似的原因，从mesh网络的第3列节点到第4列节点的行信道都可以被删除，如图 2a所示。消息经过从节点18到节点23的信道后，由于NW转弯的限制不能向左(节点23到节点22的方向)转发，并且向右的信道已经被删除，因此该消息只能被节点23接收。从节点18到节点23的信道开始，依次删除第4列上由南向北的信道，然后从节点8到节点3的信道开始，依次删除第4列上由北向南的信道，从而将第4列上的信道完全删除，如图 2b所示。类似地，根据奇偶转弯规则的限制以及考虑已经被删除的信道，能够逐一将网络中各信道删除，具体过程见图 2c、2d和2e，最后的结果如图 2f所示，从而证明了基于奇偶转弯模型的路由算法是没有死锁的。
 |
| 图 2 奇偶转弯模型无死锁的证明过程 |
| 图选项 |
3 列分转弯模型3.1 转弯模型规则在二维mesh网络中，节点X的坐标用二维向量(x0, x1)表示，x0是0维上的坐标，x1是一维上的坐标。假设每一维上的节点数都为k，那么每个节点的坐标满足0≤x0＜k和0≤x1＜k。同一列上的节点的x0值相同，同一行上的节点的x1值相同。对于k×k的mesh网络，中间列的0维上的坐标为
1) 若节点的
2) 若节点的
消息在路由过程中都按照最短路径路由，具体的算法过程显示在图 3算法route()中。算法route()首先根据当前节点和目的节点在每一维上的偏移量，确定它们的相对位置。然后，计算出中间列节点的0维坐标mid值，再根据当前节点0维上的坐标c0与mid的比较结果，将候选的方向加入变量avail_dimension_set中。最后，从avail_dimension_set中随机选择一个方向，返回相应的输出通道。
 |
| 图 3 算法route |
| 图选项 |
以5×5的二维mesh网络为例，中间列0维上的坐标为2，本文提出的模型规定禁止的转弯显示在图 4中。从列的角度看，在1列和2列上的每个节点都禁止NW转弯和SW转弯，在3列和4列上的每个节点都禁止EN转弯和ES转弯。例如消息的源节点为(1, 1)，目的节点的为(0, 2)，消息只能向西路由，不能向北路由，因为消息在节点(1, 2)禁止NW转弯。
 |
| 图 4 列分转弯模型禁止的转弯 |
| 图选项 |
3.2 无死锁证明定理1??基于列分转弯模型的路由算法是无死锁的。
证明??利用图 1中描述的判断路由算法是否是无死锁的方法，证明基于本文提出的列分转弯模型的路由算法是无死锁的。从k-2列上的任何一个节点(k-2, j)，其中0≤j＜k，通过0维上的通道到达k-1列上相应的节点(k-1, j)，一定到达目的地，因为消息走了东向的通道，并且k-1列上的节点不允许EN转弯和ES转弯，即消息到达k-1列上的节点后，不能向任何方向路由。可见，基于列分转弯模型的路由算法满足方法1中无死锁的条件，因此此算法是无死锁的。
3.3 自适应度分析基于列分转弯模型的路由算法的自适应度可以分为6种情况讨论。图 5中的Si和Di分别表示每种情况下消息msgi的源节点和目的节点，其中1≤i≤6。图 5中节点里的数字表示节点的标签l，l=x0+x1·k。假设源节点坐标为(s0, s1)，目的节点坐标为(d0, d1)，网络每一维的节点数为k。定义Δx和Δy分别为Δx=d0-s0，Δy=d1-s1。定义dx和dy分别为dx=|Δx|，dy=|Δy|。
 |
| 图 5 基于列分转弯模型的算法在5×5 mesh网络中路由示例 |
| 图选项 |
第1种情况，目的节点在源节点的东南(北)或南(北)方向，并且目的节点在中间列或在中间列的西侧，即满足条件s0≤d0且
| ${P_1} = \frac{{\left( {{d_x} + {d_y}} \right)!}}{{{d_x}!{d_y}!}}.$ | (1) |
第3种情况，目的节点在源节点的西南(北)方向，并且源节点在中间列或在中间列的西侧，即满足条件s0＞d0且
第4种情况，目的节点在源节点的西南(北)方向，并且目的节点在中间列或在中间列的东侧，即满足条件s0＞d0且
| ${P_4} = \frac{{\left( {{d_x} + {d_y}} \right)!}}{{{d_x}!{d_y}!}}.$ | (2) |
| ${P_5} = \frac{{\left( {\left( {{\rm{mid}} - {s_0}} \right) + {d_y}} \right)!}}{{\left( {{\rm{mid}} - {s_0}} \right)!{d_y}!}} \times 1.$ | (3) |
| ${P_6} = \frac{{\left( {\left( {{s_0} - {\rm{mid}}} \right) + {d_y}} \right)!}}{{\left( {{s_0} - {\rm{mid}}} \right)!{d_y}!}} \times 1.$ | (4) |
基于本文提出的转弯模型的路由算法存在完全自适应路由的情况，并且这种情况出现的可能性达到了1/4，但有1/4的概率消息只能通过一条给定的路径路由，算法的自适应度受到影响。与传统的转弯模型west-first、negative-first、north-last相比，本文提出的列分转弯模型具有更均匀的自适应度。为了比较列分转弯模型与奇偶转弯模型的自适应度分布情况，计算了奇偶转弯模型和列分转弯模型在整个网络中的平均自适应度，即网络中每个节点到其他所有节点的可能路径数的平均值，
| $\overline P = \frac{{\sum\limits_{0 \le i \le {k^2} - 1} {\sum\limits_{0 \le j \le {k^2} - 1} {{p_{i, j}}} } }}{{{k^2}}}.$ | (5) |
4 实验结果及分析使用基于Java编写的模拟器来评估本文提出的列分转弯模型的性能。实验构造了一个8×8的二维mesh网络，相邻节点之间存在两条单向的通道，节点之间通过传递消息进行通信。
4.1 实验配置消息长度设置为16个微片，采用虚跨步交换技术，缓存区的深度为1个消息，不需要额外的虚拟通道。消息注入率不断增加，对于每个消息注入率，刚开始10 000个周期的数据不统计，因为模拟刚开始时网络状态不稳定，可能造成统计数据的准确性下降。一共执行30 000个周期。选择奇偶转弯(odd-even)模型[12]、west-first[11]和negative-first[11]作为比较模型，4种模型的所有实验配置都相同。
实验测试了4种模型对于每个消息注入率的平均延迟(单位：周期)，即消息从源节点发出到消息到达目的节点的时间；还测试了网络可接受流量，并进行标准化，得到标准化可接受流量, 即标准化到达的消息占产生的总消息的百分比。在模拟中，采用了3种典型的流量模式，分别是：1)均匀流量模式，源节点和目的节点在网络中完全随机分布；2)两种转置流量模式，第1种是一个节点(i, j)仅仅发送消息到节点(7-j, 7-i)，第2种是一个节点(i, j)仅仅发送消息到节点(j, i)；3)热点流量模式，设置一个点或多个点作为热点，网络中一个节点可以向任何其他节点发送消息，但会以某个概率向热点发送消息。
4.2 实验结果分析图 6a和6b显示了对于均匀流量模式的模拟结果。可以看出，当消息注入率低于37%时，本文提出的列分转弯模型和奇偶转弯模型的平均延迟和标准化可接受流量几乎没有差别，但当消息注入率继续增加时，列分转弯模型的平均延迟明显低于奇偶转弯模型。在消息注入率为44%时，列分转弯模型的延迟比奇偶转弯模型降低了47.53%，随后两种模型的平均延迟都迅速增加，到达饱和点。还可以看出，west-first在高流量负载(消息注入率大于45%)的情况下具有最好的性能，negative-first的性能最差。
 |
| 图 6 均匀和转置流量模式下算法性能比较 |
| 图选项 |
图 6c和6d显示了对于第1种转置流量模式的模拟结果。可以观察到，本文提出的列分转弯模型优于奇偶转弯模型，但在低流量负载的情况下差距很小，只有在消息注入率大于35%时差距才相对比较明显。negative-first的性能最好，并且它的饱和点比本文提出的模型的饱和点高很多。图 6e和6f显示了对于第2种转置流量模式的模拟结果。在消息注入率为35%时，本文提出的列分转弯模型和奇偶转弯模型的平均延迟差距最大，标准化可接受流量差别不明显。但随着消息注入率的增大，两者在平均延迟上的差距逐渐减小。在此转置流量模式下，本文模型的性能优于其他3种转弯模型。
图 7a和7b显示了对于设置一个热点(4, 4)且热点百分比为6%时的模拟结果。本文提出的列分转弯模型的网络饱和点比奇偶模型提高了2.44%，更能适应较高的消息注入率。图 7c和7d显示了对于设置2个热点(2, 6)和(6, 2)且热点百分比为6%时的模拟结果。本文模型在奇偶模型的延迟迅速升高时延迟还较低。图 7e和7f显示了对于设置4个热点(2, 2)、(2, 6)、(6, 2)、(6, 6)且热点百分比为6%时的模拟结果。本文提出的模型的网络饱和点比奇偶模型提高了2.33%。
 |
| 图 7 热点流量模式下算法性能比较 |
| 图选项 |
由此得出结论，本文提出的列分转弯模型相比于奇偶转弯模型针对mesh网络具有更好的性能。
5 总结本文首先提出了一种判断片上网络路由算法是否存在死锁的方法；然后提出了一种列分转弯模型用于实现针对二维mesh网络的基于虚跨步交换技术的无死锁、最短路径的部分自适应路由。列分转弯模型是在奇偶转弯模型的基础上，改变了受限制转弯的位置，使得网络中存在完全自适应路由情况。模拟结果显示，无论是在均匀的流量模式还是非均匀的流量模式下，列分转弯模型相比于奇偶转弯模型对网络的平均延迟有所降低，饱合点有所提高。可见，本文提出的列分转弯模型具有更优的性能。
参考文献
| [1] | XU Y, DU Y, ZHAO B, et al. A low-radix and low-diameter 3D interconnection network design[C]//Proceedings of the 15th International Symposium on High Performance Computer Architecture. Raleigh, USA, 2009: 30-42. |
| [2] | 李晨, 马胜, 王璐, 等. 三维片上网络体系结构研究综述[J]. 计算机学报, 2016, 39(9): 1812-1828. LI C, MA S, WANG L, et al. A survey on architecture for three-dimensional networks-on-chip[J]. Chinese Journal of Computers, 2016, 39(9): 1812-1828. (in Chinese) |
| [3] | XIANG D. Deadlock-free adaptive routing in meshes with fault-tolerance ability based on channel overlapping[J]. IEEE Transactions on Dependable and Secure Computing, 2011, 8(1): 74-88. DOI:10.1109/TDSC.2009.3 |
| [4] | KHAN H U R, SHI F, JI W X, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29): 3363-3371. DOI:10.1007/s11434-010-4118-z |
| [5] | XIANG D, ZHANG Y L, PAN Y, et al. Deadlock-free adaptive routing in meshes based on cost-effective deadlock avoidance schemes[C]//Proceedings of International Conference on Parallel Processing. Xi'an, China, 2007: 41-48. |
| [6] | ALLEN F, ALMASI G, ANDREONI G, et al. Blue gene:A vision for protein science using a petaflop supercomputer[J]. IBM Systems Journal, 2011, 40(2): 310-327. |
| [7] | MUKHERJEE S S, BANNON R, LANG S, et al. The Alpha 21364 network architecture[J]. IEEE Micro, 2002, 22(1): 26-35. |
| [8] | DALLY W, TOWLES B. Principles and practices of interconnection networks[M]. San Francisco, USA: Morgan Kaufmann, 2003. |
| [9] | DUATO J, YALAMANCHILI S, NI L. Interconnection networks:An engineering approach[M]. San Francisco, USA: Morgan Kaufmann, 2002. |
| [10] | VERBEEK F, SCHMALTZ J. A decision procedure for deadlock-free routing in wormhole networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(8): 1935-1944. DOI:10.1109/TPDS.2013.121 |
| [11] | GLASS C J, NI L M. The turn model for adaptive routing[J]. Journal of the ACM, 1994, 41(5): 874-902. DOI:10.1145/185675.185682 |
| [12] | CHIU G M. The odd-even turn model for adaptive routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7): 729-738. DOI:10.1109/71.877831 |
| [13] | DUATO J. A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(8): 841-854. DOI:10.1109/71.532115 |
