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

方木云，王 俊，王 超

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

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

方木云，王 俊，王 超

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

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

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

1 概 述

目前，高性能計算機(jī)技術(shù)已成為世界各國競相爭奪的戰(zhàn)略制高點，是衡量一個國家綜合國力的重要標(biāo)志，以服務(wù)國家經(jīng)濟(jì)建設(shè)和改善民生為最高目的，并廣泛應(yīng)用于國家經(jīng)濟(jì)和人民生活相關(guān)領(lǐng)域[1]。無向多環(huán)網(wǎng)絡(luò)即m(m≥2)環(huán)網(wǎng)絡(luò)是計算機(jī)互連網(wǎng)絡(luò)或通訊系統(tǒng)的一類重要拓?fù)浣Y(jié)構(gòu)，廣泛用于計算機(jī)局域網(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年，日本國立情報學(xué)研究所MichihiroKoibuchi等提出在環(huán)網(wǎng)中采取隨機(jī)連線的方式來構(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ù)的隨機(jī)步長環(huán)網(wǎng)與現(xiàn)在高性能計算機(jī)(HPC)中采用的傳統(tǒng)環(huán)網(wǎng)(TORUS)等拓?fù)浣Y(jié)構(gòu)相比，其直徑和平均距離小、擴(kuò)展性和容錯性好[9-10]。

文獻(xiàn)[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ù)的情況下，沒有選擇直徑和平均距離達(dá)到Wong和Coppersmith給出的下界的緊優(yōu)網(wǎng)絡(luò)[15]來與隨機(jī)步長網(wǎng)絡(luò)進(jìn)行對比。選作對比的非隨機(jī)步長(non-randomshortcut)網(wǎng)絡(luò)是固定步長環(huán)網(wǎng)中的最差情況之一，以此網(wǎng)絡(luò)與隨機(jī)步長網(wǎng)絡(luò)進(jìn)行對比，導(dǎo)致隨機(jī)步長大幅降低通信延遲的這一結(jié)論可信度不高。

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

(3)在同環(huán)數(shù)的情況下，隨著網(wǎng)絡(luò)節(jié)點數(shù)的增多，即網(wǎng)絡(luò)規(guī)模不斷增大，隨機(jī)步長網(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 隨機(jī)步長無向環(huán)網(wǎng)的生成

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

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

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

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

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

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

圖2 隨機(jī)步長無向四環(huán)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3 仿真算法

3.1 隨機(jī)步長無向環(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上不需要再加入隨機(jī)邊，開始下一次r循環(huán)。

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

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

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

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

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

其中，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)生機(jī)構(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é)果分析

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

其平均距離下界為：

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

下面給出仿真實例：

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

圖3 L=4時直徑對比圖

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

節(jié)點數(shù)N固定步長直徑/平均距離隨機(jī)步長(直徑/平均距離)最優(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)簡稱固定步長，隨機(jī)步長無向環(huán)網(wǎng)簡稱隨機(jī)步長)：

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

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

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

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

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

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

由圖5、6和表2表明：

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

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

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

由上述兩點，在保持無向環(huán)網(wǎng)中其他因素相同時，當(dāng)網(wǎng)絡(luò)環(huán)數(shù)(即節(jié)點度)在一定范圍內(nèi)，隨機(jī)步長的通信延遲優(yōu)于傳統(tǒng)固定步長，這一點也避免了高節(jié)點度拓?fù)渌鶐淼慕ㄔ旌瓦\(yùn)營成本的問題。

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

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

分析其總體趨勢如下：

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

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

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

5 結(jié)束語

文中采用隨機(jī)步長來構(gòu)造無向環(huán)網(wǎng)，分別對隨機(jī)步長無向環(huán)網(wǎng)直徑、平均距離和固定步長無向環(huán)網(wǎng)直徑下界、平均距離下界進(jìn)行仿真實驗對比。結(jié)果表明，在保持無向環(huán)網(wǎng)中其他因素相同時，當(dāng)節(jié)點度在一定范圍內(nèi)，隨機(jī)步長無向環(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ī)模的不斷增大，隨機(jī)步長降低通信延遲的優(yōu)勢更加明顯。因此，與當(dāng)前主流的HPC采用的高節(jié)點度和固定步長拓?fù)浣Y(jié)構(gòu)相比，隨機(jī)步長拓?fù)淇沙蔀橄乱淮咝阅苡嬎銠C(jī)的潛在拓?fù)浣Y(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]．計算機(jī)學(xué)報，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]．計算機(jī)學(xué)報，2008，31(3)：536-542．

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

[7] 方木云，趙保華，屈玉貴.非單位步長雙環(huán)網(wǎng)絡(luò)G(N;r,s)的L形瓦仿真算法[J]．系統(tǒng)仿真學(xué)報，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].小型微型計算機(jī)系統(tǒng)，2013，34(4)：749-752．

[12] 陳業(yè)斌,李 穎，鄭 嘯,等.關(guān)于有向環(huán)網(wǎng)平均直徑的研究[J].通信學(xué)報,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].華中科技大學(xué)學(xué)報:自然科學(xué)版,2005,33(6):17-19．

[16] 方木云，趙保華.新的無向雙環(huán)網(wǎng)絡(luò)G(N;±1,±s)直徑求解方法[J]．通信學(xué)報，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

國家自然科學(xué)基金資助項目(61003311);安徽省教育廳重大項目(ZD2008005-1)

方木云(1968-)，男，教授，博士，研究方向為計算機(jī)網(wǎng)絡(luò)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等;王 俊(1990-)，男，通信作者，碩士研究生，研究方向為計算機(jī)網(wǎng)絡(luò)與網(wǎng)絡(luò)拓?fù)浣Y(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