計算機系統(tǒng)結(jié)構(gòu)第9章

1、1 1/114/114第9章 互連網(wǎng)絡(luò)張晨曦張晨曦 劉依劉依www.GotoS2 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動態(tài)互連網(wǎng)絡(luò)9.5消息傳遞機制3 3/114/114 互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來實現(xiàn)計算機系統(tǒng)中結(jié)點之間的相互連接。結(jié)點：處理器、存儲模塊或其它設(shè)備。在拓?fù)渖?，互連網(wǎng)絡(luò)為輸入結(jié)點到輸出結(jié)點之間的一組互連或映象。 SIMD計算機和MIMD計算機的關(guān)鍵組成部分。 3大要素：互連結(jié)構(gòu)，開關(guān)元件，控制方式。 4 4/114/114 變量x：輸入（設(shè)x=0，1，N1） 函數(shù)f(x)：輸出 通過

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

3、1149.1 互連函數(shù)介紹幾種常用的基本互連函數(shù)及其主要特征。1. 恒等函數(shù) 恒等函數(shù)：實現(xiàn)同號輸入端和輸出端之間的連接。 I（xn-1xn-2x1x0）=xn-1xn-2x1x0 2. 交換函數(shù) 交換函數(shù)：實現(xià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é)點個數(shù)）為結(jié)點個數(shù)）當(dāng)N8時，n3，可得到常用的立方體互連函數(shù)： 0120122012012101

4、20120 xxxxxxCubexxxxxxCubexxxxxxCube8 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 11

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

6、牌函數(shù)第第k k個子函數(shù)個子函數(shù)：(k(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 即把輸入端的二進制編號中的低即把輸入端的二進制編號中的低k k位循環(huán)左移一位。位循環(huán)左移一位。第第k個超函數(shù)個超函數(shù)：(k)( xn-1xn-2 xn-kxn-k-1 x1x0)xn-2xn-k xn-1xn-k-1x1x0 即把輸入端的二進制編號中的高即把輸入端的二進制編號中的高k位循環(huán)左移一位。位循環(huán)左移一位。1212/114/1149.1 互連函數(shù) 下列等式成立：下列等式

7、成立： (n)(X)(n)(X) (X) (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ù)：將輸入端的二進制編號循環(huán)右移一位而得到所連接的輸出端編號。1313/114/1149.1 互連函數(shù)q互連函數(shù)互連函數(shù)p逆均勻洗牌是均勻洗牌的逆函數(shù)逆均勻洗牌是均勻洗牌的逆函數(shù) 當(dāng)N=8時，有： (x2x1x0)x1x0 x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0 -1(x2x1x0)x0 x2x1121001211xxx

8、xxxxxnnnn1414/114/1149.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/11

9、49.1 互連函數(shù)1. 碟式函數(shù) 蝶式互連函數(shù)：把輸入端的二進制編號的最高位與最低位互換位置，便得到了輸出端的編號。 第k個子函數(shù) (k)(xn-1xkxk-1xk-2x1x0)xn-1xkx0 xk-2x1xk-1 把輸入端的二進制編號的低把輸入端的二進制編號的低k k位中的最高位與最低位互換。位中的最高位與最低位互換。第k個超函數(shù) (k)(xn-1xn-2xn-k+1xn-kxn-k-1x1x0)xn-kxn-2xn-k+1xn-1xn-k-1x1x0 把輸入端的二進制編號的高把輸入端的二進制編號的高k k位中的最高位與最低位互換。位中的最高位與最低位互換。11200121nnnnxxxx

10、xxxx1616/114/1149.1 互連函數(shù)下列等式成立 (n)(X)(n)(X) (X) (1)(X)(1)(X) X當(dāng)N=8時，有： (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

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

12、k-1x1x0即把輸入端的二進制編號的高即把輸入端的二進制編號的高k位中各位的次序顛倒過來。位中各位的次序顛倒過來。下列等式成立 (n)(X)(n)(X) (X) (1)(X)(1)(X) X當(dāng)N=8時，有： (x2x1x0)x0 x1x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x01. 移數(shù)函數(shù)移數(shù)函數(shù)：將各輸入端都錯開一定的位置（模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ù)

13、 k k2 2 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 2121/114/1149.1 互連函數(shù)1. PM2I函數(shù) P和M分別表示加和減，2I表示2i。q該函數(shù)又稱為該函數(shù)又稱為“加減加減2i”函數(shù)函數(shù)。 PM2I函數(shù)：一種移數(shù)函數(shù)，將各輸入端都錯開一定的位置（模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é)點數(shù)。為結(jié)點數(shù)。PM2I互連網(wǎng)絡(luò)共有2n個互連函數(shù)。2222/114/1149.1 互連函數(shù)當(dāng)N8時，有6

14、個PM2I函數(shù)：qPM2PM2+0+0 ：（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）

15、2323/114/1149.1 互連函數(shù)N=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 陣列計算機ILLIAC 采用采用PM2PM20 0和和PM2PM2n/2n/2構(gòu)成其互連網(wǎng)絡(luò)，實現(xiàn)各構(gòu)成其互連網(wǎng)絡(luò)，實現(xiàn)各處理單元之間的上下左右互連處理單元之間的上下左右互連 。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 用移數(shù)

16、函數(shù)構(gòu)成用移數(shù)函數(shù)構(gòu)成ILLIAC ILLIAC 陣列機的互連網(wǎng)絡(luò)陣列機的互連網(wǎng)絡(luò)2525/114/1149.1 互連函數(shù) 例例9.1 9.1 現(xiàn)有現(xiàn)有1616個處理器，編號分別為個處理器，編號分別為0 0，1 1，1515，用一個，用一個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ò)實現(xiàn)。當(dāng)該互連網(wǎng)絡(luò)實現(xiàn)的互連函數(shù)分別為：的互連函數(shù)分別為： （1 1）CubeCube3 3 （2 2）PM2PM2+3+3

