[文學(xué)研究]高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)-在線瀏覽
2024-12-01 13:58本頁(yè)面
【正文】 一個(gè) N排列變成另一個(gè) N排列的變換叫做 N階置換。 一些常見(jiàn)的置換方式可以用下面的函數(shù)表示： 1. 恒等函數(shù) )()( 021021 XXXXXXXXf knnknne ???? ???? ?其中， Xn1 Xn2?Xk ? X0是 PE的地址（通常為二進(jìn)制）。 比如， n為 3時(shí)， 3立方體各結(jié)點(diǎn)地址如下： Y Z X 010 011 110 000 111 001 100 101 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 Cube0: )()( 0120210 XXXXXXc u b e ?0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 Cube1: )()( 0120211 XXXXXXc u b e ?0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 Cube2: )()( 0120212 XXXXXXc u b e ?0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 3. 洗牌函數(shù) 0 1 2 3 4 5 6 7 )()( 102021 ???? ? nknknn XXXXXXXXSh ????洗牌函數(shù)的變形： a. 均勻洗牌（ ShuffleExchange) 是 洗牌函數(shù) 與 Cube0函數(shù)的組合。 c. 第 k個(gè)超洗牌 )()( 01120211 XXXXXXXXXXSh knnknnknknnnk ???? ?????????? ?即最高 k1位循環(huán)左移一位。 6個(gè) PM2I函數(shù)如下： PM2+0: ( 0 1 2 3 4 5 6 7） 0 1 2 3 4 5 6 7 PM20: ( 7 6 5 4 3 2 1 0） 0 1 2 3 4 5 6 7 PM2+1: ( 0 2 4 6）（ 1 3 5 7） 0 1 2 3 4 5 6 7 PM21: ( 6 4 2 0）（ 7 5 3 1） 0 1 2 3 4 5 6 7 PM2?2: ( 0 4）（ 1 5）（ 2 6）（ 3 7） 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 例 2： 8 9 10 11 12 13 14 15 上面的網(wǎng)絡(luò)可以用四個(gè) PM2I函數(shù)表示。常見(jiàn)的有 2 ? 4 ? 8 ? 8等。如下圖所示： 0 1 0 1 直送 0 1 0 1 交叉 0 1 0 1 上播 0 1 0 1 下播 （ 2）級(jí)間互連模式（ InterStage Connection）： 均勻洗牌 、 蝶式 、 多路洗牌 （比如四路洗牌即是把牌平均分成 4份，然后 4堆分別進(jìn)行均勻洗牌）、 縱橫開(kāi)關(guān) （ Cross Switch)及 立方體連結(jié) 等。當(dāng)目的地址編碼從高位開(kāi)始的第 i位（從 0開(kāi)始）為 0時(shí)，第 i級(jí)的 2?2開(kāi)關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接。 Ω網(wǎng)是阻塞網(wǎng)絡(luò)：出現(xiàn)沖突時(shí)，可以采用幾次通過(guò)的方法來(lái)解決沖突。 3. 蝶式網(wǎng)絡(luò)（ Butterfly switch work） 蝶式網(wǎng)絡(luò)的開(kāi)關(guān)不允許廣播功能，它實(shí)際上是 Omega網(wǎng)的一個(gè)子集。 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ù)和同步消息的信息包。 包（ Packet） ：包的長(zhǎng)度隨協(xié)議不同而不同，它是信息傳送的最小單位， 64512位。 它們的相互關(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)之間傳遞消息。 一個(gè)網(wǎng)絡(luò)的傳輸時(shí)延 ：在一定條件下發(fā)送消息的平均時(shí)延。 bns TTTT ??? 其中， Ts稱(chēng)為 建立時(shí)延 ， Tn稱(chēng)為 網(wǎng)絡(luò)時(shí)延 ， Tb稱(chēng)為 阻塞時(shí)延 。它和機(jī)器本身的硬件、軟件技術(shù)有關(guān)。 Tsd稱(chēng)為 目的結(jié)點(diǎn)時(shí)延 ：從消息的尾部到達(dá)目的結(jié)點(diǎn)到消息完全被接收進(jìn)程接收所經(jīng)歷的時(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)之間的距離。 阻塞時(shí)延 Tb：消息傳遞過(guò)程中其他所有可能的時(shí)延（主要原因是資源沖突）。 可以分為： 最短路徑算法 非最短路徑算法 或者： 確定性算法 ：路徑的選擇只依賴(lài)于它所發(fā)送的消息的源結(jié)點(diǎn)和目的結(jié)點(diǎn)。 當(dāng)一個(gè)消息在網(wǎng)絡(luò)中沿著某條路徑傳送時(shí)，互連網(wǎng)絡(luò)如何來(lái)為它分配通道和緩沖器。 缺點(diǎn) ： 每個(gè)結(jié)點(diǎn)必須對(duì)整個(gè)消息進(jìn)行緩沖，緩沖器較大。 BLDLBLDBLBLDTT hhpn /)(/)/(/ ????????? 其中， Lh為消息頭部開(kāi)始到其目的信息域的長(zhǎng)度，顯然有 L Lh，所以 D的影響比較小。 在傳遞一個(gè)消息之前，就為它建立一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通道。 BLDLBLDBLBLDTT ccpn /)(/)/(/ ????????? 其中， Lc是為消息建立物理通路所傳遞的控制信息的長(zhǎng)度。 缺點(diǎn) ： 物理通道非共享 傳輸過(guò)程中物理通道一直被占用 Dally于 1986年提出。 尾片 是一個(gè)其最后包含了消息結(jié)束符的片。 片是最小信息單位。 用一個(gè)頭片直接開(kāi)辟一條從輸入鏈路到
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1