《互連網(wǎng)絡(luò)》PPT課件.ppt

《《互連網(wǎng)絡(luò)》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《互連網(wǎng)絡(luò)》PPT課件.ppt（27頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1 第 7章 互連網(wǎng)絡(luò) 7.1 互連網(wǎng)絡(luò)的基本概念 互連函數(shù) 互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù) 互連網(wǎng)絡(luò)的種類 7.2 消息傳遞機(jī)制 消息尋徑方式 死鎖和虛擬通道 7.3 互連網(wǎng)絡(luò)實(shí)例 2 7.3 互連網(wǎng)絡(luò)實(shí)例 7.3.1 總線互連 7.3.2 環(huán)形互連 7.3.3 交叉開(kāi)關(guān)互連 （ 補(bǔ)充 ） 多端口存儲(chǔ)器 （ 補(bǔ)充 ） STARAN交換網(wǎng)和 STARAN移數(shù)網(wǎng) 7.3.5 Omega互連網(wǎng) 3 7.3.1 總線互連 總線的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單，很方便實(shí)現(xiàn)廣播。 總線的缺點(diǎn)：帶寬低，發(fā)生沖突的可能性大。 總線沖突的解決辦法有： (1) 設(shè)置靜態(tài)優(yōu)先級(jí) (2) 在同步方式中采用時(shí)間片 (3) 采用動(dòng)態(tài)優(yōu)

2、先級(jí)（如 LRU法等） (4) 先來(lái)先服務(wù) 提高總線通信帶寬的方法有： (1) 采用多總線結(jié)構(gòu) (2) 層次總線結(jié)構(gòu) (3) 多維總線結(jié)構(gòu) 4 總線結(jié)構(gòu)的多處理機(jī) 本地 存儲(chǔ)器 本地 存儲(chǔ)器 本地 存儲(chǔ)器 全局 存儲(chǔ)器 5 多總線結(jié)構(gòu)： 西門(mén)子公司的 SMS系統(tǒng) （ Stractured Multiprocessor System） 通過(guò) 8條總線連接 128個(gè)處理機(jī) 總線驅(qū)動(dòng)器 S M S 多總線結(jié)構(gòu) 主機(jī) P1 P2 P1 6 P1 7 P1 8 P 3 2 P1 13 P1 14 P1 28 6 層次總線結(jié)構(gòu)： 卡內(nèi)基梅隆大學(xué)的 Cm*多處理機(jī)系統(tǒng) 三級(jí)總線：群總線、 Map總線、處理機(jī)

3、總線 每群 14臺(tái)處理機(jī) 群間總線 卡內(nèi)基梅隆大學(xué)的 C m * 層次總線結(jié)構(gòu) Km Cm Cm Cm Km Cm Cm Km Cm Cm Cm P B M IO 7 （補(bǔ)充）多端口存儲(chǔ)器 多個(gè)多端口存儲(chǔ)器與多個(gè) CPU和 IOP連接。 多端口存儲(chǔ)器用于處理機(jī)個(gè)數(shù)不多的系統(tǒng)中。 把復(fù)雜的互連網(wǎng)絡(luò)移到了存儲(chǔ)器中。 P1 M1 M2 M3 M4 P2 I O P1 I O P2 8 7.3.2環(huán)形互聯(lián) 既具有總線型互連的簡(jiǎn)單性，又可克服總線所固有的缺點(diǎn) 信息的傳送過(guò)程是發(fā)送進(jìn)程把信息放到環(huán)上，通過(guò)環(huán)形網(wǎng)絡(luò) 不斷向下一臺(tái)處理機(jī)傳播，直到此信息回到發(fā)送者為止 9 7.3.3 交叉開(kāi)關(guān)互連 交叉開(kāi)關(guān)包含

