基于并行處理的一種新型有效的網(wǎng)絡(luò)架構(gòu)BSN-MOT

李江昀，孫麗婷

(1. 北京科技大學(xué) 自動(dòng)化學(xué)院，北京 100083；2. 北京科技大學(xué) 鋼鐵流程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，北京 100083)

1 引言

Biswapped網(wǎng)絡(luò)(BSN)是一種雙層架構(gòu)的互聯(lián)網(wǎng)絡(luò)，它提供了一種構(gòu)建可擴(kuò)展性、模塊化、可繼承性、容錯(cuò)性等大規(guī)模的并行計(jì)算機(jī)體系結(jié)構(gòu)形式[1]?；贐SN的多處理器系統(tǒng)架構(gòu)，是由2N個(gè)規(guī)模為N的處理器組組合而成，即含有22N個(gè)處理器。另一方面，作為非常有效的互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，MOT(mesh of tree)擁有2個(gè)非常理想的性能，即小直徑及高的對(duì)分寬度，并且在只考慮速度的情況下，MOT被認(rèn)為是最快速的互聯(lián)網(wǎng)絡(luò)，在解決如分組路由、排序、前置計(jì)算、矩陣乘法運(yùn)算、最短路徑、最近鄰居等重要算法問題時(shí)，運(yùn)行在MOT上的時(shí)間復(fù)雜度只達(dá)到

本文結(jié)合BSN及MOT的雙重拓?fù)鋬?yōu)勢(shì)，提出一種新型網(wǎng)絡(luò)架構(gòu)BSN-MOT，并對(duì)新架構(gòu)的模型及基本拓?fù)湫再|(zhì)進(jìn)行了具體分析；同時(shí)，本文研究了運(yùn)行在該架構(gòu)上的基本通信及應(yīng)用等并行算法，并與其他2種流行的樹形雙層架構(gòu)在算法時(shí)間復(fù)雜度上進(jìn)行了比較，結(jié)果顯示BSN-MOT更為快速。

其實(shí)，許多其他的樹形雙層架構(gòu)都被研究給出，如MCT(mesh-connected tree)[2]、MMT(multmesh of tree)[3]、OMULT(optical multi-trees)[4]等。在文獻(xiàn)[2]中，Kemal證明了MCT是比超立方體更簡單，且成本更低的架構(gòu)體系。Jana[3]給出了MMT，分析了其拓?fù)湫再|(zhì)及架構(gòu)有效性，并理論驗(yàn)證了其并行算法的快速性。 Islam[4]提出了OMULT，并與OTIS-Mesh的比較表明，OMULT更具有優(yōu)勢(shì)。然而，根據(jù)BSN的網(wǎng)絡(luò)連通性及極大容錯(cuò)性，BSNMOT將會(huì)比其他雙層樹形架構(gòu)更具有競爭力的架構(gòu)體系，研究其拓?fù)湫再|(zhì)對(duì)網(wǎng)絡(luò)的分析及網(wǎng)絡(luò)的設(shè)計(jì)具有重要的意義。

同時(shí)，BSN-MOT作為大規(guī)模的互聯(lián)網(wǎng)絡(luò)，且根據(jù)其優(yōu)秀拓?fù)湫再|(zhì)，研究其上的并行算法可推動(dòng)現(xiàn)代并行計(jì)算機(jī)的實(shí)際應(yīng)用。實(shí)際上，近些年，針對(duì)大規(guī)模交換互聯(lián)網(wǎng)絡(luò)的并行算法研究確實(shí)也成為了熱點(diǎn)。例如，針對(duì)OTIS(optical transpose interconnection system)，Sahni等提出了建立在OTIS-Mesh上的矩陣算法[5]，以及基于OTISHypercube和OTIS-Mesh上的BPC排列算法[6,7]；Jana等給出了基于OTIS-Mesh的多項(xiàng)式插值算法[8]；Rajasekaran等研究了OTIS-Mesh上的選擇及路由等有效算法[9]；而諸如圖形處理[10]、數(shù)據(jù)求和[11]、k-k排序[12]等OTIS算法也已給出。對(duì)于BSN架構(gòu)，Wei wenhong、Sun liting等也研究了其上的矩陣算法[13,14]，在文獻(xiàn)[15]中，Ye等提出基于BSNHypercube的數(shù)據(jù)廣播等算法。本文同樣研究了在并行處理中基于BSN-MOT的基本通信及應(yīng)用操作算法，這些算法可以應(yīng)用至重要的開發(fā)程序，如圖像處理、矩陣代數(shù)、圖論等。

