随机步长无向环网通信延迟的研究

方木云，王 俊，王 超

(安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243032)

随机步长无向环网通信延迟的研究

方木云，王 俊，王 超

(安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243032)

高性能计算机(HPC)系统期望尽可能低的通信延迟和建造成本。传统固定步长拓扑已经无法降低通信延迟和建造成本，如固定步长环网无法突破Wong和Coppersmith给出的下界；高节点度拓扑能进一步降低延迟，但增加的交换机和物理链路提高了建造和运营成本。针对这两个缺点，采用随机步长构造方法来生成一种新型的无向环网，避免高节点度的同时，将减少节点间步长的长度从而降低通信延迟作为目标。通过仿真实验分别对无向环网随机步长的直径、平均距离和固定步长的直径下界、平均距离下界进行比较。结果表明：在一定节点度范围内，随机步长无向环网得到的值小于传统固定步长环网得到的值。因此，随机步长拓扑可成为下一代高性能计算机潜在的拓扑结构。

无向环网；固定步长；随机步长；通信延迟

1 概 述

目前，高性能计算机技术已成为世界各国竞相争夺的战略制高点，是衡量一个国家综合国力的重要标志，以服务国家经济建设和改善民生为最高目的，并广泛应用于国家经济和人民生活相关领域[1]。无向多环网络即m(m≥2)环网络是计算机互连网络或通讯系统的一类重要拓扑结构，广泛用于计算机局域网和各种并行处理结构[2-4]，其图论模型是指这样一个无向图G(N;±r,±m,±s)，节点记为0，1，…，N-1，每个节点i向相邻节点发出6条有向边：i→i+r(modN)、i→i+m(modN)、i→i+s(modN)、i→i+N-r(modN)、i→i+N-m(modN)和i→i+N-s(modN)，分别记为[+r]边、[+m]边、[+s]边、[-r]边、[-m]边和[-s]边，其中S为自然数，1≤r

2012年，日本国立情报学研究所MichihiroKoibuchi等提出在环网中采取随机连线的方式来构造环网，在同节点数和网络环数(即节点度)的情况下，发现网络的通信延迟比一种用在on-chip系统上的固定步长环网的通信延迟可下降300倍，同时发现同网络环数同节点数的随机步长环网与现在高性能计算机(HPC)中采用的传统环网(TORUS)等拓扑结构相比，其直径和平均距离小、扩展性和容错性好[9-10]。

文献[11-12]分别指出了度量环网优越性的两个重要参数：直径、平均距离。直径和平均距离越小，无向环网的节点步长长度越小，则环网中通信延迟越小。但根据MichihiroKoibuchi等的研究，仍存在不完善的地方[13-14]：

(1)在同节点数和网络环数的情况下，没有选择直径和平均距离达到Wong和Coppersmith给出的下界的紧优网络[15]来与随机步长网络进行对比。选作对比的非随机步长(non-randomshortcut)网络是固定步长环网中的最差情况之一，以此网络与随机步长网络进行对比，导致随机步长大幅降低通信延迟的这一结论可信度不高。

(2)没有分析随机步长构造无向m环网的直径、平均距离分布特性。因为随机步长的直径是变化的，所以固定步长也是随机步长的一个样本，MichihiroKoibuchi等并没有具体对比两者在直径和平均距离上的联系与差异，以及没有给出在构造无向m环网中随机步长优于固定步长直径和平均距离的分布特性。

(3)在同环数的情况下，随着网络节点数的增多，即网络规模不断增大，随机步长网络通信延迟优于固定步长网络。对该结论没有给出分析研究。

MichihiroKoibuchi等的工作是针对任意度的环网，为了做好横向对比，文中针对同节点数情况下，节点度为4/6/7/8/10(即环数为2/4/5/6/8)的无向环网络，同网络环数情况下，不同节点数的无向环网网络，以及将网络环数和节点数两者变化相结合的无向环网络，重点分析这三个问题。

2 随机步长无向环网的生成

