[文學研究]高等計算機系統(tǒng)結(jié)構-資料下載頁
2025-10-05 13:58本頁面
【正文】 ,6 1,5 4,5 7,5 1,4 2,4 3,4 4,4 5,4 7,4 1,3 2,3 3,3 4,3 5,3 6,3 7,3 2,2 4,2 7,2 2,1 3,1 4,1 5,1 6,1 7,1 2,0 Y X 東 — 北： ( 2 , 1 ) ? ( 7 , 6 ) 西 — 南： ( 5 , 4 ) ? ( 2 , 0 ) 東 — 南： ( 0 , 7 ) ? ( 4 , 2 ) 西 — 北： ( 6 , 3 ) ? ( 1 , 5 ) 特點 ： 總是先沿 X維方向?qū)?，然后再?Y維方向?qū)?，尋徑不會出現(xiàn)死鎖或循環(huán)等待現(xiàn)象。 可以擴充到 n維網(wǎng)絡，如 XYZ等等。 可用于存儲轉(zhuǎn)發(fā)或 Wormhole尋徑網(wǎng)絡，在源和目的結(jié)點之間形成一條距離最短的路徑。 （ 2）立方體網(wǎng)絡中的 E立方體尋徑 ： 假設有一個 N = 2n個結(jié)點的 n方體。每個結(jié)點的二進制編碼為： b = bn1 bn2 …b 1 b0 s = sn1 sn2 … s1 s0 d = dn1 dn2 … d1 d0 如何確定一條從 s到 d的步數(shù)最小的路徑 ？ 將 n維表示成 i = 1, 2, … n ，其中第 i維對應結(jié)點地址中的第 i1位。設 v = vn1 vn2 …v 1 v0 是路徑中的任一結(jié)點。 12 ?? iv方法 ： （ 1） 計算方向位。 。其中 nidSr iii ?,2,1,11 ??? ?? 使 i = 1 , v = s， 開始下面的步驟。 （ 2） 如果 ri = 1，則從當前結(jié)點 v尋徑到下一結(jié)點 ； 如果 ri = 0，則跳過這一步。 （ 3） i = i + 1，如果 i ? n，則轉(zhuǎn)第 （ 2） 步，否則退出。 如下面的例子： 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 1101 4維立方體網(wǎng)絡 n = 4， s = 0110， d = 1101 尋徑 ： （ 1） 計算方向位。 i = 1， v = s ? 0 1 1 r4 1 1 0 r3 1 0 1 r2 0 1 1 r1 （ R= ） （ 2） r1= 1， 210111000101102 11???????? ?iiss 到（ 3） r2= 1， 310 1 0 10 0 1 00 1 1 120 1 1 1 12????????? ?iivv 到（ 4） r3= 0， 41 ????ii跳過一步（ 5） r4= 1， ，結(jié)束。到5111011000010120211 14?????????? ?iidvv路徑為： 0110 ?0111?0101?1101 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 1101 特點 ： 尋徑按照從維 1到維 4的順序進行。 如果 s和 d的第 i位相同，則沿維 i的方向不需要尋徑，否則從當前結(jié)點沿著這一維方向走向下一結(jié)點（立方體中，每維包括兩個結(jié)點）。重復這一過程直到到達目的結(jié)點。 目的： 避免死鎖 虛擬通道 ：使實現(xiàn)自適應尋徑更經(jīng)濟和更靈活。 方法 ：網(wǎng)格網(wǎng)絡中，同一維的所有連接都使用虛擬通道。 如下圖所示： 02 12 22 01 11 21 00 10 20 （ a）沒有虛擬通道的原型網(wǎng)絡 02 12 22 01 11 21 00 10 20 （ b） Y維方向有兩對虛擬通道 02 12 22 01 11 21 00 10 20 （ c）向西方向傳遞消息 （ d）向東方向傳遞消息 02 12 22 01 11 21 00 10 20 單播模式（ Unicast）： 一個源結(jié)點 —— 一個目的結(jié)點。 選播模式（ Multicast）： 一個源結(jié)點 ——多個目的結(jié)點。（多播、組播） 廣播模式（ Broadcast）： 一個源結(jié)點 ——全體結(jié)點。 會議模式（ Conference）： 多個源結(jié)點 —— 多個目的結(jié)點。 通信流量（ Channel traffic）： 用傳輸有關消息所使用的通道數(shù)來表示。 通信時延（ Communication latency）： 用包的最長傳輸時間來表示。 在 Wormhole尋徑方式下，網(wǎng)絡流量這個參數(shù)比較重要。 在存儲轉(zhuǎn)發(fā)網(wǎng)絡中，時延是最重要的問題。 例 ： 網(wǎng)格連接計算機中的選播和廣播。 3?4網(wǎng)格上實現(xiàn)選播尋徑。 D2 D1 S （ a） 5次單播，流量等于 13，距離等于 4 D3 D4 D5 在一個中間結(jié)點上復制所傳送的包，然后把該包的多個拷貝送到目的結(jié)點，這樣可以減少通道流量。 D2 D1 S （ b）一種流量等于 7，距離等于 4的選播 D3 D4 D5 （ b） 中的選播方式對存儲轉(zhuǎn)發(fā)比較好， 而 （ c） 中的選播方式對 Wormhole尋徑較好。 D2 D1 S （ c）流量等于 6，距離等于 5的選播 D3 D4 D5 結(jié)點中的數(shù)字表示樹的層次號，該樹稱為廣播樹。 3 2 3 2 1 2 1 S 1 （ d）通過樹結(jié)構廣播所有結(jié)點 4 3 2 Message 由 UC Berkeley開發(fā)。 背景 ：互連網(wǎng)絡的硬件開銷已經(jīng)相當小了，通信和計算機不能相互重疊，消息發(fā)生和接收原語帶來過大的系統(tǒng)軟件開銷。 互連網(wǎng)絡接收源處理結(jié)點發(fā)來的消息包，并采用一定的尋徑算法和流控制技術將它送到目的處理結(jié)點。消息包到達后，用一個中斷信號去通知目的處理結(jié)點。此時目的處理結(jié)點會調(diào)用相應的中斷處理函數(shù)來處理到達的消息包。 —— 這是一個完全異步的過程。 傳統(tǒng)的通信機制之所以會有比較大的軟件開銷，其實質(zhì)上的原因就是過多的采用了與上述異步過程不相匹配的同步協(xié)議。 Active Message：消息發(fā)送方來指明消息處理函數(shù)的地址，當消息到達時，這一函數(shù)就自動的被調(diào)用。 —— 簡單得幾乎沒有任何協(xié)議的異步通信機制。 好處 ： 不需要任何緩沖 實現(xiàn)簡單 消息格式 ： 消息頭 源地址 指向消息處理函數(shù)的指針 參數(shù) 數(shù)據(jù) Active Message 的消息格式 高速網(wǎng)絡發(fā)展迅速： Ether： 10M?100M ?1G ATM： 155M ?622M ? Myri： 640M ? 峰值帶寬增長幅度大 通信協(xié)議基本不變
教學課件相關推薦
鄂ICP備17016276號-1