曹入輝，梁家榮，王新陽，豆秋麗

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004）

1 引言

互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是計(jì)算機(jī)科學(xué)中的一個(gè)重要研究分支，人們已提出了多種互連網(wǎng)絡(luò)，其中超立方體網(wǎng)絡(luò)是極具吸引力的網(wǎng)絡(luò)模型之一。超立方體網(wǎng)絡(luò)具有正規(guī)性、對稱性、可靠性、強(qiáng)容錯(cuò)性、可嵌入性、直徑短和網(wǎng)絡(luò)通信能力的可擴(kuò)展性等優(yōu)點(diǎn)［1～3］，然而對于n 維的超立方體，在n 值較大時(shí)，也就是網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)很大時(shí)，過多的邊數(shù)使得超立方體網(wǎng)絡(luò)的實(shí)現(xiàn)和擴(kuò)展很困難，開銷和性能提高的對比越來越大。為了保持超立方體網(wǎng)絡(luò)的優(yōu)點(diǎn)，同時(shí)避開因邊數(shù)增大給網(wǎng)絡(luò)的實(shí)現(xiàn)和擴(kuò)展等方面帶來的困難，人們轉(zhuǎn)而研究超立方體網(wǎng)絡(luò)的變種。其中，交換超立方網(wǎng)就是超立方體網(wǎng)絡(luò)的一個(gè)重要變種，它具有非常靈活的結(jié)構(gòu)，可以根據(jù)需要很容易地在原有基礎(chǔ)上進(jìn)行擴(kuò)展；此外，它在和其他超立方體網(wǎng)絡(luò)的變體比較時(shí)有自己獨(dú)特的優(yōu)勢，即交換超立方網(wǎng)可以作為P2P 環(huán)境中的一種邏輯拓?fù)浣Y(jié)構(gòu)［4］，因此相信交換超立網(wǎng)將會成為未來并行計(jì)算機(jī)系統(tǒng)中一個(gè)重要的應(yīng)用網(wǎng)絡(luò)模型。

死鎖問題一直是并行計(jì)算機(jī)系統(tǒng)互連網(wǎng)絡(luò)路由算法研究中的關(guān)鍵問題，死鎖是指系統(tǒng)在某一時(shí)刻存在若干信息因彼此等待網(wǎng)絡(luò)信道資源而永遠(yuǎn)無法達(dá)到終點(diǎn)的情形。在避免死鎖的路由算法設(shè)計(jì)中，可采取以下兩種算法：第一種為確定性路由算法，確定性路由算法是指在兩個(gè)主機(jī)之間確定單一的路徑；另一種是自適應(yīng)性的路由算法，它是指在網(wǎng)絡(luò)節(jié)點(diǎn)出錯(cuò)時(shí)，算法可通過選擇其他路徑進(jìn)行路由，進(jìn)而提高網(wǎng)絡(luò)的吞吐量并減少延遲［5］。在無死鎖自適應(yīng)性路由算法的研究中，Dally和Seitz首先提出了虛擬通道的概念，用于建立死鎖避免的理論模型。Dinder和Harden把虛擬通道的概念擴(kuò)展到多個(gè)虛擬網(wǎng)絡(luò)中去，并在此基礎(chǔ)上提出了一個(gè)無死鎖的自適應(yīng)性路由算法。Chien 和Kim 提出了planar－adaptive算法，該算法是部分自適應(yīng)性的，并且該算法只需要三條虛擬通道就可避免死鎖的發(fā) 生。隨后，Dong 和Xiang 在planar－adaptive算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種只需要兩條虛擬通道就可以避免死鎖的自適應(yīng)路由算法［6］。

作為未來并行計(jì)算機(jī)系統(tǒng)中一個(gè)重要的應(yīng)用網(wǎng)絡(luò)模型，交換超立方網(wǎng)的性能研究具有深遠(yuǎn)的意義。目前，對于交換超立方網(wǎng)在無死鎖路由方面的研究還比較欠缺，開展這方面的研究很有必要。本文首先提出了相似子網(wǎng)的概念，并證明了相似子網(wǎng)和超立方網(wǎng)的同構(gòu)關(guān)系；然后利用將一個(gè)物理通道分成兩個(gè)虛通道進(jìn)而形成兩個(gè)不相交的虛擬網(wǎng)絡(luò)，將不同點(diǎn)之間的路由限定在某一個(gè)虛擬網(wǎng)絡(luò)中的技術(shù)，提出了一種自適應(yīng)性的無死鎖路由算法。

