高級(jí)計(jì)算機(jī)體系結(jié)構(gòu) 第六 互連與路由2

1、Parallel Computer Architecture并行計(jì)算機(jī)體系結(jié)構(gòu)Lecture 6April 12, 2010 Wu junmin ()OverviewReview of Lec05MIN中的路由聚合通信支持柵欄同步硬件支持路由算法的分類確定性路由算法在任意節(jié)點(diǎn)對(duì)之間總是提供相同的路徑不考慮網(wǎng)絡(luò)的通信流量，當(dāng)網(wǎng)絡(luò)通信均勻的情況下性能一般較好，但不均勻時(shí)性能較差（尤其是一些非相鄰節(jié)點(diǎn)之間頻繁交換信息時(shí)）在蟲孔交換網(wǎng)絡(luò)中大量使用，便于硬件路由器實(shí)現(xiàn)通常為前進(jìn)式和最短型的如維序路由:前進(jìn)式路由算法每路由一步偏移量減1，當(dāng)前維的偏移量為0后才計(jì)算下一維的偏移量XY路由/Internal是

2、連接本地節(jié)點(diǎn)的通道E-cube路由/firstone()返回第一個(gè)值為1的位死鎖、活鎖及餓死死鎖避免定理路由算法使用路由函數(shù)和選擇函數(shù)來描述，路由函數(shù)根據(jù)當(dāng)前節(jié)點(diǎn)和目的節(jié)點(diǎn)提供一組輸出通道；選擇函數(shù)根據(jù)當(dāng)前節(jié)點(diǎn)輸出通道的狀態(tài)，從路由函數(shù)提供的通道中選擇一條空閑通道。路由函數(shù)決定路由算法是否是無死鎖的，而選擇函數(shù)只影響性能。通道相關(guān)：當(dāng)一個(gè)報(bào)文占用一條通道，然后請(qǐng)求使用另一條通道時(shí)，這兩條通道間就存在相關(guān)性?；ミB網(wǎng)絡(luò)I的一個(gè)（確定性）路由函數(shù)R是無死鎖的，當(dāng)且僅當(dāng)通道相關(guān)圖D中沒有環(huán)路。部分自適應(yīng)路由算法在路由決策時(shí)要考慮網(wǎng)絡(luò)的狀態(tài)在源路由時(shí)通常意義不大，收集費(fèi)時(shí)，信息可能過時(shí)分布式路由時(shí)通常只

3、考慮本地信息（從效率考慮）可分解為兩個(gè)函數(shù)：路由和選擇路由函數(shù)根據(jù)當(dāng)前節(jié)點(diǎn)和目的節(jié)點(diǎn)提供一組輸出通道選擇函數(shù)根據(jù)當(dāng)前節(jié)點(diǎn)輸出通道的狀態(tài)從路由函數(shù)提供的輸出通道組中進(jìn)行選擇，進(jìn)而選擇一條空閑通道（如果有的話）提高了路由靈活性，但增加了硬件復(fù)雜度，更慢部分自適應(yīng)算法只能使用路徑集合中的一個(gè)子集靈活性與成本的折中通過增加適當(dāng)?shù)膹?fù)雜度而獲得全自適應(yīng)路由的靈活性平面自適應(yīng)路由針對(duì)n維網(wǎng)格和超立方體在同一時(shí)刻只在兩維中提供自適應(yīng)性，報(bào)文在一系列兩維平面中進(jìn)行自適應(yīng)路由。因此，在報(bào)文向其目的地前進(jìn)時(shí)，路由的維是不斷變化的。轉(zhuǎn)彎模型轉(zhuǎn)彎模型中最基本的概念是禁止最小數(shù)量的轉(zhuǎn)彎，防止環(huán)的出現(xiàn)，從而不會(huì)發(fā)生死鎖。如

4、二維網(wǎng)格中西向優(yōu)先算法最小西向優(yōu)先算法Select()為選擇函數(shù)，從通道集中選擇一個(gè)空閑通道西向優(yōu)先路由示例二維網(wǎng)格的轉(zhuǎn)彎模型對(duì)于二維網(wǎng)孔，有8種可能的“轉(zhuǎn)彎”，會(huì)形成兩種簡(jiǎn)單的圈在二維網(wǎng)孔中，有16種方法可禁止兩轉(zhuǎn)彎（Two Turn），其中12種可以避免死鎖，只有3種是獨(dú)立的。 不能防止死鎖的情況轉(zhuǎn)彎模型P立方路由算法P立方路由算法：超立方體的部分自適應(yīng)路由算法二元n立方體的源s=sn-1sn-2s0目的d=dn-1dn-2d0集合E由所有s和d有差別的維數(shù)組成，E分為兩個(gè)不相交的子集E0和E1對(duì)于E中的所有i，如果si=0且di=1，則i E0，否則iE1P立方路由的基本概念就是將路由選

