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 交叉開關(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)簡單，很方便實(shí)現(xiàn)廣播。 總線的缺點(diǎn)：帶寬低，發(fā)生沖突的可能性大。 總線沖突的解決辦法有： (1) 設(shè)置靜態(tài)優(yōu)先級 (2) 在同步方式中采用時(shí)間片 (3) 采用動(dòng)態(tài)優(yōu)先級（如LR

2、U法等） (4) 先來先服務(wù) 提高總線通信帶寬的方法有： (1) 采用多總線結(jié)構(gòu) (2) 層次總線結(jié)構(gòu) (3) 多維總線結(jié)構(gòu),4,總線結(jié)構(gòu)的多處理機(jī),5,多總線結(jié)構(gòu)：西門子公司的SMS系統(tǒng) （Stractured Multiprocessor System） 通過8條總線連接128個(gè)處理機(jī),6,層次總線結(jié)構(gòu)：卡內(nèi)基梅隆大學(xué)的Cm*多處理機(jī)系統(tǒng) 三級總線：群總線、Map總線、處理機(jī)總線 每群14臺(tái)處理機(jī),7,（補(bǔ)充）多端口存儲(chǔ)器,多個(gè)多端口存儲(chǔ)器與多個(gè)CPU和IOP連接。 多端口存儲(chǔ)器用于處理機(jī)個(gè)數(shù)不多的系統(tǒng)中。 把復(fù)雜的互連網(wǎng)絡(luò)移到了存儲(chǔ)器中。,8,7.3.2環(huán)形互聯(lián),既具有總線型互連的簡單性

3、，又可克服總線所固有的缺點(diǎn) 信息的傳送過程是發(fā)送進(jìn)程把信息放到環(huán)上，通過環(huán)形網(wǎng)絡(luò)不斷向下一臺(tái)處理機(jī)傳播，直到此信息回到發(fā)送者為止,9,7.3.3 交叉開關(guān)互連,交叉開關(guān)包含一組縱橫開關(guān)陣列，把橫向的m個(gè)處理機(jī)及i個(gè)I/O設(shè)備與縱向的n個(gè)存儲(chǔ)器模塊連接起來，如下圖所示。,10,7.4.3 STARAN交換網(wǎng)和移數(shù)網(wǎng),多級立方體網(wǎng)，應(yīng)用在巨型機(jī)STARAN中 有n=log2N級，每級N/2個(gè)開關(guān)，整個(gè)網(wǎng)絡(luò)開關(guān)數(shù)(N/2)log2N 采用22的2功能開關(guān) 開關(guān)級號：K0,K1, ,Kn-1 級間連接：C0恒等置換, C1-Cn-1子蝶式置換, Cn逆洗牌置換。 開關(guān)控制方式有2種：級控方式和組控方式

4、。 采用級控制可以構(gòu)成STARAN交換網(wǎng)。 采用部分級控制，可以構(gòu)成STARAN移數(shù)網(wǎng)。,11,多級立方體網(wǎng)絡(luò),12,3級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 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) ：

5、分成一組： 每組八元交換（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 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=(0

6、10),F=(011),F=(100),F=(101),F=(110),F=(111),15,3級STARAN移數(shù)網(wǎng)絡(luò)實(shí)現(xiàn)的入出端連接及執(zhí)行的移數(shù)函數(shù)功能,16,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,0 1 2 3 4 5 6 7,0 1 2 3 4 5

7、 6 7,恒等,移1模2,移1模4,移2模4,移1模8,移2模8,移4模8,17,題目：編號分別為0,1,2,F的16個(gè)處理器之間要求按下列配對通信：(B,1), (8,2), (7,D), (6,C), (E,4), (A,0), (9,3), (5,F)。試選擇互連網(wǎng)絡(luò)類型、控制方式，并畫出該互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和各級交換開關(guān)狀態(tài)圖。,分析：要求配對通訊的處理器號用二進(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

8、) (9,3)是(1001,0011) (5,F)是(0101,1111),18,0 1,2 3,4 5,6 7,8 9,A B,C D,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ù)功能，請寫出此時(shí)各處理器之間所實(shí)現(xiàn)之互連函數(shù)的一般式；畫出相應(yīng)多級網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，標(biāo)出各級交換開關(guān)的狀態(tài)。,20,7.3.5 Omega網(wǎng)絡(luò),采用全混洗函數(shù)和交換函數(shù)，又稱混洗交換網(wǎng)絡(luò)。 1

9、、N個(gè)輸入的Omega網(wǎng)絡(luò)有l(wèi)og2N級，每級有N/2個(gè)22的四功能交換開關(guān) 2、每級的拓?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,N=8的多級混洗交換網(wǎng)絡(luò),22,網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)： 采用22的4功能開關(guān)，4功能為直送、交叉、上播、下播。 網(wǎng)絡(luò)各級開關(guān)的級號從網(wǎng)絡(luò)輸入端到輸出端，依次為Kn-1，K1，K0，即按降序排列。 級間連接從網(wǎng)絡(luò)輸入端到輸出端依次為Cn-1，C1，C0，其中Cn-1-C1都是均勻洗牌置換函數(shù)，C0為恒等置換。因此網(wǎng)絡(luò)輸入端對輸出端互連函

10、數(shù)表達(dá)式為： =EEE=(E)n 其中E是開關(guān)級在開關(guān)控制方式下實(shí)現(xiàn)的交換置換函數(shù)，是級間連接模式實(shí)現(xiàn)的混洗函數(shù)。,23,多級混洗交換網(wǎng)絡(luò)尋徑算法（路由算法）,目的：根據(jù)給定的輸入/輸出對應(yīng)關(guān)系，確定各開關(guān)的狀態(tài)。 名稱：源-目的地址異或法 操作：將任一個(gè)輸入地址與它要到達(dá)的輸出地址作異或運(yùn)算，其結(jié)果的biti位控制數(shù)據(jù)到達(dá)的第i級開關(guān)，“0”表示“直連”，“1”表示“交換”。（例如給定傳輸101B011B）,C3,C2,C1,C0,24,題目：畫出0-7號共8個(gè)處理器的三級混洗交換網(wǎng)絡(luò)，在該圖上標(biāo)出實(shí)現(xiàn)將6號處理器數(shù)據(jù)播送給0-4號，同時(shí)將3號處理器數(shù)據(jù)播送給其余3個(gè)處理器時(shí)的各有關(guān)交換開關(guān)的控制狀態(tài)。,分析：,25,如果采用級控制，是STARAN交換網(wǎng)的逆網(wǎng) 如果采用部分級控制，是STARAN移數(shù)網(wǎng)的逆網(wǎng) 因此，Omega網(wǎng)的許多性質(zhì)與多級立方體網(wǎng)相反，如發(fā)生沖突的情況 Omega網(wǎng)屬于多級互連網(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)，有