2 基本知識和定義

定義1［4］交換超立方網(wǎng)是一個(gè)無向圖，符號表示為：EH（s，t）＝（V，E），（s≥1，t≥1），其中，V 表示頂點(diǎn)的集合，E 表示邊的集合：

其中，⊕為異或符號；v［x：y］表示字符串v 從x位到y(tǒng) 位的部分字符串；H（x，y）表示點(diǎn)x 到點(diǎn)y的海明距離，并且（x，y）∈V×V。

邊集E（Qs（j））＝｛（v1，v2）∈E（EH（s，t）），v1，v2∈V（Qs（j））｝。

邊集為：

定理1任意Qs（j）與s維的超立方體是同構(gòu)的，任意Qt（k）與t維的超立方體是同構(gòu)的。

證明（1）把任意Qs（j）中的節(jié)點(diǎn)和s維超立方體網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行下列方式的映射：

兩個(gè)網(wǎng)絡(luò)的點(diǎn)是一一對應(yīng)的，并且對應(yīng)點(diǎn)的邊也是一一對應(yīng)的，則Qs（j）與s維超立方體是同構(gòu)的。同理可證：任意Qt（k）與t維的超立方體是同構(gòu)的。

3 無死鎖路由算法

對于路由算法的研究是基于文獻(xiàn)［7］中等待消息的相關(guān)假設(shè)。

3.1 超立方體的P－cube路由算法

轉(zhuǎn)彎模型用于超立方體，形成了一種稱為P立方路由算法的自適應(yīng)路由算法［8］。令x＝x1x2…xn和y＝y(tǒng)1y2…yn分別是n 維超立方體Qn中的源節(jié)點(diǎn)和目的節(jié)點(diǎn)。設(shè)集合S 由所有x 和y中不相同的維數(shù)構(gòu)成，即S：＝e＿SCAN（x＋y）。顯然S 的大小剛好是x 和y 之間的海明距離。將S 中的元素分成兩個(gè)不相交的子集S0和S1。如果xi＝0且yi＝1，則ei∈S0；如果xi＝1且yi＝0，則ei∈S1。P－cube路由的基本思想就是將路由選擇分成兩個(gè)階段。第一階段，消息先在S0中以任意維序路由，維序的選擇取決于選擇函數(shù)select（）。第二階段，消息在S1中以任意維序路由，維序的選擇也取決于選擇函數(shù)select（）。如果S0為空，則消息在S1中以任意維序路由，文獻(xiàn)［8］中證明了其P－cube算法是無死鎖的。下面給出了超立方體的P－cube路由算法。

算法1超立方體最短P－cube算法

3.2 相似子網(wǎng)的最短P－cube算法

算法2s位相似子網(wǎng)的P－cube算法

3.3 交換超立方網(wǎng)的路由算法

若所有的節(jié)點(diǎn)都只在s位相似子網(wǎng)（或t位相似子網(wǎng)）中路由，只使用算法2（或算法3），算法2和算法3都是避免死鎖的，不會出現(xiàn)死鎖。若u和v位于不同的相似子網(wǎng)中，s位相似子網(wǎng)和t 位相似子網(wǎng)之間會存在交互，也就是說，在某個(gè)s位相似子網(wǎng)（或t位相似子網(wǎng)）發(fā)出的消息到達(dá)另一個(gè)t位相似子網(wǎng)（或s位相似子網(wǎng)），或者經(jīng)過另一個(gè)t位相似子網(wǎng)（或s位相似子網(wǎng)）后到達(dá)另一個(gè)s位相似子網(wǎng)（或t位相似子網(wǎng)），在這種情況下，就會發(fā)生死鎖。