4、一組縱橫開(kāi)關(guān)陣列，把橫向的 m個(gè)處理機(jī)及 i 個(gè) I/O設(shè)備與縱向的 n個(gè)存儲(chǔ)器模塊連接起來(lái)，如下圖所示。 10 7.4.3 STARAN交換網(wǎng)和移數(shù)網(wǎng) 多級(jí)立方體網(wǎng)，應(yīng)用在巨型機(jī) STARAN中 1) 有 n=log2N級(jí)，每級(jí) N/2個(gè)開(kāi)關(guān)，整個(gè)網(wǎng)絡(luò)開(kāi)關(guān)數(shù) (N/2)log2N 2) 采用 2 2的 2功能開(kāi)關(guān) 3) 開(kāi)關(guān) 級(jí)號(hào)： K0,K1, ,Kn-1 4) 級(jí)間連接： C0恒等置換 , C1-Cn-1子蝶式置換 , Cn逆洗牌置換。 5) 開(kāi)關(guān)控制方式有 2種：級(jí)控方式和組控方式。 采用級(jí)控制可以構(gòu)成 STARAN交換網(wǎng) 。 采用部分級(jí)控制，可以構(gòu)成 STARAN移數(shù)網(wǎng) 。 11 A

5、 B C D E F G H I J K L 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 C0 輸 入 端 輸 出 端 C1 C2 C3 K0 K1 K2 N=8的 STARAN網(wǎng)絡(luò) 多級(jí)立方體網(wǎng)絡(luò) 12 級(jí)控制信號(hào)（ f2f1f0） 000 001 010 011 100 101 110 111 入 端 號(hào) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 3 2 1 0 7 6 5 4 4 5 6 7 0 1 2 3 5 4 7 6 1 0 3 2 6 7 4 5 2 3 0 1 7 6 5

6、4 3 2 1 0 執(zhí)行的 交換函 數(shù)功能 恒等 4組 2元 4組 2元 + 2組 4元 2組 4元 1組 8元 + 2組 4元 4組 2元 + 2組 4元 + 1組 8元 4組 2元 + 1組 8元 1組 8元 i Cube0 Cube1 Cube0 + Cube1 Cube2 Cube0 + Cube2 Cube1 + Cube2 Cube0 +Cube1 +Cube0 3級(jí) STARAN交換網(wǎng)絡(luò)實(shí)現(xiàn)的入出端連接及執(zhí)行的交換函數(shù)功能 13 除 F=(000)實(shí)現(xiàn)恒等置換外，其他 7種實(shí)現(xiàn)分組交換置換，如 F=(101)實(shí)現(xiàn)的置換可表示為： 0 1 2 3 4 5 6 7 0 1 2 3 4

7、 5 6 7 1 0 3 2 5 4 7 6 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 2 3 0 1 6 7 4 5 5 4 7 6 1 0 3 2 入端排列： 分成 4組： 每組二元交換（ 4G2E)： 分成二組： 每組四元交換 （ 2G4E) ： 分成一組： 每組八元交換 （ 1G8E) ： 14 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3

8、4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 F=(000) F=(001) F=(010) F=(011) F=(100) F=(101) F=(110) F=(111) 15 3級(jí) STARAN移數(shù)網(wǎng)絡(luò)實(shí)現(xiàn)的入出端連接及執(zhí)行的移數(shù)函數(shù)功能 組 控 制 信 號(hào) 2級(jí) F23 F22 F21 K,L J I 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1級(jí) F12

9、 F11 F,H E,G 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0級(jí) F0 A,B, C,D 1 0 0 1 0 1 0 入 端 號(hào) 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 2 3 4 5 6 7 0 1 4 5 6 7 0 1 2 3 1 2 3 0 5 6 7 4 2 3 0 1 6 7 4 5 1 0 3 2 5 4 7 6 0 1 2 3 4 5 6 7 執(zhí)行的移數(shù) 功能 移 1 mod 8 移 2 mod 8 移 4 mod 8 移 1 mod 4 移 2 mod 4 移 1 mod 2 不移 恒等 16 0 1 2 3 4 5 6 7 0

