混合网络拓扑论文范文

1相关工作

常见的直接网络拓扑有Mesh／Torus、Flat－tenedButterfly、Dragonfly等。Mesh／Torus网络拓扑（k－ary，n－cube）（如图1和图2所示）是一个n维网格，每一维上有k个节点，相邻节点之间有通道相连，其节点规模为kn。Mesh／Torus网络拓扑结构具有较优良的特性。Mesh／Torus网络拓扑结构十分简单，具有高度的规则性，易于布局布线，便于实际部署，也具有很好的扩展性。Mesh／To－rus网络拓扑结构具有广泛的应用，比如64个节点的Tilera［5］、TRIPS［6］处理器、RAW处理器［7］，还有英特尔Teraflops［8］，都是采用2－DMesh网络拓扑结构。但是，随着节点规模的扩大，其劣势就表现出来了。这主要体现在网络直径增大、吞吐率下降等。Mesh／Torus网络拓扑是早期提出的经典网络拓扑，由于其结构简单、性能较好一直沿用至今。为了满足日益增长的性能要求和节点规模增大的情况，KimJ等人［9］于2007年提出了Flat－tenedButterfly（如图3所示）网络拓扑结构，这种结构利用高阶（High－radix）路由器［10］将每个路由节点与之同维的所有路由器节点相连，这样每一维上的跳数就变成了1。一个n维、每一维规模为k的FlattenedButterfly（k－ary，n－cube）网络拓扑上的数据包的路由跳数最多为n跳。FlattenedBut－terfly网络中的每个高阶路由器能连接多个计算终端（p），整个网络能够连接总共p×kn个终端。KimJ的实验表明，FlattenedButterfly丰富的链路特性使得网络性能得到提升，但是物理开销的增加也是巨大的。2009年KimJ又相继提出层次化［11］的Dragonfly（如图4所示）拓扑结构［12］。Dragonfly网络拓扑可以分为三层。在最底层，每个路由器节点连接p个计算终端。在中间层，也就是在局部组内，每个路由器与组内a－1个路由器相连。在最高层，每个局部组内总共b×a跳全局通道与其余局部组进行相连。Dragonfly拓扑结构实际上是基于光通信技术的发展提出的。对于链路较长的全局通道，采用光纤通信来代替电信号通信，这样可以大大降低全局通信的延时，局部组内由于距离较短，仍然采用电信号通信。为了更好地进行均衡负载，将参数p和b取同值，将a取为2p或者2b。Dragonfly拓扑结构能够获得比较好的性能，如延时相对较低、跳步数较短。但是，同时也可以看到，Dragonfly网络拓扑具有很差的扩展性，全局通道的延时仍然会较大。实际中应用Dragonfly拓扑结构的系统有Cray［13］和IBM的PERCS［14］。