2 基本概念和性質(zhì)

本文定義BSN-MOT是由2n2個(gè)同構(gòu)的n×n(定義)MOT組成，即在BSN-MOT多處理器系統(tǒng)中，BSN-MOT含有2n4個(gè)處理器，它是由2n2個(gè)點(diǎn)不相交的同構(gòu)MOT組成，每個(gè)處理器的索引都記為(i, g, p)，其中，i代表部索引，二維布局g(x, y)是組索引，代表了組的位置，p(x, y)是處理器的本地索引，則索引(i,gx,gy,px,py)代表了處于第i部的g(x, y)組的p(x, y)處理器。其中，同一組內(nèi)的處理器鏈接是組內(nèi)鏈接，而不同部的處理器鏈接則是組間鏈接，即第i部組g中的處理器p是與第i部組p中的處理器g連接，也就是(i,gx,gy, px,py)與連接。圖1給出了含有32個(gè)處理器的BSN-MOT。在圖中，小方框代表處理器，大方框則代表處理器組。小方框中的數(shù)據(jù)對(duì)(i, j)指明每組MOT中的本地索引；而大方框外的數(shù)據(jù)對(duì)(a, b)則是每部中的組索引。

2.1 基本定義

定義1 (組內(nèi)鏈接)。MOT中的組內(nèi)鏈接包含了行樹鏈接及列樹鏈接[16]。

在MOT的每行中，處理器都形成了一顆行樹，根節(jié)點(diǎn)索引記為(i,gx,gy,px,1)，且在每部中，對(duì)任意gx，gy，1≤gx,gy≤n ，P(i,gx,gy,px,py)都直接與P(i,gx,gy,px,2py)及P(i,gx,gy,px,2py+1)（若存在）連接，其中，1≤px,py≤n 。

相似地，在MOT的每列中，處理器都形成了一棵列樹，其根節(jié)點(diǎn)為P(i,gx,gy,1,py)，且對(duì)gx，gy,1≤gx,gy≤n ,P(i,gx,gy,px,py)都直接與P(i,gx,gy,2px,py)及P(i,gx,gy,2px+1,py)(若存在)連接，其中，1≤px,py≤n 。

圖2給出了BSN-MOT中單組6×6MOT示例。

定義2 (組間鏈接)。組間鏈接定義如下：處理器P(i,gx,gy,px,py)直接與連接。

圖1 32處理器的BSN-MOT

圖2 BSN-MOT6中部0中的組g(0,0)

2.2 拓?fù)湫再|(zhì)

2.2.1 最短路徑

假設(shè)d(u,v)表示MOT中處理器P1到P2的最短路徑長度；P1(i1,gx1,gy1,px1,py1)與P2(i2,gx2,gy2,px2,py2)是BSN-MOT中的任意兩不同點(diǎn)，則P1到P2的最短路徑分下列3種情況構(gòu)造。

1) 路徑只存在組內(nèi)移動(dòng)。當(dāng)且僅當(dāng)i1=i2，g(x1,y1)=g(x2,y2) ，且p(x1,y1)≠p(x2,y2)，即P1與P2是同部內(nèi)同組中的不同兩點(diǎn)，則在MOT中，從P1到P2的一條最短路徑為p1→s1?s2→p2，其中s1屬于與p1相鄰的處理器集合，s2屬于與p2相鄰的處理器集合。

2) 路徑包含偶數(shù)個(gè)組間移動(dòng)。當(dāng)且僅當(dāng)i1=i2，g(x1,y1)≠g(x2,y2)，且p(x1,y1)≠p(x2,y2)，即P1與P2是同部內(nèi)不同組的兩點(diǎn)。如果組間移動(dòng)的數(shù)量超過2個(gè)，則可壓縮得到從P1到P2的一條最短路徑p1→s1?s2→p2，即

其中，雙箭頭代表組內(nèi)移動(dòng)，單箭頭表示組間移動(dòng)。

3) 路徑包含奇數(shù)個(gè)組間移動(dòng)。當(dāng)且僅當(dāng)i1≠i2，即P1與P2屬于不同部的兩點(diǎn)。在這種情況下，最短路徑必包含一個(gè)組間移動(dòng)，其最短路徑為p1→s1?s2→p2，即

注意的是，如果p(x1,y1)=g(x2,y2)，則

