第9章互連網(wǎng)絡(luò)

1、1 1/114/114第9章 互連網(wǎng)絡(luò)2 2/114/1149.1互連函數(shù)9.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)9.3靜態(tài)互連網(wǎng)絡(luò)9.4動(dòng)態(tài)互連網(wǎng)絡(luò)9.5消息傳遞機(jī)制3 3/114/114 互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)中結(jié)點(diǎn)之間的相互連接。結(jié)點(diǎn)：處理器、存儲(chǔ)模塊或其它設(shè)備。在拓?fù)渖?，互連網(wǎng)絡(luò)為輸入結(jié)點(diǎn)到輸出結(jié)點(diǎn)之間的一組互連或映象。 SIMD計(jì)算機(jī)和MIMD計(jì)算機(jī)的關(guān)鍵組成部分。 3大要素：互連結(jié)構(gòu)，開關(guān)元件，控制方式。 4 4/114/114 變量x：輸入（設(shè)x=0，1，N1） 函數(shù)f(x)：輸出 通過數(shù)學(xué)表達(dá)式建立輸入端號與輸出端號的連接關(guān)

2、系。即在互連函數(shù)f的作用下，輸入端x連接到輸出端f(x)。互連函數(shù)反映了網(wǎng)絡(luò)輸入數(shù)組和輸出數(shù)組之間對應(yīng)的置換關(guān)系或排列關(guān)系。（有時(shí)也稱為（有時(shí)也稱為置換函數(shù)置換函數(shù)或或排列函數(shù)排列函數(shù)） 9.1.1 互連函數(shù)9.1 互連函數(shù)5 5/114/1149.1 互連函數(shù)互連函數(shù)f(x)有時(shí)可以采用循環(huán)表示 即：（x0 x1 x2 xj-1） 表示： f(x0)=x1，f(x1)=x2，f(xj-1)=x0 j稱為該循環(huán)的長度。設(shè)n=log2N，則可以用n位二進(jìn)制來表示N個(gè)輸入端和輸出端的二進(jìn)制地址，互連函數(shù)表示為： f（xn-1xn-2x1x0）6 6/114/1149.1 互連函數(shù)介紹幾種常用的基本

3、互連函數(shù)及其主要特征。1. 恒等函數(shù) 恒等函數(shù)：實(shí)現(xiàn)同號輸入端和輸出端之間的連接。 I（xn-1xn-2x1x0）=xn-1xn-2x1x0 2. 交換函數(shù) 交換函數(shù)：實(shí)現(xiàn)二進(jìn)制地址編碼中第k位互反的輸入端與輸出端之間的連接。9.1.2 幾種基本的互連函數(shù)011121011121xxxxxxxxxxxxxxEkkknnkkknn7 7/114/1149.1 互連函數(shù)主要用于構(gòu)造立方體互連網(wǎng)絡(luò)和各種超立方體互連網(wǎng)絡(luò)。它共有nlog2N種互連函數(shù)。 （N N為結(jié)點(diǎn)個(gè)數(shù)）為結(jié)點(diǎn)個(gè)數(shù)）當(dāng)N8時(shí)，n3，可得到常用的立方體互連函數(shù)： 012012201201210120120 xxxxxxCubexxxx

4、xxCubexxxxxxCube8 8/114/1149.1 互連函數(shù)q變換圖形變換圖形 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) Cube0交換函數(shù)交換函數(shù) 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 (b) Cube1交換函數(shù)交換函數(shù) (c) Cube2交換函數(shù)交換函數(shù) N=8 N=8 的立方體交換函數(shù)的立方體交換函數(shù) 9 9/114/1149.1 互連函數(shù)立方體網(wǎng)絡(luò)立方體網(wǎng)絡(luò) 000 010 001 011 101 111 100 110 1010/114/1149.1 互連

5、函數(shù)3. 均勻洗牌函數(shù)均勻洗牌函數(shù)：將輸入端分成數(shù)目相等的兩半，前一半和后一半按類似均勻混洗撲克牌的方式交叉地連接到輸出端（輸出端相當(dāng)于混洗的結(jié)果）。 q也稱為也稱為混洗函數(shù)（置換）混洗函數(shù)（置換） q函數(shù)關(guān)系函數(shù)關(guān)系 即把輸入端的二進(jìn)制編號循環(huán)左移一位。即把輸入端的二進(jìn)制編號循環(huán)左移一位。101320121nnnnnxxxxxxxxx1111/114/1149.1 互連函數(shù)互連函數(shù)（設(shè)為s）的第k個(gè)子函數(shù)：把s作用于輸入端的二進(jìn)制編號的低k位?；ミB函數(shù)（設(shè)為s）的第k個(gè)超函數(shù)：把s作用于輸入端的二進(jìn)制編號的高k位。例如：例如：對于均勻洗牌函數(shù)對于均勻洗牌函數(shù)第第k k個(gè)子函數(shù)個(gè)子函數(shù)：(k)

6、(k)( x( xn-1n-1 x xk kx xk-1k-1x xk-2k-2 x x0 0) )x xn-1n-1xxk kx xk-2k-2xx0 0 x xk-1k-1 即把輸入端的二進(jìn)制編號中的低即把輸入端的二進(jìn)制編號中的低k k位循環(huán)左移一位。位循環(huán)左移一位。第第k個(gè)超函數(shù)個(gè)超函數(shù)：(k)( xn-1xn-2 xn-kxn-k-1 x1x0)xn-2xn-k xn-1xn-k-1x1x0 即把輸入端的二進(jìn)制編號中的高即把輸入端的二進(jìn)制編號中的高k位循環(huán)左移一位。位循環(huán)左移一位。1212/114/1149.1 互連函數(shù) 下列等式成立：下列等式成立： (n)(X)(n)(X) (X)

7、(1)(X)(1)(X) X對于任意一種函數(shù)f(x)，如果存在g(x)，使得 f(x)g(x)=I(x) 則稱g(x)是f(x)的逆函數(shù)，記為f-1(x)。 f-1(x)= g(x) 逆均勻洗牌函數(shù)：將輸入端的二進(jìn)制編號循環(huán)右移一位而得到所連接的輸出端編號。1313/114/1149.1 互連函數(shù)q互連函數(shù)互連函數(shù)p逆均勻洗牌是均勻洗牌的逆函數(shù)逆均勻洗牌是均勻洗牌的逆函數(shù) 當(dāng)N=8時(shí)，有： (x2x1x0)x1x0 x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0 -1(x2x1x0)x0 x2x1121001211xxxxxxxxnnnn1414/114/114

8、9.1 互連函數(shù)qN=8N=8 的均勻洗牌和逆均勻洗牌函數(shù)的均勻洗牌和逆均勻洗牌函數(shù) N=8 N=8 的均勻洗牌函數(shù)的均勻洗牌函數(shù) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) 均勻洗牌函數(shù)均勻洗牌函數(shù) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (d) 逆均勻洗牌函數(shù)逆均勻洗牌函數(shù)-1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (b) 子洗牌函數(shù)子洗牌函數(shù)(2) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (c) 超洗牌函數(shù)超洗牌函數(shù)(2) 1515/114/1149.1 互連函數(shù)4. 碟式函數(shù) 蝶式互連

