ECQ網(wǎng)絡(luò)中嵌入哈密頓圈的高效算法研究

周東仿

(1.上海出版印刷高等?？茖W(xué)校出版?zhèn)髅窖芯吭?，上?200093；2.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006)

0 引言

互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)一直是并行計(jì)算領(lǐng)域研究的熱點(diǎn)，受到了國內(nèi)外學(xué)者的廣泛關(guān)注。迄今為止，人們陸續(xù)提出了多種互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如超立方體網(wǎng)絡(luò)(Hypercube)[1]、交叉立方體(crossed cube，CQ)網(wǎng)絡(luò)[2]、莫比烏斯立方體(Mobius cube，MQ)網(wǎng)絡(luò)[3]、扭立方體(twisted cube，TQ)網(wǎng)絡(luò)[4]。這幾種n-維的互連網(wǎng)絡(luò)的鏈路數(shù)均為n2n-1。為了既降低網(wǎng)絡(luò)成本開銷又保持網(wǎng)絡(luò)性能不受影響，同時減少網(wǎng)絡(luò)連接的復(fù)雜度，Loh等進(jìn)一步在超立方體網(wǎng)絡(luò)基礎(chǔ)上有條理地刪除一些邊，構(gòu)建了一種新的網(wǎng)絡(luò)——交換超立方體(exchanged hypercube，EH)網(wǎng)絡(luò)[5]。在維度相同的情況下，與超立方體網(wǎng)絡(luò)相比，EH網(wǎng)絡(luò)的鏈路數(shù)約為超立方體網(wǎng)絡(luò)鏈路數(shù)的一半，而直徑與超立方體網(wǎng)絡(luò)的直徑近似相等。

為了既降低網(wǎng)絡(luò)直徑又減少網(wǎng)絡(luò)構(gòu)造成本，以保持良好的網(wǎng)絡(luò)性能，Li等[6]在CQ網(wǎng)絡(luò)基礎(chǔ)上構(gòu)建了一種新的網(wǎng)絡(luò)，即交換交叉立方體(exchanged crossed cube，ECQ)網(wǎng)絡(luò)。該網(wǎng)絡(luò)既保持了CQ網(wǎng)絡(luò)的許多優(yōu)越性質(zhì)，又融合了EH網(wǎng)絡(luò)的良好性質(zhì)。首先，ECQ網(wǎng)絡(luò)的直徑為同維EH網(wǎng)絡(luò)直徑的一半，與同維CQ網(wǎng)絡(luò)的直徑幾乎相等。其次，ECQ網(wǎng)絡(luò)的鏈路數(shù)約為同維CQ網(wǎng)絡(luò)的鏈路數(shù)的一半，與同維EH網(wǎng)絡(luò)的鏈路數(shù)相等。另外，ECQ網(wǎng)絡(luò)還具有良好的可擴(kuò)展性、可分割性、同構(gòu)性[6]、可嵌入性[7-8]和可診斷性[9]等。

一個互連網(wǎng)絡(luò)可以用一個簡單無向圖G來表示。圖G的頂點(diǎn)V(G)表示網(wǎng)絡(luò)中的處理器(或處理機(jī))，邊E(G)表示處理器(或處理機(jī))之間的通信鏈路。若圈C包含圖G中所有頂點(diǎn)一次且僅一次，則稱G具有哈密頓性質(zhì)、圈C為哈密頓圈。

如果在網(wǎng)絡(luò)的路由算法中使用哈密頓圈，則能夠減少或避免死鎖和擁塞，提高通信效率[10]。其次，哈密頓性問題可視為不交路徑覆蓋問題的一個特例。例如一對二不交路徑覆蓋性問題本質(zhì)上就是哈密頓性問題。再者，如果在互連網(wǎng)絡(luò)或數(shù)據(jù)中心網(wǎng)絡(luò)的故障診斷中使用哈密頓性質(zhì)，則能降低該網(wǎng)絡(luò)故障診斷的次數(shù)，實(shí)現(xiàn)該網(wǎng)絡(luò)的故障檢測與快速定位，從而進(jìn)一步提高該網(wǎng)絡(luò)故障診斷的效率。除此之外，哈密頓性質(zhì)也可應(yīng)用在計(jì)算機(jī)科學(xué)編碼中[10]。因此，研究網(wǎng)絡(luò)的哈密頓性質(zhì)具有重要價值。但是，并不是所有的網(wǎng)絡(luò)都具有哈密頓性質(zhì)，且如何判定一個網(wǎng)絡(luò)是否具有哈密頓性質(zhì)的充分必要條件也是不存在的。哈密頓圈或哈密頓路徑的求解也是一個多項(xiàng)式復(fù)雜程度的非確定性多項(xiàng)式(non-deterministic polynomial，NP)問題[11-14]。