10、1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 恒等 移 1模 2 移 1模 4 移 2模 4 移 1模 8 移 2模 8 移 4模 8 17 題目： 編號(hào)分別為 0,1,2, ,F的 16個(gè)處理器之間要求按下列配對(duì) 通信： (B,1)

11、, (8,2), (7,D), (6,C), (E,4), (A,0), (9,3), (5,F)。試選擇互連網(wǎng)絡(luò)類型、控制方式，并畫(huà)出該互連網(wǎng)絡(luò)的 拓?fù)浣Y(jié)構(gòu)和各級(jí)交換開(kāi)關(guān)狀態(tài)圖。 分析 ： 要求配對(duì)通訊的處理器號(hào)用二進(jìn)制表示如下： (B,1)是 (1011,0001) (8,2)是 (1000,0010) (7,D)是 (0111,1101) (6,C)是 (0110,1100) (E,4)是 (1110,0100) (A,0)是 (1010,0000) (9,3)是 (1001,0011) (5,F)是 (0101,1111) 18 0 1 2 3 4 5 6 7 8 9 A B C D

12、E F 0 1 2 3 4 5 6 7 8 9 A B C D E F Cube0 Cube1 Cube2 Cube3 直連 直連 交換 交換 入端 出端 19 題目： 并行處理機(jī)有 16個(gè)處理器，要實(shí)現(xiàn)相當(dāng)于先 4組 4元交換， 然后是兩組 8元交換，再次是一組 16元交換的交換函數(shù)功能，請(qǐng) 寫(xiě)出此時(shí)各處理器之間所實(shí)現(xiàn)之互連函數(shù)的一般式；畫(huà)出相應(yīng)多 級(jí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，標(biāo)出各級(jí)交換開(kāi)關(guān)的狀態(tài)。 分析 ： 輸入端號(hào)為 |0 1 2 3|4 5 6 7|8 9 A B|C D E F| 經(jīng) 4組 4元交換后為 |3 2 1 0|7 6 5 4|B A 9 8|F E D C| 分成 2組后為 |3

13、 2 1 0 7 6 5 4|B A 9 8 F E D C| 然后經(jīng) 2組 8元交換后為 |4 5 6 7 0 1 2 3|C D E F 8 9 A B| 再經(jīng) 1組 16元變換后為 |B A 9 8 F E D C 3 2 1 0 7 6 5 4| 最后，可得出配對(duì)互連的是 (0,B), (1,A), (2,9), (3,8), (4,F), (5,E), (6,D), (7,C) 用二進(jìn)制表示就是 Cube(P3P2P1P0)= P3P2P1P0 20 7.3.5 Omega網(wǎng)絡(luò) 采用 全混洗函數(shù) 和 交換函數(shù) ，又稱混洗交換網(wǎng)絡(luò)。 1、 N個(gè)輸入的 Omega網(wǎng)絡(luò)有 log2N級(jí)，每

14、級(jí)有 N/2個(gè) 2 2的四功 能交換開(kāi)關(guān) 2、每級(jí)的拓?fù)浣Y(jié)構(gòu)相同 3、采用單元控制 4、能夠?qū)崿F(xiàn)任意一個(gè)輸入端到任意一個(gè)輸出端的連接。但不 能同時(shí)實(shí)現(xiàn)多個(gè)輸入端到多個(gè)輸出端的連接。 5、能夠?qū)崿F(xiàn)從任意一個(gè)輸入端到所有輸出端的廣播。 21 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 k= 2 k= 1 k = 0 A B C D E F G H I J K L N=8的多級(jí)混洗交換網(wǎng)絡(luò) 22 網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)： 1) 采用 2 2的 4功能開(kāi)關(guān)， 4功能為直送、交叉、上播、下播。 2) 網(wǎng)絡(luò) 各級(jí)開(kāi)關(guān)的級(jí)號(hào)從網(wǎng)絡(luò)輸入端到輸出端，依次為 Kn-1 ， ， K1， K0，即按降序排列