9、函數(shù)：把輸入端的二進(jìn)制編號的最高位與最低位互換位置，便得到了輸出端的編號。 第k個(gè)子函數(shù) (k)(xn-1xkxk-1xk-2x1x0)xn-1xkx0 xk-2x1xk-1 把輸入端的二進(jìn)制編號的低把輸入端的二進(jìn)制編號的低k k位中的最高位與最低位互換。位中的最高位與最低位互換。第k個(gè)超函數(shù) (k)(xn-1xn-2xn-k+1xn-kxn-k-1x1x0)xn-kxn-2xn-k+1xn-1xn-k-1x1x0 把輸入端的二進(jìn)制編號的高把輸入端的二進(jìn)制編號的高k k位中的最高位與最低位互換。位中的最高位與最低位互換。11200121nnnnxxxxxxxx1616/114/1149.1 互

10、連函數(shù)下列等式成立 (n)(X)(n)(X) (X) (1)(X)(1)(X) X當(dāng)N=8時(shí)，有： (x2x1x0)x0 x1x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0蝶式變換與交換變換的多級組合可作為構(gòu)成方體多級網(wǎng)絡(luò)的基礎(chǔ)。 1717/114/1149.1 互連函數(shù) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (b) (2)(2) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (c) (2)(2) N=8 N=8 的蝶式函數(shù)和反位序函數(shù)的蝶式函數(shù)和

11、反位序函數(shù) 1818/114/1149.1 互連函數(shù)5. 反位序函數(shù) 反位序函數(shù)：將輸入端二進(jìn)制編號的位序顛倒過來求得相應(yīng)輸出端的編號。q互連函數(shù)互連函數(shù) 第k個(gè)子函數(shù) (k)(xn-1xkxk-1xk-2x1x0)xn-1xkx0 x1xk-2xk-1即把輸入端的二進(jìn)制編號的低即把輸入端的二進(jìn)制編號的低k位中各位的次序顛倒過來。位中各位的次序顛倒過來。12100121nnnnxxxxxxxx1919/114/1149.1 互連函數(shù)第k個(gè)超函數(shù) (k)(xn-1xn-2xn-k+1xn-kxn-k-1x1x0)xn-kxn-k+1xn-2xn-1xn-k-1x1x0即把輸入端的二進(jìn)制編號的高即

12、把輸入端的二進(jìn)制編號的高k位中各位的次序顛倒過來。位中各位的次序顛倒過來。下列等式成立 (n)(X)(n)(X) (X) (1)(X)(1)(X) X當(dāng)N=8時(shí)，有： (x2x1x0)x0 x1x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x06. 移數(shù)函數(shù)移數(shù)函數(shù)：將各輸入端都錯(cuò)開一定的位置（模N）后連到輸出端。q函數(shù)式函數(shù)式 (x)= （xk）mod N 1xN-1，1kN-1 (a) 左移移數(shù)函數(shù)左移移數(shù)函數(shù) k k2 2 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (b) 右移移數(shù)函數(shù)右移移數(shù)函數(shù) k k2 2 0 1 2 3 4 5 6

13、 7 0 1 2 3 4 5 6 7 2121/114/1149.1 互連函數(shù)7. PM2I函數(shù) P和M分別表示加和減，2I表示2i。q該函數(shù)又稱為該函數(shù)又稱為“加減加減2i”函數(shù)函數(shù)。 PM2I函數(shù)：一種移數(shù)函數(shù)，將各輸入端都錯(cuò)開一定的位置（模N）后連到輸出端。 互連函數(shù) PM2+i(x) x2i mod N PM2-i(x) x2i mod N 其中：其中： 0 xN0 xN1 1，0in0in1 1，n nloglog2 2N N，N N為結(jié)點(diǎn)數(shù)。為結(jié)點(diǎn)數(shù)。PM2I互連網(wǎng)絡(luò)共有2n個(gè)互連函數(shù)。2222/114/1149.1 互連函數(shù)當(dāng)N8時(shí)，有6個(gè)PM2I函數(shù)：qPM2PM2+0+0 ：

14、（0 1 2 3 4 5 6 70 1 2 3 4 5 6 7）qPM2PM2-0-0 ：（7 6 5 4 3 2 1 07 6 5 4 3 2 1 0）qPM2PM2+1+1 ：（0 2 4 6 0 2 4 6 ）（）（1 3 5 71 3 5 7）qPM2PM2-1-1 ：（6 4 2 06 4 2 0）（）（7 5 3 17 5 3 1）qPM2PM2+2 +2 ：（0 40 4）（）（1 51 5）（）（2 62 6）（）（3 73 7） qPM2PM2-2 -2 ：（4 04 0）（）（5 15 1）（）（6 26 2）（）（7 37 3） 2323/114/1149.1 互連函數(shù)N

15、=8 N=8 的的PM2IPM2I函數(shù)函數(shù) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) PM2+0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (b) PM2+1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (c) PM2+2 陣列計(jì)算機(jī)ILLIAC 采用采用PM2PM20 0和和PM2PM2n/2n/2構(gòu)成其互連網(wǎng)絡(luò)，實(shí)現(xiàn)各構(gòu)成其互連網(wǎng)絡(luò)，實(shí)現(xiàn)各處理單元之間的上下左右互連處理單元之間的上下左右互連 。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 用移數(shù)函數(shù)構(gòu)成用移數(shù)函數(shù)構(gòu)成ILLIAC ILL

16、IAC 陣列機(jī)的互連網(wǎng)絡(luò)陣列機(jī)的互連網(wǎng)絡(luò)2525/114/1149.1 互連函數(shù) 例例9.1 9.1 現(xiàn)有現(xiàn)有1616個(gè)處理器，編號分別為個(gè)處理器，編號分別為0 0，1 1，1515，用一個(gè)，用一個(gè)N=16N=16的互連網(wǎng)絡(luò)互連。處理器的互連網(wǎng)絡(luò)互連。處理器i i的輸出通道連接互連網(wǎng)絡(luò)的輸入端的輸出通道連接互連網(wǎng)絡(luò)的輸入端i i，處理器，處理器i i的輸入通道連接互連網(wǎng)絡(luò)的輸出端的輸入通道連接互連網(wǎng)絡(luò)的輸出端i i。當(dāng)該互連網(wǎng)絡(luò)實(shí)現(xiàn)。當(dāng)該互連網(wǎng)絡(luò)實(shí)現(xiàn)的互連函數(shù)分別為：的互連函數(shù)分別為： （1 1）CubeCube3 3 （2 2）PM2PM2+3+3 （3 3）PM2PM2-0-0 （4 4）

17、 （5 5）()()時(shí)，分別給出與第時(shí)，分別給出與第1313號處理器所連接的處理器號。號處理器所連接的處理器號。2626/114/1149.1 互連函數(shù) 解：解：（1）由）由 ， 得得Cube3（1101）= 0101，即處理器，即處理器13連接到處理器連接到處理器5。 令令Cube3（ x3x2x1x0 ） = 1101，得，得x3x2x1x0= 0101，故與處理器，故與處理器13相連的相連的是處理器是處理器5。 所以處理器所以處理器13與處理器與處理器5雙向互連。雙向互連。 （2）由）由PM2+3 = j+23 mod 16，得，得PM2+3 （13）= 13+23 = 5， 即處理器即

18、處理器13連接到處理器連接到處理器5。令令PM2+3（j）= j+23 mod 16 =13，得，得j= 5，故與處理器，故與處理器13相連的是處理器相連的是處理器5。 所以處理器所以處理器13與處理器與處理器5雙向互連。雙向互連。 （3）由）由PM2-0（j）= j-20 mod 16，得，得PM2-0（13）= 13-20 = 12，即處理器，即處理器13連接到處理器連接到處理器12。令令PM2-0（j）= j-20 mod 16 =13，得，得j= 14，故與處理器，故與處理器13相連的是處理器相連的是處理器14。 所以處理器所以處理器13連至處理器連至處理器12，而處理器，而處理器14

