方木云，王 俊，王 超

(安徽工業(yè)大學 計算機科學與技術(shù)學院，安徽 馬鞍山 243032)

隨機步長無向環(huán)網(wǎng)通信延遲的研究

方木云，王 俊，王 超

(安徽工業(yè)大學 計算機科學與技術(shù)學院，安徽 馬鞍山 243032)

高性能計算機(HPC)系統(tǒng)期望盡可能低的通信延遲和建造成本。傳統(tǒng)固定步長拓撲已經(jīng)無法降低通信延遲和建造成本，如固定步長環(huán)網(wǎng)無法突破Wong和Coppersmith給出的下界；高節(jié)點度拓撲能進一步降低延遲，但增加的交換機和物理鏈路提高了建造和運營成本。針對這兩個缺點，采用隨機步長構(gòu)造方法來生成一種新型的無向環(huán)網(wǎng)，避免高節(jié)點度的同時，將減少節(jié)點間步長的長度從而降低通信延遲作為目標。通過仿真實驗分別對無向環(huán)網(wǎng)隨機步長的直徑、平均距離和固定步長的直徑下界、平均距離下界進行比較。結(jié)果表明：在一定節(jié)點度范圍內(nèi)，隨機步長無向環(huán)網(wǎng)得到的值小于傳統(tǒng)固定步長環(huán)網(wǎng)得到的值。因此，隨機步長拓撲可成為下一代高性能計算機潛在的拓撲結(jié)構(gòu)。

無向環(huán)網(wǎng)；固定步長；隨機步長；通信延遲

1 概 述

目前，高性能計算機技術(shù)已成為世界各國競相爭奪的戰(zhàn)略制高點，是衡量一個國家綜合國力的重要標志，以服務(wù)國家經(jīng)濟建設(shè)和改善民生為最高目的，并廣泛應(yīng)用于國家經(jīng)濟和人民生活相關(guān)領(lǐng)域[1]。無向多環(huán)網(wǎng)絡(luò)即m(m≥2)環(huán)網(wǎng)絡(luò)是計算機互連網(wǎng)絡(luò)或通訊系統(tǒng)的一類重要拓撲結(jié)構(gòu)，廣泛用于計算機局域網(wǎng)和各種并行處理結(jié)構(gòu)[2-4]，其圖論模型是指這樣一個無向圖G(N;±r,±m(xù),±s)，節(jié)點記為0，1，…，N-1，每個節(jié)點i向相鄰節(jié)點發(fā)出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為自然數(shù)，1≤r

2012年，日本國立情報學研究所MichihiroKoibuchi等提出在環(huán)網(wǎng)中采取隨機連線的方式來構(gòu)造環(huán)網(wǎng)，在同節(jié)點數(shù)和網(wǎng)絡(luò)環(huán)數(shù)(即節(jié)點度)的情況下，發(fā)現(xiàn)網(wǎng)絡(luò)的通信延遲比一種用在on-chip系統(tǒng)上的固定步長環(huán)網(wǎng)的通信延遲可下降300倍，同時發(fā)現(xiàn)同網(wǎng)絡(luò)環(huán)數(shù)同節(jié)點數(shù)的隨機步長環(huán)網(wǎng)與現(xiàn)在高性能計算機(HPC)中采用的傳統(tǒng)環(huán)網(wǎng)(TORUS)等拓撲結(jié)構(gòu)相比，其直徑和平均距離小、擴展性和容錯性好[9-10]。

文獻[11-12]分別指出了度量環(huán)網(wǎng)優(yōu)越性的兩個重要參數(shù)：直徑、平均距離。直徑和平均距離越小，無向環(huán)網(wǎng)的節(jié)點步長長度越小，則環(huán)網(wǎng)中通信延遲越小。但根據(jù)MichihiroKoibuchi等的研究，仍存在不完善的地方[13-14]：

(1)在同節(jié)點數(shù)和網(wǎng)絡(luò)環(huán)數(shù)的情況下，沒有選擇直徑和平均距離達到Wong和Coppersmith給出的下界的緊優(yōu)網(wǎng)絡(luò)[15]來與隨機步長網(wǎng)絡(luò)進行對比。選作對比的非隨機步長(non-randomshortcut)網(wǎng)絡(luò)是固定步長環(huán)網(wǎng)中的最差情況之一，以此網(wǎng)絡(luò)與隨機步長網(wǎng)絡(luò)進行對比，導致隨機步長大幅降低通信延遲的這一結(jié)論可信度不高。