(i1,gx1,gy1,px1,py1)?(i1,gx1,gy1,gx2,gy2)為一條空路徑；若g(x1,y1)=p(x2,y2)，則(i2,gx2,gy2,gx1,gy1)?(i2,gx2,gy2,px2,py2)同為空路徑。

從以上情況可以看出，情況1)的最短路徑長度為d(p(x1,y1),p(x2,y2))，情況2)和情況3)的最短路徑長度則分別為d(p(x1,y1),p(x2,y2))+d(g(x1,y1),g(x2,y2))+2及d(p(x1,y1),g(x2,y2))+d(g(x1,y1),p(x2,y2))+1。

2.2.2 直徑

定理1 BSN-MOT的直徑為8logn+2。

證明 因BSN-MOT的每組都是一n×n MOT，而直徑是指網(wǎng)絡(luò)圖中最大的離徑，則BSN-MOT每組的直徑為4logn。假設(shè)P1與P2各自代表BSN-MOT中任意不同的源節(jié)點(diǎn)及目標(biāo)節(jié)點(diǎn)。如果i1≠i2，則兩節(jié)點(diǎn)可通過一組間鏈接來連接。如此，可從源節(jié)點(diǎn)過渡到一中間節(jié)點(diǎn)，即(i1,gx1,gy1,gx2,gy2)，其路由距離即為4logn。而從(i1,gx1,gy1,gx2,gy2)出發(fā)，可以通過一組間移動(dòng)到達(dá)(i2,gx2,gy2,gx1,gy1)，之后通過另一組內(nèi)移動(dòng)，這樣就可到達(dá)目標(biāo)節(jié)點(diǎn)P2。通過計(jì)算，從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最大離徑即為8logn+1。然而，通過另一種假想，如果i1=i2，則整個(gè)路由過程會(huì)通過2個(gè)組間移動(dòng)和2個(gè)組內(nèi)移動(dòng)來完成，依照這種情況，兩節(jié)點(diǎn)的最大離徑即為8logn+2，因此，BSN-MOT的直徑即為8logn+2。

2.2.3 容錯(cuò)直徑

假設(shè)BSN-MOT的任意源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)分別由P1及P2來表示。

倘若i1≠i2，g(x1,y1)≠g(x2,y2) ，則如果容錯(cuò)節(jié)點(diǎn)是在源節(jié)點(diǎn)所在的同行或同列，那么BSN-MOT的直徑將變?yōu)?logn+1，其路徑即是2.2.1節(jié)提及的第3種情況；然而，如果容錯(cuò)節(jié)點(diǎn)是其路徑上的中間節(jié)點(diǎn)(i1,gx1,gy1,gx2,gy2)，其路由路徑將變?yōu)?/p>

BSN-MOT的直徑變?yōu)?logn+3。

倘若i1=i2，g(x1,y1)≠g(x2,y2) ，而容錯(cuò)節(jié)點(diǎn)是在源節(jié)點(diǎn)所在的同行或同列時(shí)，BSN-MOT的直徑仍保持為8logn+2，其路由路徑即是2.2.1節(jié)提及的第2種情況；相似地，如果容錯(cuò)節(jié)點(diǎn)是其路徑上的中間節(jié)點(diǎn)(i1,gx1,gy1,px2,py2)，則路由將繞過此節(jié)點(diǎn)，其路由路徑變?yōu)?/p>

此時(shí)，BSN-MOT的直徑變?yōu)?logn+3。

2.2.4 寬直徑

寬直徑也是衡量網(wǎng)絡(luò)容錯(cuò)性的一個(gè)重要度量標(biāo)準(zhǔn)，而描述寬直徑就需要提到容器的概念。假設(shè)G是連通圖，u及v是它的節(jié)點(diǎn)，則圖G中從u到v的一組并行路被稱為一(u,v)容器，容器的寬度為其中并行路的條數(shù)，容器的長度為其中最長路的長度。某兩點(diǎn)間寬度為d的所有容器的最小長度稱為這兩點(diǎn)間的d-寬距離，所有點(diǎn)對(duì)間的d-寬距離的最大值稱作是圖G的d-寬直徑[1]。然而求一般圖的寬直徑是NP完全難問題，但是參考文獻(xiàn)[1]的式(1)～式(8)，本文可推理得到BSN-MOT的寬直徑上限不超過3d(MOT)+6，即12logn+6。

3 通信操作算法