随机步长无向环网是在传统固定步长无向环网的基础上构造的，在传统固定步长环网生成时，将固定步长改为随机步长，同时改变网络环数。因此需依次遍历网络中各个节点。以节点数N=32和环数L=4为例，随机步长无向四环网络的生成如下：

步骤1：生成一个节点数为32的环网，如图1(a)所示。

步骤3：逆时针依次遍历剩下的节点，若当前节点i的度数为ik，则当前节点i可发出的随机边数ik'=6-ik，在节点度小于6且与i节点不相连的节点集合Gi中，若Gi的元素个数小于ik'，则说明图G中已不存在足够的可选节点供节点i连接，返回步骤1，重新生成环网。

步骤4：重复执行步骤3，直到所有节点满足条件。节点2的生成如图1(c)所示，节点3的生成如图1(d)所示。

图1 节点1、2、3生成示意图

由上述步骤可知，此次随机步长无向四环网络生成后的拓扑结构如图2所示。

图2 随机步长无向四环网络拓扑结构

3 仿真算法

3.1 随机步长无向环网的生成算法

Step1：构建一个N*N的邻接矩阵A[N-1,N-1],矩阵内的每个元素赋初值0；构建一个长度为N的队列C[N-1]，队列中每个元素赋初值0，并建立一个空链表L，同时令网络的环数为H，这里H≥2。

Step2：r从0到N-1循环：置A[r,(r+N-1)%N]=1和A[r,(r+N+1)%N]=1。

Step3：s从0到N-1循环(对每个s,k从s+1到N-1循环)：

(1)记T=C[k]，若T=0，则节点r上不需要再加入随机边，开始下一次r循环。

(2)清空L，若A[r,k]≠1并且C[k]

(3)记L中元素的个数为LLength，若LLength

(4)若T=1，则在L中随机选择节点d1，置A[r,d1]=A[d1,r]=1，C[r]=2，C[d1]=C[d1]+1。

(5)若T=2，则在L中随机选择两个互不相同节点d1,d2，置A[r,d1]=A[d1,r]=A[r,d2]=A[d2,r]=1，C[r]=2，C[d1]=C[d1]+1，C[d2]=C[d2]+1。

(7)若T=H，则在L中随机选择H个不相同节点d1,d2,…,dH，置A[r,d1]=A[d1,r]=A[r,d2] =A[d2,r]=A[r,d3]=A[d3,r]=…=A[r,dH]=A[dH,r]=1，C[r]=2,C[d1]=C[d1]+1,C[d2]=C[d2]+1,C[d3]=C[d3]+1,…,C[dH]=C[dH]+1。

3.2 随机步长无向环网的直径和平均距离求解算法

Step1：对随机步长无向环网G=(V,E)的邻接矩阵A进行如下变换：

其中，A是具有如下性质的N阶方阵：

Step2：r从0到N-1循环：对每个i,j从0到N-1循环，对每个j,k从0到N-1循环，若D[j,i]+D[i,k]

黄冈市贫困地区26家农村基层医疗卫生机构基本药物使用情况调查 ……………………………………… 王文杰等（2）：156

Step3：对Step2中得到的距离矩阵D，求出直径[12,16]：

Dia=Max(D[i,j]),0≤i,j≤N

Step4：对Step2中得到的距离矩阵D，求平均距离[12]：

4 仿真实验及结果分析

由文献[12]可知传统固定步长环网的直径下界为：

其平均距离下界为：

文中选择与传统固定非单位步长无向环网的下界作对比实验。选用VisioStudio2013中C#语言编制程序进行仿真，计算直径和平均距离，同时将网络拓扑结构和得到的结果数据输入到Matlab中进行分析。

下面给出仿真实例：

(1)当环数L=4不变，改变节点数时，进行100次对随机步长无向环网的仿真实验，对其产生的直径的平均值和平均距离的平均值与固定步长环网的直径下界和平均距离下界进行对比并做出相应的分析，如图3和图4所示，其数据对比如表1所示。

图3 L=4时直径对比图

图4 L=4时平均距离对比图

