[文學(xué)研究]高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)-wenkub
2022-10-29 13:58:40 本頁面
【正文】 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ù)的組合。 置換： 把一個(gè) N排列變成另一個(gè) N排列的變換叫做 N階置換。 傳統(tǒng)的環(huán)網(wǎng)等價(jià)于 4元 2立方體。 例子： Intel的 iPSC/ iPSC/ nCUBE 一個(gè)帶環(huán) n立方體由 N = 2n個(gè)結(jié)點(diǎn)環(huán)構(gòu)成，每個(gè)結(jié)點(diǎn)環(huán)是一個(gè)有 n個(gè)結(jié)點(diǎn)的環(huán)，所以結(jié)點(diǎn)總數(shù)為 n 2n個(gè)。 Nr ? b. 環(huán)形網(wǎng)（ 2D— Torus） 有 N個(gè)結(jié)點(diǎn)的 r?r網(wǎng)（其中 )，有2N 條鏈路，直徑為 2?r/2?， 結(jié)點(diǎn)度為 4，對稱。 星形實(shí)際上是一種二層樹（如右圖）。 4層的二叉樹 一棵 K層完全二叉樹應(yīng)有 N = 2K 1個(gè)結(jié)點(diǎn)，大多數(shù)結(jié)點(diǎn)的結(jié)點(diǎn)度為 3，直徑為 2（ K 1）（即右邊任意一個(gè)葉子結(jié)點(diǎn)到左邊任意一個(gè)葉子結(jié)點(diǎn)）。 結(jié)點(diǎn)度為 4：鏈路數(shù)為 24，直徑 3（比如紅色結(jié)點(diǎn)），度為 4，對稱，等分寬度為 8。 對 N個(gè)結(jié)點(diǎn)的環(huán)，考慮相鄰結(jié)點(diǎn)數(shù)據(jù)傳送方向： 雙向環(huán) ：鏈路數(shù)為 N，直徑 ?N/2?，度為 2，對稱，等分寬度為 2。 典型的靜態(tài)網(wǎng)絡(luò) 對 N個(gè)結(jié)點(diǎn)的線性陣列，有 N1條鏈路，直徑為 N1（任意兩點(diǎn)之間距離的最大值），度為 2，不對稱，等分寬度為 1。 結(jié)點(diǎn)間的線長 ：兩個(gè)結(jié)點(diǎn)間的線的長度。 距離 ：與兩個(gè)結(jié)點(diǎn)之間相連的最少邊數(shù)。 操作方式： 同步通信（ Synchronous Communication) 異步通信 (Asynchronous Communication) 控制策略： 集中控制 (Centralized control) 分布控制 (Distributed control) ?交換方式： 電路交換 (Circuit switching) 分組交換 (Packet switching) Wormhole交換 (Wormhole switching) 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)： 靜態(tài)網(wǎng)絡(luò) (Static work) 動(dòng)態(tài)網(wǎng)絡(luò) (Dynamic work) 第三章 互連與通信 互連網(wǎng)絡(luò)的作用 靜態(tài)網(wǎng)絡(luò) 靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo) 典型的靜態(tài)網(wǎng)絡(luò) 動(dòng)態(tài)網(wǎng)絡(luò) 通信問題 靜態(tài)網(wǎng)絡(luò) 靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo) 靜態(tài)網(wǎng)絡(luò) 由點(diǎn) — 點(diǎn)直接相連而成，這種連結(jié)方式在程序執(zhí)行過程中不會(huì)改變 。 如果用圖來表示，結(jié)點(diǎn)代表開關(guān)，邊代表通信鏈路，則 (1) 結(jié)點(diǎn)間的鏈路無源，不能重構(gòu) (2) 開關(guān)元件與處理機(jī)相連 (3) 不直接相連結(jié)點(diǎn)間的通信需通過中間結(jié)點(diǎn)中轉(zhuǎn)。 網(wǎng)絡(luò)直徑 ：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間距離的最大值。 對稱性 ：從任何結(jié)點(diǎn)看，拓?fù)浣Y(jié)構(gòu)都一樣，這種網(wǎng)絡(luò)實(shí)現(xiàn)和編程都很容易。 N很大時(shí)，通信效率很低。比如 KSR1（ 1990）。 度為3的帶弦環(huán) 度為4的帶弦環(huán) 全鏈接是帶弦環(huán)的一種特殊情形。不對稱，等分度為 1。有 N個(gè)結(jié)點(diǎn)的星形網(wǎng)絡(luò)，有 N 1條鏈路，直徑為 2，最大結(jié)點(diǎn)度為 N 1，非對稱，等分寬度為 1。 c. 搏動(dòng)式陣列（ Systolic Array） 0立方體 1立方體 2立方體 3立方體 4立方體 一個(gè) n立方體由 N = 2n個(gè)結(jié)點(diǎn)構(gòu)成，它們分布在 n維上，每維有兩個(gè)結(jié)點(diǎn)。直徑通常為 2n，結(jié)點(diǎn)度為 3，對稱。 第三章 互連與通信 互連網(wǎng)絡(luò)的作用 靜態(tài)網(wǎng)絡(luò) 動(dòng)態(tài)網(wǎng)絡(luò) 互連函數(shù) 多級(jí)互聯(lián)網(wǎng)絡(luò) 通信問題 動(dòng)態(tài)網(wǎng)絡(luò) 特點(diǎn)： 網(wǎng)絡(luò)的開關(guān)元件有源，鏈路可通過設(shè)置這些開關(guān)的狀態(tài)來重構(gòu)。 在有 N個(gè)輸入端和 N個(gè)輸出端的網(wǎng)絡(luò)中，輸入端和輸出端的連接關(guān)系可以用置換來表示（輸入端與輸出端一一對應(yīng)）。 0 1 2 3 4 5 6 7 ： Cube0 ：洗牌 b. 第 k個(gè)子洗牌 )()( 01110111 kkknkkknk XXXXXXXXXXSh ???? ?????? ?即最低 k位循環(huán)左移一位。 PM2+0: ( 0 1 2 … 15 ) PM20: ( 15 14 13 … 0 ) PM2?2: ( 0 4）（ 1 5）（ 2 6）（ 3 7） ( 4 8）（ 5 9）（ 6 10）（ 7 11） ( 8 12）（ 9 13）（ 10 14）（ 11 15） ( 12 0）（ 13 1）（ 14 2）（ 15 3） 多級(jí)互連網(wǎng)絡(luò) 1. 多級(jí)網(wǎng)絡(luò)的三要素 （ 1）開關(guān)單元： a個(gè)輸入 a個(gè)輸出的開關(guān)單元記做 a?a的開關(guān)單元，其中， a是 2的整數(shù)倍 。 （ 3）控制方式 級(jí)控制： 每級(jí)只有一個(gè)控制信號(hào) 單元控制： 每個(gè)開關(guān)一個(gè)控制信號(hào) 部分級(jí)控制： 幾個(gè)開關(guān)合用一個(gè)控制信號(hào) 2. Ω網(wǎng) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級(jí) 第 1級(jí) 第 2級(jí) Ω網(wǎng)的特點(diǎn)： 開關(guān)單元 ： 2?2四功能開關(guān) ISC： 洗牌變換 +恒等變換 控制方式 ：采用單元控制方式。 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開關(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開關(guān)元件時(shí)，則可以定義 k路洗牌函數(shù)來構(gòu)造更大的級(jí)數(shù)為 logkn的 Ω網(wǎng)絡(luò)。它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成。互連網(wǎng)絡(luò)的描述： 拓?fù)洌?Topology） 尋徑算法（ Routing） 流控制（ Flow Control） 互連網(wǎng)絡(luò)性能的兩個(gè)重要指標(biāo)： 傳輸時(shí)延（ Transmission Latency） 吞吐量（ Throu
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1