本節(jié)將提出并行處理中基于BSN-MOT架構(gòu)的各類基本的通信及應(yīng)用操作算法，如廣播算法、數(shù)據(jù)求和、矩陣乘積、排序、最短路徑路由及多項(xiàng)式求根等，然后通過算法復(fù)雜度分析及與其他2種流行樹形網(wǎng)絡(luò)MMT及OMULT的比較來證明BSNMOT是非?？焖?、有效的網(wǎng)絡(luò)架構(gòu)。

3.1 行樹廣播(Vx, A)

數(shù)據(jù)廣播是并行計(jì)算中最基本的通信操作之一。在本算法中，數(shù)據(jù)vx將被廣播至二維BSN-MOT的第x行。此算法描述如下。

step1 賦值v(gx-1)n+px至不同部的首列組的首列處理器，則寄存器A(i,gx,1,px,1)都有了賦值。

step2 通過行樹鏈接，廣播寄存器A內(nèi)的值至同行的其他處理器，如此，第1列組的所有處理器都有了數(shù)據(jù)值。

step3 對(duì)整個(gè)網(wǎng)絡(luò)通過組間鏈接執(zhí)行組間移動(dòng)。這樣，不同部的第1列處理器都擁有了一數(shù)值。

step4 廣播處理器中的數(shù)值至同行的其他處理器。

step5 再次執(zhí)行組間移動(dòng)。

step6 在step1中廣播處理器中的數(shù)值至同行的其他處理器。

step7 算法結(jié)束。最后，所有x行的處理其都有了數(shù)值vx。

圖3給出了BSN-MOT3經(jīng)過行樹廣播之后的賦值示例。

圖3 3 3×BSN-MOT中經(jīng)過行樹廣播的賦值示例

時(shí)間復(fù)雜度：從算法可以看到step3及step5各執(zhí)行一次組間移動(dòng)，step2通過廣播處理器中的數(shù)據(jù)至本地同行的其他處理器而消耗了logn次組內(nèi)移動(dòng)，step4與step2過程相似，同樣需要logn次組內(nèi)移動(dòng)，由此算法，可得出行樹廣播的時(shí)間復(fù)雜度為2logn次組內(nèi)移動(dòng)及2次的組間移動(dòng)。

注意：本文在分析時(shí)間復(fù)雜度時(shí)將以組間移動(dòng)及組內(nèi)移動(dòng)為度量標(biāo)準(zhǔn)，并且，組間移動(dòng)及組內(nèi)移動(dòng)是分開描述的。執(zhí)行組間移動(dòng)比執(zhí)行組內(nèi)移動(dòng)需要消耗更大的網(wǎng)絡(luò)帶寬，且組間鏈接與組內(nèi)鏈接在數(shù)據(jù)傳輸及等待時(shí)間上也是有差異的。

3.2 列樹廣播(Vy, A)

在列樹廣播算法中，數(shù)據(jù)vy將被廣播至BSNMOT的第y列。算法描述如下。

step1 賦值v(gy-1)n+py至不同部的第1行組的第1行處理器，則寄存器B(i,1,gy,1,py)都有了賦值。

step2 通過列樹鏈接，廣播寄存器B內(nèi)的值至同列的其他處理器，如此，第1行組的所有處理器都有了相應(yīng)的值。

step3 對(duì)整個(gè)網(wǎng)絡(luò)通過組間鏈接執(zhí)行組間移動(dòng)。這樣，不同部的所有第1行處理器都擁有了一數(shù)值。

step4 廣播處理器中的數(shù)值至同列的其他處理器。

step5 再次執(zhí)行組間移動(dòng)。

step6 在step1中廣播處理器中的數(shù)值至同列的其他處理器。

step7 算法結(jié)束。最后，所有y列的處理器都有了數(shù)值vy。

圖4給出了BSN-MOT3在經(jīng)過列樹廣播之后的賦值示例。

時(shí)間復(fù)雜度：與行樹廣播算法分析相似，此算法的時(shí)間復(fù)雜度為2logn次組內(nèi)移動(dòng)及2次的組間移動(dòng)。

圖4 3 3×BSN-MOT中經(jīng)過列樹廣播的賦值示例

3.3 單向廣播

在此算法中，數(shù)據(jù)首先被初始放置在一處理器(i,gx,gy,px,py)中，算法執(zhí)行后，數(shù)據(jù)將被廣播至其他2n4-1個(gè)處理器。算法如下。

step1 通過行樹鏈接及列樹鏈接，廣播(i,gx,gy,px,py)中的數(shù)據(jù)至本地組的其他處理器。