节点数N固定步长直径/平均距离随机步长(直径/平均距离)最优生成最差生成平均生成643.130/2.5043/2.4864/2.5333.970/2.4881283.723/2.9794/2.9154/2.9154.000/2.9152564.527/3.5424/3.3345/3.3564.315/3.3415125.264/4.2125/3.7656/3.7715.120/3.76810246.260/5.0086/4.1987/4.2036.030/4.20120487.545/5.9567/4.6257/4.6257.000/4.625

由图3、4，表1得出如下结论(固定步长无向环网简称固定步长，随机步长无向环网简称随机步长)：

①随机步长的平均生成直径和平均生成的平均距离均小于固定步长的直径下界和平均距离下界。

②随着节点数N不断增大，固定步长直径下界与平均距离下界的值增加速度明显快于随机步长平均生成直径和平均生成的平均距离的值增加速度。

由上述结论可知，在保持无向环网中其他因素相同时，当环数为定值，随机步长的通信延迟优于传统固定步长。

(2)当节点数N=1 024不变，改变网络环数时，同样进行相应的仿真实验，并对其结果做出分析，如图5和图6所示，其数据如表2所示。

图5 N=1 024时直径对比图

图6 N=1 024时平均距离对比图

由图5、6和表2表明：

①随机步长平均生成的平均距离均小于固定步长平均距离的下界。

表2 N=1 024时随机步长与固定步长的直径、平均距离数据对比表

②随着网络环数L不断增大，随机步长的直径和平均距离均小于固定步长直径下界和平均距离下界的趋势越来越不明显。

由上述两点，在保持无向环网中其他因素相同时，当网络环数(即节点度)在一定范围内，随机步长的通信延迟优于传统固定步长，这一点也避免了高节点度拓扑所带来的建造和运营成本的问题。

(3)结合实验(1)、(2)，同时改变节点数N和网络环数L，进行100次直径和平均距离对比实验，并对结果做出分析。实验结果如表3所示。

表3 固定步长直径/平均距离(随机步长直径/平均距离)

分析其总体趋势如下：

①当L≤4(即节点度≤6)不同节点数时，随机步长直径、平均距离均小于固定步长直径下界和平均距离下界；当L≥5时，随机步长直径≥固定步长直径下界，但随机步长平均距离≤固定步长平均距离下界。

②当L一定节点数不断增加时，随机步长直径和平均距离的值增加速度明显小于固定步长直径下界和平均距离下界的值增加速度；当N一定环数不断增加时，虽然随机步长直径≥固定步长，但随机步长直径的值增加速度相比固定步长直径下界的值增加速度较慢，且随机步长平均距离均小于固定步长平均距离下界。

综上，在保持无向环网中其他因素相同时，当网络环数(即节点度)在一定范围内，随机步长得到的直径、平均距离均小于传统固定步长直径下界、平均距离下界，则随机步长网络节点步长长度较小，从而得出结论：在无向环网中，随机步长较传统固定步长通信延迟占有优势。

5 结束语

文中采用随机步长来构造无向环网，分别对随机步长无向环网直径、平均距离和固定步长无向环网直径下界、平均距离下界进行仿真实验对比。结果表明，在保持无向环网中其他因素相同时，当节点度在一定范围内，随机步长无向环网的网络通信延迟和网络性能均优于固定步长无向环网，同时随着网络节点数不断增加，即网络规模的不断增大，随机步长降低通信延迟的优势更加明显。因此，与当前主流的HPC采用的高节点度和固定步长拓扑结构相比，随机步长拓扑可成为下一代高性能计算机的潜在拓扑结构。

[1] 周兴铭．高性能计算技术发展[J]．自然杂志，2011，33(5)：249-254．

[2]ChenCY,HwangFK.EquivalentL-shapesofdouble-loopnetworksforthedegeneratecase[J].JournalofInterconnectionNetworks,2000,1(1):47-60.

[3] 陈协彬.步长有限制的双环网络的最优路由算法[J]．计算机学报，2004，27(5)：596-603．

[4]HwangFK.Asurveyonmulti-loopnetworks[J].TheoreticalComputerScience,2003,299(1):107-121.

