超立方體雙環(huán)互連網(wǎng)絡(luò)及路由算法
2009-01-01 00:00:00劉有耀韓俊剛
計(jì)算機(jī)應(yīng)用研究 2009年3期
（1.西安電子科技大學(xué) 微電子學(xué)院， 西安 710071; 2.西安郵電學(xué)院 計(jì)算機(jī)系， 西安 710121）
摘要：
給出了一種可擴(kuò)展的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，稱為超立方體雙環(huán)。該互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)結(jié)合了超立方體拓?fù)涞亩讨睆健⒏哌B通性、對(duì)稱性、路由簡(jiǎn)單和一種新的雙環(huán)拓?fù)浣Y(jié)構(gòu)的可擴(kuò)展性和常數(shù)節(jié)點(diǎn)度的優(yōu)點(diǎn)，使得網(wǎng)絡(luò)規(guī)模增大時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)度可以保持常數(shù)；網(wǎng)絡(luò)節(jié)點(diǎn)采用格雷編碼和約翰遜編碼的混合編碼方法，網(wǎng)絡(luò)的任意相鄰節(jié)點(diǎn)編碼有且僅有一位不同，使得路由算法設(shè)計(jì)簡(jiǎn)單。最后分別設(shè)計(jì)了基于混合編碼的單播、廣播路由算法。分析表明提出的互連網(wǎng)絡(luò)具有較好的拓?fù)湫再|(zhì)和通信性能。
關(guān)鍵詞：超立方體； 雙環(huán)； 網(wǎng)絡(luò)拓?fù)洌?節(jié)點(diǎn)編碼； 路由算法
中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：10013695(2009)03099704
Topology and routing algorithms of hypercubeconnecteddoubleloop interconnect network
LIU Youyao1，2， HAN Jungang1，2
(1.School of Microelectronics， Xidian University， Xi’an 710071， China; 2.Dept. of Computer， Xi’an Institute of Post Telecommunications，Xi’an 710121， China)
Abstract:
This paper proposed a new scalable interconnection network topology， called hypercubeconnected doubleloop(HCDL). The HCDL network combined the positive features of hypercube topology， such as small diameter， high connectivity， symmetry and simple routing， and the scalability and constant node degree of a new doubleloop topology. The HCDL network could maintain a constant node degree regardless of the increase in the network size. The nodes of the HCDL network adopted the hybrid coding combining Johnson code and Gray code. The hybrid coding scheme could make routing algorithms simple and efficient. Designed both unicasting and broadcasting routing algorithms for the HCDL network， and they were based on the hybrid coding scheme. A detailed analysis shows that the HCDL network is a better interconnection network in the properties of topology and the performance of communication.
Key words：hypercube； doubleloop； network topology； nodes coding； routing algorithms
0引言
隨著硬件技術(shù)的不斷發(fā)展，特別是超大規(guī)模集成電路工藝的發(fā)展，使得包含成千上萬處理器的大規(guī)模多處理器系統(tǒng)成為可能[1]，例如CM（connection machine）多處理器包含多達(dá)216個(gè)處理器[2]。隨著多處理器系統(tǒng)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)如此大規(guī)模的多處理器系統(tǒng)的性能具有重要的影響。為了提高并行計(jì)算的通信效率，人們一直在研究結(jié)構(gòu)簡(jiǎn)單、節(jié)點(diǎn)度小、網(wǎng)絡(luò)直徑小以及良好可擴(kuò)展的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[1，3~8]。由于超立方體的拓?fù)浣Y(jié)構(gòu)具有正規(guī)性、對(duì)稱性、強(qiáng)容錯(cuò)性、短直徑、可嵌入性等特殊性質(zhì)， 是一種最為重要和最具吸引力的并行計(jì)算機(jī)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[1，3，4，6~10]。
在超立方體網(wǎng)絡(luò)拓?fù)渲校?jié)點(diǎn)的編碼極大地方便了路由算法的實(shí)現(xiàn)；然而，隨著網(wǎng)絡(luò)規(guī)模的增大，節(jié)點(diǎn)度也隨之增加，使得設(shè)計(jì)和制造變得更加困難，并且超立方體不具有可擴(kuò)展性，因此，在實(shí)際應(yīng)用中超立方體互連網(wǎng)絡(luò)受到了限制[1，3，4，11，12]。立方環(huán)[11]（cube connectedcycles）是一個(gè)節(jié)點(diǎn)度為3的拓?fù)浣Y(jié)構(gòu)，平衡了網(wǎng)絡(luò)直徑和節(jié)點(diǎn)度；但是該網(wǎng)絡(luò)限制節(jié)點(diǎn)度為3降低了它的性能，而路由算法的實(shí)現(xiàn)較超立方體的復(fù)雜。許多基于超立方體的互連網(wǎng)絡(luò)都與超立方體相似，不具有可擴(kuò)展性，使其應(yīng)用受到了限制[12~18]。兩個(gè)基于超立方體的可擴(kuò)展互連網(wǎng)絡(luò)被提出，但它們沒有考慮網(wǎng)絡(luò)節(jié)點(diǎn)編碼，使得路由算法的實(shí)現(xiàn)較超立方體復(fù)雜[19，20]。
本文將超立方體網(wǎng)絡(luò)拓?fù)涞亩讨睆健⒏哌B通性和簡(jiǎn)單的路由策略和一種新的雙環(huán)網(wǎng)絡(luò)拓?fù)涞某?shù)節(jié)點(diǎn)度和可擴(kuò)展性結(jié)合，給出了一種超立方體連接雙環(huán)（hypercubeconnected doubleloop，HCDL(m， d)）互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。HCDL(m， d)是一種正規(guī)的、對(duì)稱的和可擴(kuò)展的互連網(wǎng)絡(luò)拓?fù)洹Ｓ眉s翰遜編碼對(duì)雙環(huán)互連網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行編碼，采用該編碼方法進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)編碼隱含互連網(wǎng)絡(luò)的相鄰節(jié)點(diǎn)和鏈路信息；編碼形成4m個(gè)節(jié)點(diǎn)的雙環(huán)互連網(wǎng)絡(luò)時(shí)，若節(jié)點(diǎn)編碼位數(shù)每增加一位，相應(yīng)的節(jié)點(diǎn)個(gè)數(shù)只增加四個(gè)；任意節(jié)點(diǎn)編碼有且僅有三個(gè)相鄰節(jié)點(diǎn)編碼。HCDL(m， d)網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)采用格雷碼和約翰遜碼的混合編碼，節(jié)點(diǎn)編碼中隱含路由信息，使得路由算法設(shè)計(jì)簡(jiǎn)單。HCDL(m， d)網(wǎng)絡(luò)可以在保持節(jié)點(diǎn)度不變進(jìn)行網(wǎng)絡(luò)的擴(kuò)展。最后，根據(jù)節(jié)點(diǎn)的混合編碼給出了HCDL (m， d)互連網(wǎng)絡(luò)路由算法。
1超立方體雙環(huán)互連網(wǎng)絡(luò)
1.1預(yù)備知識(shí)
定義1如果一組二進(jìn)制編碼具有如下性質(zhì)：a）任意兩個(gè)相鄰的編碼有且僅有一位不同（單位距離性質(zhì)）；b)第一個(gè)編碼和最后一個(gè)編碼也有且僅有一位不同（循環(huán)性質(zhì)）。這樣的二進(jìn)制編碼稱之為二進(jìn)制單位距離循環(huán)碼。
定義2對(duì)于遞減整數(shù)序列(n-1，n-2，…，2，1，0)，采用m=「n/2位的編碼表示整數(shù)序列的每個(gè)值。如果該編碼具有定義1的性質(zhì)且滿足：a）當(dāng)整數(shù)k 定義3對(duì)于互連網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)，如果它們兩者的節(jié)點(diǎn)編碼的二進(jìn)制值當(dāng)且僅當(dāng)相差一位時(shí)，這樣的兩個(gè)節(jié)點(diǎn)稱之為相鄰節(jié)點(diǎn)。 定義4雙環(huán)互連網(wǎng)絡(luò)（doubleloop，DL(2m)）是具有下述性質(zhì)的一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：a）由4m個(gè)節(jié)點(diǎn)和6m條直接鏈路組成，即由一個(gè)2m個(gè)節(jié)點(diǎn)的內(nèi)環(huán)和一個(gè)2m個(gè)節(jié)點(diǎn)的外環(huán)以及內(nèi)環(huán)和外環(huán)對(duì)應(yīng)節(jié)點(diǎn)連接所構(gòu)成的平面互連網(wǎng)絡(luò)拓?fù)洌籦）用m位的2m個(gè)約翰遜編碼標(biāo)志一個(gè)環(huán)上的節(jié)點(diǎn)，分別加上一位內(nèi)環(huán)或外環(huán)的標(biāo)志碼，即用CmCm1，…，C2C1C0對(duì)節(jié)點(diǎn)編碼，內(nèi)環(huán)與外環(huán)的對(duì)應(yīng)節(jié)點(diǎn)編碼只有最高位相反其余位相同；c）節(jié)點(diǎn)編碼的規(guī)則為：當(dāng)且僅當(dāng)DL(2m)中兩個(gè)節(jié)點(diǎn)的編碼有且僅有一位不同時(shí)，兩個(gè)節(jié)點(diǎn)是相鄰的，即這兩個(gè)節(jié)點(diǎn)之間有一直接鏈路。 圖1給出了一個(gè)m=4的DL(2m)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，圖中有4×4=16個(gè)節(jié)點(diǎn)和6×4=24條直接鏈路，相鄰節(jié)點(diǎn)的編碼只有一位不同。DL(2m)互連網(wǎng)絡(luò)具有正規(guī)性、可擴(kuò)展性、對(duì)稱性和平面性。 定義5n維超立方體（hypercube）互連網(wǎng)絡(luò)是具有下述性質(zhì)的一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：a)它由2n個(gè)節(jié)點(diǎn)和n×2n1條直接鏈路構(gòu)成；b) 每一個(gè)節(jié)點(diǎn)可由一個(gè)n位二進(jìn)制格雷碼Bn1Bn2，…，B1B0進(jìn)行編碼；c)節(jié)點(diǎn)編碼的規(guī)則為：當(dāng)且僅當(dāng)兩個(gè)節(jié)點(diǎn)的二進(jìn)制碼有且僅有一位不同時(shí)，兩個(gè)節(jié)點(diǎn)是相鄰的，即這兩個(gè)節(jié)點(diǎn)之間有一直接鏈路。 圖2 給出了一個(gè)4 維超立方體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，圖中有24 = 16 個(gè)節(jié)點(diǎn)和4×241 = 32 條直接鏈路，并標(biāo)志出了節(jié)點(diǎn)的編號(hào)(分別從0000~1111)。Hypercube網(wǎng)絡(luò)具有正規(guī)性、對(duì)稱性、短直徑等優(yōu)良特性，但是不具有可擴(kuò)展性。 定義6節(jié)點(diǎn)組的距離[5，6]。對(duì)于一個(gè)互連網(wǎng)絡(luò)N中的一組節(jié)點(diǎn)G，節(jié)點(diǎn)組G的距離定義為該組中任意兩個(gè)節(jié)點(diǎn)距離的最大值。 定義7最優(yōu)分組[5，6]。對(duì)于給定的正整數(shù)λ，在互連網(wǎng)絡(luò)N中存在多個(gè)包含λ個(gè)節(jié)點(diǎn)的組，稱距離最短的組為包含λ個(gè)節(jié)點(diǎn)的最優(yōu)分組，記為Gλ(N)。 定義8可分組性[5，6]。對(duì)于給定的兩個(gè)互連網(wǎng)絡(luò)N1和N2，若對(duì)于任意正整數(shù)λ有Gλ(N1)的距離≤Gλ(N2)的距離，則稱互連網(wǎng)絡(luò)N1 的可分組性優(yōu)于互連網(wǎng)絡(luò)N2 的可分組性。 1.2超立方體雙環(huán)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 定義9超立方體雙環(huán)HCDL(m， d)互連網(wǎng)絡(luò)拓?fù)涞臉?gòu)造。對(duì)于4m×2d個(gè)節(jié)點(diǎn)，按如下方法來構(gòu)造HCDL(m， d)互連網(wǎng)絡(luò)： a)4m個(gè)節(jié)點(diǎn)連接成DL(2m)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，共得到2d個(gè)DL(2m)。在每個(gè)DL(2m)中，節(jié)點(diǎn)按定義4的方法進(jìn)行編碼，每個(gè)DL(2m)稱為一片。 b)將2d個(gè)DL(2m)按照如下方法連接成超立方體：2d個(gè)DL(2m)按照0~2d-1進(jìn)行編碼，將所有DL(2m)中節(jié)點(diǎn)編碼相同的節(jié)點(diǎn)按定義5的方式構(gòu)成超立方體。 c）HCDL(m， d)的編碼。HCDL(m， d)采用如下編碼方法，每個(gè)節(jié)點(diǎn)編碼由兩部分(Ah， At)組成。其中Ah(d位二進(jìn)制碼)為每個(gè)DL(2m)片的編碼；At(m+1位二進(jìn)制碼)為DL(2m)片內(nèi)各節(jié)點(diǎn)的編碼。 定理1對(duì)HCDL(m， d)互連網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)A(Am+d，…，Am+1AmAm1，…，A1A0)、B(Bm+d，…，Bm+1BmBm1，…，B1B0)；Ai， Bi∈{0，1}，i∈{0，1，…， m+d}，則A、B間的距離d(A，B)=∑iAiBi。 證明由HCDL(m， d)互連網(wǎng)絡(luò)的構(gòu)造過程易知每個(gè)DL(2m)片的編碼是格雷編碼，兩個(gè)DL(2m)片編碼的格雷碼有且僅有一位不同時(shí)對(duì)應(yīng)節(jié)點(diǎn)之間有直接鏈路，DL(2m)片內(nèi)兩個(gè)節(jié)點(diǎn)編碼有且僅有一位不同時(shí)是相鄰節(jié)點(diǎn)，所以，整個(gè)網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)編碼之間有且僅有一位不同時(shí)是相鄰節(jié)點(diǎn)。超立方體節(jié)點(diǎn)編碼采用格雷編碼且兩個(gè)節(jié)點(diǎn)之間有且僅有一位不同時(shí)是相鄰節(jié)點(diǎn)，在超立方體中任意兩個(gè)節(jié)點(diǎn)之間的距離是兩節(jié)點(diǎn)編碼不同位數(shù)之和，即漢明距離[3，4]。所以HCDL(m， d)互連網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的距離為兩個(gè)DL(2m)片編碼的不同位數(shù)和DL(2m)片內(nèi)節(jié)點(diǎn)編碼的不同位數(shù)之和。該定理結(jié)論成立。 由于DL(2m)片內(nèi)節(jié)點(diǎn)的編碼采用約翰遜碼簡(jiǎn)化了路由算法的實(shí)現(xiàn)，但是節(jié)點(diǎn)編碼位數(shù)隨著節(jié)點(diǎn)的增加而線性增加。可以將約翰遜碼轉(zhuǎn)換為自然二進(jìn)制碼進(jìn)行存儲(chǔ)，使得它的二進(jìn)制碼的位數(shù)和節(jié)點(diǎn)之間是對(duì)數(shù)關(guān)系。對(duì)DL(2m)的內(nèi)環(huán)或者外環(huán)節(jié)點(diǎn)的約翰遜編碼（Q2m1，Q2m2，…， Q2，Q1，Q0），可以找出一組連續(xù)的m=「log2n」位的自然二進(jìn)制碼來與之對(duì)應(yīng)。a) 當(dāng)Qp的最高位為0時(shí)，它的自然二進(jìn)制碼就是把Qp中含1的個(gè)數(shù)相加所得結(jié)果對(duì)應(yīng)的二進(jìn)制碼；b)當(dāng)Qp的最高位為1時(shí)，它的自然二進(jìn)制碼就是由m加上0的個(gè)數(shù)所得結(jié)果對(duì)應(yīng)的二進(jìn)制碼。根據(jù)定義2，可以將自然二進(jìn)制碼轉(zhuǎn)換為約翰遜碼。所以，自然二進(jìn)制碼和約翰遜碼之間存在一一對(duì)應(yīng)關(guān)系。 1.3HCDL( m， d)網(wǎng)絡(luò)的性質(zhì) 性質(zhì)1HCDL(m， d)網(wǎng)絡(luò)是正規(guī)互連網(wǎng)絡(luò)，任意節(jié)點(diǎn)的連接度均為d+3。 由于每個(gè)DL(2m)片是正規(guī)互連網(wǎng)絡(luò)且節(jié)點(diǎn)連接度均為3，根據(jù)HCDL(m， d)網(wǎng)絡(luò)的構(gòu)造過程易知，把DL(2m)片看做一個(gè)節(jié)點(diǎn)，該網(wǎng)絡(luò)就是超立方體且節(jié)點(diǎn)連接度為d，所以，HCDL(m， d)網(wǎng)絡(luò)是正規(guī)網(wǎng)絡(luò)，節(jié)點(diǎn)連接度為d+3。 性質(zhì)2HCDL(m， d)網(wǎng)絡(luò)具有良好的擴(kuò)展性。 可擴(kuò)展性是指在網(wǎng)絡(luò)拓?fù)湫阅鼙３植蛔兊那闆r下擴(kuò)充節(jié)點(diǎn)的能力，即系統(tǒng)有效利用所增加的處理資源能力的反映，影響網(wǎng)絡(luò)的路由效率。在DL(2m)片內(nèi)，只要將編碼位數(shù)增加一位，即m增大1，則相應(yīng)的節(jié)點(diǎn)個(gè)數(shù)就增加四個(gè)，整個(gè)HCDL(m， d)的節(jié)點(diǎn)數(shù)就增加4×2d個(gè)。在DL(2m)片內(nèi)，除了與新增節(jié)點(diǎn)相連的節(jié)點(diǎn)外，其他節(jié)點(diǎn)與連接關(guān)系沒有任何變動(dòng)。原來節(jié)點(diǎn)的超立方體連接關(guān)系沒有變化，節(jié)點(diǎn)的連接度沒有變化。 性質(zhì)3HCDL(m， d)網(wǎng)絡(luò)是對(duì)稱網(wǎng)絡(luò)。 根據(jù)HCDL(m， d)網(wǎng)絡(luò)的構(gòu)造過程易知，該網(wǎng)絡(luò)中任何節(jié)點(diǎn)標(biāo)志為原點(diǎn)都同構(gòu)于本身，即從任何節(jié)點(diǎn)觀察網(wǎng)絡(luò)都是一樣的。簡(jiǎn)化了路由算法的實(shí)現(xiàn)，即路由算法與節(jié)點(diǎn)位置無關(guān)系。 性質(zhì)4HCDL(m， d)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間的距離最大值（網(wǎng)絡(luò)直徑）為m+d+1。 由于DL(2m)片的直徑為2m個(gè)節(jié)點(diǎn)環(huán)的直徑和兩個(gè)環(huán)之間的距離之和，即為m+1。根據(jù)HCDL(m， d)網(wǎng)絡(luò)的構(gòu)造過程易知，把DL(2m)片看做一個(gè)節(jié)點(diǎn)，該網(wǎng)絡(luò)就是d維的超立方體，其直徑為d。所以，HCDL(m， d) 的網(wǎng)絡(luò)直徑為DL(2m)直徑和超立方體直徑之和，即m+d+1。 性質(zhì)5HCDL(m， d)網(wǎng)絡(luò)的成本（鏈路數(shù)）為2d+1×m×(d+3)。 HCT(k， m， d)網(wǎng)絡(luò)的鏈路數(shù)為4m個(gè)d維超立方體鏈路數(shù)(2dlog22d)/2和2d個(gè)DL(2m)鏈路數(shù)6m之和，4m×2d1×d+2d ×6m= 2d+1×m×(d+3)。 性質(zhì)6HCDL(m， d)網(wǎng)絡(luò)的等分寬度為m×2d+1。 網(wǎng)絡(luò)等分寬度是把網(wǎng)絡(luò)分成兩個(gè)相等網(wǎng)絡(luò)時(shí)必須刪去的最小通信鏈路數(shù)；是將4m的d維超立方體等分，所以等分寬度為4m×2d1= m×2d+1。 為了進(jìn)一步說明HCDL(m， d)網(wǎng)絡(luò)的優(yōu)良特性，表1給出了HCDL(m， d)互連網(wǎng)絡(luò)和2維Torus、Hypercube互連網(wǎng)絡(luò)的對(duì)比。其中N=4m×2d。 表1三種靜態(tài)網(wǎng)絡(luò)的性能特征 網(wǎng)絡(luò)類型 度鏈路數(shù)網(wǎng)絡(luò)直徑等分寬度 HCDL(m， d)d+32d+1×m×(d+3)m+d+1m×2d+1 2維Torus42N2 N/2」2N Hypercube log2N(Nlog2N)/2log2NN/2 如果互連網(wǎng)絡(luò)N1的可分組性優(yōu)于N2的可分組性，則利用Gλ(N1)作為一組計(jì)算節(jié)點(diǎn)的通信開銷就小于Gλ(N2)作為一組計(jì)算節(jié)點(diǎn)的通信開銷，因此考慮互連網(wǎng)絡(luò)的可分組性具有重要意義[5，6]。根據(jù)HCT(k， m， d)的構(gòu)造過程及定義6~8，HCDL(m， d)、 Torus和Hypercube的最優(yōu)分組距離分別為式(1)~(3)。 d(Gλ(Torus))=2(|λ-1|)(1) d(Gλ(HCDL))=「log2λ(2) d(Gλ(Hypercube))=「log2λ(3) 性質(zhì)7HCDL(m， d)的可分組性和超立方體的可分組性相同，優(yōu)于Torus的可分組性。 由式(1)(3)可知，當(dāng)λ≤6時(shí)，d(Gλ(Torus))=d(Gλ(HCDL))，因此只要λ＞6時(shí)結(jié)論成立即可。構(gòu)造函數(shù) f(λ)=log2λ-2λ+2， f ′(λ)=1/(λ ln 2)-1/λ=(1-λ ln 2)/λ ln 2。 當(dāng)λ＞6時(shí)，f ′(λ)＜0， 可知 f(λ)單調(diào)遞減，即d(Gλ(HCDL))＜d(Gλ(Torus)) 。 由上述性質(zhì)可知，HCDL(m， d)互連網(wǎng)絡(luò)具有較好的拓?fù)湫再|(zhì)和通信性能。 2 HCDL( m， d)互連網(wǎng)絡(luò)上的路由算法 路由算法是影響并行計(jì)算效率的重要因素，本文主要對(duì)單播和多播路由算法及性能進(jìn)行分析。 2.1HCDL( m， d)網(wǎng)絡(luò)的單播路由算法及性能分析 2.1.1單播路由算法 假設(shè)節(jié)點(diǎn)S(Sm+d，…，Sm+1Sm Sm1，…，S1S0)向節(jié)點(diǎn)D(Dm+d，…，Dm+1DmDm1，…，D1D0)發(fā)送數(shù)據(jù)。由DL(2m)節(jié)點(diǎn)的編碼方法和HCDL(m， d)互連網(wǎng)絡(luò)的構(gòu)造過程可知，HCDL(m， d)任意相鄰節(jié)點(diǎn)編碼有且僅有一位不同，該節(jié)點(diǎn)編碼隱含了全局的路由信息。源節(jié)點(diǎn)(S)與目的節(jié)點(diǎn)(D)的距離則為d= Hamming（SD）。其中：代表S和D進(jìn)行位異或運(yùn)算；Hamming函數(shù)代表把S和D異或后1的個(gè)數(shù)相加運(yùn)算，即結(jié)果為漢明距離。路由過程如下： a)如果S和D在同一個(gè)DL(2m)片中，由定義4、5和1.2節(jié)可知，S節(jié)點(diǎn)和D節(jié)點(diǎn)的超立方體編碼是相同的，即Hamming（Sm+d，…，Sm+1Dm+d，…，Dm+1）≡0，只進(jìn)行ST=Sm，…，S1S0，DT=Dm，…，D1D0的片內(nèi)路由。由定義4可知，片內(nèi)ST節(jié)點(diǎn)與相鄰節(jié)點(diǎn)編碼只相差一位，它的兩個(gè)同環(huán)相鄰節(jié)點(diǎn)編碼分別為ST1= SmS0Sm-1，…，S2S1，ST2= SmSm-2Sm-3，…，S0Sm-1；一個(gè)異環(huán)相鄰節(jié)點(diǎn)編碼為ST3=SmSm-1Sm-2，…，S1S0，那么相鄰節(jié)點(diǎn)與D的距離為dT1=Hamming（ST1DT）， dT2= Hamming（ST2DT）， dT3= Hamming（ST3DT）。如果dT3≡0，dmin＝dT3，否則dmin＝min{dT1，dT2}；再將包發(fā)送到dmin所對(duì)應(yīng)的相鄰節(jié)點(diǎn)并將S修改為該片內(nèi)相鄰節(jié)點(diǎn)的編碼。然后計(jì)算d值，如果d≡0，那么S標(biāo)志的節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn)，否則重復(fù)該過程。 b）如果S和D在同一個(gè)Hypercube中，那么由定義4、5和第1.2節(jié)可知，S節(jié)點(diǎn)和D節(jié)點(diǎn)的DL(2m)片內(nèi)編碼是相同的，即Hamming（Sm Sm-1，…，S1S0DmDm-1，…，D1D0）≡0，只進(jìn)行SH=Sm+d，…，Sm+1，DH=Dm+d，…，Dm+1的超立方體路由。F=1m+d0 m+d-1，…，0m+20m+1。路由過程如下：首先計(jì)算R=SHDH，Q=RF（代表R和F進(jìn)行位與運(yùn)算）。如果Q≠0，那么SH＝SHQ，將包發(fā)送到SH標(biāo)志的節(jié)點(diǎn)；否則將F右移一位重復(fù)該過程，直到F為全0序列。 c）如果S和D既不在同一個(gè)Hypercube中，也不在同一個(gè)DL(2m)片中，是任意的兩個(gè)節(jié)點(diǎn)，那么首先按a）的方式將數(shù)據(jù)包路由在同一個(gè)Hypercube中，即到達(dá)節(jié)點(diǎn)S′＝(Sm+k+d-5，…，Sm+kDm+k-1，…，DmDm-1，…，D1D0)；然后按b)的方式將包路由到目的節(jié)點(diǎn)D。 2.1.2算法性能分析 HCDL(m， d)的路由算法主要優(yōu)點(diǎn)是網(wǎng)絡(luò)節(jié)點(diǎn)采用了格雷碼和約翰遜碼的混合編碼方法，使得任意兩個(gè)節(jié)點(diǎn)編碼異或所得1的個(gè)數(shù)即為兩個(gè)節(jié)點(diǎn)間的最小距離，并且該編碼隱含了全局的路由信息和相鄰節(jié)點(diǎn)間的關(guān)系。使得網(wǎng)絡(luò)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，只要存儲(chǔ)當(dāng)前節(jié)點(diǎn)和目的節(jié)點(diǎn)的編碼就可以正確地路由數(shù)據(jù)。 根據(jù)HCDL(m， d)單播路由算法，數(shù)據(jù)在DL(2m)中傳播最壞情況下需要m+1輪通信操作；在同一個(gè)Hypercube中傳播最壞情況下需要d輪通信操作，因此，最壞情況下總共需要m+d+1輪通信操作。算法能沿著越短的路徑將數(shù)據(jù)從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn)，算法的通信效率就越高。以上單播路由算法的每一次轉(zhuǎn)發(fā)數(shù)據(jù)是按最短路徑進(jìn)行的，所以最壞情況下，路由的路徑不會(huì)超過網(wǎng)絡(luò)的直徑m+d+1。 2.2HCDL(m， d)的廣播路由算法及性能分析 2.2.1廣播路由算法 假設(shè)由節(jié)點(diǎn)S發(fā)送數(shù)據(jù)到其他所有節(jié)點(diǎn)。將節(jié)點(diǎn)S的數(shù)據(jù)在所在的DL(2m)片內(nèi)采用遞歸加倍方法進(jìn)行廣播到所在片的所有節(jié)點(diǎn)；收到數(shù)據(jù)信息的節(jié)點(diǎn)將數(shù)據(jù)采用基于樹的路由方法擴(kuò)散給各自所在的超立方體之內(nèi)的所有節(jié)點(diǎn)。 2.2.2算法性能分析 以這種方式進(jìn)行廣播路由，節(jié)點(diǎn)S將數(shù)據(jù)廣播給所在DL(2m)片內(nèi)的所有節(jié)點(diǎn)需要m+1輪通信操作；然后數(shù)據(jù)在超立方體之內(nèi)進(jìn)行廣播需要d輪通信操作，所以整個(gè)廣播需要m+d+1輪通信操作。 3結(jié)束語 Hypercube互連網(wǎng)絡(luò)是最為重要和最具吸引力的并行計(jì)算機(jī)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，但是Hypercube不具有可擴(kuò)展性，在多處理器系統(tǒng)互連網(wǎng)絡(luò)的實(shí)際應(yīng)用中受到了限制。因此，本文提出了一種簡(jiǎn)單的可擴(kuò)展的DL(2m)互連網(wǎng)絡(luò)結(jié)構(gòu)，結(jié)合Hypercube網(wǎng)絡(luò)的高連接度、短直徑、簡(jiǎn)單的路由策略和DL(2m)網(wǎng)絡(luò)的常數(shù)節(jié)點(diǎn)度、可擴(kuò)展性，給出了一種HCDL(m， d)互連網(wǎng)絡(luò)。該互連網(wǎng)絡(luò)是一種節(jié)點(diǎn)度為d+3的正規(guī)對(duì)稱可擴(kuò)展的互連網(wǎng)絡(luò)，可以在保持節(jié)點(diǎn)度不變而進(jìn)行網(wǎng)絡(luò)的擴(kuò)展，網(wǎng)絡(luò)節(jié)點(diǎn)編碼采用約翰遜碼與格雷碼的混合編碼方法，使得路由算法簡(jiǎn)單高效。HCDL(m， d)互連網(wǎng)絡(luò)的可分組性和超立方體的可分組性相同，優(yōu)于Torus的可分組性，是一種適合大規(guī)模并行計(jì)算的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。 參考文獻(xiàn)： [1] WU Rueiyu ， CHANG J G， CHEN Genhuey. Nodedisjoint paths in hierarchical hypercube networks[C]//Proc of the 20th International Parallel and Distributed Processing Symposium.[s.l.]: IEEE， 2006:42004207. [2]HILLIS W D. The connection machine[M]. Cambridge:MIT Press， 1985. [3]DALLY W， TOWLES B. Principles and practices of interconnection networks[M]. San Francisco: Morgan Kaufmann Press， 2004. [4]GRAMA A， GUPTA A， KARYPIS G， et al. Introduction to parallel computing[M].2nd ed.[s.l.]:AddisonWesley， 2003. [5]劉方愛，劉志勇，喬香珍.一種實(shí)用的互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)RP(k)及路由算法[J].中國(guó)科學(xué)：E輯， 2002，32(3):461473. [6]王雷，林亞平，陳治平.基于Petersen圖互連的超立方體網(wǎng)絡(luò)及其路由算法[J].系統(tǒng)仿真學(xué)報(bào)， 2007，19(6):13391343. [7]王雷，林亞平.基于超立方體環(huán)連接的Petersen圖互連網(wǎng)絡(luò)研究[J].計(jì)算機(jī)學(xué)報(bào)， 2005，28(3) :409413. [8]LOH P K K， HSU W J， PAN Y. The exchanged hypercube[J]. IEEE Trans on Parallel and Distributed Systems， 2005，16(9):866874. [9]ABACHI H， WALKER AJ. Network expandability and cost analysis of torus， hypercube and tree multiprocessor systems[C]//Proc of the 28th Southeastern Symposium on System Theory. Washington DC: IEEE Computer Society， 1996:426430. [10]OULDKHAOUA M. On the optimal network for multicomputers: torus or hypercube?[C]//Proc of the 4th International EuroPar Conference on Parallel Processing. London: SpringerVerlag， 1998:989992. [11]PREPARATA F P， VUILLEMIN J. The cubeconnected cycles: a versatile network for parallel computation[J]. Communications of the ACM， 1981，24(5):300309. [12]MALLUHI Q M， BAYOUMI M A. The hierarchical hypercube: a new interconnection topology for massively parallel systems[J]. IEEE Trans on Parallel and Distributed Systems， 1994，5(1):1730. [13]GHOSE K， DESAI K R. Hierarchical cubic networks[J]. IEEE Trans on Computers， 1995，6(4):427435. [14]KUMAR J M， PATNAIK L M. Extended hypercube: a hierarchical interconnection network of hypercubes[J]. IEEE Trans on Parallel and Distributed Systems， 1992， 3(1):4557. [15]TZENG N F， WEI S. Enhanced hypercubes[J]. IEEE Trans on Computers， 1991，40(3):284294. [16]BHUYAN L N， AGRAWAL D P. Generalized hypercube and hyperbus structures constructing massively parallel computers[J]. IEEE Trans on Computers， 1984，33(5):323333. [17]CHEN C， AGRAWAL D P， BURKE J R. dBCube: a new class of hierarchical multiprocessor interconnection networks with area efficient layout[J]. IEEE Trans on Parallel and Distributed Systems， 1993，4(1):13321344. [18]EFE K. The crossed cube architecture for parallel computation[J]. IEEE Trans on Parallel and Distributed Systems， 1992，3(9):513524. [19]LOURI A， SUNG H. Scalable optical hypercubebased interconnection network for massively parallel computing[J]. Applied Optics， 1994， 33(11):75887598. [20]LOURI A， WEECH B， NEOCLEOUS C. A spanning multichannel linked hypercube: a gradually scalableoptical interconnection network for massively parallel computing[J]. IEEE Trans on Parallel and Distributed Systems， 1998，9(5):497512.