step2 對(duì)非空組執(zhí)行一次組間移動(dòng)。

step4 通過組間鏈接，廣播i內(nèi)的數(shù)據(jù)至i部。

step5 算法結(jié)束。

時(shí)間復(fù)雜度：執(zhí)行完step2，部i中的每組內(nèi)的一處理器都含有了數(shù)據(jù)副本，而經(jīng)過step4，數(shù)據(jù)在整個(gè)BSN-MOT中得到廣播。在此算法中，step1及step3各自需要2logn次組內(nèi)移動(dòng)，而step2及step4則各需要一次組間移動(dòng)，算法的時(shí)間復(fù)雜度為4logn次組內(nèi)移動(dòng)及2次組間移動(dòng)。

3.4 數(shù)據(jù)求和

在此算法中，每個(gè)處理器都含有一數(shù)據(jù)值，最后，2n4個(gè)數(shù)據(jù)的和值被放置在處理器(0,1,1,1,1)中。算法描述如下。

step1 通過行樹及列樹鏈接，對(duì)每部中的每組執(zhí)行本地求和，之后，將和值轉(zhuǎn)至處理器A(i,gx,gy,1,1)。

step2 對(duì)含有本地和值的處理器執(zhí)行組間移動(dòng)。

step3 分別在處理器A(0,1,1,px,py)及A(1,1,1,px,py)上執(zhí)行本地求和算法，之后，在i部，將和值移動(dòng)至A(i,1,1,1,1)。

step4 將處理器A(1,1,1,1,1)上的和值移動(dòng)至A(0,1,1,1,1)，然后將A(0,1,1,1,1)上的兩和值相加。

step5 算法結(jié)束。2n4個(gè)處理器中的數(shù)據(jù)的總和值即被存放在處理器(0,1,1,1,1)。

時(shí)間復(fù)雜度：執(zhí)行完step2，每部中組g(1,1)的每個(gè)處理器都含有一本地和值，在step4中，總的和值被存放在了處理器A(0,1,1,1,1)。此算法的時(shí)間復(fù)雜度即為4logn次組內(nèi)移動(dòng)及2次組間移動(dòng)。

3.5 矩陣乘法

算法初始，首先利用GRM(group row mapping)[5]方式將2個(gè)N2()Nn=階矩陣A和B映射到含有個(gè)處理器的BSN-MOT中，矩陣A被映射到BSN-MOT的0部，矩陣B被映射到1部。圖5給出了如何利用GRM將矩陣映射到BSN-MOT的分圖示例。在算法中，本文實(shí)現(xiàn)BSN-MOT上矩陣A及B的相乘，其乘積即為其中，矩陣第i行j列的元素被映射到組i的第j個(gè)處理器。算法如下。

step1 將部1中的B值通過組間鏈接移至0部。

step2 在部0中，每個(gè)處理器都通過行樹鏈接及列樹鏈接將本地組中的A、B值集結(jié)。

step3 將集結(jié)的B值沿組間鏈接移至部1中。

step4 將集結(jié)的A值也從處理器(0,,)ij移至(1,,)ij。

step5 在部1中，每個(gè)處理器都計(jì)算其內(nèi)的A值與B值的對(duì)應(yīng)內(nèi)積。

step6 算法結(jié)束。乘積矩陣在部1中生成。

圖5 GRM矩陣元素映射至BSN-MOT4的分布示例

由上述算法得知，算法開始時(shí)，矩陣元素Aij及Bij被分別放置在處理器(0,i,j)及(1,i,j)中。執(zhí)行完step1，(0,i,j)含有Aij及Bij；在step2中，每組中的每個(gè)處理器都含有矩陣A的第i行值及B的第j列值；執(zhí)行完step3，部1中每組的處理器都含有B的第j列值。而在step5，乘積矩陣的元素Cij在部1中得出。

時(shí)間復(fù)雜度：值得說明的是，在step2中，本地組中的所有A值與B值都被集結(jié)，此步需要4logn次組內(nèi)移動(dòng)。最后，此算法的時(shí)間復(fù)雜度即為2次的組間移動(dòng)及4logn+2次的組內(nèi)移動(dòng)。

注意：可以利用此映射方式及BSN-MOT計(jì)算兩向量的乘積，如列向量×行向量，行向量×列向量，或行向量×矩陣以及矩陣×列向量。

3.6 排序