[5] 方木云，屈玉贵，赵保华.双环网络的[+h]边优先寻径策略[J]．计算机学报，2008，31(3)：536-542．

[6] 苏小虎，方木云，邰伟鹏，等.双环网络G(N;1,s)的L形瓦仿真算法改进[J].小型微型计算机系统，2012，33(9)：2053-2055．

[7] 方木云，赵保华，屈玉贵.非单位步长双环网络G(N;r,s)的L形瓦仿真算法[J]．系统仿真学报，2006，18(10)：2963-2965.

[8]WongCK,CoppersmithD.Acombinatorialproblemrelatedtomulti-modulememoryorganizations[J].JournalofACM,1974,21(3)：392-402．

[9]KoibuchM,MatsutaniH,AmanoH,etal.AcaseforrandomshortcuttopologiesforHPCinterconnects[C]//Procof39thannualinternationalsymposiumoncomputerarchitecture.[s.l.]:IEEE,2012:177-188.

[10]KimJ,BalfourJ,DallyW.Flattenedbutterflytopologyforon-chipnetworks[C]//Proceedingsofthe40thannualIEEE/ACMinternationalsymposiumonmicro-architecture.[s.l.]:IEEEComputerSociety,2007:172-182.

[11] 方木云，侯海金，吴爱清，等.双环网络直径点和宽直径点的分布特性[J].小型微型计算机系统，2013，34(4)：749-752．

[12] 陈业斌,李 颖，郑 啸,等.关于有向环网平均直径的研究[J].通信学报,2013，34(2)：138-146．

[13]FujiwaraI,KoibuchiM,CasanovaH.Cabinetlayoutoptimizationofsupercomputertopologiesforshortercablelength[C]//Procof13thinternationalconferenceonparallelanddistributedcomputing,applicationsandtechnologies.[s.l.]:IEEE,2012:227-232.

[14]KoibuchiM,FujiwaraI,MatsutaniH,etal.Layout-consciousrandomtopologiesforHPCoff-chipintercomnects[C]//Procof19thinternationalsymposiumonhighperformancecomputerarchitecture.[s.l.]:IEEE,2013:484-495.

[15] 方木云,赵保华,屈玉贵．基于圈的紧优双环网络G(N;1,s)求解算法[J].华中科技大学学报:自然科学版,2005,33(6):17-19．

[16] 方木云，赵保华.新的无向双环网络G(N;±1,±s)直径求解方法[J]．通信学报，2007，28(2)：124-129．

Research on Communication Delay of Random-step Undirected Loop Networks

FANG Mu-yun,WANG Jun,WANG Chao

(School of Computer Science and Technology,Anhui University of Technology,Ma’anshan 243032,China)

High-performance computer system expects the lowest possible communication delays and construction costs.Traditional fixed-step topology has been unable to reduce communication latency and construction costs.For example,fixed-step loop networks cannot break through the lower bound given by Wong and Coppersmith,and high degree of topological node can further reduce latency,but increased switch and physical links improve the construction and operating costs.In view of two shortcomings,random-step is used to construct a new type of undirected loop networks which can reduce the length of steps between nodes to reduce the communication delay as the destination,at the same time can avoid high degree of node.Respectively compares diameter and average distance of random-step undirected loop networks as well as lower diameter and average lower distance of fixed-step through simulation experiments.The results show that within a certain range of the node,the value of the random-step to the ring obtained less than the value of traditional fixed-step ring obtained.Thus,random-step topology may be the next generation of high-performance computer underlying topology.

undirected loop networks;fixed-step;random-step;communication delay

2016-01-08

2016-04-13

时间：2016-09-19

国家自然科学基金资助项目(61003311);安徽省教育厅重大项目(ZD2008005-1)

方木云(1968-)，男，教授，博士，研究方向为计算机网络、网络拓扑结构等;王 俊(1990-)，男，通信作者，硕士研究生，研究方向为计算机网络与网络拓扑结构。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0843.062.html

TP393

A

1673-629X(2016)10-0027-05

10.3969/j.issn.1673-629X.2016.10.006