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