(2)沒有分析隨機步長構(gòu)造無向m環(huán)網(wǎng)的直徑、平均距離分布特性。因為隨機步長的直徑是變化的，所以固定步長也是隨機步長的一個樣本，MichihiroKoibuchi等并沒有具體對比兩者在直徑和平均距離上的聯(lián)系與差異，以及沒有給出在構(gòu)造無向m環(huán)網(wǎng)中隨機步長優(yōu)于固定步長直徑和平均距離的分布特性。

(3)在同環(huán)數(shù)的情況下，隨著網(wǎng)絡(luò)節(jié)點數(shù)的增多，即網(wǎng)絡(luò)規(guī)模不斷增大，隨機步長網(wǎng)絡(luò)通信延遲優(yōu)于固定步長網(wǎng)絡(luò)。對該結(jié)論沒有給出分析研究。

MichihiroKoibuchi等的工作是針對任意度的環(huán)網(wǎng)，為了做好橫向?qū)Ρ?，文中針對同?jié)點數(shù)情況下，節(jié)點度為4/6/7/8/10(即環(huán)數(shù)為2/4/5/6/8)的無向環(huán)網(wǎng)絡(luò)，同網(wǎng)絡(luò)環(huán)數(shù)情況下，不同節(jié)點數(shù)的無向環(huán)網(wǎng)網(wǎng)絡(luò)，以及將網(wǎng)絡(luò)環(huán)數(shù)和節(jié)點數(shù)兩者變化相結(jié)合的無向環(huán)網(wǎng)絡(luò)，重點分析這三個問題。

2 隨機步長無向環(huán)網(wǎng)的生成

隨機步長無向環(huán)網(wǎng)是在傳統(tǒng)固定步長無向環(huán)網(wǎng)的基礎(chǔ)上構(gòu)造的，在傳統(tǒng)固定步長環(huán)網(wǎng)生成時，將固定步長改為隨機步長，同時改變網(wǎng)絡(luò)環(huán)數(shù)。因此需依次遍歷網(wǎng)絡(luò)中各個節(jié)點。以節(jié)點數(shù)N=32和環(huán)數(shù)L=4為例，隨機步長無向四環(huán)網(wǎng)絡(luò)的生成如下：

步驟1：生成一個節(jié)點數(shù)為32的環(huán)網(wǎng)，如圖1(a)所示。

步驟3：逆時針依次遍歷剩下的節(jié)點，若當前節(jié)點i的度數(shù)為ik，則當前節(jié)點i可發(fā)出的隨機邊數(shù)ik'=6-ik，在節(jié)點度小于6且與i節(jié)點不相連的節(jié)點集合Gi中，若Gi的元素個數(shù)小于ik'，則說明圖G中已不存在足夠的可選節(jié)點供節(jié)點i連接，返回步驟1，重新生成環(huán)網(wǎng)。

步驟4：重復執(zhí)行步驟3，直到所有節(jié)點滿足條件。節(jié)點2的生成如圖1(c)所示，節(jié)點3的生成如圖1(d)所示。

圖1 節(jié)點1、2、3生成示意圖

由上述步驟可知，此次隨機步長無向四環(huán)網(wǎng)絡(luò)生成后的拓撲結(jié)構(gòu)如圖2所示。

圖2 隨機步長無向四環(huán)網(wǎng)絡(luò)拓撲結(jié)構(gòu)

3 仿真算法

3.1 隨機步長無向環(huán)網(wǎng)的生成算法

Step1：構(gòu)建一個N*N的鄰接矩陣A[N-1,N-1],矩陣內(nèi)的每個元素賦初值0；構(gòu)建一個長度為N的隊列C[N-1]，隊列中每個元素賦初值0，并建立一個空鏈表L，同時令網(wǎng)絡(luò)的環(huán)數(shù)為H，這里H≥2。

Step2：r從0到N-1循環(huán)：置A[r,(r+N-1)%N]=1和A[r,(r+N+1)%N]=1。

Step3：s從0到N-1循環(huán)(對每個s,k從s+1到N-1循環(huán))：

(1)記T=C[k]，若T=0，則節(jié)點r上不需要再加入隨機邊，開始下一次r循環(huán)。

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

(3)記L中元素的個數(shù)為LLength，若LLength

(4)若T=1，則在L中隨機選擇節(jié)點d1，置A[r,d1]=A[d1,r]=1，C[r]=2，C[d1]=C[d1]+1。