常见的间接网络有FatTree［15］、Butterfly等。FatTree（如图5所示）是一种是应用很广泛的间接网络拓扑结构。最早由LeisersonCE于1985年提出，当时提出的FatTree是一个标准的Bina－ryTree结构，树的每个叶子节点连接p个计算终端，每个叶子节点又有p条链路连接其父亲节点，越高层的节点所连接的链路数就越多，也就显得越来越“fat”。由于每一路由器节点的开关规模差异较大，不利于实际应用，后来经过不断发展变化，形成了每级节点开关规模一致的FatTree结构。FatTree网络拓扑结构中间路由器较多，链路非常丰富，能够使网络获得比较好的性能，其缺点是开销较大、成本较高。Butterfly（如图6所示）网络拓扑结构是一种经典间接网络结构，对于确定的终端数N和开关度为2k的Butterfly具有最短的网络直径logkN＋1，虽然有此优点，但是其缺点也是很明显的。首先Butterfly网络具有很差的路径多样性，对于每一个从源节点到目的节点的数据包，其路由路径是唯一的；其次Butterfly级与级之间的链路较长，这会增加电信号传送链路的延时。对于第一个缺点，可以对Butterfly网络拓扑结构做一些改变，比如增加级数来解决这一问题。在间接拓扑网络中使用Butterfly的有BBNButterfly［16］等。为了应对节点规模扩大的情况，要对网络拓扑的结构做一些调整。对于直接网络，扩展的方式有两种方式。第一种方式是扩展每一维上的路由节点规模。第二种方式是扩展网络拓扑的维数。第一种方式简单，每个路由器节点的端口数不会改变，易于部署，但是其缺点是随着跳数的增大，吞吐率等性能会急剧下降，在节点数较大的情况下一般不采用这种扩展方式。第二种扩展网络维数的方法是一个可行的方法，它会使网络拓扑节点的基数增大，但数据包在网络中的跳数增加缓慢。通过实验发现，在相同节点规模下，维数较大的网络拓扑的性能要优于低维的网络拓扑性能。比如To－fu结构就是采用6－D的Mesh来解决这一问题的。但是，增加维数会给实际部署带来较大难度，维数越大，难度也变得越大。对于间接网络拓扑结构，其扩展的方法是增加间接网络拓扑的级数，这种方式能够给系统带来比较好的性能，具有广泛的应用，比如Tianhe－2就是采用FatTree这种间接网络结构来实现的。但是，间接网络的弊端是物理开销太大。随着终端规模的增大，级数会变大，中间路由节点会急剧增多。RobertoP等人［4］在2012年提出了一种新型混合拓扑结构，这种新型的混合拓扑结构（Hybridtopology，后续内容的图表中将这种拓扑结构简称为“HD”）是结合了直接网络和间接网络的优点而提出的。本文将这种新型混合网络拓扑结构的参数表示为（k－ary，n－direct，m－indirect，p－c）。k代表每一维的节点数，n代表网络的维数，m代表间接网络的级数，p代表每个路由节点所连接的终端数，若网络节点所连接的终端数为1，则该参数可缺省。如图7所示为这种新型混合拓扑结构。每一维上的节点布局类似于Mesh／Torus网络，只是相邻节点之间并没有链路相连，而是通过每一维所在的间接网络进行相连。每个间接网络的级数m视每一维的节点规模而定，比如k值较小，间接网络的级数可以小到仅仅为1，也就是说每一维上的间接网络就是一个Crossbar。如果k值较大，间接网络可以为m级的FatTree网络。每个直接网络的节点可以连接多于一个的计算终端。计算终端连接数为p的混合拓扑结构网络所连接的终端规模为p×kn。这种新型混合拓扑结构有一些比较好的静态特性。相对于直接网络，新型混合拓扑结构的直径要比普通直接网络的直径小很多。在网络拓扑规模比较小的情况下，间接网络可以为一个交叉开关Crossbar，其网络直径仅为2n（n表示网络拓扑维数），而普通直接网络拓扑结构，比如Torus，其网络直径为k／2×logkN。同等节点规模下网络直径的减小能够减小网络的延时，提升吞吐率。另外一方面，规模比较小的间接网络（FatTree），其层数要比同等节点规模的FatTree要小很多，整个混合网络拓扑的路由节点数、链路数要比完全间接网络小很多，因此其开销会比完全间接网络小。文献［4］对这种新型的混合网络拓扑与传统的直接网络、间接网络性能进行了比较，得出的结果是新型混合拓扑结构的吞吐率性能要优于Mesh／Torus、FatTree等网络，但比FlattenedButterfly要差。

2新型混合拓扑结构的优化

新型混合拓扑结构Hybrid的每一维上均由以FatTree为代表的间接网络相连接，这实际上可以将规模为（k－ary，n－direct，m－indirect，p－c）的混合拓扑结构看成由规模为（k1／m－ary，m×logkp＋m×n－tree）的FatTree网络分解为n×kn－1个规模为（k1／m－ary，m－tree）的FatTree，然后将这些FatTree的叶节点组成直接网络。这样做的好处是可以降低FatTree的级数，减小数据包路由的跳数。但是，当每一维上的节点规模增大时，间接网络（FatTree）的级数仍然较高。本文提出一种解决的方法，就是每一维上的节点由多个间接网络相连接。本文提出的改进优化的混合拓扑结构（Hy－brid－Ytopology，后续内容的图表中将简称为“HY”）是将Hybrid网络每一维上的间接网络由原来的单个间接网络改造成多个间接网络。这些间接网络的叶节点的链路相间地与Hybrid网络同一维上的节点相连接，Hybrid网络同一维上的节点若连接着不同的间接网络，则将这些节点用链路连接起来。