19、連至處理器連至處理器13。012301233xxxxxxxxCube）（2727/114/1149.1 互連函數(shù) （4）由）由(x3x2x1x0)= x2x1x0 x3，得，得(1101)= 1011，即處理器，即處理器13連連接到處理器接到處理器11。 令令(x3x2x1x0)= 1101，得，得x3x2x1x0= 1110，故與處理器，故與處理器13相連的相連的是處理器是處理器14。 所以處理器所以處理器13連至處理器連至處理器11，而處理器，而處理器14連至處理器連至處理器13。 （5）由）由(x3x2x1x0)= x1x0 x3x2，得，得(1101)= 0111，即處理，即處理器器1

20、3連接到處理器連接到處理器7。 令令(x3x2x1x0)= 1101，得，得x3x2x1x0= 0111，故與處理器，故與處理器13相連相連的是處理器的是處理器7。 所以處理器所以處理器13與處理器與處理器7雙向互連。雙向互連。2828/114/1141. 網(wǎng)絡(luò)通常是用有向邊或無向邊連接有限個(gè)結(jié)點(diǎn)的圖來表示。2. 互連網(wǎng)絡(luò)的主要特性參數(shù)有：網(wǎng)絡(luò)規(guī)模N：網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù)。 表示該網(wǎng)絡(luò)所能連接的部件的數(shù)量。表示該網(wǎng)絡(luò)所能連接的部件的數(shù)量。結(jié)點(diǎn)度d：與結(jié)點(diǎn)相連接的邊數(shù)（通道數(shù)），包括入度和出度。9.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)9.2.1 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)2929/114/1149.2 互連網(wǎng)絡(luò)

21、的結(jié)構(gòu)參數(shù)與性能指標(biāo)q進(jìn)入結(jié)點(diǎn)的邊數(shù)叫進(jìn)入結(jié)點(diǎn)的邊數(shù)叫入度入度。q從結(jié)點(diǎn)出來的邊數(shù)叫從結(jié)點(diǎn)出來的邊數(shù)叫出度出度。結(jié)點(diǎn)距離：對于網(wǎng)絡(luò)中的任意兩個(gè)結(jié)點(diǎn)，從一個(gè)結(jié)點(diǎn)出發(fā)到另一個(gè)結(jié)點(diǎn)終止所需要跨越的邊數(shù)的最小值。網(wǎng)絡(luò)直徑D：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間距離的最大值。網(wǎng)絡(luò)直徑應(yīng)當(dāng)盡可能地小。網(wǎng)絡(luò)直徑應(yīng)當(dāng)盡可能地小。等分寬度b：把由N個(gè)結(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)切成結(jié)點(diǎn)數(shù)相同（N/2）的兩半，在各種切法中，沿切口邊數(shù)的最小值。 3030/114/1149.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)q線等分寬度：線等分寬度：B Bb bw wn其中：其中：w w為通道寬度（用位表示）為通道寬度（用位表示）n該參數(shù)主要反映了網(wǎng)絡(luò)最大流量

22、。該參數(shù)主要反映了網(wǎng)絡(luò)最大流量。對稱性：從任何結(jié)點(diǎn)看到的拓?fù)浣Y(jié)構(gòu)都是相同的網(wǎng)絡(luò)稱為對稱網(wǎng)絡(luò)。 對稱網(wǎng)絡(luò)比較容易實(shí)現(xiàn)，編程也比較容易。對稱網(wǎng)絡(luò)比較容易實(shí)現(xiàn)，編程也比較容易。3131/114/1149.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)評估互連網(wǎng)絡(luò)性能的兩個(gè)基本指標(biāo)：時(shí)延和帶寬1. 通信時(shí)延 指從源結(jié)點(diǎn)到目的結(jié)點(diǎn)傳送一條消息所需的總時(shí)間，它由以下4部分構(gòu)成：軟件開銷：在源結(jié)點(diǎn)和目的結(jié)點(diǎn)用于收發(fā)消息的軟件所需的執(zhí)行時(shí)間。q主要取決于兩端端結(jié)點(diǎn)處理消息的軟件內(nèi)核。主要取決于兩端端結(jié)點(diǎn)處理消息的軟件內(nèi)核。 通道時(shí)延：通過通道傳送消息所花的時(shí)間。p通路時(shí)延通路時(shí)延 = 消息長度消息長度/通道帶寬通道帶寬p通

23、常由瓶頸鏈路的通道帶寬決定。通常由瓶頸鏈路的通道帶寬決定。 9.2.2 互連網(wǎng)絡(luò)的性能指標(biāo)3232/114/1149.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)選路時(shí)延：消息在傳送路徑上所需的一系列選路決策所需的時(shí)間開銷。q與傳送路徑上的結(jié)點(diǎn)數(shù)成正比。與傳送路徑上的結(jié)點(diǎn)數(shù)成正比。 競爭時(shí)延：多個(gè)消息同時(shí)在網(wǎng)絡(luò)中傳送時(shí)，會(huì)發(fā)生爭用網(wǎng)絡(luò)資源的沖突。為避免或解決爭用沖突所需的時(shí)間就是競爭時(shí)延。 q很難預(yù)測，它取決于網(wǎng)絡(luò)的傳輸狀態(tài)。很難預(yù)測，它取決于網(wǎng)絡(luò)的傳輸狀態(tài)。 2. 網(wǎng)絡(luò)時(shí)延 通道時(shí)延與選路時(shí)延的和。q它是由網(wǎng)絡(luò)硬件特征決定的，與程序行為和網(wǎng)絡(luò)傳輸它是由網(wǎng)絡(luò)硬件特征決定的，與程序行為和網(wǎng)絡(luò)傳輸狀態(tài)無關(guān)。狀

24、態(tài)無關(guān)。 3333/114/1149.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)3. 端口帶寬對于互連網(wǎng)絡(luò)中的任意一個(gè)端口來說，其端口帶寬是指單位時(shí)間內(nèi)從該端口傳送到其他端口的最大信息量。q在對稱網(wǎng)絡(luò)中，端口帶寬與端口位置無關(guān)。網(wǎng)絡(luò)的端在對稱網(wǎng)絡(luò)中，端口帶寬與端口位置無關(guān)。網(wǎng)絡(luò)的端口帶寬與各端口的端口帶寬相同?？趲捙c各端口的端口帶寬相同。q非對稱網(wǎng)絡(luò)的端口帶寬則是指所有端口帶寬的最小值。非對稱網(wǎng)絡(luò)的端口帶寬則是指所有端口帶寬的最小值。4. 聚集帶寬 網(wǎng)絡(luò)從一半結(jié)點(diǎn)到另一半結(jié)點(diǎn)，單位時(shí)間內(nèi)能夠傳送的最大信息量。 3434/114/1149.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo) 例如，例如，HPS是一種對稱網(wǎng)