(5)若T=2，則在L中隨機選擇兩個互不相同節(jié)點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個不相同節(jié)點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 隨機步長無向環(huán)網(wǎng)的直徑和平均距離求解算法

Step1：對隨機步長無向環(huán)網(wǎng)G=(V,E)的鄰接矩陣A進行如下變換：

其中，A是具有如下性質(zhì)的N階方陣：

Step2：r從0到N-1循環(huán)：對每個i,j從0到N-1循環(huán)，對每個j,k從0到N-1循環(huán)，若D[j,i]+D[i,k]

黃岡市貧困地區(qū)26家農(nóng)村基層醫(yī)療衛(wèi)生機構(gòu)基本藥物使用情況調(diào)查 ……………………………………… 王文杰等（2）：156

Step3：對Step2中得到的距離矩陣D，求出直徑[12,16]：

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

Step4：對Step2中得到的距離矩陣D，求平均距離[12]：

4 仿真實驗及結(jié)果分析

由文獻[12]可知傳統(tǒng)固定步長環(huán)網(wǎng)的直徑下界為：

其平均距離下界為：

文中選擇與傳統(tǒng)固定非單位步長無向環(huán)網(wǎng)的下界作對比實驗。選用VisioStudio2013中C#語言編制程序進行仿真，計算直徑和平均距離，同時將網(wǎng)絡(luò)拓撲結(jié)構(gòu)和得到的結(jié)果數(shù)據(jù)輸入到Matlab中進行分析。

下面給出仿真實例：

(1)當環(huán)數(shù)L=4不變，改變節(jié)點數(shù)時，進行100次對隨機步長無向環(huán)網(wǎng)的仿真實驗，對其產(chǎn)生的直徑的平均值和平均距離的平均值與固定步長環(huán)網(wǎng)的直徑下界和平均距離下界進行對比并做出相應(yīng)的分析，如圖3和圖4所示，其數(shù)據(jù)對比如表1所示。

圖3 L=4時直徑對比圖

圖4 L=4時平均距離對比圖

節(jié)點數(shù)N固定步長直徑/平均距離隨機步長(直徑/平均距離)最優(yōu)生成最差生成平均生成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得出如下結(jié)論(固定步長無向環(huán)網(wǎng)簡稱固定步長，隨機步長無向環(huán)網(wǎng)簡稱隨機步長)：

①隨機步長的平均生成直徑和平均生成的平均距離均小于固定步長的直徑下界和平均距離下界。

②隨著節(jié)點數(shù)N不斷增大，固定步長直徑下界與平均距離下界的值增加速度明顯快于隨機步長平均生成直徑和平均生成的平均距離的值增加速度。

由上述結(jié)論可知，在保持無向環(huán)網(wǎng)中其他因素相同時，當環(huán)數(shù)為定值，隨機步長的通信延遲優(yōu)于傳統(tǒng)固定步長。

(2)當節(jié)點數(shù)N=1 024不變，改變網(wǎng)絡(luò)環(huán)數(shù)時，同樣進行相應(yīng)的仿真實驗，并對其結(jié)果做出分析，如圖5和圖6所示，其數(shù)據(jù)如表2所示。

圖5 N=1 024時直徑對比圖

圖6 N=1 024時平均距離對比圖

由圖5、6和表2表明：

①隨機步長平均生成的平均距離均小于固定步長平均距離的下界。

表2 N=1 024時隨機步長與固定步長的直徑、平均距離數(shù)據(jù)對比表

②隨著網(wǎng)絡(luò)環(huán)數(shù)L不斷增大，隨機步長的直徑和平均距離均小于固定步長直徑下界和平均距離下界的趨勢越來越不明顯。

由上述兩點，在保持無向環(huán)網(wǎng)中其他因素相同時，當網(wǎng)絡(luò)環(huán)數(shù)(即節(jié)點度)在一定范圍內(nèi)，隨機步長的通信延遲優(yōu)于傳統(tǒng)固定步長，這一點也避免了高節(jié)點度拓撲所帶來的建造和運營成本的問題。

(3)結(jié)合實驗(1)、(2)，同時改變節(jié)點數(shù)N和網(wǎng)絡(luò)環(huán)數(shù)L，進行100次直徑和平均距離對比實驗，并對結(jié)果做出分析。實驗結(jié)果如表3所示。

表3 固定步長直徑/平均距離(隨機步長直徑/平均距離)