在此，本文對(duì)n2個(gè)數(shù)據(jù)元素z0,z1,…,zn2-1進(jìn)行排序。假設(shè)BSN-MOT的每個(gè)處理器都含有3個(gè)寄存器A、B、C，寄存器A及B用來存儲(chǔ)數(shù)據(jù)元素，C用來存儲(chǔ)數(shù)據(jù)排名。首先，寄存器A的初始賦值如下：(i,gxy,A00)←z(nx+y)，其中，0≤x,y≤n-1。算法如下。

step1 對(duì)任意x及y，0≤x,y≤n-1 ，廣播(i,gxy,A00)中的值至本地組的其他處理器。

step2 對(duì)任意x及y，0≤x,y≤n-1，將(i,gxy,Akl)賦值給(i,gxy,Bkl)。

step3 對(duì)任意x，y，k，l，0≤x,y,k,l≤n-1 ，對(duì)(i,gxy,Bkl)中的數(shù)據(jù)執(zhí)行組間移動(dòng)。

step4 對(duì)任意x，y，k，l，0≤x,y,k,l≤n-1，如果(i,gxy,Akl)≥(i,gxy,Bkl)則(i,gxy,Ckl)=1；反之，(i,gxy,Ckl)=0。

step5 對(duì)寄存器C中的數(shù)據(jù)執(zhí)行本地組的求和，之后和值寄存在處理器(i,gxy,C00)。

step6 對(duì)任意x及y，0≤x,y≤n-1，廣播處理器(i,gxy,C00)的數(shù)據(jù)至本組內(nèi)的其他處理器。

step7 對(duì)任意x，y，k，l，0≤x,y,k,l≤n-1，如果(i,gxy,Ckl)=nk+l+1，對(duì)(i,gxy,Akl)及(i,gxy,Ckl)執(zhí)行組間移動(dòng)，隨后各自在本地組內(nèi)進(jìn)行廣播。

step8 對(duì)任意x，y，k，l，0≤x,y,k,l≤n-1，對(duì)(i,gxy,Akl)執(zhí)行組間移動(dòng)。

step9 算法結(jié)束。

圖6給出了數(shù)據(jù)集{60，45，65，55，23，18，59，78，3}在BSN-MOT3上執(zhí)行完排序算法后的分布示例。

時(shí)間復(fù)雜度：可以看出，在step3、step7及step8中各執(zhí)行了一次組間移動(dòng)，而step1、step4、step5及step7則各自執(zhí)行了2logn次組內(nèi)移動(dòng)。此算法的時(shí)間復(fù)雜度則為8logn次組內(nèi)移動(dòng)及3次的組間移動(dòng)。

3.7 最短路徑路由

本節(jié)提出一種應(yīng)用在MOT上的基于SPR[2]的新的最短路徑路由算法，稱之為E-SPR，隨后將E-SPR應(yīng)用在整個(gè)BSN-MOT中。

首先，將E-SPR應(yīng)用在MOT中。本文定義(x,y)為頂點(diǎn)u的二維二進(jìn)制表示，其中，“x”表示u的行索引，“y”表示u的列索引。對(duì)整個(gè)MOT，其根節(jié)點(diǎn)被標(biāo)志為(1,1)。對(duì)任意的內(nèi)部節(jié)點(diǎn)u，它的左孩子被標(biāo)記為2u，右孩子被標(biāo)記為2u+1。接下來便給出從節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑路由算法，其中，u用(x1,y1)表示，v用(x2,y2)表示。在路由過程中，首先遍歷行鏈接的二進(jìn)制樹，直到滿足x1=x2，接下來，便開始搜尋列鏈接的二進(jìn)制樹，直到y(tǒng)1=y2?，F(xiàn)在，先以一個(gè)行鏈接的二進(jìn)制搜索為例：如果x1不是x2的前綴，則將x1移至它的父節(jié)點(diǎn)，并將父節(jié)點(diǎn)索引標(biāo)為x1；然而，如果x1是x2的前綴，則將此前綴從x2消除，之后觀察x2剩余比特的最左邊的一位，如果此比特是1，則將x1移至它的右孩子，并且將右孩子的二進(jìn)制索引標(biāo)為x1；若此比特是0，則將x1移至它的左孩子，并將左孩子的索引標(biāo)為x1。圖7就給出了MOT6中從節(jié)點(diǎn)u(10,1)到目標(biāo)節(jié)點(diǎn)v(110,101)的最短路由路徑。

圖6 排序之后寄存器A及C內(nèi)的數(shù)值示例