盡管對一般互連網(wǎng)絡(luò)哈密頓性質(zhì)的求解問題是NP完全問題，但是對一些特定網(wǎng)絡(luò)中的哈密頓問題求解已經(jīng)得到解決。本文研究了ECQ網(wǎng)絡(luò)的哈密頓性質(zhì)，給出了在ECQ網(wǎng)絡(luò)中構(gòu)造哈密頓圈的算法。具體是：給出了當(dāng)s≥3并且t≥3時，從ECQ網(wǎng)絡(luò)中任意一個結(jié)點(diǎn)出發(fā)即可高效地構(gòu)造出哈密頓圈;分析了當(dāng)1≤s≤2并且s≤t時，從ECQ網(wǎng)絡(luò)中任意一個結(jié)點(diǎn)出發(fā)哈密頓圈的構(gòu)造算法，也考慮了所有情形，確保了研究問題的完備性；通過模擬試驗(yàn)，對該算法進(jìn)行了驗(yàn)證。

1 準(zhǔn)備工作

定義1.1 設(shè)u=u1u0、v=v1v0，u、v均為二進(jìn)制字符串。若滿足(u,v)∈{(00,00),(10,10),(01,11),(11,01)}，那么稱u與v是相關(guān)的,記為u～v[2]。

①當(dāng)n為偶數(shù)時，un-2=vn-2。

X3和X4如圖1所示。

圖1 X3和X4

根據(jù)文獻(xiàn)[6]和ECQ網(wǎng)絡(luò)的基本性質(zhì)，對ECQ網(wǎng)絡(luò)進(jìn)行如下定義。

定義1.3 (s+t+1)維的ECQ網(wǎng)絡(luò)可表示為:ECQ(s,t)=(V,E)。其中：s≥1且t≥1；V為頂點(diǎn)集，V={as-1...a0bt-1...b0c|ai,bj,c∈{0,1},i∈[0,s- 1],j∈[0,t- 1]}；E為邊集，由三種邊集(E1、E2和E3)組成，且E1、E2和E3互不相交，E=E1∪E2∪E3。ECQ網(wǎng)絡(luò)中任意兩個頂點(diǎn)u與v，有u、v∈V。

邊集E1、E2和E3定義如下。

①(u,v)∈E1,有且只有u[0]≠v[0]，u⊕v=1。其中，?表示異或操作。

②(u,v)∈E2,有且只有u[t:1]=v[t:1],u[0]=v[0]=0,并且(u[s+t:t+1],v[s+t:t+1])∈E(Xs)。

③(u,v)∈E3,有且只有u[s+t:t+1]=v[s+t:t+1],u[0]=v[0]=1，并且(u[t:1],v[t:1])∈E(Xt)。

由以上的定義可知，ECQ(s,t)具有2s+t+1個頂點(diǎn)、(s+t+2)2s+t-1條邊，并且ECQ(s,t)和ECQ(t,s)是同構(gòu)的，一個ECQ(s,t)可分成2s個Xt和2t個Xs[6]。ECQ(2,3)如圖2所示。圖2中：虛線表示E1邊；細(xì)實(shí)線表示E3邊；粗實(shí)線表示E2邊。

為了簡便，不妨假設(shè)s≤t,把“as-1...a0bt-1...b0c”簡寫成“abc”。

圖2 ECQ(2,3)

2 哈密頓圈算法設(shè)計(jì)

Chen等給出了在Xn中時間復(fù)雜度為O(n)的求解哈密頓圈的LGC算法[13]。其基本思想如下。

(1)設(shè)πn=(d1,d2,…,dn)是1,2…n的一個隨機(jī)排列，滿足:①min(dn-1,dn)為奇數(shù)； ②|dn-1-dn|=1。

(2)構(gòu)造以下數(shù)列。

RLπ(1)=d1，RLπ(i)=RLπ(i-1),di,RLπ(i-1)(2≤i≤n),RLπ=RLπ(n)=(p1,p2,…,p2n-1)。

(3)對任一點(diǎn)u,ui=neighbor(ui-1,pi)。

(u0,u1,…,u2n-1)為Xn中的哈密頓回路。

當(dāng)3≤s≤t時，首先在Xn基礎(chǔ)上，按照LGC算法構(gòu)造Xn的哈密頓圈。方法如下。

假設(shè)(a0,a1,…an-1)、(b0,b1,…bm-1)分別為Xs和Xt中構(gòu)造出的哈密頓回路(其中n=2s,m=2t)。則按照LGC算法以及ECQ(s,t)的定義，構(gòu)造如下。

a0b00→a0b01→a0b11→a0b10→a1b10→a1b11→…→a1bm-10→a1bm-11→a1b01→a1b00→a2b00→a2b01→a2b11→a2b10→a3b10→a3b11…→a3bm-10→a3bm-11→a3b01→a3b00→…an-2b00→an-2b01→an-2b11→an-2b10→an-1b10→an-1b11→…→an-1bm-10→an-1bm-11→an-1b01→an-1b00→

以上即為ECQ(s,t)上的哈密頓回路。由于該構(gòu)造方法是根據(jù)ECQ(s,t)的定義在常數(shù)時間內(nèi)即可構(gòu)造完成，所以該算法是高效的。進(jìn)一步考慮了1≤s≤2的情形。當(dāng)1≤s≤2且s≤t時，設(shè)計(jì)了FindHcycle算法，即考慮了所有情形。

算法:FindHcycle

