[文學(xué)研究]高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(編輯修改稿)
2024-11-10 13:58 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ter 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級(jí) 第 1級(jí) 第 2級(jí) 無(wú)阻塞的實(shí)現(xiàn)置換 π1=（ 0 7 6 4 2）（ 1 3）（ 5） 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級(jí) 第 1級(jí) 第 2級(jí) 置換 π2=（ 0 6 4 7 3）（ 1 5）（ 2） 在開(kāi)關(guān) F、 G、 H、 I和 J上發(fā)生阻塞 F G H J I Ω網(wǎng)的特點(diǎn) (2)： 并不是所有的置換在 Ω網(wǎng)中一次通過(guò)便可以實(shí)現(xiàn)。 Ω網(wǎng)是阻塞網(wǎng)絡(luò)：出現(xiàn)沖突時(shí)，可以采用幾次通過(guò)的方法來(lái)解決沖突。 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級(jí) 第 1級(jí) 第 2級(jí) Ω網(wǎng)的廣播功能： 001?8個(gè)輸出端 0 1 第 1級(jí) 4?4開(kāi)關(guān)構(gòu)成的 Ω網(wǎng)：多路洗牌 如 16輸入 4路洗牌：網(wǎng)路級(jí)數(shù)為 log416 = 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 第 0級(jí) Ω網(wǎng)的特點(diǎn) (3)： 當(dāng)采用 k?k開(kāi)關(guān)元件時(shí)，則可以定義 k路洗牌函數(shù)來(lái)構(gòu)造更大的級(jí)數(shù)為 logkn的 Ω網(wǎng)絡(luò)。 3. 蝶式網(wǎng)絡(luò)（ Butterfly switch work） 蝶式網(wǎng)絡(luò)的開(kāi)關(guān)不允許廣播功能，它實(shí)際上是 Omega網(wǎng)的一個(gè)子集。 兩級(jí) 64 ? 64的蝶式網(wǎng)絡(luò)如下圖所示：它采用 16個(gè) 8 ? 8交叉開(kāi)關(guān)構(gòu)成，兩級(jí)間采用8路洗牌連接。 8?8 8?8 8?8 0 . . . 7 8?8 8?8 8?8 第 1級(jí) 第 0級(jí) 8 . . . 15 56 . . . 63 . . . . . . . . . 0 7 8 15 56 63 . . . . . . . . . . . . . . . . . . . . . . . . 兩級(jí) 64 ? 64的蝶式網(wǎng)絡(luò) 總線 交叉開(kāi)關(guān) 第三章 互連與通信 互連網(wǎng)絡(luò)的作用 靜態(tài)網(wǎng)絡(luò) 動(dòng)態(tài)網(wǎng)絡(luò) 通信問(wèn)題 基本術(shù)語(yǔ)與性能指標(biāo) 尋徑算法 虛擬通道與死鎖 包沖突的解決 維序?qū)? 通信模式 通信問(wèn)題 、包和片 消息（ Message） ：是在多計(jì)算機(jī)系統(tǒng)的處理結(jié)點(diǎn)之間傳遞包含數(shù)據(jù)和同步消息的信息包。它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成。 包（ Packet） ：包的長(zhǎng)度隨協(xié)議不同而不同，它是信息傳送的最小單位， 64512位。 片（ Flit） ：片的長(zhǎng)度固定，一般為 8位。 它們的相互關(guān)系如下圖： 包 …… 消息 包 片 據(jù) 片 頭片 尾片 …… 順序號(hào) 數(shù) b b b b b b b b 互連網(wǎng)絡(luò)用來(lái)在多計(jì)算機(jī)系統(tǒng)的處理結(jié)點(diǎn)之間傳遞消息?；ミB網(wǎng)絡(luò)的描述： 拓?fù)洌?Topology） 尋徑算法（ Routing） 流控制（ Flow Control） 互連網(wǎng)絡(luò)性能的兩個(gè)重要指標(biāo)： 傳輸時(shí)延（ Transmission Latency） 吞吐量（ Throughput） 一個(gè)消息的傳輸時(shí)延 ：從它在源結(jié)點(diǎn)進(jìn)行發(fā)送初始化到它在目的結(jié)點(diǎn)完整的被接收所耗費(fèi)的時(shí)間。 一個(gè)網(wǎng)絡(luò)的傳輸時(shí)延 ：在一定條件下發(fā)送消息的平均時(shí)延。 網(wǎng)絡(luò)的吞吐量 ：?jiǎn)挝粫r(shí)間內(nèi)網(wǎng)絡(luò)所能傳輸?shù)南?shù)目或長(zhǎng)度。 bns TTTT ??? 其中， Ts稱(chēng)為 建立時(shí)延 ， Tn稱(chēng)為 網(wǎng)絡(luò)時(shí)延 ， Tb稱(chēng)為 阻塞時(shí)延 。 它們具體定義如下： 建立時(shí)延 Ts：一個(gè)消息在源結(jié)點(diǎn)和目的結(jié)點(diǎn)上裝配和分解、從存儲(chǔ)器拷貝到通信緩沖區(qū)以及正確性驗(yàn)證等所耗費(fèi)的時(shí)間。它和機(jī)器本身的硬件、軟件技術(shù)有關(guān)。 sdsss TTT ?? 其中： Tss稱(chēng)為 源結(jié)點(diǎn)時(shí)延 ：從發(fā)送進(jìn)程開(kāi)始消息發(fā)送初始化到消息的頭部進(jìn)入網(wǎng)絡(luò)所經(jīng)歷的時(shí)間。 Tsd稱(chēng)為 目的結(jié)點(diǎn)時(shí)延 ：從消息的尾部到達(dá)目的結(jié)點(diǎn)到消息完全被接收進(jìn)程接收所經(jīng)歷的時(shí)間。 網(wǎng)絡(luò)時(shí)延 Tn：消息頭部從源結(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)到消息的尾部到達(dá)目的結(jié)點(diǎn)的時(shí)間間隔。 BLDTT pn /??? 其中： Tp?D稱(chēng)為 結(jié)點(diǎn)時(shí)延 ：其中 Tp是消息在它所經(jīng)過(guò)的路徑上的每個(gè)中間結(jié)點(diǎn)上的平均時(shí)延， D為中間結(jié)點(diǎn)或源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間的距離。 L/B稱(chēng)為 線路時(shí)延 ：其中 L為消息長(zhǎng)度， B為結(jié)點(diǎn)之間的通道帶寬。 阻塞時(shí)延 Tb：消息傳遞過(guò)程中其他所有可能的時(shí)延（主要原因是資源沖突）。 第一代并行計(jì)算機(jī) ： HyperCube 第二代并行計(jì)算機(jī) ： n— Mesh 決定發(fā)送一個(gè)消息到其目的地所經(jīng)過(guò)的路徑。 可以分為： 最短路徑算法 非最短路徑算法 或者： 確定性算法 ：路徑的選擇只依賴(lài)于它所發(fā)送的消息的源結(jié)點(diǎn)和目的結(jié)點(diǎn)。 可適應(yīng)算法 ：消息從結(jié)點(diǎn) A到結(jié)點(diǎn) B可以由幾條不同的路徑。 當(dāng)一個(gè)消息在網(wǎng)絡(luò)中沿著某條路徑傳送時(shí)，互連網(wǎng)絡(luò)如何來(lái)為它分配通道和緩沖器。 我們介紹四種尋徑方式： 存儲(chǔ)轉(zhuǎn)發(fā)（ StoreandForward） 虛擬直通（ Virtual cut through） 線路交換（ Circuit Switching） Wormhole交換（ Wormhole Switching) 當(dāng)一個(gè)消息到達(dá)中間結(jié)點(diǎn) A時(shí)， A把整個(gè)消息放入其通信緩沖器中，然后在尋徑算法的控制下選擇下一個(gè)相鄰結(jié)點(diǎn) B，當(dāng)從 A到 B的通道空閑并且 B的通信緩沖器可用時(shí)，把消息從A發(fā)向 B。 缺點(diǎn) ： 每個(gè)結(jié)點(diǎn)必須對(duì)整個(gè)消息進(jìn)行緩沖，緩沖器較大。 網(wǎng)絡(luò)時(shí)延與發(fā)送消息所經(jīng)歷的結(jié)點(diǎn)數(shù)成正比 )1()/(/)/(/ ????????? DBLBLDBLBLDTT pn 中間結(jié)點(diǎn)沒(méi)有必要等到整個(gè)消息全部被緩沖后再作出路由選擇，只要消息的目的信息域可用后，就可以作出路由選擇。 BLDLBLDBLBLDTT hhpn /)(/)/(/ ????????? 其中， Lh為消息頭部開(kāi)始到其目的信息域的長(zhǎng)度，顯然有 L Lh，所以 D的影響比較小。 而當(dāng)通向下一結(jié)點(diǎn)的通道忙或結(jié)點(diǎn)的緩沖器非空閑時(shí)，必須把整個(gè)消息緩沖起來(lái)，這時(shí)和存儲(chǔ)轉(zhuǎn)發(fā)一樣。 在傳遞一個(gè)消息之前，就為它建立一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1