李文升,岳孟田,李同勝,馮志芳
(廊坊師范學(xué)院理學(xué)院,河北廊坊 065000)
隨著并行處理規(guī)模的不斷擴(kuò)大,為了進(jìn)一步提高并行計(jì)算機(jī)的通信效率,人們一直在追求結(jié)構(gòu)簡(jiǎn)單,節(jié)點(diǎn)度小,網(wǎng)絡(luò)直徑小的并行計(jì)算機(jī)網(wǎng)絡(luò)模型。廣義Petersen 圖為3 正則圖,節(jié)點(diǎn)的度均為3,因而其可用于構(gòu)造并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)模型。Ohring 等提出了一種k維FPN 網(wǎng)絡(luò)(Folded Petersen Network)。一個(gè)FPk網(wǎng)絡(luò)包括5k個(gè)節(jié)點(diǎn),也就是k個(gè)Petersen 圖的笛卡爾積[1]。Das 等把Petersen 圖嵌入Hypercube 網(wǎng)絡(luò),構(gòu)造了一種HP 網(wǎng)絡(luò)(Hyper Petersen Network)。因?yàn)镠P 網(wǎng)絡(luò)有非常小的直徑,所以有很好的通訊效率[2]。Ohring 等把Hypercube 與Petersen圖做笛卡爾積,構(gòu)造了一種FPQn,k網(wǎng)絡(luò)并分析了其容錯(cuò)性和可靠性,給出了路由算法[3]。劉宏英等[4]分析了RCP(n)互聯(lián)網(wǎng)絡(luò)并給出了基于該網(wǎng)絡(luò)的組播路由算法。劉方愛(ài)等和邢長(zhǎng)明等分別構(gòu)造了RP(k)和RPC(k)互聯(lián)網(wǎng)絡(luò)并給出了對(duì)應(yīng)的路由算法[5-7]。主要構(gòu)造了一類(lèi)基于廣義Petersen 圖GP(n,k)的互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)EGP(k3,k2,k),并分析了EGP(k3,k2,k)的直徑和良好的通信性能。
設(shè)G=(V,E) 為簡(jiǎn)單連通無(wú)向圖。對(duì)任意的u,v∈V(G),dG(u,v)表示G中(u-v)最短路的長(zhǎng)度,在不引起混淆的情況下,簡(jiǎn)記為d(u,v)。對(duì)任意的v∈V(G)和S?V(G),頂點(diǎn)v到點(diǎn)集S的距離為d(v,S)=min{d(v,u)|u∈S}。對(duì)任意的S?V(G)和T?V(G),點(diǎn)集S到點(diǎn)集T的距離為d(S,T)=min{d(u,v)|u∈S,v∈T}。
定義1設(shè)n和k為兩個(gè)正整數(shù),且n>2k,廣義Petersen圖P(n,k)共含有2n個(gè)頂點(diǎn),其頂點(diǎn)集為
V(P(n,k))={ui,wi|1≤i≤n}。
邊集為
E(P(n,k))={uiui+1,uiwi,wiwi+k|1≤i≤n,下標(biāo)模n}[8]。
定義2設(shè)n,k,t為正整數(shù),且n>2k,k>t,拓展的廣義Petersen 圖(Expended Generalized Petersen Graphs)EGP(n,k,t)共含有2n個(gè)頂點(diǎn),其頂點(diǎn)集為
V(EGP(n,k,t))={ui,wi|1≤i≤n},
邊集為
E(EGP(n,k,t))={uiui+1,uiwi,wiwi+k,wiwi+t|1 ≤i≤n,下標(biāo)模}n。
EGP(n,k,t)的構(gòu)造方法:對(duì)于P(n,t),在頂點(diǎn)wi和wi+k間連接邊,其中i=pt,0≤p≤且p為整數(shù),下標(biāo)模n。
討論一類(lèi)特殊的EGP(n,k,t),即EGP(t3,t2,t)(t≥2)網(wǎng)絡(luò),設(shè)
則U,W,T為EGP(t3,t2,t)的三個(gè)圈,t=3 時(shí)的EGP(33,32,3)如圖1所示。
圖1 t=3 時(shí)的互聯(lián)網(wǎng)絡(luò)EGP(33,32,3)
此時(shí)EGP(33,32,3)的三個(gè)圈U,W,T(如圖2所示)具體為
圖2 EGP(33,32,3)中的三個(gè)圈U, W, T
引理1設(shè)v∈V(EGP(t3,t2,t)),則有d(v,U)≤1。
引理2設(shè)v∈V(U)=,
則有d(v,W)≤1+t/2。
證明對(duì)任意,不妨設(shè)v=ukt+r(0≤k≤t2-1,0≤r≤t-1)。
(1)若r≤t/2,取(ukt-ukt+r)路,
P=uktukt+1ukt+2…ukt+r,
則d(v,ukt)≤t/2,可得
d(v,W)≤d(v,ukt)+d(ukt,wkt)≤t/2+1。
(2)若r>t/2,取(ukt+r-u(k+1)t-1)路,
P=ukt+rukt+r+1ukt+r+2…u(k+1)t,
則d(v,u(k+1)t)≤t/2,可得
d(v,W)≤d(v,u(k+1)t)+d(u(k+1)t,w(k+1)t)≤t/2+1,
綜上得證。
引理3設(shè)v∈V(W)=,則有d(v,T)≤t/2。
證明對(duì)任意v∈,不妨設(shè)v=(0≤k≤t-1,0≤r≤t-1)。
(1)若r≤t/2,取路,
(2)若r>t/2,取路,
綜上得證。
引理4設(shè)u,v∈V(T)=,則有d(u,v)≤t/2。
證明對(duì)任意
不妨設(shè)
(1)若q-p≤t/2,取路,
則d(u,v)≤q-p≤t/2。
(2)若q-p>t/2,取路,
則d(u,v)≤[(t-1)-q]+(p+1)=t-(q-p)<t/2,綜上得證。
定理1對(duì)于任意不小于3 的正整數(shù)t,EGP(t3,t2,t)網(wǎng)絡(luò)的直徑
diam(EGP(t3,t2,t))=+4。
證明對(duì)任意u,v∈V(EGP(t3,t2,t)),根據(jù)引理1,2,3,4可有
故EGP(t3,t2,t)網(wǎng)絡(luò)的直徑
綜上可有
通過(guò)表1,可以看到,EGP(k3,k2,k)網(wǎng)絡(luò)與RPC(k)網(wǎng)絡(luò)和RP(k)網(wǎng)絡(luò)的性能比較,連接度是相同的,但網(wǎng)絡(luò)直徑更小,優(yōu)于文獻(xiàn)[5]中的RP(n)網(wǎng)絡(luò)的直徑,也優(yōu)于[6]中的RPC(k)網(wǎng)絡(luò)的直徑。
表1 EGP(k3, k2, k)網(wǎng)絡(luò)與RPC(k)和RP(k)的性能比較
在廣義Petersen 圖的基礎(chǔ)上進(jìn)行擴(kuò)展,通過(guò)對(duì)廣義Petersen 圖的重構(gòu)形成了EGP(k3,k2,k)網(wǎng)絡(luò)。與其它基于Petersen圖構(gòu)造的并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)(如RPC(k)網(wǎng)絡(luò)和RP(k)網(wǎng)絡(luò))相比,EGP(k3,k2,k)網(wǎng)絡(luò)具有高度近正則性和小直徑特點(diǎn),特別是網(wǎng)絡(luò)直徑方面,階為,優(yōu)于RPC(k)網(wǎng)絡(luò)和RP(k)網(wǎng)絡(luò)的O(n)階網(wǎng)絡(luò)直徑值,表明構(gòu)造的EGP(k3,k2,k)互聯(lián)網(wǎng)絡(luò)具有更好的通信性能。