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