蜂窩網絡上的路由算法
2009-01-01 00:00:00殷玉玲楊小帆
計算機應用研究 2009年6期
摘 要：主要研究蜂窩網絡上的無死鎖單播路由算法和一對全的廣播路由算法。基于蜂窩網絡的磚形畫法，利用二維網絡維序路由的基本思想和兩個虛擬網絡實現了無死鎖的最短單播路由算法，并證明了算法的無死鎖性。然后基于這個單播路由算法和線列上的廣播算法，用軟件實現了蜂窩網絡上一對全的廣播路由算法，經過簡單比較得出該廣播算法比以往的算法在通信效率上有了極大的提高。
關鍵詞：蜂窩網絡；路由算法；虛擬網絡；無死鎖；單播；線列；一對全廣播
中圖分類號：TP338；TP393文獻標志碼：A
文章編號：1001-3695(2009)06-2217-03
doi:10.3969/j.issn.1001-3695.2009.06.066
Routing algorithm on honeycomb networks
YIN Yu-ling，YANG Xiao-fan
（School of Computer Science， Chongqing University， Chongqing 400030， China）
Abstract:This paper addressed the routing algorithm on its brick drawing. First， based on its topology and the routing algorithm on square mesh，proposed a minimum-path unicast routing algorithm by two virtual networks.And proved to be deadlock-free. Second， based on the one-to-all broadcast algorithm on linear array，presented a one-to-all broadcast strategy by emp-loying the unicast routing algorithm given at the very start. And proved to be much lower than the prior ones by simple analyse.
Key words:honeycomb meshes; routing algorithm; virtual networks; deadlock-free property; unicast route; linear array; one-to-all broadcast
并行處理系統是當前計算機科學領域研究的主要方向之一。并行多處理器互聯網絡[1]（簡稱互聯網絡）是指處理器以一定方式相互連接而構成的網絡。直接網絡是通過交互消息或報文來實現節(jié)點之間的通信。路由算法則是建立消息或報文在網絡中將要執(zhí)行的傳遞路徑。
網絡通信費用的一種計算方式：cost=degree×diameter。與常用的二維網絡相比，蜂窩網絡具有較小的節(jié)點度和較小的網絡直徑，而且還有其他一些優(yōu)于網絡的特性 [2~4]，所以蜂窩網絡有很大的應用前景，這就使得研究蜂窩網絡上的路由算法具有重要的實際意義。但相關方面的研究還比較欠缺，文獻[2]提出了一個簡單的單播路由算法，不過該算法是死鎖的。
大多數并行計算機在硬件上只支持單播，這時廣播必須用軟件來實現。廣播算法的研究主要有Carle等人[5]提出的一種all-to-all全廣播算法和Song等人[6]針對單口傳播方式提出的一個點廣播算法，但這個點廣播算法并不是最優(yōu)的。
筆者首先提出了無死鎖的最短路徑單播路由算法，并證明了算法的無死鎖性；然后基于這個算法研究了蜂窩網絡上的廣播算法，并對廣播的費用進行了分析。
1 蜂窩網絡
1.1 基本概念
1997年，加拿大學者Stojmenovic最早提出了蜂窩網絡的拓撲結構。為了強調對稱性，蜂窩網絡按如下規(guī)則構建：一個六角形是一個大小為1的蜂窩網，記為HM1。通過在HM1的邊界上增加六個六角形可得到大小為2的蜂窩網HM2。類似地，圍繞HMt-1的邊界增加一層六角形，可以得到大小為t的蜂窩網HMt。由于它們比同樣大小的二維網絡的度數低、直徑小，按照成本=度數×直徑來計算，可得知蜂窩網的成本要小很多，研究蜂窩網絡上的路由算法具有很大的實際意義。
1.2 坐標系統與拓撲結構
蜂窩網可以使用XYZ三坐標的坐標系來對蜂窩網絡的節(jié)點進行編碼[2]。以蜂窩網絡的中心作為坐標原點，X、Y、Z三個坐標軸分別平行于六角形的三條邊。僅當平行于x軸（如x+或x-）移動一條邊時，x坐標才改變。同理，僅當平行于y軸（如y+或y-）移動一條邊時，y坐標才改變；僅當平行于z軸（如z+或z-）移動一條邊時，z坐標才改變。編碼示例可參見圖1中A節(jié)點的編碼。經過編碼，蜂窩網絡任意兩個鄰節(jié)點的坐標編碼中僅有一個坐標值相差1，另外兩個坐標是相等的。有一個固定z坐標的所有點屬于一個鋸齒鏈。如果兩條中心鏈給定z坐標為1和0，關于z軸的六條鋸齒鏈是z=-2，z=-1，z=0，z=1，z=2，z=3。相似的可以為x和y軸定義鋸齒鏈。另外，蜂窩網絡結構是二部圖網絡[2]。該網絡中所有的節(jié)點可以分為兩組：a）為XYZ坐標值和為1的節(jié)點（如圖1中HM3的黑節(jié)點），它們的一個坐標值比鄰節(jié)點對應坐標值小1；b)為XYZ坐標值和為2的節(jié)點（如圖1中的白節(jié)點），它們的一個坐標值比鄰節(jié)點對應坐標值大1。1.3 磚形畫法及其拓撲性質
把蜂窩網絡的每條Z鋸齒鏈畫成一條垂直的線，就得到蜂窩網絡的磚形畫法，如圖2所示。磚形畫法中每個節(jié)點的坐標可以用二維XY坐標表示，任意兩個鄰節(jié)點的坐標編碼中一個坐標值相差1，另外一個坐標值是相等的，這就方便了對路由算法的研究。
由于蜂窩網絡是二部圖，而且相鄰節(jié)點僅一維的坐標值相差1。如果白（黑）節(jié)點兩坐標值之和為偶數，那么黑（白）節(jié)點兩坐標值之和為奇數。規(guī)定：奇數大小的蜂窩網絡白節(jié)點兩坐標值之和為偶數，黑節(jié)點兩坐標值之和為奇數。偶數大小的蜂窩網絡白節(jié)點兩坐標值之和為奇數，黑節(jié)點兩坐標值之和為偶數。而且，任意一個蜂窩網絡中的白節(jié)點在X正方向存
在通信鏈路，黑節(jié)點在X負方向存在通信鏈路。
2 路由算法
2.1 無死鎖的單播路由算法
從源節(jié)點到目的節(jié)點發(fā)現一條路徑并沿這條路徑轉發(fā)報文的問題稱為路由問題。對蜂窩網絡的單播算法，Stojmenovic提出一個最短路徑單播路由算法[2]。假設源節(jié)點=(u′，v′，w′)，目的節(jié)點=(u″，v″，w″)，令X方向的偏移量X offset=u″-u′，Y方向的偏移量Y offset=v″-v′，Z方向的偏移量Z offset=w″-w′。這兩個點間的最短路徑由平行于x軸的|X offset|邊、平行于y軸的|Y offset|邊和平行于z軸的|Z offset|邊組成。考察一維蜂窩網絡的最短路由算法，可以構建出一個死鎖配置，如圖3所示。從圖中可見，該死鎖配置的通道相關圖形成了環(huán)從而構成死鎖，所以一維單信道蜂窩網絡的最短路由算法是死鎖的。由此可見，更高維的蜂窩網絡也是不存在單信道的無死鎖最短路徑路由算法。
蜂窩網絡磚形畫法的無死鎖最短單播路由類似于二維網絡中的維序路由。由于蜂窩網絡中并不是每個節(jié)點在X的正負兩個方向都有邊相連（它們在拓撲結構中表現為通信鏈路），在最短路由算法中不可能嚴格地按照先走完X方向的偏移量再走Y方向的偏移量。在這里優(yōu)先沿X方向路由，即當X方向有偏移量且存在減小絕對偏移量的通信鏈路時，選擇此X方向的通道。
蜂窩網絡只需兩個虛擬網絡[1]即可實現無死鎖路由，如圖4所示。在這種虛擬網絡中，每維中的通道不再是雙向的，每個虛擬網絡的第0維只有一個方向的通道，而第一維有兩個方向的通道。當X方向偏移量非負時，在升序虛擬網絡中路由；當X方向偏移量小于0時，在降序虛擬網絡中路由。
算法Odd_XY_Route_Asc和Odd_XY_Route_Desc是奇數大小的蜂窩網絡中的兩個路由算法，前者用于升序網，后者用于降序網。算法中，internal是連接本地節(jié)點的通道。Select()是選擇函數，該函數從一組作為參數傳遞的通道中選擇一個空閑通道；（Xc ， Yc）為當前節(jié)點坐標，（Xd ， Yd）為目的節(jié)點坐標；channel為選擇的輸出通道。
算法1 奇數大小蜂窩網絡升序網中的路由算法
Procedure Odd_XY_Route_Asc (Xc ， Yc， Xd ， Yd)
begin
X offset:=Xd-Xc;
Y offset:=Yd-Yc;
if(Xc+Yc)mod 2=0then//白節(jié)點
if X offset > 0 then
channel:=X+;
else if X offset=0 and Y offset>0 then
channel:=Y+;
else if X offset=0 and Y offset < 0 then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
endif
else//黑節(jié)點
if Y offset>0then
channel:=Y+;
else ifY offset<0then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
else
channel:=select(Y+，Y-);
endif
endif
end Odd_XY_Route_Asc
算法2 奇數大小蜂窩網絡降序網中的路由算法
Procedure Odd_XY_Route_Desc (Xc ， Yc， Xd ， Yd)
begin
X offset:=Xd-Xc;
Y offset:=Yd-Yc;
if(Xc+Yc) mod 2=0then//白節(jié)點
ifY offset>0then
channel:=Y+;
else ifY offset<0then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
else
channel:=select(Y+，Y-);
endif
else//黑節(jié)點
ifX offset<0then
channel:=X-;
else if X offset=0 and Y offset>0 then
channel:=Y+;
else if X offset=0 and Y offset<0 then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
endif
endif
end Odd_XY_Route_Desc
同理，算法Even_XY_Route_Asc和Even_XY_Route_Desc是偶數大小的蜂窩網絡中的兩個路由算法。
算法3 偶數大小蜂窩網絡升序網中的路由算法
Procedure Even_XY_Route_Asc (Xc ， Yc， Xd ， Yd)
begin
X offset:=Xd-Xc;
Y offset:=Yd-Yc;
if (Xc+Yc) mod 2=0then//黑節(jié)點
ifY offset>0then
channel:=Y+;
else ifY offset<0then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
else
channel:=select(Y+，Y-);
endif
else//白節(jié)點
ifX offset>0then
channel:=X+;
else if X offset=0 and Y offset > 0 then
channel:=Y+;
else if X offset=0 and Y offset < 0 then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
endif
endif
end Even_XY_Route_Asc
算法4 偶數大小蜂窩網絡降序網中的路由算法
Procedure Even_XY_Route_Desc (Xc， Yc， Xd， Yd)
begin
X offset:=Xd-Xc;
Y offset:=Yd-Yc;
if(Xc+Yc) mod 2=0then//黑節(jié)點
ifX offset < 0then
channel:=X-;
else if X offset=0 and Y offset > 0 then
channel:=Y+;
else if X offset=0 and Y offset < 0 then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
endif
else //白節(jié)點
ifY offset > 0then
channel:=Y+;
else ifY offset<0then
channel:=Y-;
else if X offset=0 and Y offset=0 then
channel:=internal;
else
channel:=select(Y+，Y-);
endif
endif
end Even_XY_Route_Desc
定理1 利用兩個虛擬網絡實現的蜂窩網絡中的路由算法Odd_XY_Route_Asc、Odd_XY_Route_Desc、Even_XY_Route_Asc和Even_XY_Route_Desc是無死鎖的。
證明 在每個虛擬網絡內部不會形成通道之間的環(huán)相關，而且兩個虛擬網絡之間不存在耦合，所以不會形成死鎖。
2.2 一對全的廣播路由算法
并行處理系統經常需要一個處理器發(fā)送相同的數據到所有其他處理器。這個操作就是一對全的廣播[7]。開始時，只有源處理器擁有待廣播的大小為m的數據。在程序終止時，有初始數據的p份復制——每個處理器擁有一份。
2.2.1 線列上的廣播
首先，源處理器發(fā)送消息到某一個處理器；然后這兩個處理器同時發(fā)送消息到其他的兩個未接收到消息的處理器。繼續(xù)這個過程，直到所有的處理器接收到數據。這樣，消息的廣播可以經過log p個步驟完成。
八個節(jié)點的線列的一對全廣播步驟如圖5所示。其中，0節(jié)點為源節(jié)點；節(jié)點標記從0~7。標有數字的箭頭表示從消息的源地址傳送到目的地址，箭頭表示消息的傳送，在同一個時間傳送的消息由相同的數字標記，經過以下三個步驟完成廣播：
a）節(jié)點0發(fā)送消息到節(jié)點4。
b)節(jié)點0和4分別發(fā)送消息到節(jié)點2和6。
c)節(jié)點0、2、4和6分別發(fā)送消息到節(jié)點1、3、5和7。
在算法設計中，先將p個節(jié)點表示成二進制的形式，需要的步驟數d=log p。這樣設計的算法避免了通信鏈路的擁擠，并且充分利用了通信網絡資源。
若源節(jié)點是0~p-1中任意一個處理器，設計算法廣播時需當前節(jié)點和源節(jié)點執(zhí)行一個XOR操作，具體的一對全廣播算法請參考文獻[7]。
當節(jié)點數目p不等于2d時，算法需要進一步改進。對任意的整數N，都有N=2n1+2n2+2n3+…。其中n1，n2，n3，…∈ (0∪Z+)。所以可以把整個網絡分為幾個子網絡，使得每個子網絡的節(jié)點數目均為2n個。源節(jié)點首先在每個子網絡中發(fā)送一條消息，然后幾個子網絡內部同時廣播消息。把p表示成二進制形式，設有n位，計算子網絡個數j以及每個子網絡中節(jié)點個數a(0)， a(1)， a(2)， …， a(j-1)的算法如下：
算法5 計算線列上子網絡個數及每個子網絡中節(jié)點個數的算法
Procedure No_Count(p，n)
begin
j=0;
fori=n-1 downto 0
ifp(i)=1 then
a(j):=2i;
j++;
endif
endfor
end No_Count
2.2.2 蜂窩網絡上的廣播
首先用蜂窩網絡的單播路由算法將消息發(fā)送到蜂窩網絡每列的一個節(jié)點上；然后把每列看做一個線列，
用線列的廣播算法進行廣播。設n為線列節(jié)點總個數，j為子網絡個數，h為最大子網絡中的節(jié)點數目，則這n個節(jié)點的廣播費用為j+log2 h。
蜂窩網絡廣播的費用等于單播的費用和最長列廣播的費用之和。假設蜂窩網絡的節(jié)點數目為N，則N=6 t2(t為蜂窩網絡的大小)，大小為t的蜂窩網絡共有2t列。其中最長列的節(jié)點數目為4t-1，而從蜂窩網絡的一個節(jié)點發(fā)送消息到每列的通信時間最長為4t-3，從而可以計算出大小為t的蜂窩網絡最長的通信時間。而Song等人提出的點廣播算法的通信時間是log2 N，即log2 6t2，本文由log的指數級降到了log的線性級，可見廣播效率有了極大的提高。
3 結束語
針對蜂窩網絡的磚形畫法，本文提出了一個無死鎖的最短路徑的單播路由算法，該算法使用兩個虛擬網絡來避免死鎖。基于此單播路由算法還提出了蜂窩網絡中的一個一對全的廣播路由算法，該算法比以往的算法在通信效率上有了極大提高。
參考文獻：
［1］杜阿托.并行計算機互聯網絡技術——一種工程方法[M].謝倫國，張民選，竇強，等譯.北京：電子工業(yè)出版社，2004:58-148.
[2]STOJMENOVIC I. Honeycomb networks:topological properties and communication algorithms [J].IEEE Trans on Parallel Distributed Systems，1997，8(10):1036-1042.
[3]YANG Xiao-fan.The diameter of honeycomb rhombi tori[J].Applied Mathematics Letters，2004，17(2):167-172.
[4]MEGSON G M，YANG Xiao-fan，LIU Xiao-ping.Honeycomb tori are hamiltonian[J].Information Processing Letters，1999，72(34):99-103.
[5]CARLE J， MYOUPO J F， SEME D.All-to-all Broadcasting algorithms on honeycomb networks and applications [J].Parallel Processing Letters，1999，9(4):539-550.
[6]SONG Jian-ping，HOU Zi-feng，SHI Yun-tao.Optimal routing and multicasting in wormhole-routed honeycomb networks[C]//Proc of High Performance Computing in the Asia-Pacific Region.2000:142-144.
[7]ANANTH G， ANSHUL G， GEORGE K，et al.Introduction to parallel computing [M].2nd ed.2003:149-167.