2.1Hybrid－Y拓扑结构描述Hybrid－Y拓扑网络结构每一维上的间接网络和Hybrid拓扑网络结构的间接网络一样，可以是一个简单的Crossbar或者多级FatTree。Hy－brid－Y拓扑网络结构和Hybrid拓扑网络结构的差异体现在两个方面：（1）间接网络与每一维节点的连接方式不同。Hybrid网络拓扑结构的间接网络叶节点（或者Crossbar）的链路依次分别与同维直接网络的节点相连接。Hybrid－Y拓扑网络结构的s个间接网络的叶节点的链路相互交替地与同维直接网络的节点相连接。（2）直接网络中节点之间的连接方式不同。Hybrid网络拓扑结构的直接网络节点之间没有链路连接，Hybrid－Y网络拓扑结构直接网络某一维中的节点若连接着不同的间接网络，就将这些节点用链路连接起来。下面引入如表1的参数来描述这个改进优化的混合拓扑结构。描述拓扑结构表达式的参数之间需要满足一定的条件。对于某一维上的直接网络连接的间接网络，参数k和参数s、m需要满足这样的条件：s×lm＝k，其中l代表间接网络，也就是FatTree每个叶节点所连接的终端数。对于给定的k值，参数s、m都是可以发生相应改变的。即便是参数s指定了，也就是每一维上的间接网络的个数确定了，间接网络的级数m也可能会有变化。若m取值为1，那么间接网络是一个规模为（k／s）×（k／s）的Crossbar；若m取大于1的值，则间接网络是一个FatTree，这个FatTree网络在m值给定后也就确定了。如图8是这种改进拓扑结构的一个实例。这个图中的直接网络每一维上由两个间接网络相连接。直接网络上的节点00连接间接网络00－0，节点01连接间接网络00－1，节点00与节点01连接着不同的间接网络，因此有一条链路连接节点00与节点01。同样，节点02也有一条链路与节点03相连。注意，节点01与节点02虽然连接着不同的间接网络，但是这两个节点之间并不用链路连接，这是因为这两个节点已经与它们相邻的连接着不同间接网络的节点相连了。

2.2Hybrid－Y网络路由策略在Hybrid－Y拓扑结构上主要采用了两种路由算法：维序路由和自适应路由。为了突出Hy－brid－Y拓扑结构的分析研究，本文将不对间接网络内部的路由进行分析，在后续所讲的维序路由和自适应路由，其间接网络都是文献［18］中使用的针对FatTree的基本自适应路由算法。Hybrid－Y网络拓扑的维序路由算法可以分为两个阶段。第一个阶段为跨维。在n维的Hy－brid－Y网络上执行维序路由算法首先要从数据包的源节点所在的维路由到目的节点所在的维。为了更好地描述这一过程，我们将数据包从某一维路由到另外一维这两维所决定的平面依据节点序号的递增方向划分为x轴方向和y轴方向。维序路由算法在执行跨维路由计算时统一执行先x轴方向后y轴方向或者先y轴方向后x轴方向。执行的x轴或者y轴方向确定后，具体沿着哪一条路径从一维跨到另外一维取决于直接网络每一维上的路由策略了，也就是第二阶段了。第二阶段为维内路由。简单来说，维内路由就是数据包如何从同一维上的一个节点路由到另外一个节点，这个过程是Hybrid－Y网络拓扑维序路由算法的关键步骤，它决定着网络的数据包路由跳数和延时。本文在实现这一过程时采用下面的策略。源节点和目的节点只有可能是直接网络中的节点，消息包所在的当前节点有可能是直接网络中的节点也有可能是间接网络中的节点。情景1源节点、当前节点s和目的节点d均是直接网络中的节点。（1）若当前节点s和目的节点d相邻且有链路连接，则数据包直接从当前节点路由到目的节点，如图9a所示；（2）如当前节点s和目的节点d不相邻，但是当前节点s和目的节点d连接着相同的间接网络，则数据包从当前节点s路由到其所连接的间接网络，如图9b所示；（3）若当前节点s和目的节点d不相邻，且连接着不同的间接网络，则数据包从当前节点s路由到与节点s有链路相连并且连接着与目的节点d相同间接网络的节点，如图9c所示。路由算法执行上面三个步骤就可以将数据包在同一维上从当前节点路由到目的节点。策略（3）的做法能够保证网络的流量相对均衡，不至于都去争抢直接网络中相邻节点之间的链路而导致直接网络节点之间链路的拥塞。（1）数据包从当前节点在间接网络内执行基本自适应路由算法朝着目的节点d的方向路由。情景2只有一种策略情形，这是因为情景2是依赖于情景1的，情景1中策略（3）的执行能够保证情景2只有唯一一种路由策略。至于间接网络内部的路由，这里不加以分析。对于Hybrid－Y网络拓扑的自适应路由算法，其路由执行过程也可以分为与维序路由算法类似的两个阶段：跨维阶段和维内路由阶段，但是每个阶段有所不同。在跨维阶段，自适应路由算法的不同点在于能够动态选择x轴方向或者y轴方向，其判断的依据是x轴方向和y轴方向链路通道的拥塞情况。路由算法将数据包沿着x和y方向链路通道中拥塞状况较好的方向路由。在维内路由阶段，其不同点体现在情景1中的策略（3）。维序路由算法中策略（3）的做法是为了保证网络流量的相对均衡，减小拥塞情况，但自适应路由算法将依据直接网络相邻节点链路拥塞情况与所连接的间接网络链路通道拥塞情况相比较，选择拥塞情况较小的链路通道路由，从而能够考虑到网络中链路通道的实际拥塞情况，避开拥塞较严重的链路通道，从而能够改善网络性能。对于自适应路由可能存在的死锁问题，根据路由路径的选择，可从两个方面分析：（1）路由路径经过间接网络。在这种情况下，由于间接网络是FatTree，所以不会发生死锁。（2）路由路径不经过间接网络。出现这种可能的唯一情形如图10a所示，节点a、b、c和d分别有链路相连接。当这些节点之间的数据包路由路径构成相关环时，就有可能发生死锁。为了避免这种情形的发生，使用虚通道的分配来避免死锁。如图10b所示，节点a、b、c和d之间的物理通道被划分为两个虚通道，分别标记为虚通道0和虚通道1。为了打破相关环路，当节点a、b、c和d之间的数据包的原地址编号和目的地址编号是升序时，使用虚通道0，当数据包的原地址编号和目的地址编号是降序时，使用虚通道1。分配虚通道后，图10a中的路径相关环就不存在了，也就避免了死锁的发生。