25、絡(luò)是一種對稱網(wǎng)絡(luò) 網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模N的上限：的上限：512 端口帶寬：端口帶寬：40MB/s HPS的聚集帶寬：的聚集帶寬：（40MB/s512）/210.24GB/s 5. 等分帶寬 與等分寬度對應(yīng)的切平面中，所有邊合起來單位時(shí)間所能傳送的最大信息量。3535/114/114互連網(wǎng)絡(luò)通?？梢苑譃閮纱箢悾红o態(tài)互連網(wǎng)絡(luò) 各結(jié)點(diǎn)之間有固定的連接通路、且在運(yùn)行中不能各結(jié)點(diǎn)之間有固定的連接通路、且在運(yùn)行中不能改變的網(wǎng)絡(luò)。改變的網(wǎng)絡(luò)。動(dòng)態(tài)互連網(wǎng)絡(luò) 由交換開關(guān)構(gòu)成、可按運(yùn)行程序的要求動(dòng)態(tài)地改由交換開關(guān)構(gòu)成、可按運(yùn)行程序的要求動(dòng)態(tài)地改變連接狀態(tài)的網(wǎng)絡(luò)。變連接狀態(tài)的網(wǎng)絡(luò)。下面介紹幾種靜態(tài)互連網(wǎng)絡(luò)。 （其中：（

26、其中：N N表示結(jié)點(diǎn)的個(gè)數(shù)）表示結(jié)點(diǎn)的個(gè)數(shù)） 9.3 靜態(tài)互連網(wǎng)絡(luò)3636/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)1. 線性陣列 一種一維的線性網(wǎng)絡(luò)，其中N個(gè)結(jié)點(diǎn)用N-1個(gè)鏈路連成一行。q端結(jié)點(diǎn)的度：端結(jié)點(diǎn)的度：1 1q其余結(jié)點(diǎn)的度：其余結(jié)點(diǎn)的度：2 2q直徑：直徑：N N1 1q等分寬度等分寬度b=1b=1 3737/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)3838/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)q對稱對稱q結(jié)點(diǎn)的度：結(jié)點(diǎn)的度：2 2q雙向環(huán)的直徑：雙向環(huán)的直徑：N/2N/2q單向環(huán)的直徑：單向環(huán)的直徑：N N q環(huán)的等分寬度環(huán)的等分寬度b=2 2. 環(huán)和帶弦環(huán) 環(huán) 用一條附加鏈路將線性陣列的兩個(gè)

27、端點(diǎn)連接起來而構(gòu)成。可以單向工作，也可以雙向工作。3939/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)帶弦環(huán) 增加的鏈路愈多，結(jié)點(diǎn)度愈高，網(wǎng)絡(luò)直徑就愈小。4040/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)全連接網(wǎng)絡(luò) q結(jié)點(diǎn)度：結(jié)點(diǎn)度：1515q直徑最短，為直徑最短，為1 1。 3. 循環(huán)移數(shù)網(wǎng)絡(luò)通過在環(huán)上每個(gè)結(jié)點(diǎn)到所有與其距離為2的整數(shù)冪的結(jié)點(diǎn)之間都增加一條附加鏈而構(gòu)成。N=16N=16q結(jié)點(diǎn)度：結(jié)點(diǎn)度：7 7q直徑：直徑：2 2 4242/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)一般地，如果j-i=2r（r=0,1,2,n-1，n=log2N），則結(jié)點(diǎn)i與結(jié)點(diǎn)j連接。q結(jié)點(diǎn)度：結(jié)點(diǎn)度：2n2n1 1q直徑：直徑

28、：n/2n/2q網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模N=2n4343/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)4. 樹形和星形 一棵5層31個(gè)結(jié)點(diǎn)的二叉樹 一般說來，一棵k層完全平衡的二叉樹有N=2k-1個(gè)結(jié)點(diǎn)。q最大結(jié)點(diǎn)度：最大結(jié)點(diǎn)度：3 3q直徑：直徑：2(k-1) 2(k-1) q等分寬度等分寬度b=1 星形 q結(jié)點(diǎn)度較高，為結(jié)點(diǎn)度較高，為N N1 1。q直徑較小，是一常數(shù)直徑較小，是一常數(shù)2 2。等分寬度等分寬度b= N/2 q可靠性比較差，只要中心結(jié)點(diǎn)出故障，整個(gè)系統(tǒng)就會(huì)可靠性比較差，只要中心結(jié)點(diǎn)出故障，整個(gè)系統(tǒng)就會(huì)癱瘓。癱瘓。 4444/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)4545/114/1149.3 靜態(tài)

29、互連網(wǎng)絡(luò)5. 胖樹形 4646/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)6. 網(wǎng)格形和環(huán)網(wǎng)形 網(wǎng)格形q一個(gè)一個(gè)3 33 3的網(wǎng)格形網(wǎng)絡(luò)的網(wǎng)格形網(wǎng)絡(luò)q一個(gè)規(guī)模為一個(gè)規(guī)模為N=nn的的2維網(wǎng)格形網(wǎng)絡(luò)維網(wǎng)格形網(wǎng)絡(luò)n內(nèi)部結(jié)點(diǎn)的度內(nèi)部結(jié)點(diǎn)的度d=4n邊結(jié)點(diǎn)的度邊結(jié)點(diǎn)的度d=3n角角結(jié)點(diǎn)的度結(jié)點(diǎn)的度d=2n網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑D=2（n-1）n等分寬度等分寬度b=nq一個(gè)由一個(gè)由N=nk 個(gè)個(gè)結(jié)點(diǎn)構(gòu)成的結(jié)點(diǎn)構(gòu)成的k維網(wǎng)格形網(wǎng)絡(luò)（每維維網(wǎng)格形網(wǎng)絡(luò)（每維n個(gè)結(jié)個(gè)結(jié)點(diǎn)）的內(nèi)部結(jié)點(diǎn)度點(diǎn)）的內(nèi)部結(jié)點(diǎn)度d=2k，網(wǎng)絡(luò)直徑，網(wǎng)絡(luò)直徑D=k(n-1) 。4747/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)Illiac網(wǎng)絡(luò) q名稱來源于采用

30、了這種網(wǎng)絡(luò)的名稱來源于采用了這種網(wǎng)絡(luò)的Illiac 計(jì)算機(jī)計(jì)算機(jī) q把把2維網(wǎng)格形網(wǎng)絡(luò)的每一列的兩個(gè)端結(jié)點(diǎn)連接起來，維網(wǎng)格形網(wǎng)絡(luò)的每一列的兩個(gè)端結(jié)點(diǎn)連接起來，再把每一行的尾結(jié)點(diǎn)與下一行的頭結(jié)點(diǎn)連接起來，并再把每一行的尾結(jié)點(diǎn)與下一行的頭結(jié)點(diǎn)連接起來，并把最后一行的尾結(jié)點(diǎn)與第一行的頭結(jié)點(diǎn)連接起來。把最后一行的尾結(jié)點(diǎn)與第一行的頭結(jié)點(diǎn)連接起來。q一個(gè)規(guī)模為一個(gè)規(guī)模為nn的的Illiac網(wǎng)絡(luò)網(wǎng)絡(luò)n所有結(jié)點(diǎn)的度所有結(jié)點(diǎn)的度d=4n網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑D=n-1 Illiac網(wǎng)絡(luò)的直徑只有純網(wǎng)格形網(wǎng)絡(luò)直徑的一半。網(wǎng)絡(luò)的直徑只有純網(wǎng)格形網(wǎng)絡(luò)直徑的一半。 n等分寬度：等分寬度：2n4848/114/1149.3 靜

