故障Ｔｏｒｕｓ網絡中的空閑子網搜索方案研究
2009-01-01 00:00:00徐霜梁家榮伍華健
計算機應用研究 2009年2期
（1.廣西大學 計算機與電子信息學院， 南寧 530004； 2. 玉林師范學院 數學與計算機系， 廣西 玉林 537000）
摘 要：
為了提高多處理機系統的抗故障能力，對現有的子網搜索算法進行改進，提出了一種新的基于故障節點模式的空閑子網搜索方案。以具有故障節點的二維Torus網絡為例，詳細闡述了方案的具體內容，并給出了相關的算法。該方案是基于集合操作的，能夠顯著縮小搜索范圍并縮短比較時間。實例證明該方法具有可行性。
關鍵詞：空閑子網； 子網搜索； 故障模式
中圖分類號：TP393文獻標志碼：A
文章編號：1001-3695(2009)02-0665-03
Research of submesh searching scheme for Torus networks with faulty nodes
XU Shuang1， LIANG Jia-rong1， WU Hua-jian2
(1.School of Computer，Electronics Information， Guangxi University， Nanning 530004， China; 2.Dept. of Mathematics Computer Science， Yulin Normal University， Yulin Guangxi 537000， China)
Abstract:In order to enhance multi-processor system’s anti-breakdown ability， this paper proposed a new free submesh-searching scheme. Based on two-dimensional Torus network’s with faulty nodes， explained the scheme， and proposed the related algorithm. The scheme was based on manipulating set expressions， with the search space reduced considerably. The experiment proves that this scheme is feasible.
Key words：free submesh; submesh search; faulty mode
0 引言
隨著并行計算機互聯網絡和VLSI技術的迅速發展，系統中的并行處理機越來越多，人們對并行計算機互聯網絡拓撲結構進行了大量的研究，并對其中的一些拓撲結構已研制出了相應的商用和研究用的并行計算機系統[1~4]。Torus網絡是一種完全對稱的直連網絡拓撲結構，它具有很多優秀的網絡特性，如規則對稱性、路徑多樣性以及良好的擴展性。因此，它廣泛應用于許多商用系統中。例如，2004年底評出的全球超級計算機TOP100中排名首位的IBM Blue Gene/L就采用Torus網絡；而另一家通信設備制造商，Avici公司在其推出的世界上第一臺太比特路由器中也采用Torus網絡作為其交換網絡拓撲[5]。
通常多處理機系統中都存在一個獨立的主處理機，它可以實現任務調度和處理機分配。在并行計算機系統中，請求任務被分配給網絡中適當大小的子網執行，該子網可以從一個節點機到整個網絡[6，7]。而對處理機進行分配的前提是對網絡中的空閑子網進行搜索，在這方面已進行了大量的研究[8]。
隨著系統中處理機數目的增加，處理機出現故障的情況是難以避免的，一旦出現故障節點，原有的搜索算法將受到限制：要么不具備完全搜索能力，不能搜索出網絡中所有可用的空閑子網；要么需要較高的時間復雜度，從而影響系統的性能。因此研究基于故障節點模式的空閑子網搜索方案是非常必要的[8]。文獻[9]中提出的算法能夠在具有故障節點的超立方體網絡中搜索出所有最大的空閑子立方體；在此基礎上文獻[10]對具有故障節點的Torus網絡進行研究，給出了搜索所有最大空閑子網的算法。為了提高系統中處理機的利用率，減少系統碎片的產生，在進行處理機分配前總是希望能夠找出所有可用的空閑子網，而不僅僅是最大的空閑子網，為此本文在文獻[10]的基礎上，以二維故障Torus網絡為例，給出了一種改進的搜索方案，該方案能夠搜索出所有互不包含的空閑子網。
1 相關概念及理論基礎[10]
1． 1 相關概念
一個二維Torus網絡用T（k0，k1）表示，共有k0×k1個節點。k0和k1表示在相應維上的節點數。其中k0≥2，k1≥2。網絡中的每一個節點代表一個處理機，每個節點用坐標(x，y)表示，0≤x＜k0，0≤y＜k1。
定義1 在二維Torus網絡T(k0，k1)中，對于兩個y坐標相同的相鄰節點A(xu，yv)和B(xs，yv)，如果xs=(xu+1)mod m，則節點B稱為節點A的正相鄰節點，而從A到B的方向為正方向；同理，對于兩個x坐標相同的相鄰節點A′(xu，yv)和B′(xu，yt)，如果yt=(yv+1)mod n，則B′稱為A′的正相鄰節點，從A′到B′的方向為正方向。相反，從B到A（或從B′到A′）的方向為負方向，所以節點A稱為節點B的負相鄰節點（節點A′稱為節點B′的負相鄰節點）。
關于正方向的定義同樣適用于Mesh網絡。在Mesh網絡中，如果一個節點的所有相鄰節點都是它的正鄰節點，則該節點稱為Mesh網絡的基節點；相應地，如果一個節點的所有相鄰節點都是它的負鄰節點，則該節點稱為Mesh網絡的末端節點。
定義2 在二維Torus網絡T(k0，k1)中，一個子網S可表示為d0(i∶j)d1(s∶t)。其中：0≤i，j＜k0，0≤s，t＜k1；d0和d1分別代表x方向和y方向；在x維上從i到j為正方向，在y維上從s到t為正方向。一個空表達式代表整個網絡。例如在圖1中，節點(0，0)， (0，1)，(0，2)，(0，3)所在的子網可表示為 d0(0，0)，由于在y方向上跨越整個網絡，在該方向上的表達式就可省略。
定義 3 在Torus網絡中，對于一個給定的節點D，相對于D的候選子網是以D為基節點且包括整個網絡節點的一個Mesh結構的子網。圖2是相對于節點(1，1)的候選子網。
定義4 在二維Torus網絡T(k0，k1)中，對于給定的節點D(x1，y1)，相對于D的候選子網中離D最遠的節點稱為D的末端節點，末端節點用E(x2，y2)表示，其坐標值可由以下式子得到：
x2=x1-1， 0＜x1＜k0k0-1，x1=0， y2=y1-1， 0＜y1＜k0k1-1， y1=0
如圖1所示，節點(0，0)的末端節點為(3，3)，而節點(1，1)的末端節點為節點（0，0）。
定義5 在一個具有故障節點的Torus網絡中，對于一個給定的正常節點D，相對于D的拒絕區域是包括一個故障節點和D的末端節點的最小子網。
圖1中(1，2)和(2，1)為故障節點，對于節點(0，0)，它的兩個拒絕區域為圖中用虛線框標出的子網：d0(1∶3)d1(2∶3)和d0(2∶3)d1(1∶3)。
定義6 對于給定的正常節點D，以D為基節點的基本子網滿足以下條件：基本子網內的節點都是正常且空閑的，且該子網不被以D為基節點的其他任何空閑子網所覆蓋。
定義7 一個空閑子網被稱為控制子網，若它不能被其他空閑子網完全覆蓋，控制子網之間可以相互重疊。
1． 2 理論基礎
a)用+號表示兩個子網的并集，用#8226;表示兩個子網的交集。例如在圖1中，子網d0(0∶0)，d1(0∶0)的并集可表示為d0(0∶0)+d1(0∶0)，交集運算符#8226;有時可以省略。
b)對于一個表達式di(b∶e)，它的補集可表示為di(b∶e)，且di(b∶e)=di((e+1) mod ki∶(b-1) mod ki)。
c)得摩根定律：A+B=A#8226;B， A#8226;B=A+B（在本文中A、B代表子網表達式）。
d)化簡規則：若BA，則AB=B， A+B=A。
2 基于故障節點模式的子網搜索方案
2. 1 子網搜索方案的理論依據
引理1[10]一個基本子網不包括拒絕區域內的任一節點
引理2[10] 一個節點如果處于所有的拒絕區域之外，則它必處于一個或多個基本子網之內。
由以上概念以及引理1、2可知，對于網絡中給定的一個正常節點D，所有正常節點可以分為兩類：a)屬于D的拒絕區域內的節點（該類節點構成的集合用R表示）;b)以D為基節點的基本子網中的節點（該類節點構成的集合用P表示）。例如在圖1中，對于正常節點(0，0)，R={(2，1)(3，1)(1，2)(2，2)(3，2)(1，3)(2，3)(3，3)}， P={(0，0)(1，0)(2，0)(3，0)(0，1)(1，1)(1，1)(0，2)(0，3)}。
本文提出的搜索方案的基本目標就是當網絡中出現故障節點時，在節點恢復正常之前，能夠搜索出所有的控制子網。
在Torus網絡中，對于幾個子網的并集，利用得摩根定律可以快速得到不在該并集中的所有節點的地址。根據節點的故障信息以及定義4中給出的公式，可以很容易地得到相對于某個正常節點的拒絕區域，而有了拒絕區域就可以利用得摩根定律求出相應的基本子網構成的集合。在圖1中，正常節點(0，0)的末端節點為(3，3)。故障節點(1，2)，(2，1)和節點(3，3)構成的拒絕區域為
R=d0(1∶3)d1(2∶3)+d0(2∶3)d1(1:3)
則基本子網集
P=R=（d0(1∶3)d1(2∶3)+d0(2∶3)d1(1∶3)）=
(d0(1∶3)+d1(2∶3))(d0(2∶3)+(d1(1∶3))(利用得摩根定律)=
(d0(0∶0)+d1(0∶1))(d0(0∶1)+d1(0∶1))(利用補集公式)=
d0(0∶0)+d1(0∶0)+d0(0∶1)d1(0∶1)
(利用分布律、結合律、化簡規則)
對于基本子網集的獲取，可以直接調用文獻[10]中的算法A。
2. 2 具體的子網搜索方案
搜索方案的基本設計思想如下：首先每個故障節點將其地址信息以廣播形式發送給與其相鄰的正常節點，收到信息的正常節點再將故障信息發送給與其相鄰的正常節點，直到網絡中的所有正常節點都收到信息為止。然后每個正常節點根據定義4中的公式計算出其末端節點，由末端節點及故障節點的信息就可以得到拒絕區域，拒絕區域的補集就是所有基本子網構成的集合。利用文獻[10]中的算法A就可得到所有的基本子網，由此得到的基本子網可能存在著這樣的情況：一個基本子網可能覆蓋一個或多個子網。最后利用下面給出的一個比較算法，即可得到所有的控制子網。綜合上面的敘述，給出得到控制子網集合的完整算法：
a)故障節點機向正常節點廣播故障節點地址信息；
b)每個正常節點計算其末端節點的地址；
c)每個正常節點根據末端節點以及故障節點地址計算出該節點的拒絕區域；
d)利用得摩根定律對基本子網集進行轉換；
e)每個正常節點調用文獻[10]中的算法A，得到其基本子網的集合；
f)網絡中的主機調用compare()算法，得到所有的控制子網。
下面給出compare()算法的具體描述。用列表f存儲控制子網，最初f為空，每個正常節點按照規定的順序向主機發送其基本子網的信息。假設當前節點發送來的基本子網的個數為n，這n個子網構成的集合用p表示，其中的每一個子網用pi(1≤i≤n)表示，現將pi與f中的每個元素進行比較（f中的元素用ci表示）。如果存在某個子網ck滿足ckpi，則將ck從f中移出；如果存在某個子網ck滿足ckpi，則終止pi的比較。當全部比較完后，如果沒有一個子網cj使得pi滿足picj或cjpi，則將pi添加到f中。具體算法如下：
compare()
a) {if (f為空)則將p中的元素全部添加到f中
b) else
c)for(i=1; i≤n; i++)//假設pi為d0(x1，x2)d1(y1+y2)， cj為d0(x1′，x′2)d1(y1′，y2′)
d){ for(j=1;i≤f. length; j++)
e) { flag1=0; flag2=0;// flag1、flag2為兩個標記變量
f) if (x1≤x1′≤x2′≤x2)//在x方向上cj處于pi范圍內
{ if (y1≤y1′≤y′2≤y2‖y1′≤y2′≤y2≤y1‖y2′≤y2≤y1≤y1′)//pi包含cj
{將cj從f中移出；flag1++;} }
g) if (x1==1 x2==1)
//在x方向上qi跨越整個網絡
{if(y1≤y1′≤y2′≤y2){將cj從f中移出；flag 1++;}}
h) if (x2′≤x2≤x1≤x1′)
{if(yi≤y1′≤y2′≤y2‖y1′≤y2′≤y2≤y1‖y2′≤y2≤y１≤y1′‖y2≤y1≤y1′≤y2′‖ y1==1){將cj從f中移出；flag1++;} }
i) if (x1′≤x1≤x2≤x2′)//在x方向上pi處于cj范圍內
{if (y1′≤y1≤y2≤y2′‖y1≤y2≤y2′≤y1′‖y2≤y2′≤y1′≤y1)//picj
{ flag2++;;返回到c);}}
j)if (x1′==1 x2′==1)
{if(y1′≤y1≤y2≤y2′){ flag2++;;返回到C);} }
k)if(x2≤x2′≤x1′≤x1)
{if (y1′≤y1≤y2≤y2′‖y1≤y2≤y2′≤y1′‖y2≤y2′≤y1′≤y1‖y2′≤y1′≤y1≤y2‖y1′==1）
{ flag2++;;返回到c); } }
}
l} if (flag1!=0 flag2==0)將pi添加到f中；
}
3 實驗
本文用一個仿真實驗來驗證算法的可行性。利用仿真軟件OPNET進行仿真，業務源是經典假設的泊松源，仿真網絡中共有17個節點機。其中1個作為主機，并與其他節點直接相連，接收這些節點機發送來的信息，然后執行相應的算法對其進行處理；其他16個節點構成4×4的二維Torus網絡結構（圖1），仿真時假設節點(1，2)和(2，1)為故障節點，故障節點可以向其周圍節點發送故障信息。當執行完算法A后，每個正常節點的基本子網集如表1所示。最后執行完compare()算法后，得到的控制子網的集合為{d0(0∶0)，d0(0∶1)d1(0∶1)， d1(0∶0)， d0(3∶0)， d0(3∶1)d1(0∶1)，d0(2∶0)d1(2∶0)，d1(3∶0)，d0(0∶1)d1(3∶1)，d0(3∶1)d1(3∶1)}共九個控制子網。這與實際情況是完全一致的，達到了預期的目標。
表1 正常節點的基本子網集
基節點相應的基本子網基節點相應的基本子網
(0，0)d0(0∶0)，d0(0∶1)d1(0∶0)，d1(0∶0)(0，2)d0(0，0)
(1，0)d0(1∶1)d１(0∶1)，d1(0∶0)(2，2)d0(2∶0)d1(2∶0)
(2，0)d1(0∶0)(3，2)d0(3∶0)
(3，0)d0(3∶0)，d0(3∶1)d1(0∶1)，d1(0∶0)(0，3)d0(0∶0)，d0(0∶1)d1(3∶1)，d1(3∶0)
(0，1)d0(0∶0)，d0(0∶1)d1(1∶1)(1，3)d0(1∶1)d1(3∶1)，d1(3∶0)
(1，1)d0(1∶1)d1(1∶1)(2，3)d1(3∶0)
(3，1)d0(3∶0)，d0(3∶1)d1(1∶1)(3，3)d0(3∶0)，d0(3∶1)d1(3∶1)，d1(3，0)
4 結束語
本文提出了一個基于故障節點模式的空閑子網搜索策略和相關算法，充分考慮二維Torus網絡中節點故障的發生對系統產生的影響，推廣了已有的研究成果，并用實例驗證了方案的可行性。這有利于進一步推廣Torus網絡在大規模并行處理機中的應用，同時也為具有故障節點的Torus網絡中處理機的分配提供了重要的理論基礎。
參考文獻：
[1]LENOSJI D， LAUDON J，GHARACHORLOO K，et al．The Stanford DASH multiprocessor[J]．Computer，1992，25(3)：63-79．
[2]GABRANI G， MULKAR T. A quad-tree based algorithm for processor allocation in 2D Mesh-connected multicomputers[J]. Computer Standards Interfaces， 2005，27(2):133-147.
[3]YOO B S， DAS C R. A fast and efficient processor allocation scheme for Mesh-connected multicomputers[J]. IEEE Trans on Compu-ters，2002，51(1):46-60.
[4]CHIU G M， CHEN S K. An efficient submesh allocation scheme for two-dimensional Meshes with little overhead[J]. IEEE Trans on Parallel Distributed Systems， 1999，10(5):471-486.
[5]顧華璽，劉增基，王琨，等.Torus網絡中分布式自適應路由算法[J].西安電子科技大學學報：自然科學版，2006，33(3):352-358.
[6]張艷，孫世新，彭文欽.網格多處理機的一種改進的子網分配算法[J].軟件學報，2001，12（8）:1250-1257.
[7]張艷，孫世新，彭文欽.一種最佳的Mesh中的空閑子網搜索算法[J].系統工程與電子技術， 2001，23(4):83-86.
[8]ISMIAL I， DAVIS J. Program-based static allocation policies for highly parallel computers[C]//Proc of IPCCC’95.[S.l.]: IEEE Computer Society，1995:61-68.
[9]CHEN H L， TZENG N F. A boolean expression-based approach for maximum incomplete subcube identification in faulty hypercubes[J]. IEEE Trans on Parallel Distributed Systems，1997，11(8):1171-1183.
[10]CHEN H L， HU Shu-hua. Submesh determinationin faulty Tori and Meshes[J]. IEEE Trans on Parallel and Distributed Systems， 2001，12(3):272-282.