17、（3 3）PM2PM2-0-0 （4 4） （5 5）() )時，分別給出與第時，分別給出與第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 （

18、13）= 13+23 = 5， 即處理器即處理器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連至處

19、理器連至處理器12，而處理器，而處理器14連至處理器連至處理器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，得，得(1

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

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

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

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

24、征決定的，與程序行為和網(wǎng)絡(luò)傳輸狀態(tài)無關(guān)。狀態(tài)無關(guān)。 3333/114/1149.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)1. 端口帶寬對于互連網(wǎng)絡(luò)中的任意一個端口來說，其端口帶寬是指單位時間內(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ò)的端口帶寬則是指所有端口帶寬的最小值。2. 聚集帶寬 網(wǎng)絡(luò)從一半結(jié)點到另一半結(jié)點，單位時間內(nèi)能夠傳送的最大信息量。 3434/114/1149.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)

25、與性能指標(biāo) 例如，例如，HPS是一種對稱網(wǎng)絡(luò)是一種對稱網(wǎng)絡(luò) 網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模N的上限：的上限：512 端口帶寬：端口帶寬：40MB/s HPS的聚集帶寬：的聚集帶寬：（40MB/s512）/210.24GB/s 1. 等分帶寬 與等分寬度對應(yīng)的切平面中，所有邊合起來單位時間所能傳送的最大信息量。3535/114/114互連網(wǎng)絡(luò)通常可以分為兩大類：靜態(tài)互連網(wǎng)絡(luò) 各結(jié)點之間有固定的連接通路、且在運行中不能各結(jié)點之間有固定的連接通路、且在運行中不能改變的網(wǎng)絡(luò)。改變的網(wǎng)絡(luò)。動態(tài)互連網(wǎng)絡(luò) 由交換開關(guān)構(gòu)成、可按運行程序的要求動態(tài)地改由交換開關(guān)構(gòu)成、可按運行程序的要求動態(tài)地改變連接狀態(tài)的網(wǎng)絡(luò)。變連接狀態(tài)的網(wǎng)