5、擇分成兩個(gè)階段第一個(gè)階段報(bào)文在E0中以任意維序路由第二個(gè)階段在E1中以任意維序路由為什么無死鎖可以派生出其它算法轉(zhuǎn)彎模型=OverviewReview of Lec5MIN中的路由聚合通信支持柵欄同步硬件支持MIN中的阻塞N個(gè)處理器，每一級(jí)kxk開關(guān)之間恰好有N條鏈路，網(wǎng)絡(luò)共有l(wèi)ogkN級(jí)，其中每級(jí)具有N/k個(gè)開關(guān)。如果兩對(duì)輸入/輸出路徑經(jīng)過同一中間鏈路或共享任意一個(gè)中間級(jí)的同一個(gè)輸出，那么這兩對(duì)輸入輸出路徑就產(chǎn)生沖突。以O(shè)mega網(wǎng)絡(luò)為例，假設(shè)網(wǎng)絡(luò)是基于電路交換的Omega網(wǎng)絡(luò)結(jié)構(gòu)Omega中的地址映射考慮從Sn-1Sn-2S1S0 到dn-1dn-2d1d0建立一條電路經(jīng)過第0級(jí)鏈路： S

6、n-1Sn-2S1S0-Sn-2Sn-3S1S0Sn-1作為第0級(jí)開關(guān)的輸入地址，所以第0級(jí)開關(guān)必須將Sn-2Sn-3S1S0Sn-1 - Sn-2Sn-3S1S0Sn-1經(jīng)過第1級(jí)鏈路： Sn-2Sn-3S1S0Sn-1-Sn-3Sn-4S0Sn-1Sn-2作為第1級(jí)開關(guān)的輸入地址，所以第1級(jí)開關(guān)必須將Sn-3Sn-4S0S0-1Sn-2 - Sn-3Sn-4S0Sn-1Sn-2類似的有第i級(jí)開關(guān)的輸出為Sn-i-2Sn-i-3S0Sn-1Sn-2Sn-i-1從而第n-1級(jí)開關(guān)的輸出為Sn-1Sn-2S1S0最后一級(jí)連接為恒等排列，所以Sn-1Sn-2S1S0=dn-1dn-2d1d0從而有

7、Si=di所以第i級(jí)開關(guān)的輸出為Sn-i-2Sn-i-3S0dn-1dn-2dn-i-1阻塞條件對(duì)于任意兩個(gè)輸入/輸出對(duì)（S,D)和（R,T)，可以建立無沖突的兩條路徑的充要條件是：對(duì)于任意的i都有sn-i-2sn-i-3s0dn-1dn-2dn-i-1不等于rn-i-2rn-i-3r0tn-1tn-2tn-i-1將兩個(gè)輸入/輸出對(duì)的地址級(jí)聯(lián)在一起，將一個(gè)大小為n的窗口在兩個(gè)輸入/輸出對(duì)上滑動(dòng)，并對(duì)兩個(gè)窗口中的內(nèi)容進(jìn)行比較。如果它們?cè)谌我恻c(diǎn)相等，那么兩條路徑在網(wǎng)絡(luò)的某一級(jí)存在沖突。如（0110，1100） （1010，1111）有沖突 （0110，1100） （1110，1011）有沖突 （0

8、110，1100） （1010，1011）無沖突MIN的自路由算法Delta網(wǎng)絡(luò)的自路由特性：允許根據(jù)目的地址做出路由決策，不必考慮源地址。自路由使用路由標(biāo)志T=tn-1.t1t0執(zhí)行，ti控制Gi級(jí)開關(guān)每一級(jí)路由標(biāo)志都考慮哪一位是最低有效位，其最終映射到的目標(biāo)地址的相應(yīng)位為哪一位，從而ti等于目標(biāo)地址中該位的值。在OMEGA網(wǎng)絡(luò)中，在第i級(jí)開關(guān)最低有效位為第n-i-1位，并且最終映射到的目標(biāo)地址中的對(duì)應(yīng)位為第n-i-1位，所以ti=dn-i-1 0=i=n-1在蝶形MIN中，ti=di+1(0=i=n-2),tn-1=d0在立方體MIN中ti=?蝶式MIN中基于標(biāo)志的路由OverviewRe