31、態(tài)互連網(wǎng)絡(luò)環(huán)網(wǎng)形q可看作是直徑更短的另一種網(wǎng)格。可看作是直徑更短的另一種網(wǎng)格。 q把把2維網(wǎng)格形網(wǎng)絡(luò)的每一行的兩個(gè)端結(jié)點(diǎn)連接起來，維網(wǎng)格形網(wǎng)絡(luò)的每一行的兩個(gè)端結(jié)點(diǎn)連接起來，把每一列的兩個(gè)端結(jié)點(diǎn)也連接起來。把每一列的兩個(gè)端結(jié)點(diǎn)也連接起來。 q將環(huán)形和網(wǎng)格形組合在一起，并能向高維擴(kuò)展。將環(huán)形和網(wǎng)格形組合在一起，并能向高維擴(kuò)展。 q一個(gè)一個(gè)n nn n的的環(huán)網(wǎng)形網(wǎng)環(huán)網(wǎng)形網(wǎng) n結(jié)點(diǎn)度：結(jié)點(diǎn)度：4 4n網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)直徑：2 2 n/2n/2 n等分寬度等分寬度b=2n 4949/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)（a a）網(wǎng)格形）網(wǎng)格形（b b）IlliacIlliac網(wǎng)網(wǎng)（c c）環(huán)網(wǎng)形）環(huán)網(wǎng)形50

32、50/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)7. 超立方體 一種二元n-立方體結(jié)構(gòu)一般來說，一個(gè)二元n-立方體由N=2n 個(gè)結(jié)點(diǎn)組成，它們分布在n維上，每維有兩個(gè)結(jié)點(diǎn)。 例例 8 8個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的3 3維立方體維立方體 4 4維立方體維立方體為實(shí)現(xiàn)一個(gè)n-立方體，只要把兩個(gè)（n1）立方體中相對應(yīng)的結(jié)點(diǎn)用鏈路連接起來即可。共需要2n-1條鏈路。n-立方體中結(jié)點(diǎn)的度都是n，直徑也是n，等分寬度為b=N/2 。 5151/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)5252/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)8. 帶環(huán)立方體 （簡稱3-CCC） 把3-立方體的每個(gè)結(jié)點(diǎn)換成一個(gè)由3個(gè)結(jié)點(diǎn)構(gòu)成的環(huán)而形成的。帶環(huán)k-

33、立方體（簡稱k-CCC）qk-立方體的變形，它是通過用立方體的變形，它是通過用k個(gè)結(jié)點(diǎn)構(gòu)成的環(huán)取代個(gè)結(jié)點(diǎn)構(gòu)成的環(huán)取代k-立方體中的每個(gè)結(jié)點(diǎn)而形成的。立方體中的每個(gè)結(jié)點(diǎn)而形成的。q網(wǎng)絡(luò)規(guī)模為網(wǎng)絡(luò)規(guī)模為N=k2kq網(wǎng)絡(luò)直徑為網(wǎng)絡(luò)直徑為D=2k-1+ k/2 n比比k-立方體的直徑大一倍立方體的直徑大一倍q等分寬度為等分寬度為b=N/（2k）5353/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)1234 k k-15 k k-112345(b) (b) 將將k-k-立方體的每個(gè)結(jié)點(diǎn)用由立方體的每個(gè)結(jié)點(diǎn)用由k k個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的環(huán)來代替，組成帶環(huán)環(huán)來代替，組成帶環(huán)k-k-立方體組成立方體組成5454/114/1

34、149.3 靜態(tài)互連網(wǎng)絡(luò)9. k元n-立方體網(wǎng)絡(luò)環(huán)形、網(wǎng)格、環(huán)網(wǎng)形、二元n-立方體（超立方體）和Omega網(wǎng)絡(luò)都是k元n-立方體網(wǎng)絡(luò)系列的拓?fù)渫瑯?gòu)體。在k元n-立方體網(wǎng)絡(luò)中，參數(shù)n是立方體的維數(shù)，k是基數(shù)，即每一維上的結(jié)點(diǎn)個(gè)數(shù)。 N=kn，（，（ ，n=logkN）k元n-立方體的結(jié)點(diǎn)可以用基數(shù)為k的n位地址A =a1a2an來表示。q其中其中ai表示該結(jié)點(diǎn)在第表示該結(jié)點(diǎn)在第i維上的位置維上的位置通常把低維k元n-立方體稱為環(huán)網(wǎng)，而把高維k元n-立方體稱為超立方體。 nNk 5555/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)4元元3-立方體網(wǎng)絡(luò)立方體網(wǎng)絡(luò) NrNr 網(wǎng)絡(luò)類型網(wǎng)絡(luò)類型結(jié)點(diǎn)度結(jié)點(diǎn)度d d

35、網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑D D鏈路數(shù)鏈路數(shù)l l等分寬度等分寬度B B對稱性對稱性網(wǎng)絡(luò)規(guī)格說明網(wǎng)絡(luò)規(guī)格說明線線陣列線線陣列2 2N-1N-1N-1N-11 1非非N N個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)環(huán)形環(huán)形2 2N/2N/2N N2 2是是N N個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)全連接全連接N-1N-11 1N(N-1)/2N(N-1)/2(N/2)(N/2)2 2是是N N個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)二叉樹二叉樹3 32(h-1)2(h-1)N-1N-11 1非非樹高樹高h(yuǎn)=logh=log2 2NN星形星形N-1N-12 2N-1N-1N/2N/2非非N N個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)2D2D網(wǎng)格網(wǎng)格4 42(r-1)2(r-1)2N-2r2N-2rr r非非r rr

36、 r網(wǎng)格，網(wǎng)格，IlliacIlliac網(wǎng)網(wǎng)4 4r-1r-12N2N2r2r非非與與 的帶弦的帶弦環(huán)等效環(huán)等效 2D2D環(huán)網(wǎng)環(huán)網(wǎng)4 42r/22r/22N2N2r2r是是r rr r環(huán)網(wǎng)，環(huán)網(wǎng)，超立方體超立方體n nn nnN/2nN/2N/2N/2是是N N個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，n=logn=log2 2NN（維數(shù)）（維數(shù)）CCCCCC3 32k-1+k/22k-1+k/23N/23N/2N/(2k)N/(2k)是是N=kN=k2 2k k結(jié)點(diǎn)結(jié)點(diǎn)環(huán)長環(huán)長k3k3k k元元n-n-立方體立方體2n2nnk/2nk/2nNnN2k2kn-1n-1是是N=kN=kn n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)靜態(tài)互連網(wǎng)絡(luò)特征一

37、覽表靜態(tài)互連網(wǎng)絡(luò)特征一覽表 Nr 5757/114/1149.3 靜態(tài)互連網(wǎng)絡(luò) 例例9.2 已知有已知有16臺(tái)個(gè)處理器用臺(tái)個(gè)處理器用Illiac網(wǎng)絡(luò)互連，寫出網(wǎng)絡(luò)互連，寫出Illiac網(wǎng)絡(luò)的網(wǎng)絡(luò)的互連函數(shù)，給出表示任何一個(gè)處理器互連函數(shù)，給出表示任何一個(gè)處理器PUi（0i15）與其他處理器）與其他處理器直接互連的一般表達(dá)式。直接互連的一般表達(dá)式。 解：解：Illiac網(wǎng)絡(luò)連接的結(jié)點(diǎn)數(shù)網(wǎng)絡(luò)連接的結(jié)點(diǎn)數(shù)N=16，組成，組成44的陣列。每一列的的陣列。每一列的4個(gè)處理器互連為一個(gè)雙向環(huán)，第個(gè)處理器互連為一個(gè)雙向環(huán)，第1列第列第4列的雙向環(huán)可分別用循環(huán)列的雙向環(huán)可分別用循環(huán)互連函數(shù)表示為：互連函數(shù)表示