分析其總體趨勢如下：

①當L≤4(即節(jié)點度≤6)不同節(jié)點數(shù)時，隨機步長直徑、平均距離均小于固定步長直徑下界和平均距離下界；當L≥5時，隨機步長直徑≥固定步長直徑下界，但隨機步長平均距離≤固定步長平均距離下界。

②當L一定節(jié)點數(shù)不斷增加時，隨機步長直徑和平均距離的值增加速度明顯小于固定步長直徑下界和平均距離下界的值增加速度；當N一定環(huán)數(shù)不斷增加時，雖然隨機步長直徑≥固定步長，但隨機步長直徑的值增加速度相比固定步長直徑下界的值增加速度較慢，且隨機步長平均距離均小于固定步長平均距離下界。

綜上，在保持無向環(huán)網(wǎng)中其他因素相同時，當網(wǎng)絡(luò)環(huán)數(shù)(即節(jié)點度)在一定范圍內(nèi)，隨機步長得到的直徑、平均距離均小于傳統(tǒng)固定步長直徑下界、平均距離下界，則隨機步長網(wǎng)絡(luò)節(jié)點步長長度較小，從而得出結(jié)論：在無向環(huán)網(wǎng)中，隨機步長較傳統(tǒng)固定步長通信延遲占有優(yōu)勢。

5 結(jié)束語

文中采用隨機步長來構(gòu)造無向環(huán)網(wǎng)，分別對隨機步長無向環(huán)網(wǎng)直徑、平均距離和固定步長無向環(huán)網(wǎng)直徑下界、平均距離下界進行仿真實驗對比。結(jié)果表明，在保持無向環(huán)網(wǎng)中其他因素相同時，當節(jié)點度在一定范圍內(nèi)，隨機步長無向環(huán)網(wǎng)的網(wǎng)絡(luò)通信延遲和網(wǎng)絡(luò)性能均優(yōu)于固定步長無向環(huán)網(wǎng)，同時隨著網(wǎng)絡(luò)節(jié)點數(shù)不斷增加，即網(wǎng)絡(luò)規(guī)模的不斷增大，隨機步長降低通信延遲的優(yōu)勢更加明顯。因此，與當前主流的HPC采用的高節(jié)點度和固定步長拓撲結(jié)構(gòu)相比，隨機步長拓撲可成為下一代高性能計算機的潛在拓撲結(jié)構(gòu)。

[1] 周興銘．高性能計算技術(shù)發(fā)展[J]．自然雜志，2011，33(5)：249-254．

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

[3] 陳協(xié)彬.步長有限制的雙環(huán)網(wǎng)絡(luò)的最優(yōu)路由算法[J]．計算機學報，2004，27(5)：596-603．

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

[5] 方木云，屈玉貴，趙保華.雙環(huán)網(wǎng)絡(luò)的[+h]邊優(yōu)先尋徑策略[J]．計算機學報，2008，31(3)：536-542．

[6] 蘇小虎，方木云，邰偉鵬，等.雙環(huán)網(wǎng)絡(luò)G(N;1,s)的L形瓦仿真算法改進[J].小型微型計算機系統(tǒng)，2012，33(9)：2053-2055．

[7] 方木云，趙保華，屈玉貴.非單位步長雙環(huán)網(wǎng)絡(luò)G(N;r,s)的L形瓦仿真算法[J]．系統(tǒng)仿真學報，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] 方木云，侯海金，吳愛清，等.雙環(huán)網(wǎng)絡(luò)直徑點和寬直徑點的分布特性[J].小型微型計算機系統(tǒng)，2013，34(4)：749-752．

[12] 陳業(yè)斌,李 穎，鄭 嘯,等.關(guān)于有向環(huán)網(wǎng)平均直徑的研究[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] 方木云,趙保華,屈玉貴．基于圈的緊優(yōu)雙環(huán)網(wǎng)絡(luò)G(N;1,s)求解算法[J].華中科技大學學報:自然科學版,2005,33(6):17-19．

[16] 方木云，趙保華.新的無向雙環(huán)網(wǎng)絡(luò)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-)，男，教授，博士，研究方向為計算機網(wǎng)絡(luò)、網(wǎng)絡(luò)拓撲結(jié)構(gòu)等;王 俊(1990-)，男，通信作者，碩士研究生，研究方向為計算機網(wǎng)絡(luò)與網(wǎng)絡(luò)拓撲結(jié)構(gòu)。

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