9、view of Lec5MIN中的路由聚合通信支持柵欄同步硬件支持聚合通信服務(wù)涉及全局?jǐn)?shù)據(jù)遷移和全局控制的操作稱為聚合通信，執(zhí)行這些操作時(shí)會(huì)聚合地涉及到許多處理器。很多并行編程支持聚合通信，如HPF，MPI等很多科學(xué)應(yīng)用需要，能簡(jiǎn)化并行編程聚合通信包括一組進(jìn)程，通常稱為一個(gè)進(jìn)程組假設(shè)一個(gè)進(jìn)程組G有n個(gè)進(jìn)程P1,P2,Pn，所有進(jìn)程都涉及到聚合通信多個(gè)點(diǎn)到點(diǎn)通信每個(gè)進(jìn)程至多可以發(fā)送一個(gè)消息并至多接收一個(gè)消息如果每個(gè)進(jìn)程都恰好發(fā)送一個(gè)消息并恰好接收一個(gè)消息，則總共有n!種排列或通信模式。一對(duì)全通信一個(gè)進(jìn)程作為發(fā)送者，組中所有的進(jìn)程都是接收者，包括兩種不同的服務(wù)：廣播：同一個(gè)消息從發(fā)送者發(fā)送到所有的

10、接收者散播：發(fā)送者向不同的接收者發(fā)送不同的消息，也稱為私人化廣播。多對(duì)一通信進(jìn)程組中所有進(jìn)程都是發(fā)送者，而只有一個(gè)進(jìn)程被確定為唯一的接收者。包括：歸約：來自不同發(fā)送者的不同消息結(jié)合在一起形成一條消息送往發(fā)送者。結(jié)合操作碼通常是可交換或可結(jié)合的聚集: 來自不同發(fā)送者的不同消息級(jí)聯(lián)在一起形成一條消息送往接收者。級(jí)聯(lián)的順序取決于發(fā)送者的ID多對(duì)多通信進(jìn)程組中所有的進(jìn)程執(zhí)行各自的一對(duì)多通信，每個(gè)進(jìn)程接收來自進(jìn)程組內(nèi)n個(gè)不同發(fā)送者的n個(gè)消息。包括：全廣播：所有的進(jìn)程都執(zhí)行各自的廣播，所有的進(jìn)程都擁有同一組接收消息全散播：所有的進(jìn)程執(zhí)行各自的散播多播通信的評(píng)價(jià)標(biāo)準(zhǔn)通信量：消息從源發(fā)送到所有目的節(jié)點(diǎn)所使用的

11、通道數(shù)，包括某些重復(fù)使用的通道。時(shí)間：源發(fā)送第一個(gè)消息副本到最后一個(gè)目的節(jié)點(diǎn)接收完消息副本之間的時(shí)間。多播的硬件實(shí)現(xiàn)多地址編碼多目的消息的消息頭包含多個(gè)目的地址，好的多地址編碼策略應(yīng)能最小化消息頭長(zhǎng)度，減少消息頭的處理時(shí)間全目的編碼：所有的目的地址都包含在消息頭中。單播的路由硬件可以用于多播消息消息頭可以在地址微片一到達(dá)就馬上處理只適合于地址數(shù)目較少的情形位串編碼：每一位代表一個(gè)目的節(jié)點(diǎn)平均地址數(shù)目很大時(shí)有優(yōu)勢(shì)路由器通常需要緩沖整個(gè)位串以做出路由決策和產(chǎn)生輸出位串地址解碼不能使用和單播消息相同的硬件執(zhí)行位串的長(zhǎng)度通常取決于網(wǎng)絡(luò)大小，限制了擴(kuò)展性多地址編碼方案多播的硬件實(shí)現(xiàn)基于樹的多播路由盡可能