3性能评估

本文将改进的混合拓扑结构（Hybrid－Y）与新型混合拓扑结构（Hybrid）、FatTree、Mesh、To－rus、FlattenedButterfly进行比较。我们的模拟工具是时钟精确模拟器Booksim2．0［19］，混合拓扑结构的间接网络都是基于FatTree的网络。模拟的时候，数据包packet的尺寸都取10个flit，模拟的流量模式为均衡模式uniform，路由算法采用维序路由，网络维数均为2－D。此外，在节点规模较大的情况下（本文指节点数为1024），对FatTree网络和混合拓扑结构以及改进优化的混合拓扑结构在worst－case流量模式下进行性能的比较。

3.1模拟实验结果分析图11是在均衡流量模式下，64个节点规模的网络吞吐率模拟结果。从这个图中可以看出，FlattenedButterfly取得了最低的延时和最高的吞吐率，然后依次是改进的混合拓扑结构Hybrid－Y和新型混合拓扑结构Hybrid，结果显示最差的是Torus和Mesh。当网络节点规模增加到256个时，如图12a所示，结果显示FlattenedButterfly仍然能够获得最低的延时和最高的吞吐率，但这些都是建立在较高的开销基础之上的。改进的混合拓扑结构Hybrid－Y（间接网络级数大于1）获得了次之的吞吐率。同时注意到，间接网络级数大于1的混合拓扑结构Hybrid－Y的基本延时要比新型混合拓扑结构Hybrid（这里指间接网络级数小于4）高，从图12b的模拟跳步数可以看出，间接网络级数为3的混合拓扑结构Hybrid－Y的跳步数是10．5，新型混合拓扑结构Hybrid的平均跳步数分别为4．75和7．75。混合拓扑结构Hybrid－Y（间接网络级数大于1的情况）的基本延时要比新型混合拓扑结构Hybrid（这里指间接网络级数小于4）高的原因是线头阻塞效应（Head－Of－LineBloc－king）［20］。Mesh和Torus仍旧是表现最差的网络拓扑，这也说明了Mesh和Torus的2－D结构不适合作为大规模互连网络的拓扑结构。将节点规模增加到1024，如图13所示，能够得到类似的结论。FatTree网络在大规模节点的巨型机系统具有广泛的应用。如图14所示，在流量模式为worst－case的情况下，混合拓扑结构和改进优化的混合拓扑结构均获得了比FatTree更好的吞吐率。对于新型混合拓扑结构Hybrid与改进优化混合拓扑结构Hybrid－Y，在间接网络级数相近的情况下（图示中Hybrid的间接网络级数为5，Hy－brid－Y间接网络级数为4），改进优化的Hybrid－Y网络拥有更好的网络性能。对于维数高于2－D的情形能够得到类似的结果。