38、為： （0 4 8 12） （12 8 4 0） （1 5 9 13） （13 9 5 1） （2 6 10 14） （14 10 6 2） （3 7 11 15） （15 11 7 3）其中，傳送方向?yàn)轫槙r(shí)針的其中，傳送方向?yàn)轫槙r(shí)針的4個(gè)單向環(huán)的循環(huán)互連函數(shù)可表示為：個(gè)單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2+2（X）= （X + 22）mod N =（X + 4）mod 165858/114/1149.3 靜態(tài)互連網(wǎng)絡(luò) 傳送方向?yàn)槟鏁r(shí)針的傳送方向?yàn)槟鏁r(shí)針的4個(gè)單向環(huán)的循環(huán)互連函數(shù)可表示為：個(gè)單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2-2（X）= （X - 22）mod N =（X 4）mod 1

39、6 16個(gè)處理器由個(gè)處理器由Illiac網(wǎng)絡(luò)的水平螺線互連為一個(gè)雙向環(huán)，用循環(huán)網(wǎng)絡(luò)的水平螺線互連為一個(gè)雙向環(huán)，用循環(huán)互連函數(shù)表示為：互連函數(shù)表示為： （0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15） （15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0）其中，傳送方向?yàn)轫槙r(shí)針的單向環(huán)的循環(huán)互連函數(shù)可表示為：其中，傳送方向?yàn)轫槙r(shí)針的單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2+0（X）= （X + 20）mod N =（X + 1）mod 16 傳送方向?yàn)槟鏁r(shí)針的單向環(huán)的循環(huán)互連函數(shù)可表示為：傳送方向?yàn)槟鏁r(shí)針的單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2

40、-0（X）=（X 20）mod N =（X 1）mod 16所以，所以，N=16的的Illiac網(wǎng)絡(luò)的互連函數(shù)有網(wǎng)絡(luò)的互連函數(shù)有4個(gè)：個(gè)： PM20（X）和和PM22（X）5959/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)由互連函數(shù)可得任何一個(gè)處理器由互連函數(shù)可得任何一個(gè)處理器i直接與下述直接與下述4個(gè)處理器雙向互連：個(gè)處理器雙向互連： i1 mod 16 i4 mod 166060/114/1141. 由一組導(dǎo)線和插座構(gòu)成，經(jīng)常被用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)中處理機(jī)模塊、存儲(chǔ)模塊和外圍設(shè)備等之間的互連。 每一次總線只能用于一個(gè)源（主部件）到一個(gè)或多個(gè)目的（從部件）之間的數(shù)據(jù)傳送。多個(gè)功能模塊之間的爭用總線或

41、時(shí)分總線 特點(diǎn)q結(jié)構(gòu)簡單、實(shí)現(xiàn)成本低、帶寬較窄結(jié)構(gòu)簡單、實(shí)現(xiàn)成本低、帶寬較窄9.4.1 總線網(wǎng)絡(luò)9.4 動(dòng)態(tài)互連網(wǎng)絡(luò)6161/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)2. 一種由總線連接的多處理機(jī)系統(tǒng) 6262/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)q系統(tǒng)總線在處理機(jī)、系統(tǒng)總線在處理機(jī)、I/O子系統(tǒng)、主存儲(chǔ)器以及輔助子系統(tǒng)、主存儲(chǔ)器以及輔助存儲(chǔ)設(shè)備（磁盤、磁帶機(jī)等）之間提供了一條公用通存儲(chǔ)設(shè)備（磁盤、磁帶機(jī)等）之間提供了一條公用通路。路。q系統(tǒng)總線通常設(shè)置在印刷電路板底板上。處理器板、系統(tǒng)總線通常設(shè)置在印刷電路板底板上。處理器板、存儲(chǔ)器板和設(shè)備接口板都通過插座或電纜插入底板。存儲(chǔ)器板和設(shè)備接口板都通過插

42、座或電纜插入底板。 3. 解決總線帶寬較窄問題：采用多總線或多層次的總線多總線是設(shè)置多條總線有兩種做法：有兩種做法：q為不同的功能設(shè)置專門的總線為不同的功能設(shè)置專門的總線q重復(fù)設(shè)置相同功能的總線重復(fù)設(shè)置相同功能的總線多層次的總線是按層次的架構(gòu)設(shè)置速度不同的總線，使得不同速度的模塊有比較適合的總線連接。 6363/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)1. 單級開關(guān)網(wǎng)絡(luò) 交叉點(diǎn)開關(guān)能在對偶（源、目的）之間形成動(dòng)態(tài)連接，同時(shí)實(shí)現(xiàn)多個(gè)對偶之間的無阻塞連接。 帶寬和互連特性最好。 一個(gè)nn的交叉開關(guān)網(wǎng)絡(luò)，可以無阻塞地實(shí)現(xiàn)n!種置換。 對一個(gè)nn的交叉開關(guān)網(wǎng)絡(luò)來說，需要n2套交叉點(diǎn)開關(guān)以及大量的連線。q當(dāng)當(dāng)

43、n很大時(shí)，交叉開關(guān)網(wǎng)絡(luò)所需要的硬件數(shù)量非常巨很大時(shí)，交叉開關(guān)網(wǎng)絡(luò)所需要的硬件數(shù)量非常巨大。大。9.4.2 交叉開關(guān)網(wǎng)絡(luò)6464/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)2. C.mmp多處理機(jī)的互連結(jié)構(gòu) 用1616的交叉開關(guān)網(wǎng)絡(luò)把16臺(tái)PDP-11處理機(jī)與16個(gè)存儲(chǔ)模塊連在一起最多可同時(shí)實(shí)現(xiàn)16臺(tái)處理機(jī)對16個(gè)不同存儲(chǔ)模塊的并行訪問q每個(gè)存儲(chǔ)模塊一次只能滿足一臺(tái)處理機(jī)的請求每個(gè)存儲(chǔ)模塊一次只能滿足一臺(tái)處理機(jī)的請求q當(dāng)多個(gè)請求要同時(shí)訪問同一存儲(chǔ)模塊時(shí)，交叉開關(guān)就當(dāng)多個(gè)請求要同時(shí)訪問同一存儲(chǔ)模塊時(shí)，交叉開關(guān)就必須分解所發(fā)生的沖突，每一列只能接通一個(gè)交叉點(diǎn)必須分解所發(fā)生的沖突，每一列只能接通一個(gè)交叉點(diǎn)開關(guān)

44、。開關(guān)。q為了支持并行（或交叉）存儲(chǔ)器訪問，可以在同一行為了支持并行（或交叉）存儲(chǔ)器訪問，可以在同一行中接通幾個(gè)交叉點(diǎn)開關(guān)。中接通幾個(gè)交叉點(diǎn)開關(guān)。 6565/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)6666/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)3. Fujitsu公司制造的向量并行處理機(jī)VPP500所采用的大型交換開關(guān)網(wǎng)絡(luò)（224224） PE：帶存儲(chǔ)器的處理機(jī)CP：控制處理機(jī) 每一行和每一列只能接通一個(gè)交叉點(diǎn)開關(guān)6767/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)PE220發(fā)送發(fā)送PE222CP001斷開斷開CP002PE001PE219PE221PE222PE221PE220PE219PE001CP002