12、遠(yuǎn)地沿一條共用的路徑傳送消息，然后復(fù)制消息，再把副本傳到結(jié)合一個(gè)特定目的節(jié)點(diǎn)集的不同通道上每個(gè)副本傳送的路徑可以按這種方式進(jìn)一步分支，直到消息傳到每個(gè)目的節(jié)點(diǎn)。目的節(jié)點(diǎn)可以是樹的葉節(jié)點(diǎn)，也可以是樹的中間節(jié)點(diǎn)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都應(yīng)該能夠復(fù)制消息，把副本傳送到不同的輸出通道上超立方體中的廣播樹考慮一個(gè)n立方拓?fù)浣Y(jié)構(gòu)，該算法形成一棵生成二項(xiàng)式樹，系統(tǒng)中的每個(gè)節(jié)點(diǎn)都在不超過n步的時(shí)間內(nèi)恰好接收一次廣播消息，令s為源節(jié)點(diǎn)的地址，v為接收廣播消息的節(jié)點(diǎn)地址，F(xiàn)irstOne(d)表示一個(gè)n位二進(jìn)制數(shù)d中最低有效位為1的位置(0到n-1）；若d=0，令Firstone(d)=n。4立方中的廣播樹XY多播路由模

13、式基于樹的多播蟲孔交換中的死鎖由于路由器中沒有消息緩沖，如果樹的一個(gè)分支被阻塞，則所有的分支會(huì)被阻塞，進(jìn)而可能導(dǎo)致死鎖雙通道XY多播蟲孔路由該算法基于網(wǎng)絡(luò)分割概念，一個(gè)多播操作由幾個(gè)子多播操作實(shí)現(xiàn)，每個(gè)子多播以一個(gè)目的節(jié)點(diǎn)子集為目的，在不同的子網(wǎng)上路由。因?yàn)樽泳W(wǎng)是不相交和無環(huán)的，不存在任何資源的環(huán)相關(guān)，該算法是無死鎖的二維網(wǎng)格中的每條通道都加倍，網(wǎng)絡(luò)被分成四個(gè)子網(wǎng)：N+x,+yN+x,-yN-x,+yN-x,-y,其中N+x,+y包含(i,j),(i,j+1)和(i,j),(i+1,j)的單向通道，以此類推。網(wǎng)絡(luò)分割示意子網(wǎng)上的子多播對(duì)一個(gè)給定的多播，根據(jù)源節(jié)點(diǎn)u0與目的節(jié)點(diǎn)的相對(duì)位置，將目的

14、節(jié)點(diǎn)集D至多分成4個(gè)子集：D+x,+y、D+x,-y、D-x,+y、D-x,-y。集合D+x,+y包括u0右上方的目的節(jié)點(diǎn)，依次類推。這樣多播最多被分成從u0到D+x,+y、D+x,-y、D-x,+y、D-x,-y的四個(gè)子多播， u0到D+x,+y的子多播在子網(wǎng)N+x,+y上使用XY路由實(shí)現(xiàn)，依次類推。多級(jí)網(wǎng)絡(luò)中基于樹的多播多播在某些交叉開關(guān)同時(shí)向幾個(gè)輸出端口發(fā)送微片，一次性通過網(wǎng)絡(luò)在開關(guān)中復(fù)制消息可以是同步或異步同步復(fù)制時(shí)多目的消息的分支只有在所有請(qǐng)求的輸出通道都有效時(shí)才能夠前進(jìn)，在某一個(gè)給定時(shí)刻，消息頭都處于網(wǎng)絡(luò)同一級(jí)的不同開關(guān)中。需要復(fù)雜的硬件信號(hào)傳輸機(jī)制，使微片傳送變慢異步復(fù)制中每個(gè)分

15、支可以獨(dú)立的傳輸，不用與其它分支保持一致死鎖通過剪枝從死鎖中恢復(fù)MIN中多目的消息的死鎖MIN中利用剪枝恢復(fù)死鎖基于路徑的多播通信基于樹的多播通信中任何一個(gè)分支被阻塞，整個(gè)樹都會(huì)被阻塞。解決方法：阻止在中間節(jié)點(diǎn)的分支，形成多播路徑模式為了減少多播路徑的長(zhǎng)度，目的節(jié)點(diǎn)集可以分成幾個(gè)不相交的子集，源消息的副本可以在不相交的幾條多播路徑上傳送，每條路徑對(duì)應(yīng)一個(gè)目的節(jié)點(diǎn)子集。這種多目的路由策略稱為基于路徑的路由。每個(gè)副本的消息頭包含多個(gè)目的節(jié)點(diǎn)，源節(jié)點(diǎn)根據(jù)目的節(jié)點(diǎn)傳輸?shù)捻樞蚪o目的地址安排一個(gè)次序表，只要消息注入網(wǎng)絡(luò)，它就按照對(duì)應(yīng)于第一個(gè)目的節(jié)點(diǎn)的地址路由，一旦消息頭到達(dá)第一個(gè)目的節(jié)點(diǎn)路由器，路由器將包