為解決這種問題，引入虛擬通道［9，10］（Virtual Channel）構(gòu)造兩個(gè)虛擬網(wǎng)絡(luò)（Virtual Network）來解決路由中出現(xiàn)的死鎖問題［11，12］。將每一個(gè)物理通道分成兩個(gè)虛擬通道，分屬于兩個(gè)不同的虛擬網(wǎng)絡(luò)N1和N2，然后再根據(jù)源節(jié)點(diǎn)u中的c值判斷在哪一個(gè)虛擬網(wǎng)絡(luò)上進(jìn)行路由。當(dāng)c＝0時(shí)，在N1中路由；當(dāng)c＝1時(shí)，在N2中路由。同時(shí)，N1和N2中不存在消息交換，即一旦消息進(jìn)入了其中一個(gè)虛擬網(wǎng)絡(luò)，它就會在此網(wǎng)絡(luò)中完成路由，而不會進(jìn)入到另外一個(gè)虛擬網(wǎng)絡(luò)中。算法如下：

算法4交換超立方網(wǎng)的無死鎖路由算法

為了提高路由算法的自適應(yīng)性，在對s位相似子網(wǎng)和t位相似子網(wǎng)進(jìn)行路由時(shí)采用的是改進(jìn)后的自適應(yīng)的P－cube算法。不難看出，算法的時(shí)間復(fù)雜度為O（s）＋O（t），算法是無死鎖的，其無死鎖性在3.4節(jié)的定理2中得到了證明。

為了驗(yàn)證算法的實(shí)用性，在自主開發(fā)的交換超立方體網(wǎng)絡(luò)仿真平臺上進(jìn)行了模擬實(shí)驗(yàn)。針對維數(shù)為（10，10），（10，15），（15，15），（20，20）的交換超立方體網(wǎng)絡(luò)，隨機(jī)設(shè)置20對節(jié)點(diǎn)進(jìn)行消息傳遞，實(shí)驗(yàn)結(jié)果如表1所示。其中，N 表示交換超立方網(wǎng)的維數(shù)，h表示源節(jié)點(diǎn)和目的結(jié)點(diǎn)不相同維數(shù)的個(gè)數(shù)，path 表示尋得的路徑數(shù)。從表1中可以看出，算法構(gòu)建的路徑長度path 小于或者等于h＋2，接近于最優(yōu)路徑長度。

Table 1 Routing result of the algorithm表1 算法尋徑結(jié)果

3.4 算法4的無死鎖性證明

定理2算法4是無死鎖的。

證明采用反證法，假設(shè)算法4存在死鎖。由于路由是在兩個(gè)互不相交的虛擬網(wǎng)絡(luò)N1和N2中進(jìn)行的，故只需分別對N1和N2進(jìn)行討論。

假設(shè)N1中存在死鎖，這就是源節(jié)點(diǎn)c＝0時(shí)的情況，消息的傳送全部在N1中進(jìn)行。因?yàn)樵趕位相似子網(wǎng)（或t位相似子網(wǎng)）使用的是P－cube算法，故在s位相似子網(wǎng)（或t位相似子網(wǎng)）是不會產(chǎn)生死鎖的。那么，當(dāng)死鎖產(chǎn)生時(shí)，肯定存在節(jié)點(diǎn)u和v 位于不同的相似子網(wǎng)的情況，即s位相似子網(wǎng)和t位相似子網(wǎng)之間存在交互的情況。在分析死鎖時(shí)，把s位相似子網(wǎng)作為一個(gè)網(wǎng)絡(luò)，把交換超立方網(wǎng)中其他的子網(wǎng)絡(luò)作為另一個(gè)網(wǎng)絡(luò)來分析，如圖1所示。

Figure 1 s－dim similar subnet and other subnet圖1 s位相似子網(wǎng)與其它子網(wǎng)

設(shè)圖1 是為一個(gè)存在于N1中的死鎖配置。A、B、C、D 分別是位于s位相似子網(wǎng)和其他子網(wǎng)的四個(gè)節(jié)點(diǎn)。AB 和CD 之間有通道相連，節(jié)點(diǎn)D 傳到A 的消息經(jīng)過路徑P1上的通道，B 到C 經(jīng)過P2上的通道。作為一個(gè)死鎖配置，此時(shí)應(yīng)該存在消息占用了通道CD 而申請使用位于P1上的通道。而算法3中在N1路由時(shí)，消息在s位相似子網(wǎng)路由完了后再回到其他子網(wǎng)只有一種情況，就是變換C 到達(dá)目的節(jié)點(diǎn)而不再需要用到其他子網(wǎng)中的任何通道。也就是說，對于從s位相似子網(wǎng)上路由過來的消息，因?yàn)镈 點(diǎn)已是目的節(jié)點(diǎn)，沒有消息會在占用CD 通道后再申請位于P1路徑上的通道了，這與假設(shè)矛盾。因此，算法3 在N1中是不存在死鎖的。當(dāng)c＝1時(shí)使用的是N2中的網(wǎng)絡(luò)。同理可證此時(shí)算法中不存在死鎖。