45、CP001接通接通接收接收6868/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)1. 多級互連網(wǎng)絡(luò)的構(gòu)成 MIMD和SIMD計(jì)算機(jī)都采用多級互連網(wǎng)絡(luò)MIN（Multistage Interconnection Network）一種通用的多級互連網(wǎng)絡(luò) q由由a ab b開關(guān)開關(guān)模塊和級間連接構(gòu)成的通用多級互連網(wǎng)絡(luò)結(jié)構(gòu)模塊和級間連接構(gòu)成的通用多級互連網(wǎng)絡(luò)結(jié)構(gòu)q每一級都用了多個(gè)每一級都用了多個(gè)a ab b開關(guān)開關(guān)na a個(gè)輸入和個(gè)輸入和b b個(gè)輸出個(gè)輸出n在理論上，在理論上，a a和和b b不一定相等，然而實(shí)際上不一定相等，然而實(shí)際上a a和和b b經(jīng)常經(jīng)常選為選為2 2的整數(shù)冪，即的整數(shù)冪，即a ab b2

46、 2k k，k1k1。 q相鄰各級開關(guān)之間都有固定的級間連接相鄰各級開關(guān)之間都有固定的級間連接9.4.3 多級互連網(wǎng)絡(luò)6969/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)7070/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)幾種常用的開關(guān)模塊 模塊大小模塊大小 合法狀態(tài)合法狀態(tài) 置換連接置換連接 2 22 2 4 4 2 24 44 4 25625624248 88 8 16 777 21616 777 21640 32040 320n nn n n nn n n! n! 7171/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)最簡單的開關(guān)模塊：22開關(guān) 22開關(guān)的4種連接方式 7272/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)

47、各種多級互連網(wǎng)絡(luò)的區(qū)別在于所用開關(guān)模塊、控制方式和級間互連模式的不同。q控制方式控制方式：對各個(gè)開關(guān)模塊進(jìn)行控制的方式。：對各個(gè)開關(guān)模塊進(jìn)行控制的方式。n級控制：級控制：每一級的所有開關(guān)只用一個(gè)控制信號每一級的所有開關(guān)只用一個(gè)控制信號控制，只能同時(shí)處于同一種狀態(tài)?？刂疲荒芡瑫r(shí)處于同一種狀態(tài)。n單元控制：單元控制：每一個(gè)開關(guān)都有一個(gè)獨(dú)立的控制信每一個(gè)開關(guān)都有一個(gè)獨(dú)立的控制信號，可各自處于不同的狀態(tài)。號，可各自處于不同的狀態(tài)。n部分級控制：部分級控制：第第i i級的所有開關(guān)分別用級的所有開關(guān)分別用i i1 1個(gè)信個(gè)信號控制，號控制，0in0in1 1，n n為級數(shù)。為級數(shù)。 q常用的級間互連模式

48、：常用的級間互連模式：均勻洗牌、蝶式、多路洗牌、縱橫交叉、立方體連接等均勻洗牌、蝶式、多路洗牌、縱橫交叉、立方體連接等 7373/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)2. 多級立方體網(wǎng)絡(luò)多級立方體網(wǎng)絡(luò)包括STARAN網(wǎng)絡(luò)和間接二進(jìn)制n方體網(wǎng)絡(luò)等。q兩者僅在控制方式上不同，在其他方面都是一樣的。兩者僅在控制方式上不同，在其他方面都是一樣的。q都采用二功能（直送和交換）的都采用二功能（直送和交換）的22開關(guān)。開關(guān)。q當(dāng)?shù)诋?dāng)?shù)趇級（級（0in-1）交換開關(guān)處于交換狀態(tài)時(shí)，實(shí)現(xiàn)）交換開關(guān)處于交換狀態(tài)時(shí)，實(shí)現(xiàn)的是的是Cubei互連函數(shù)。互連函數(shù)。 一個(gè)N輸入的多級立方體網(wǎng)絡(luò)有l(wèi)og2N級，每級用N/2個(gè)2

49、2開關(guān)模塊，共需要log2NN/2個(gè)開關(guān)。一個(gè)8個(gè)入端的多級立方體網(wǎng)絡(luò)7474/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò) 7 5 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 A B C D E F G H I J K L 級級 0 級級 1 級級 2 0 0 0 0 0 0 1 出端出端 入端入端 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 3 多級立方體網(wǎng)絡(luò)多級立方體網(wǎng)絡(luò) 7575/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)STARAN網(wǎng)絡(luò)采用級控制和部分級控制。q采用級控制時(shí)，

50、所實(shí)現(xiàn)的是交換功能；采用級控制時(shí)，所實(shí)現(xiàn)的是交換功能；q采用部分級控制時(shí)，則能實(shí)現(xiàn)移數(shù)功能。采用部分級控制時(shí)，則能實(shí)現(xiàn)移數(shù)功能。間接二進(jìn)制n方體網(wǎng)絡(luò)則采用單元控制。q具有更大的靈活性。具有更大的靈活性。交換q將有序的一組元素頭尾對稱地進(jìn)行交換。將有序的一組元素頭尾對稱地進(jìn)行交換。 例如：例如：對于由對于由8 8個(gè)元素構(gòu)成的組，各種基本交換的圖形：個(gè)元素構(gòu)成的組，各種基本交換的圖形：7676/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a)(a)4 4 組組 2 2 元交換元交換 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6

51、 7 (b) 2 2 組組 4 4 元交換元交換 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (c) 1 1 組組 8 8 元交換元交換 8 8個(gè)元素的基本交換圖形個(gè)元素的基本交換圖形 7777/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)3級STARAN網(wǎng)絡(luò)在各種級控制信號的情況下所實(shí)現(xiàn)的入出端連接以及所實(shí)現(xiàn)的交換函數(shù)和功能。其中：其中：qK2k1k0：控制信號，：控制信號，ki（i=0，1，2）為第）為第i級的級控級的級控制信號。制信號。q從表中可以看出從表中可以看出 下面的下面的4行中每一行所實(shí)現(xiàn)的功能可以從級控制行中每一行所實(shí)現(xiàn)的功能可以從級控制信號為其反碼的一行中所實(shí)現(xiàn)的功

52、能加上信號為其反碼的一行中所實(shí)現(xiàn)的功能加上1組組8元變元變換來獲得。換來獲得。 例如：例如：級控制信號為級控制信號為110所實(shí)現(xiàn)的功能是其反碼所實(shí)現(xiàn)的功能是其反碼001所實(shí)所實(shí)現(xiàn)的現(xiàn)的4組組2元交換再加上元交換再加上1組組8元交換來獲得。元交換來獲得。 級控制信號級控制信號k2k1k0連接的輸出端號序列連接的輸出端號序列（入端號序列：（入端號序列：01234567）實(shí)現(xiàn)的分組交換實(shí)現(xiàn)的分組交換實(shí)現(xiàn)的互連函數(shù)實(shí)現(xiàn)的互連函數(shù)0000 1 2 3 4 5 6 7恒等恒等I0011 0 3 2 5 4 7 64組組2元交換元交換Cube00102 3 0 1 6 7 4 54組組2元交換元交換2組組4