26、絡(luò)。下面介紹幾種靜態(tài)互連網(wǎng)絡(luò)。 （其中：（其中：N N表示結(jié)點的個數(shù)）表示結(jié)點的個數(shù)） 9.3 靜態(tài)互連網(wǎng)絡(luò)3636/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)1. 線性陣列 一種一維的線性網(wǎng)絡(luò)，其中N個結(jié)點用N-1個鏈路連成一行。q端結(jié)點的度：端結(jié)點的度：1 1q其余結(jié)點的度：其余結(jié)點的度：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é)點的度：結(jié)點的度：2 2q雙向環(huán)的直徑：雙向環(huán)的直徑：N/2N/2q單向環(huán)的直徑：單向環(huán)的直徑：N N q環(huán)的等分寬度環(huán)的等分寬度b=2 1. 環(huán)和

27、帶弦環(huán) 環(huán) 用一條附加鏈路將線性陣列的兩個端點連接起來而構(gòu)成?？梢詥蜗蚬ぷ?，也可以雙向工作。3939/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)帶弦環(huán) 增加的鏈路愈多，結(jié)點度愈高，網(wǎng)絡(luò)直徑就愈小。4040/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)全連接網(wǎng)絡(luò) q結(jié)點度：結(jié)點度：1515q直徑最短，為直徑最短，為1 1。 1. 循環(huán)移數(shù)網(wǎng)絡(luò)通過在環(huán)上每個結(jié)點到所有與其距離為2的整數(shù)冪的結(jié)點之間都增加一條附加鏈而構(gòu)成。N=16N=16q結(jié)點度：結(jié)點度：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é)點i與結(jié)點j連接。q

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

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

30、互連網(wǎng)絡(luò)Illiac網(wǎng)絡(luò) q名稱來源于采用了這種網(wǎng)絡(luò)的名稱來源于采用了這種網(wǎng)絡(luò)的Illiac 計算機計算機 q把把2維網(wǎng)格形網(wǎng)絡(luò)的每一列的兩個端結(jié)點連接起來，維網(wǎng)格形網(wǎng)絡(luò)的每一列的兩個端結(jié)點連接起來，再把每一行的尾結(jié)點與下一行的頭結(jié)點連接起來，并再把每一行的尾結(jié)點與下一行的頭結(jié)點連接起來，并把最后一行的尾結(jié)點與第一行的頭結(jié)點連接起來。把最后一行的尾結(jié)點與第一行的頭結(jié)點連接起來。q一個規(guī)模為一個規(guī)模為nn的的Illiac網(wǎng)絡(luò)網(wǎng)絡(luò)n所有結(jié)點的度所有結(jié)點的度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等分寬度：等分寬

31、度：2n4848/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)環(huán)網(wǎng)形q可看作是直徑更短的另一種網(wǎng)格?？煽醋魇侵睆礁痰牧硪环N網(wǎng)格。 q把把2維網(wǎng)格形網(wǎng)絡(luò)的每一行的兩個端結(jié)點連接起來，維網(wǎng)格形網(wǎng)絡(luò)的每一行的兩個端結(jié)點連接起來，把每一列的兩個端結(jié)點也連接起來。把每一列的兩個端結(jié)點也連接起來。 q將環(huán)形和網(wǎng)格形組合在一起，并能向高維擴展。將環(huán)形和網(wǎng)格形組合在一起，并能向高維擴展。 q一個一個n nn n的的環(huán)網(wǎng)形網(wǎng)環(huán)網(wǎng)形網(wǎng) n結(jié)點度：結(jié)點度：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）IlliacI

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

33、成一個由3個結(jié)點構(gòu)成的環(huán)而形成的。帶環(huán)k-立方體（簡稱k-CCC）qk-立方體的變形，它是通過用立方體的變形，它是通過用k個結(jié)點構(gòu)成的環(huán)取代個結(jié)點構(gòu)成的環(huán)取代k-立方體中的每個結(jié)點而形成的。立方體中的每個結(jié)點而形成的。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-立方體的每個結(jié)點用由立方體的每個結(jié)點用由k k個結(jié)點的個結(jié)點的環(huán)來代替，組成帶環(huán)環(huán)來代替，組成帶環(huán)k-k