輸入:ECQ(s,t)上任意一個結(jié)點(diǎn)，且滿足1≤s≤2，s≤t。

輸出:若存在一個哈密頓圈HC，則輸出并返回。

a←ECQ(s,t)中第一個結(jié)點(diǎn)；

v←a；

l←0；

s.push(v)；

flag←1；

while(stack s is not empty) do

v=s.peek();

ifl=2s+t +1-1

then ifv與a相鄰

then return HC；

elsev←s.pop()；

flag←0；

l←l-1；

end if

elsev←next(v);

ifv!=null and flag !=true

thens.push(v)；

flag =true；

l←l+1；

elsev←s.pop()；

flag←0;

l←l-1；

end if

end if

end while

3 仿真試驗(yàn)

通過仿真試驗(yàn)，對FindHcycle算法和證構(gòu)造算法進(jìn)行有效性和正確性驗(yàn)證。試驗(yàn)環(huán)境是內(nèi)存為8 GB、CPU為Intel(R) Core(TM) i5-3320M/4核/2.60G Hz的筆記本電腦，操作系統(tǒng)為64位Windows 7系統(tǒng)。該試驗(yàn)揭示了如何在ECQ(s,t)網(wǎng)絡(luò)上使用FindHcycle算法和構(gòu)造算法快速構(gòu)建出哈密頓圈。按照ECQ網(wǎng)絡(luò)的定義，首先模擬構(gòu)造出ECQ(2,3)網(wǎng)絡(luò)、ECQ(3,3)網(wǎng)絡(luò)。當(dāng)ECQ網(wǎng)絡(luò)的規(guī)模更大時，該構(gòu)造算法也能給出相應(yīng)的運(yùn)行結(jié)果。因篇幅有限，更大規(guī)模的ECQ網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)目較多，不再進(jìn)行列舉。

對于ECQ(3,3) 網(wǎng)絡(luò),運(yùn)行上述構(gòu)造算法相應(yīng)的程序，如在其中任選取一個頂點(diǎn)(如0001100)為起點(diǎn)，得到的哈密頓圈如下。如<0001100 ,0001101,0000101,0000100>表示ECQ(3,3)中起點(diǎn)為0001100、終點(diǎn)為0000100的一條路徑。以此類推，為了節(jié)省空間，省去了“，”。下同。

<0001100 0001101 0000101 0000100

1000100 1000101 1000001 1000000 0000000

0000001 0001001 0001000 1001000 1001001

1001011 1001010 0001010 0001011 0000111

0000110

1000110 1000111 1000011 1000010 0000010

0000011 0001111 0001110 1001110 1001111

1001101 1001100 1101100 1101101 1100101

1100100 0100100 0100101 0100001 0100000

1100000 1100001 1101001 1101000 0101000

0101001 0101011 0101010 1101010 1101011

1100111 1100110 0100110 0100111 0100011

0100010 1100010 1100011 1101111 1101110

0101110 0101111 0101101 0101100 0111100

0111101 0110101 0110100 1010100 1010101

1010001 1010000 0110000 0110001 0111001

0111000 1011000 1011001 1011011 1011010

0111010 0111011 0110111 0110110 1010110

1010111 1010011 1010010 0110010 0110011

0111111 0111110 1011110 1011111 1011101

1011100 1111100 1111101 1110101 1110100

0010100 0010101 0010001 0010000 1110000

1110001 1111001 1111000 0011000 0011001

0011011 0011010 1111010 1111011 1110111

1110110 0010110 0010111 0010011 0010010

1110010 1110011 1111111 1111110 0011110

0011111 0011101 0011100 0001100>。

對于ECQ(2,3) 網(wǎng)絡(luò),運(yùn)行FindHcycle算法對應(yīng)的程序，如在其中任選取一個結(jié)點(diǎn)(如101100)為起點(diǎn)，得到的哈密頓圈如下。

<101100 101101 100101 100100 110100

110101 110111 110110 100110 100111 100011

100010 110010 110011 110001 110000 100000

100001 101001 101000 111000 111001 111011

111010 101010 101011 101111 101110 001110

001111 001011 001010 011010 011011 011001

011000 001000 001001 000001 000000 010000

010001 010011 010010 000010 000011 000111

000110 010110 010111 010101 010100 000100

000101 001101 001100 011100 011101 011111

011110 111110 111111 111101 111100 101100>。

仿真試驗(yàn)進(jìn)一步驗(yàn)證了本文構(gòu)造算法和算法FindHcycle的有效性和正確性。

4 結(jié)論

本文給出了在ECQ網(wǎng)絡(luò)中求解哈密頓圈的構(gòu)造算法，通過仿真試驗(yàn)實(shí)現(xiàn)了該算法并給出了試驗(yàn)結(jié)果，進(jìn)一步驗(yàn)證了算法的正確性和有效性，為該網(wǎng)絡(luò)高效地通信提供理論參考依據(jù)[15]。

由于在網(wǎng)絡(luò)中發(fā)生故障是不可避免的，基于當(dāng)前研究成果，下一步研究將考慮ECQ網(wǎng)絡(luò)的容錯哈密頓性質(zhì)。