53、元交換元交換Cube10113 2 1 0 7 6 5 42組組4元交換元交換Cube0Cube11004 5 6 7 0 1 2 32組組4元交換元交換1組組8元交換元交換Cube21015 4 7 6 1 0 3 24組組2元交換元交換2組組4元交換元交換1組組8元交換元交換Cube0Cube21106 7 4 5 2 3 0 14組組2元交換元交換1組組8元交換元交換Cube1Cube21117 6 5 4 3 2 1 01組組8元交換元交換Cube0Cube1Cube2當(dāng)STARAN網(wǎng)絡(luò)用作移數(shù)網(wǎng)絡(luò)時(shí)，采用部分級控制，控制信號的分組和控制結(jié)果。部分級控制信號部分級控制信號連接的輸出端號

54、序列連接的輸出端號序列（入端號序列：（入端號序列：0123456701234567）所實(shí)現(xiàn)的移數(shù)所實(shí)現(xiàn)的移數(shù)功能功能第第0 0級級第第1 1級級第第2 2級級A AB BC CD DE EG GF FH HI IJ JK KL L1 10 00 01 10 01 10 01 11 10 01 11 10 00 00 01 10 00 01 10 00 01 11 11 10 00 00 00 00 01 11 10 00 00 00 00 00 01 10 00 00 00 01 2 3 4 5 6 7 01 2 3 4 5 6 7 02 3 4 5 6 7 0 12 3 4 5 6 7 0

55、14 5 6 7 0 1 2 34 5 6 7 0 1 2 31 2 3 0 5 6 7 41 2 3 0 5 6 7 42 3 0 1 6 7 4 52 3 0 1 6 7 4 51 0 3 2 5 4 7 61 0 3 2 5 4 7 60 1 2 3 4 5 6 70 1 2 3 4 5 6 7移移1 mod 81 mod 8移移2 mod 82 mod 8移移4 mod 84 mod 8移移1 mod 41 mod 4移移2 mod 42 mod 4移移1 mod 21 mod 2不移不移 全等全等3. Omega網(wǎng)絡(luò) 一個(gè)88的Omega網(wǎng)絡(luò)q每級由每級由4個(gè)個(gè)4功能的功能的22開關(guān)

56、構(gòu)成開關(guān)構(gòu)成q級間互連采用均勻洗牌連接方式級間互連采用均勻洗牌連接方式 0 0 0 0 0 4 2 1 1 1 2 2 1 4 2 5 6 3 3 3 4 4 2 1 4 6 3 5 5 5 6 6 3 5 6 7 7 7 7 7 8181/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)一個(gè)N輸入的Omega網(wǎng)絡(luò)q有有l(wèi)og2N級，每級用級，每級用N/2個(gè)個(gè)22開關(guān)模塊，共需要開關(guān)模塊，共需要Nlog2N/2個(gè)開關(guān)。個(gè)開關(guān)。q每個(gè)開關(guān)模塊均采用單元控制方式。每個(gè)開關(guān)模塊均采用單元控制方式。q不同的開關(guān)狀態(tài)組合可實(shí)現(xiàn)各種置換、廣播或從輸不同的開關(guān)狀態(tài)組合可實(shí)現(xiàn)各種置換、廣播或從輸入到輸出的其它連接。入到輸出

57、的其它連接。N=8的多級立方體互連網(wǎng)絡(luò)的另一種畫法 8282/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)0011223344556677ABCDEGFHIJKL級級0級級1級級28383/114/1149.4 動(dòng)態(tài)互連網(wǎng)絡(luò)9.4.4 動(dòng)態(tài)互連網(wǎng)絡(luò)的比較網(wǎng)絡(luò)特性網(wǎng)絡(luò)特性總線系統(tǒng)總線系統(tǒng)多級網(wǎng)絡(luò)多級網(wǎng)絡(luò)交叉開關(guān)交叉開關(guān)單位數(shù)據(jù)傳送的單位數(shù)據(jù)傳送的最小時(shí)延最小時(shí)延恒定恒定O(logkn)恒定恒定每臺(tái)處理機(jī)的帶寬每臺(tái)處理機(jī)的帶寬O(w/n)至至O(w)O(w)至至O(nw)O(w)至至O(nw)連線復(fù)雜性連線復(fù)雜性O(shè)(w)O(nwlogkn)O(n2w)開關(guān)復(fù)雜性開關(guān)復(fù)雜性O(shè)(n)O(nlogkn)O(n2)

58、連接特性和尋徑性能連接特性和尋徑性能一次只能一對一一次只能一對一只要網(wǎng)絡(luò)不阻塞，只要網(wǎng)絡(luò)不阻塞，可實(shí)現(xiàn)某些置換和廣播可實(shí)現(xiàn)某些置換和廣播全置換，全置換，一次一個(gè)一次一個(gè)典型計(jì)算機(jī)典型計(jì)算機(jī)Symmetry S1，Encore MultimaxBBNTC-2000IBM RP3Cray Y-MP/816Fujitsu VPP 500說明說明總線上假定有總線上假定有n臺(tái)處臺(tái)處理機(jī)；總線寬度為理機(jī)；總線寬度為w位位nn MIN采用采用kk開關(guān)，其線寬為開關(guān)，其線寬為w位位假定假定nn交叉交叉開關(guān)的線寬為開關(guān)的線寬為w位位8484/114/114 當(dāng)源結(jié)點(diǎn)和目的結(jié)點(diǎn)之間沒有直接的連接時(shí)，消息需要經(jīng)過中

59、間的結(jié)點(diǎn)進(jìn)行傳遞。尋徑就是用來實(shí)現(xiàn)這種傳遞的通信方法和算法。有的稱之為路由。9.5 消息傳遞機(jī)制1. 消息的格式 消息：結(jié)點(diǎn)之間進(jìn)行通信的邏輯單位 q由若干個(gè)由若干個(gè)“包包”組成組成q包的長度是固定的，一條消息中所包含的包的個(gè)數(shù)是包的長度是固定的，一條消息中所包含的包的個(gè)數(shù)是可變的，消息的長度是不定長的?？勺兊?，消息的長度是不定長的。 9.5.1 消息尋徑方案8585/114/1149.5 消息傳遞機(jī)制 消息消息 D 包包 片片 D D D D D S R R R：尋徑信息：尋徑信息 S S：順序號：順序號 D D：數(shù)據(jù)片：數(shù)據(jù)片 消息、包和片的格式消息、包和片的格式 8686/114/114

60、9.5 消息傳遞機(jī)制包：包含尋徑所需目的地址的基本單位。q一條消息中的各個(gè)包都依次被分配一個(gè)序號一條消息中的各個(gè)包都依次被分配一個(gè)序號以便這些包到達(dá)目的結(jié)點(diǎn)后能重新組裝出消息。以便這些包到達(dá)目的結(jié)點(diǎn)后能重新組裝出消息。q包可以進(jìn)一步分成一些更小的固定長度的單位，稱包可以進(jìn)一步分成一些更小的固定長度的單位，稱為為“片片”。q尋徑信息和包序列號形成頭片，其余的是數(shù)據(jù)片。尋徑信息和包序列號形成頭片，其余的是數(shù)據(jù)片。q包的長度主要是由尋徑方案和網(wǎng)絡(luò)的具體實(shí)現(xiàn)所決包的長度主要是由尋徑方案和網(wǎng)絡(luò)的具體實(shí)現(xiàn)所決定的定的n典型的長度是典型的長度是64512位不等位不等q片的長度經(jīng)常是受網(wǎng)絡(luò)大小的影響片的長度經(jīng)