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

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

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

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

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

5、擇分成兩個階段第一個階段報文在E0中以任意維序路由第二個階段在E1中以任意維序路由為什么無死鎖可以派生出其它算法轉(zhuǎn)彎模型=OverviewReview of Lec5MIN中的路由聚合通信支持柵欄同步硬件支持MIN中的阻塞N個處理器，每一級kxk開關(guān)之間恰好有N條鏈路，網(wǎng)絡(luò)共有l(wèi)ogkN級，其中每級具有N/k個開關(guān)。如果兩對輸入/輸出路徑經(jīng)過同一中間鏈路或共享任意一個中間級的同一個輸出，那么這兩對輸入輸出路徑就產(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級鏈路： S

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

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

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

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

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

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

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

13、式基于樹的多播蟲孔交換中的死鎖由于路由器中沒有消息緩沖，如果樹的一個分支被阻塞，則所有的分支會被阻塞，進而可能導(dǎo)致死鎖雙通道XY多播蟲孔路由該算法基于網(wǎng)絡(luò)分割概念，一個多播操作由幾個子多播操作實現(xiàn)，每個子多播以一個目的節(jié)點子集為目的，在不同的子網(wǎng)上路由。因為子網(wǎng)是不相交和無環(huán)的，不存在任何資源的環(huán)相關(guān)，該算法是無死鎖的二維網(wǎng)格中的每條通道都加倍，網(wǎng)絡(luò)被分成四個子網(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)上的子多播對一個給定的多播，根據(jù)源節(jié)點u0與目的節(jié)點的相對位置，將目的

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

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

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

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

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