交換超立方網(wǎng)的自適應性無死鎖路由算法＊

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

（廣西大學計算機與電子信息學院，廣西 南寧 530004）

1 引言

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

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

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

2 基本知識和定義

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

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

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

邊集為：

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

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

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

3 無死鎖路由算法

對于路由算法的研究是基于文獻［7］中等待消息的相關假設。

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

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

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

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

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

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

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

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

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

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

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

Table 1 Routing result of the algorithm表1 算法尋徑結果

3.4 算法4的無死鎖性證明

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

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

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

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

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

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

4 結束語

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

［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.

附中文參考文獻：

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

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