16、含該地址的微片清除，然后消息按下一個(gè)頭微片中的地址路由，該地址對(duì)應(yīng)于次序表中的第二個(gè)目的節(jié)點(diǎn)。當(dāng)消息到達(dá)最后一個(gè)目的節(jié)點(diǎn)時(shí)，將不再繼續(xù)路由而被該節(jié)點(diǎn)完全吸收?；诠軤栴D路徑的路由函數(shù)一條哈密爾頓路徑恰好能夠訪問圖中每個(gè)節(jié)點(diǎn)一次。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)u根據(jù)在哈密爾頓路徑上的位置都被指定一個(gè)標(biāo)記l(u)，第一個(gè)節(jié)點(diǎn)標(biāo)記為0，最后一個(gè)節(jié)點(diǎn)標(biāo)記為N-1。高通道子網(wǎng)包括所有從低標(biāo)記節(jié)點(diǎn)指向高標(biāo)記節(jié)點(diǎn)的通道，低通道子網(wǎng)包括所有從高標(biāo)記節(jié)點(diǎn)指向低標(biāo)記節(jié)點(diǎn)的通道。在二維網(wǎng)格中，單播消息采用一條基于標(biāo)記的路徑來代替XY路由，如果目的節(jié)點(diǎn)的標(biāo)記大于源節(jié)點(diǎn)的標(biāo)記，則路由總在高通道子網(wǎng)上進(jìn)行，否則將在低通道子網(wǎng)上進(jìn)行。

17、二維網(wǎng)格節(jié)點(diǎn)標(biāo)記法l(x,y)=yn+x y為偶數(shù) =yn+n-x-1 y為奇數(shù)路由函數(shù)：假設(shè)當(dāng)前節(jié)點(diǎn)為u，目的節(jié)點(diǎn)為v,定義R(u,v)=w，使w為u的鄰居節(jié)點(diǎn),并且l(w)=maxl(z):l(z)=l(v)，z為u的相鄰節(jié)點(diǎn),若l(u)=l(v)，z為u的相鄰節(jié)點(diǎn),若l(u)l(v)節(jié)點(diǎn)標(biāo)記示意雙路徑多播路由把目的節(jié)點(diǎn)集分割成兩個(gè)子集：DH和DL ,其中DH中每個(gè)節(jié)點(diǎn)的標(biāo)記都比源節(jié)點(diǎn)的標(biāo)記高， DL中每個(gè)節(jié)點(diǎn)的標(biāo)記都比源節(jié)點(diǎn)低。從源節(jié)點(diǎn)發(fā)出的多播消息使用高通道網(wǎng)絡(luò)向DH中的目的節(jié)點(diǎn)發(fā)送消息，使用低通道網(wǎng)絡(luò)向DL中的目的節(jié)點(diǎn)發(fā)送消息。雙路徑多播路由的消息準(zhǔn)備路徑路由算法雙路徑多播路由示意多

18、路徑多播路由多路徑算法中將DH和DL進(jìn)一步分割DH集被分成兩個(gè)集合，分割節(jié)點(diǎn)的規(guī)則取決于源節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置和所用的標(biāo)記方法，如(源節(jié)點(diǎn)為8時(shí)）：一個(gè)包含X坐標(biāo)大于或等于源的節(jié)點(diǎn)，另一個(gè)包含DH中其它節(jié)點(diǎn)，DL類似分割。這樣可以利用更多的路徑來發(fā)送消息多路徑多播路由的消息準(zhǔn)備且l(v1)l(v2)多路徑多播路由示意OverviewReview of Lec5MIN中的路由聚合通信支持柵欄同步硬件支持線性陣列的柵欄同步第一階段用聚集消息實(shí)現(xiàn)報(bào)告，第二階段使用廣播消息實(shí)現(xiàn)喚醒結(jié)構(gòu)支持路由器接口提供一組緩沖，可支持實(shí)現(xiàn)多個(gè)柵欄緩沖器包括：id位、加入位、到達(dá)位、聚集消息緩沖聚集廣播消息中目的地址編碼為位串通信序列執(zhí)行柵欄x前，每個(gè)中間處理器要加入柵欄就會(huì)獲得其路由器接口的x緩沖，并將相應(yīng)的加入標(biāo)志位置1、到達(dá)標(biāo)志位清0。最右邊的加入處理器發(fā)出一個(gè)同步id=x的聚集消息，該消息通過中間路由器接口時(shí)檢查相應(yīng)緩沖器x的加入標(biāo)志和到達(dá)標(biāo)志。如果處理器沒有加入，則消息繼續(xù)前進(jìn)如果處理器已經(jīng)加入并且已經(jīng)到達(dá)同步點(diǎn)，則消息繼續(xù)前進(jìn)如果處理器已經(jīng)加入但沒有到達(dá)同步點(diǎn)，則消息阻塞在相應(yīng)的路由器接口上。此時(shí)消息保存在緩沖器x的“消息”域中，直到到達(dá)標(biāo)志被處理器置為1。然后聚集消息再次發(fā)往網(wǎng)絡(luò)最后這個(gè)聚集消息被最左邊的加入處理器吸收聚集階段結(jié)束后，最左邊的處理器發(fā)出一個(gè)廣播消息，該消息通過中