綜上，由于N1和N2可看成是兩個(gè)不相交的虛擬網(wǎng)絡(luò)，彼此間不存在消息交換，故算法4在各自虛擬網(wǎng)絡(luò)中不存在死鎖，整個(gè)算法也是無死鎖的。

4 結(jié)束語

無死鎖自適應(yīng)性路由算法是并行計(jì)算機(jī)系統(tǒng)互連網(wǎng)絡(luò)路由算法研究中的關(guān)鍵問題。本文利用虛擬網(wǎng)絡(luò)技術(shù)，即將物理通道分成兩條虛擬通道進(jìn)而形成兩個(gè)虛擬網(wǎng)絡(luò)，提出了一種交換超立方網(wǎng)的自適應(yīng)性的無死鎖路由算法，并給予了理論性的證明，這為交換立方體網(wǎng)絡(luò)安全通信提供了保障。

［1］Sinanoglu O，AlBdaiw B.An inherently stabilizing algorithm for node－to－node routing over all shortest node－disjoint paths in hypercube networks［J］.IEEE Transactions on Computer，2010，56（7）：995－999.

［2］Hsieh Sun－yuan，Chang Nai－wen.Extended fault－tolerant cycle embedding in faulty hypercubes［J］.IEEE Transactions on Reliability，2009，58（4）：702－710.

［3］Liu Ying－ying，Liu Hong－mei.The bipanconnectivity and hamiltonian－connectivity of enhanced hypercube［C］∥Proc of Inte－rnational Conference on Computational Intelligence and Security，2010：454－456.

［4］Loh P K K，Hsu W－J，Pan Yi.The exchanged hypercube［J］.IEEE Transactions on Parallel and Distributed System，2005，9（16）：866－873.

［5］Wang Gao－cai，Wang Guo－jun，Chen Jian－er，et al.Adaptive routing algorithm excel in deterministic routing algorithm［J］.Mini－Micro Systems，2005，26（2）：40－45.（in Chinese）

［6］Xiang Dong.Deadlock－free adaptive routing in meshes with fault－tolerance ability based on channel overlapping［J］.IEEE Transactions on Department and Secure Computer，2011，8（1）：74－87.

［7］Park H，Agrawal D P.A generic design methodology for deadlock－free routing in multicomputer networks［J］.Journal of Parallel and Distributed Computing，2001，61（9）：1225－1248.

［8］Tang Rong－wang，Yang Xiao－fan，Zhu Ce，et al.A deadlock－free routing algorithm for locally twisted cubes［J］.Journal of Chongqing University，2006，29（4）：95－99.（in Chinese）

［9］Zang Ming－xiang，Zhang Xiang－xiang，Jia Wen.Wormhole routing optimization algorithm based on virtual channel switching［C］∥Proc of International Conference on Multimedia Technology，2011：3798－3800.

［10］Dally W J.Virtual－channel flow control［J］.IEEE Transactions on Parallel and Distributed Systems，1992，3（2）：194－205.

［11］Xiang Dong，Wang Qi，Pan Yi.Deadlock－free fully adaptive routing in tori based on a new virtual network partitioning scheme［C］∥Proc of the 37th International Conference on Parallel Processing，2008，10（1109）：612－619.

［12］EI－Darieby M，Rolia J.Hierachical creating of virtual networks［C］∥Proc of IEEE Symposium on Network Operations and Management，2006，10（1109）：220－229.

附中文參考文獻(xiàn)：

［5］王高才，王國軍，陳建二，等.自適應(yīng)路由算法優(yōu)于確定性路由算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2005，26（2）：40－45.

［8］唐榮旺，楊小帆，朱策，等.一種基于局部扭曲立方體的無死鎖路由算法［J］.重慶大學(xué)學(xué)報(bào)，2006，29（4）：95－99.