34、-立方體組成立方體組成5454/114/1149.3 靜態(tài)互連網(wǎng)絡(luò)1. 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é)點個數(shù)。 N=kn，（，（ ，n=logkN）k元n-立方體的結(jié)點可以用基數(shù)為k的n位地址A =a1a2an來表示。q其中其中ai表示該結(jié)點在第表示該結(jié)點在第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ò) N

35、rNr 網(wǎng)絡(luò)類型網(wǎng)絡(luò)類型結(jié)點度結(jié)點度d d網(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個結(jié)點個結(jié)點環(huán)形環(huán)形2 2N/2N/2N N2 2是是N N個結(jié)點個結(jié)點全連接全連接N-1N-11 1N(N-1)/2N(N-1)/2(N/2)(N/2)2 2是是N N個結(jié)點個結(jié)點二叉樹二叉樹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個結(jié)點個結(jié)點2D2D網(wǎng)格網(wǎng)格4 42(r-1)2(r-

36、1)2N-2r2N-2rr r非非r rr 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個結(jié)點，個結(jié)點，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é)點結(jié)點環(huán)長環(huán)長k3k3k k元元n-n-立方體立方體2n2nnk/2nk/2nNnN2k2kn-1n-1是是N=k

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

38、環(huán)可分別用循環(huán)互連函數(shù)表示為：互連函數(shù)表示為： （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）其中，傳送方向為順時針的其中，傳送方向為順時針的4個單向環(huán)的循環(huán)互連函數(shù)可表示為：個單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2+2（X）= （X + 22）mod N =（X + 4）mod 165858/114/1149.3 靜態(tài)互連網(wǎng)絡(luò) 傳送方向為逆時針的傳送方向為逆時針的4個單向環(huán)的循環(huán)互連函數(shù)可表示為：個單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2-2（X）= （X -