15、。 3) 級(jí)間連接從網(wǎng)絡(luò)輸入端到輸出端依次為 Cn-1， ， C1， C0， 其中 Cn-1-C1都是均勻洗牌置換函數(shù)， C0為恒等置換。因此 網(wǎng)絡(luò)輸入端對(duì)輸出端互連函數(shù)表達(dá)式為： = E E E=( E)n 其中 E是開(kāi)關(guān)級(jí)在開(kāi)關(guān)控制方式下實(shí)現(xiàn)的交換置換函數(shù)， 是 級(jí)間連接模式實(shí)現(xiàn)的混洗函數(shù)。 23 多級(jí)混洗 交換網(wǎng)絡(luò)尋徑算法（路由算法） 目的：根據(jù)給定的輸入 /輸出對(duì)應(yīng)關(guān)系 ， 確定各開(kāi)關(guān)的狀態(tài) 。 名稱：源 -目的地址異或法 操作：將任一個(gè)輸入地址與它要到達(dá)的輸出地址作異或運(yùn)算 ， 其結(jié)果的 biti位控制數(shù)據(jù)到達(dá)的第 i級(jí)開(kāi)關(guān) ， “ 0”表示 “ 直連 ” ， “ 1”表示 “ 交換

16、 ” 。 （ 例如給定傳輸 101B 011B） C3 C2 C1 C0 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 k= 2 k= 1 k = 0 A B C D E F G H I J K L 24 題目： 畫(huà)出 0-7號(hào)共 8個(gè)處理器的三級(jí)混洗交換網(wǎng)絡(luò)，在該圖上標(biāo) 出實(shí)現(xiàn)將 6號(hào)處理器數(shù)據(jù)播送給 0-4號(hào)，同時(shí)將 3號(hào)處理器數(shù)據(jù)播 送給其余 3個(gè)處理器時(shí)的各有關(guān)交換開(kāi)關(guān)的控制狀態(tài)。 分析 ： 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 k= 2 k= 1 k = 0 A B C D E F G H I J K L 25 如果采用級(jí)控制，是 STAR

17、AN交換網(wǎng)的逆網(wǎng) 如果采用部分級(jí)控制，是 STARAN移數(shù)網(wǎng)的逆網(wǎng) 因此， Omega網(wǎng)的許多性質(zhì)與多級(jí)立方體網(wǎng)相反，如發(fā)生沖突 的情況 Omega網(wǎng)屬于多級(jí)互連網(wǎng) 當(dāng)有 N個(gè)輸入端時(shí)，共有 N(N/2)個(gè)變換 要同時(shí)實(shí)現(xiàn)任意一個(gè)輸入端到任意一個(gè)輸出端的連接，共需 N! 個(gè)變換 8個(gè)輸入端的 Omega網(wǎng)絡(luò)實(shí)際上只能實(shí)現(xiàn)全部變換的 10%(84/8! = 4096/40320=0.1016)，有 90%的變換將引起 阻塞 Omega網(wǎng)絡(luò)是一種阻塞網(wǎng)絡(luò)，采用多次通過(guò)來(lái)解決沖突 有 N個(gè)輸入端時(shí)，實(shí)現(xiàn)連接的通過(guò)次數(shù)最多為 log2N 26 N=8的多級(jí)立方體網(wǎng)絡(luò)和 Omega網(wǎng)絡(luò)的關(guān)系 27 本章重點(diǎn)： 1. 主要的互連函數(shù) 2. 幾種典型互連網(wǎng)絡(luò)的構(gòu)成方法及特點(diǎn) 3. 尋徑方式的原理及優(yōu)缺點(diǎn) 練習(xí)題 : 4， 5， 13 （ P446-447）