方木云，王 俊，王 超

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

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

方木云，王 俊，王 超

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

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

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

1 概 述

目前，高性能計(jì)算機(jī)技術(shù)已成為世界各國(guó)競(jìng)相爭(zhēng)奪的戰(zhàn)略制高點(diǎn)，是衡量一個(gè)國(guó)家綜合國(guó)力的重要標(biāo)志，以服務(wù)國(guó)家經(jīng)濟(jì)建設(shè)和改善民生為最高目的，并廣泛應(yīng)用于國(guó)家經(jīng)濟(jì)和人民生活相關(guān)領(lǐng)域[1]。無向多環(huán)網(wǎng)絡(luò)即m(m≥2)環(huán)網(wǎng)絡(luò)是計(jì)算機(jī)互連網(wǎng)絡(luò)或通訊系統(tǒng)的一類重要拓?fù)浣Y(jié)構(gòu)，廣泛用于計(jì)算機(jī)局域網(wǎng)和各種并行處理結(jié)構(gòu)[2-4]，其圖論模型是指這樣一個(gè)無向圖G(N;±r,±m(xù),±s)，節(jié)點(diǎn)記為0，1，…，N-1，每個(gè)節(jié)點(diǎn)i向相鄰節(jié)點(diǎn)發(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年，日本國(guó)立情報(bào)學(xué)研究所MichihiroKoibuchi等提出在環(huán)網(wǎng)中采取隨機(jī)連線的方式來構(gòu)造環(huán)網(wǎng)，在同節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)環(huán)數(shù)(即節(jié)點(diǎn)度)的情況下，發(fā)現(xiàn)網(wǎng)絡(luò)的通信延遲比一種用在on-chip系統(tǒng)上的固定步長(zhǎng)環(huán)網(wǎng)的通信延遲可下降300倍，同時(shí)發(fā)現(xiàn)同網(wǎng)絡(luò)環(huán)數(shù)同節(jié)點(diǎn)數(shù)的隨機(jī)步長(zhǎng)環(huán)網(wǎng)與現(xiàn)在高性能計(jì)算機(jī)(HPC)中采用的傳統(tǒng)環(huán)網(wǎng)(TORUS)等拓?fù)浣Y(jié)構(gòu)相比，其直徑和平均距離小、擴(kuò)展性和容錯(cuò)性好[9-10]。

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

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

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

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

MichihiroKoibuchi等的工作是針對(duì)任意度的環(huán)網(wǎng)，為了做好橫向?qū)Ρ?，文中針?duì)同節(jié)點(diǎn)數(shù)情況下，節(jié)點(diǎn)度為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é)點(diǎn)數(shù)的無向環(huán)網(wǎng)網(wǎng)絡(luò)，以及將網(wǎng)絡(luò)環(huán)數(shù)和節(jié)點(diǎn)數(shù)兩者變化相結(jié)合的無向環(huán)網(wǎng)絡(luò)，重點(diǎn)分析這三個(gè)問題。

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

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

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

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

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

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

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

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

3 仿真算法

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

Step1：構(gòu)建一個(gè)N*N的鄰接矩陣A[N-1,N-1],矩陣內(nèi)的每個(gè)元素賦初值0；構(gòu)建一個(gè)長(zhǎng)度為N的隊(duì)列C[N-1]，隊(duì)列中每個(gè)元素賦初值0，并建立一個(gè)空鏈表L，同時(shí)令網(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)(對(duì)每個(gè)s,k從s+1到N-1循環(huán))：

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

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

(3)記L中元素的個(gè)數(shù)為L(zhǎng)Length，若LLength

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

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

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

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

Step2：r從0到N-1循環(huán)：對(duì)每個(gè)i,j從0到N-1循環(huán)，對(duì)每個(gè)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：對(duì)Step2中得到的距離矩陣D，求出直徑[12,16]：

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

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

4 仿真實(shí)驗(yàn)及結(jié)果分析

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

其平均距離下界為：

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

下面給出仿真實(shí)例：

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

圖3 L=4時(shí)直徑對(duì)比圖

圖4 L=4時(shí)平均距離對(duì)比圖

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

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

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

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

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

圖5 N=1 024時(shí)直徑對(duì)比圖

圖6 N=1 024時(shí)平均距離對(duì)比圖

由圖5、6和表2表明：

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

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

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

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

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

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

分析其總體趨勢(shì)如下：

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

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

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

5 結(jié)束語

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

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

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

[3] 陳協(xié)彬.步長(zhǎng)有限制的雙環(huán)網(wǎng)絡(luò)的最優(yōu)路由算法[J]．計(jì)算機(jī)學(xué)報(bào)，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ì)算機(jī)學(xué)報(bào)，2008，31(3)：536-542．

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

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

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

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

時(shí)間：2016-09-19

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

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