3.2性能开销比的比较和分析比较不同拓扑结构网络的指标有很多，比如平均和最大跳步数、对分带宽［21］、网络链路数量和交叉开关规模等。为了更好地将改进的混合拓扑结构Hybrid－Y和新型混合拓扑结构Hybrid进行比较，这里采用文献［1］中提出的网络开销评价指标，即链路（Links）数量、交叉开关（Switches）数量和交叉开关单元（SwitchingElements）规模。网络拓扑的硬件开销比较将采用交叉开关单元规模作为指标。网络的性能评价指标采用基本延时和吞吐率。基本延时和交叉开关单元规模的乘积越低，表示网络拓扑性能就越好；吞吐率和交叉开关单元规模的比值越高，表示网络拓扑的性能就越好。表2列出了这两种混合拓扑结构的链路数、开关单元规模、交叉开关数的计算式。表3列出了Hybrid－Y网络拓扑和Hybrid网络拓扑模拟实验的相关参数，包括基本延时（也称为0负载延时）、吞吐率（Throughput）、链路数、开关单元、交叉开关（Switches），以及性能比较的参数“吞吐率／开关单元”、“基本延时×开关单元”。当节点规模为64时，间接网络为Crossbar（间接网络级数为1）的新型混合拓扑结构Hybrid的基本延时要比间接网络同为Crossbar的改进的混合拓扑结构Hybrid－Y的基本延时要小，这是因为改进的混合拓扑结构Hybrid－Y的直接网络中每一维上有两个Crossbar，而新型混合拓扑结构Hy－brid只有一个Crossbar，因此Hybrid－Y网络中数据包的平均跳步数（Hop）要比Hybrid网络的大。但是，Hybrid－Y网络的吞吐率要比Hybrid网络的高，其原因是其线头阻塞（Head－Of－LineBlocking）效应较之要弱。对于间接网络级数大于1（即多级FatTree）的情形，Hybrid－Y网络与Hybrid网络的“吞吐率／开关单元”性能指标几乎持平，但是Hybrid－Y网络“基本延时×开关单元”性能指标要优于Hybrid。当节点规模增大到256时，间接网络为Cross－bar的Hybrid－Y网络的上述两项性能指标要明显优于Hybrid，分别提升了92％和37．8％。同时注意到，间接网络级数为3的Hybrid－Y网络的上述两项性能指标介于间接网络分别为2和4的Hy－brid网络。若继续将节点规模增大，达到1024时，从表3中可以观察到，间接网络为Crossbar或者多级FatTree的Hybrid－Y网络拓扑的两项性能指标比Hybrid网络拓扑的均要好。从上述的模拟结果分析可以得出这样的结论，Hybrid－Y网络的性能与物理开销和Hybrid网络相比，特别是在较大规模情况下，Hybrid－Y网络的性能与物理开销要优于Hybrid网络。在实际应用的时候，可以根据应用的需求寻求合适的参数配置，使得Hybrid－Y网络的优势更加突出。

4结束语

本文通过对新型混合拓扑结构Hybrid的分析发现，网络规模较大时，间接网络的级数会随着网络规模的增加而增大，从而增加网络延迟。对于这些问题，提出将混合拓扑结构Hybrid每一维上单个间接网络改进为多个间接网络，再按照一定的规则将直接网络中对应的节点用链路通道连接起来的改进混合拓扑结构Hybrid－Y。模拟实验结果表明，在网络规模较大时，改进后的混合拓扑结构Hybrid－Y的性能指标“吞吐率／开关单元”和“基本延时×开关单元”要优于Hybrid的。在实际应用中，可以根据实际应用情况调整Hybrid－Y网络的参数配置，以便获得更优的性能。

作者：杨明英雷斐董德尊沈胜宇庞征斌单位：国防科学技术大学计算机学院