圖7 E-SPR: MOT6中從u到v的最短路由路徑示例

下一步，本文運(yùn)用E-SPR至BSN-MOT。假使源節(jié)點(diǎn)及目標(biāo)節(jié)點(diǎn)分別為(i1,gx1,gy1,px1,py1)及(i2,gx2,gy2,px2,py2)，則E-SPR算法如下。

step1 在部i1中應(yīng)用E-SPR至組g(x1,y1)，直到尋到節(jié)點(diǎn)(i1,gx1,gy1,gx2,gy2)。

step2 執(zhí)行組間移動(dòng)，即可尋到節(jié)點(diǎn)(i2,gx2,gy2,gx1,gy1)。

step3 在部i2中再次應(yīng)用E-SPR至組g(x2,y2)，則目標(biāo)節(jié)點(diǎn)(i2,gx2,gy2,px2,py2)即可遍歷到。

step4 算法結(jié)束。

時(shí)間復(fù)雜度：此算法的時(shí)間復(fù)雜度為8logn次組內(nèi)移動(dòng)及1次的組間移動(dòng)，但是，倘若源節(jié)點(diǎn)及目標(biāo)節(jié)點(diǎn)是處于同一部中，則算法的時(shí)間復(fù)雜度為8logn次的組內(nèi)移動(dòng)及2次的組間移動(dòng)。

3.8 多項(xiàng)式求根

多項(xiàng)式求根是許多實(shí)踐應(yīng)用中重要的計(jì)算步驟之一，如在并行計(jì)算的負(fù)載均衡策略中[17]，多項(xiàng)式求根在基于多項(xiàng)式的迭代模型方法中是非常關(guān)鍵的一步。

首先，N次多項(xiàng)式可表示如下

則根據(jù)Durand-Kerner迭代模型，其根的表示形式為[18]

根據(jù)上面的公式可以看出，xi(k)表示根的第k個(gè)近似值。Jana[8]已經(jīng)提出了基于OTIS-Mesh的多項(xiàng)式求根算法，在此，提出基于BSN-MOT的多項(xiàng)式求根算法。首先，假設(shè)每個(gè)處理器都含有4個(gè)寄存器，即A、B、C、D。

算法執(zhí)行如下。

step2 通過行樹鏈接，將寄存器A內(nèi)的值廣播至本地組的其他同行的處理器。

step4 通過列樹鏈接，將寄存器B內(nèi)的值廣播至本地組的其他同列處理器。

step5 對(duì)A及B各執(zhí)行組間移動(dòng)。

step6 在每組中，廣播A值至本地組的同行處理器，同時(shí)，廣播B值至本地組的同列處理器。

step7 對(duì)BSN-MOT的每個(gè)處理器：

如果A中的值不等于B中的值，

則A←A-B；

反之，A←1。

step8 在每部中的每組，將同行的所有A值相乘，乘積存儲(chǔ)在A(i,gx,gy,px,1)。

step9 對(duì)A值執(zhí)行組間移動(dòng)。

step10 不同于step8，將部0中第1列組中的所有處于同一行的A值相乘，其乘積放在A(0,gx,1,px,1)。

時(shí)間復(fù)雜度：此算法的時(shí)間復(fù)雜度即為6logn次組內(nèi)移動(dòng)及2次的組間移動(dòng)。

3.9 BSN-MOT與MMT及OMULT的性能比較

本節(jié)將BSN-MOT與另外2種流行的雙層樹形網(wǎng)絡(luò)即MMT及OMULT進(jìn)行比較來說明BSNMOT的快速有效性(在文獻(xiàn)[5]中，Jana已經(jīng)分析了MMT的拓?fù)湫再|(zhì)及架構(gòu)的有效性；Islam[4]也證明了OMULT的性能優(yōu)勢(shì))。表1列出了3種架構(gòu)下的各算法的時(shí)間復(fù)雜度比較。從表中數(shù)據(jù)可以看出，BSN-MOT是比MMT及OMULT更快速、有效的網(wǎng)絡(luò)架構(gòu)，而算法有效的關(guān)鍵點(diǎn)就是利用了BSN特殊的結(jié)構(gòu)體系，以致降低了其通信流量。

4 結(jié)束語