39、 22）mod N =（X 4）mod 16 16個處理器由個處理器由Illiac網(wǎng)絡(luò)的水平螺線互連為一個雙向環(huán)，用循環(huán)網(wǎng)絡(luò)的水平螺線互連為一個雙向環(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）其中，傳送方向為順時針的單向環(huán)的循環(huán)互連函數(shù)可表示為：其中，傳送方向為順時針的單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2+0（X）= （X + 20）mod N =（X + 1）mod 16 傳送方向為逆時針的單向環(huán)的循環(huán)互連函數(shù)可表示為：傳送方向為逆時

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

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

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

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

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

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

46、 2的整數(shù)冪，即的整數(shù)冪，即a ab b2 2k k，k1k1。 q相鄰各級開關(guān)之間都有固定的級間連接相鄰各級開關(guān)之間都有固定的級間連接9.4.3 多級互連網(wǎng)絡(luò)6969/114/1149.4 動態(tài)互連網(wǎng)絡(luò)7070/114/1149.4 動態(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 動態(tài)互連網(wǎng)絡(luò)最簡單的開關(guān)模塊：22開關(guān) 22開關(guān)的4種連接方式 7

47、272/114/1149.4 動態(tài)互連網(wǎng)絡(luò)各種多級互連網(wǎng)絡(luò)的區(qū)別在于所用開關(guān)模塊、控制方式和級間互連模式的不同。q控制方式控制方式：對各個開關(guān)模塊進行控制的方式。：對各個開關(guān)模塊進行控制的方式。n級控制：級控制：每一級的所有開關(guān)只用一個控制信號每一級的所有開關(guān)只用一個控制信號控制，只能同時處于同一種狀態(tài)?？刂?，只能同時處于同一種狀態(tài)。n單元控制：單元控制：每一個開關(guān)都有一個獨立的控制信每一個開關(guān)都有一個獨立的控制信號，可各自處于不同的狀態(tài)。號，可各自處于不同的狀態(tài)。n部分級控制：部分級控制：第第i i級的所有開關(guān)分別用級的所有開關(guān)分別用i i1 1個信個信號控制，號控制，0in0in1 1，n

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

49、立方體網(wǎng)絡(luò)有l(wèi)og2N級，每級用N/2個22開關(guān)模塊，共需要log2NN/2個開關(guān)。一個8個入端的多級立方體網(wǎng)絡(luò)7474/114/1149.4 動態(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 動態(tài)互連網(wǎng)絡(luò)STARAN網(wǎng)

50、絡(luò)采用級控制和部分級控制。q采用級控制時，所實現(xiàn)的是交換功能；采用級控制時，所實現(xiàn)的是交換功能；q采用部分級控制時，則能實現(xiàn)移數(shù)功能。采用部分級控制時，則能實現(xiàn)移數(shù)功能。間接二進制n方體網(wǎng)絡(luò)則采用單元控制。q具有更大的靈活性。具有更大的靈活性。交換q將有序的一組元素頭尾對稱地進行交換。將有序的一組元素頭尾對稱地進行交換。 例如：例如：對于由對于由8 8個元素構(gòu)成的組，各種基本交換的圖形：個元素構(gòu)成的組，各種基本交換的圖形：7676/114/1149.4 動態(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

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

52、可以從級控制信號為其反碼的一行中所實現(xiàn)的功能加上信號為其反碼的一行中所實現(xiàn)的功能加上1組組8元變元變換來獲得。換來獲得。 例如：例如：級控制信號為級控制信號為110所實現(xiàn)的功能是其反碼所實現(xiàn)的功能是其反碼001所實所實現(xiàn)的現(xiàn)的4組組2元交換再加上元交換再加上1組組8元交換來獲得。元交換來獲得。 級控制信號級控制信號k2k1k0連接的輸出端號序列連接的輸出端號序列（入端號序列：（入端號序列：01234567）實現(xiàn)的分組交換實現(xiàn)的分組交換實現(xiàn)的互連函數(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

53、6 7 4 54組組2元交換元交換2組組4元交換元交換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ò)時，采用部分級控制，控制信號的分組和控制結(jié)果。

54、部分級控制信號部分級控制信號連接的輸出端號序列連接的輸出端號序列（入端號序列：（入端號序列：0123456701234567）所實現(xiàn)的移數(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

55、6 7 0 12 3 4 5 6 7 0 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不移不移 全等全等1. Omega網(wǎng)絡(luò) 一個88的Omega網(wǎng)絡(luò)

56、q每級由每級由4個個4功能的功能的22開關(guān)構(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 動態(tài)互連網(wǎng)絡(luò)一個N輸入的Omega網(wǎng)絡(luò)q有有l(wèi)og2N級，每級用級，每級用N/2個個22開關(guān)模塊，共需要開關(guān)模塊，共需要Nlog2N/2個開關(guān)。個開關(guān)。q每個開關(guān)模塊均采用單元控制方式。每個開關(guān)模塊均采用單元控制方式。q不同的開關(guān)狀態(tài)組合可實現(xiàn)各種置換、廣播或從輸不同的開關(guān)狀態(tài)組合可實現(xiàn)各種置

57、換、廣播或從輸入到輸出的其它連接。入到輸出的其它連接。N=8的多級立方體互連網(wǎng)絡(luò)的另一種畫法 8282/114/1149.4 動態(tài)互連網(wǎng)絡(luò)0011223344556677ABCDEGFHIJKL級級0級級1級級28383/114/1149.4 動態(tài)互連網(wǎng)絡(luò)9.4.4 動態(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ù)傳送的最小時延最小時延恒定恒定O(logkn)恒定恒定每臺處理機的帶寬每臺處理機的帶寬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)

58、復(fù)雜性O(shè)(n)O(nlogkn)O(n2)連接特性和尋徑性能連接特性和尋徑性能一次只能一對一一次只能一對一只要網(wǎng)絡(luò)不阻塞，只要網(wǎng)絡(luò)不阻塞，可實現(xiàn)某些置換和廣播可實現(xiàn)某些置換和廣播全置換，全置換，一次一個一次一個典型計算機典型計算機Symmetry S1，Encore MultimaxBBNTC-2000IBM RP3Cray Y-MP/816Fujitsu VPP 500說明說明總線上假定有總線上假定有n臺處臺處理機；總線寬度為理機；總線寬度為w位位nn MIN采用采用kk開關(guān)，其線寬為開關(guān)，其線寬為w位位假定假定nn交叉交叉開關(guān)的線寬為開關(guān)的線寬為w位位8484/114/114 當(dāng)源結(jié)點和目

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

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