基于BSN的一系列的理想特性，諸如擴(kuò)展性，繼承因子網(wǎng)絡(luò)的正則性、點(diǎn)傳遞性、Cayley圖、哈密爾頓圈及極大容錯(cuò)性等，在并行計(jì)算中研究其上的基本通信操作算法是非常有意義的。本文提出一種新型的雙層架構(gòu)BSN-MOT，并研究了其上的一些拓?fù)湫再|(zhì)及基本的通信及應(yīng)用操作算法，如行、列樹廣播、數(shù)據(jù)求和、矩陣相乘、排序及多項(xiàng)式求根等，并理論分析了每種算法的時(shí)間復(fù)雜度，且通過列表研究給出了BSN-MOT與同為基于樹的雙重架構(gòu)MMT及OMULT的各算法的時(shí)間復(fù)雜度比較。從數(shù)據(jù)結(jié)果可以看出，BSN-MOT是比MMT及OMULT更快速、有效的網(wǎng)絡(luò)架構(gòu)。而未來的工作將基于BSN-MOT的各操作算法是否可以延伸至其他BSN進(jìn)行展開研究。

表1 BSN-MOT、MMT和OMULT的算法時(shí)間復(fù)雜度比較

[1] 陳衛(wèi)東,肖文俊. Biswapped網(wǎng)絡(luò)(BSN)的拓?fù)湫再|(zhì)研究:點(diǎn)對(duì)稱性和極大容錯(cuò)性[J].計(jì)算機(jī)學(xué)報(bào),2010,33(5): 822-832.CHEN W D, XIAO W J. Topological properties of biswapped networks (BSN): node symmetry and maximal fault tolerance[J]. Chinese Journal of Computers, 2010, 33(5): 822-832.

[2] KEMAL K, FERNANDEZ A. Mesh-connected trees: a bridge between grids and meshes of trees[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(12):1281-1291.

[3] JANA P K. Multi-mesh of trees with its parallel algorithms[J]. Journal of Systems Architecture, 2004, 50(4):193-206.

[4] ISLAM R, AFROZ N, BANDYOPADHYAY S, etal. Computational geometry on optical multi-trees (OMULT) computer system[A].CCCG 2005[C]. 2005.150-154.

[5] WANG C F, SAHNI S. Matrix multiplication on the OTIS-Mesh optoelectronic computer[J]. IEEE Transactions on Computers, 2001,50(7):635-646.

[6] SAHNI S, WANG C. BPC permutations on the OTIS-hypercube optoelectronic computer[J]. Informatica (Ljubljana), 1998,22(3): 263-269.

[7] SAHNI S, WANG C. BPC permutations on the OTIS-mesh optoelectronic computer[A]. Proceedings of the 1997 4th International Conference on Massively Parallel Processing Using Optical Interonnections,MPPOI'97[C]. Montreal, Can,1997.

[8] JANA P K. Polynomial interpolation and polynomial root finding on OTIS-mesh[J]. Parallel Computing, 2006,32(4):301-312.

[9] RAJASEKARAN S, SAHNI S. Randomized routing, selection, and sorting on the OTIS-mesh[J]. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(9):833-840.

[10] WANG C, SAHNI S. Image processing on the OTIS-mesh optoelectronic computer[J]. IEEE Transactions on Parallel and Distributed Systems, 2000,11(2):97-109.

[11] WANG C F, SAHNI S. Basic operations on the OTIS-mesh optoelectronic computer[J]. IEEE Transactions on Parallel and Distributed Systems, 1998,9(12):1226-1236.

[12] OSTERLOH A. Sorting on the OTIS-mesh[A]. Proceedings of the International Parallel Processing Symposium, IPPS[C]. 2000.269-274.

[13] WEI W, XIAO W. Matrix multiplication on the biswapped-mesh network[A]. SNPD 2007: 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing[C]. Qingdao, China, 2007.

[14] SUN L, TONG C, SU H. New mapping scheme of matrix algorithms on the Biswapped network[J]. Journal of Computational Information Systems, 2013,9(13):5371-5378.

[15] YE H, XIAO W, WU J. Broadcasting on the BSN-hypercube network[A]. 2009 2nd International Conference on Information and Computing Science, ICIC 2009[C]. Manchester, United Kingdom,2009.

[16] CHEN W, CHEN G, HSU D F. Generalized diameters of the mesh of trees[J]. Theory of Computing Systems, 2004,37(4):547-556.

[17] DIEKMANN R, FROMMER A, MONIEN B. Efficient schemes for nearest neighbor load balancing[J]. Parallel Computing, 1999, 25(7):789-812.

[18] FREEMAN T L. Calculating polynomial zeros on a local memory parallel computer[J]. Parallel Computing, 1989,12(3):351-358.