計算機體系結構第9章

1、1 1/114/114第9章 互連網(wǎng)絡張晨曦張晨曦 劉依劉依www.GotoS2 2/114/1149.1互連函數(shù)9.2互連網(wǎng)絡的結構參數(shù)與性能指標9.3靜態(tài)互連網(wǎng)絡9.4動態(tài)互連網(wǎng)絡9.5消息傳遞機制3 3/114/114 互連網(wǎng)絡是一種由開關元件按照一定的拓撲結構和控制方式構成的網(wǎng)絡，用來實現(xiàn)計算機系統(tǒng)中結點之間的相互連接。結點：處理器、存儲模塊或其它設備。在拓撲上，互連網(wǎng)絡為輸入結點到輸出結點之間的一組互連或映象。 SIMD計算機和MIMD計算機的關鍵組成部分。 3大要素：互連結構，開關元件，控制方式。 4 4/114/114 變量x：輸入（設x=0，1，N1） 函數(shù)f(x)：輸出 通過

2、數(shù)學表達式建立輸入端號與輸出端號的連接關系。即在互連函數(shù)f的作用下，輸入端x連接到輸出端f(x)?；ミB函數(shù)反映了網(wǎng)絡輸入數(shù)組和輸出數(shù)組之間對應的置換關系或排列關系。（有時也稱為（有時也稱為置換函數(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)的長度。設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ù)主要用于構造立方體互連網(wǎng)絡和各種超立方體互連網(wǎng)絡。它共有nlog2N種互連函數(shù)。 （N N為結點個數(shù)）為結點個數(shù)）當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)絡立方體網(wǎng)絡 000 010 001 011 101 111 100 11

5、0 1010/114/1149.1 互連函數(shù)w均勻洗牌函數(shù)均勻洗牌函數(shù)：將輸入端分成數(shù)目相等的兩半，前一半和后一半按類似均勻混洗撲克牌的方式交叉地連接到輸出端（輸出端相當于混洗的結果）。 q也稱為也稱為混洗函數(shù)（置換）混洗函數(shù)（置換） q函數(shù)關系函數(shù)關系 即把輸入端的二進制編號循環(huán)左移一位。即把輸入端的二進制編號循環(huán)左移一位。101320121nnnnnxxxxxxxxx1111/114/1149.1 互連函數(shù)互連函數(shù)（設為s）的第k個子函數(shù)：把s作用于輸入端的二進制編號的低k位?；ミB函數(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ù) 當N=8時，有： (x2x1x0)x1x0 x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0 -1(x2x1x0)x0 x2x1121001211xxxxxx

8、xxnnnn1414/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/1149.

9、1 互連函數(shù)w碟式函數(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位中的最高位與最低位互換。位中的最高位與最低位互換。11200121nnnnxxxxxxxx1

10、616/114/1149.1 互連函數(shù)下列等式成立 (n)(X)(n)(X) (X) (1)(X)(1)(X) X當N=8時，有： (x2x1x0)x0 x1x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0蝶式變換與交換變換的多級組合可作為構成方體多級網(wǎng)絡的基礎。 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 的

11、蝶式函數(shù)和反位序函數(shù)的蝶式函數(shù)和反位序函數(shù) 1818/114/1149.1 互連函數(shù)w反位序函數(shù) 反位序函數(shù)：將輸入端二進制編號的位序顛倒過來求得相應輸出端的編號。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-k-1x1x0

12、即把輸入端的二進制編號的高即把輸入端的二進制編號的高k位中各位的次序顛倒過來。位中各位的次序顛倒過來。下列等式成立 (n)(X)(n)(X) (X) (1)(X)(1)(X) X當N=8時，有： (x2x1x0)x0 x1x2 (2)(x2x1x0)x2x0 x1 (2)(x2x1x0)x1x2x0w移數(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ù) k k2 2 0

13、 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 2121/114/1149.1 互連函數(shù)wPM2I函數(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為結點數(shù)。為結點數(shù)。PM2I互連網(wǎng)絡共有2n個互連函數(shù)。2222/114/1149.1 互連函數(shù)當N8時，有6個PM2I函數(shù)：qPM

14、2PM2+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） 2323/114/11

15、49.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構成其互連網(wǎng)絡，實現(xiàn)各構成其互連網(wǎng)絡，實現(xiàn)各處理單元之間的上下左右互連處理單元之間的上下左右互連 。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 用移數(shù)函數(shù)構成用移數(shù)函數(shù)構成

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

17、-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 （13）= 13+23

18、= 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連至處理器連至處理器12，而

19、處理器，而處理器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，得，得(1101)= 0111，

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

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

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

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

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

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

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

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

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

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

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

31、環(huán)網(wǎng)形q可看作是直徑更短的另一種網(wǎng)格。可看作是直徑更短的另一種網(wǎng)格。 q把把2維網(wǎng)格形網(wǎng)絡的每一行的兩個端結點連接起來，維網(wǎng)格形網(wǎng)絡的每一行的兩個端結點連接起來，把每一列的兩個端結點也連接起來。把每一列的兩個端結點也連接起來。 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結點度：結點度：4 4n網(wǎng)絡直徑：網(wǎng)絡直徑：2 2 n/2n/2 n等分寬度等分寬度b=2n 4949/114/1149.3 靜態(tài)互連網(wǎng)絡（a a）網(wǎng)格形）網(wǎng)格形（b b）IlliacIlliac網(wǎng)網(wǎng)（c c）環(huán)網(wǎng)形）環(huán)網(wǎng)形5050/11

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

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

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

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

36、iacIlliac網(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個結點，個結點，n=logn=log2 2NN（維數(shù)）（維數(shù)）CCCCCC3 32k-1+k/22k-1+k/23N/23N/2N/(2k)N/(2k)是是N=kN=k2 2k k結點結點環(huán)長環(huán)長k3k3k k元元n-n-立方體立方體2n2nnk/2nk/2nNnN2k2kn-1n-1是是N=kN=kn n個結點個結點靜態(tài)互連網(wǎng)絡特征一覽表靜態(tài)互連網(wǎng)絡特征一

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

38、2） （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)絡 傳送方向為逆時針的傳送方向為逆時針的4個單向環(huán)的循環(huán)互連函數(shù)可表示為：個單向環(huán)的循環(huán)互連函數(shù)可表示為： PM2-2（X）= （X - 22）mod N =（X 4）mod 16 16個處理器由個處

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

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

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

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

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

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

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

46、各級開關之間都有固定的級間連接相鄰各級開關之間都有固定的級間連接9.4.3 多級互連網(wǎng)絡6969/114/1149.4 動態(tài)互連網(wǎng)絡7070/114/1149.4 動態(tài)互連網(wǎng)絡幾種常用的開關模塊 模塊大小模塊大小 合法狀態(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)絡最簡單的開關模塊：22開關 22開關的4種連接方式 7272/114/1149.4 動態(tài)互連網(wǎng)絡各種多級互連網(wǎng)絡的區(qū)別在于所用

47、開關模塊、控制方式和級間互連模式的不同。q控制方式控制方式：對各個開關模塊進行控制的方式。：對各個開關模塊進行控制的方式。n級控制：級控制：每一級的所有開關只用一個控制信號每一級的所有開關只用一個控制信號控制，只能同時處于同一種狀態(tài)?？刂疲荒芡瑫r處于同一種狀態(tài)。n單元控制：單元控制：每一個開關都有一個獨立的控制信每一個開關都有一個獨立的控制信號，可各自處于不同的狀態(tài)。號，可各自處于不同的狀態(tài)。n部分級控制：部分級控制：第第i i級的所有開關分別用級的所有開關分別用i i1 1個信個信號控制，號控制，0in0in1 1，n n為級數(shù)。為級數(shù)。 q常用的級間互連模式：常用的級間互連模式：均勻洗牌

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

49、個開關。一個8個入端的多級立方體網(wǎng)絡7474/114/1149.4 動態(tài)互連網(wǎng)絡 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)絡多級立方體網(wǎng)絡 7575/114/1149.4 動態(tài)互連網(wǎng)絡STARAN網(wǎng)絡采用級控制和部分級控制。q采用級控制時，所實現(xiàn)的是交換功能；采用級控制時，

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

51、 元交換元交換 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)絡3級STARAN網(wǎng)絡在各種級控制信號的情況下所實現(xiàn)的入出端連接以及所實現(xiàn)的交換函數(shù)和功能。其中：其中：qK2k1k0：控制信號，：控制信號，ki（i=0，1，2）為第）為第i級的級控級的級控制信號。制信號。q從表中可以看出從表中可以看出 下面的下面的4行中每一行所實現(xiàn)的功能可以從級控制行中每一行所實現(xiàn)的功能可以從級控制信號為其反碼的一行中所實現(xiàn)的功能加上信號為其反碼的一行中所實現(xiàn)的

52、功能加上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 6 7 4 54組組2元交換元交換2組組4元交換元交換Cube10113 2

53、 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當STARAN網(wǎng)絡用作移數(shù)網(wǎng)絡時，采用部分級控制，控制信號的分組和控制結果。部分級控制信號部分級控制信號連接的輸出端號序列連接的輸出端號序列（入端號序列

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 6 7 0 12 3 4 5 6 7 0 14 5 6 7 0 1 2 34

55、 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不移不移 全等全等wOmega網(wǎng)絡 一個88的Omega網(wǎng)絡q每級由每級由4個個4功能的功能的22開關構成開關構成q級間互連采用均勻洗牌連接

56、方式級間互連采用均勻洗牌連接方式 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)絡一個N輸入的Omega網(wǎng)絡q有有l(wèi)og2N級，每級用級，每級用N/2個個22開關模塊，共需要開關模塊，共需要Nlog2N/2個開關。個開關。q每個開關模塊均采用單元控制方式。每個開關模塊均采用單元控制方式。q不同的開關狀態(tài)組合可實現(xiàn)各種置換、廣播或從輸不同的開關狀態(tài)組合可實現(xiàn)各種置換、廣播或從輸入到輸出的其它連接。入到輸出的其它連接。N=8的多級立方體互連網(wǎng)絡

57、的另一種畫法 8282/114/1149.4 動態(tài)互連網(wǎng)絡0011223344556677ABCDEGFHIJKL級級0級級1級級28383/114/1149.4 動態(tài)互連網(wǎng)絡9.4.4 動態(tài)互連網(wǎng)絡的比較網(wǎng)絡特性網(wǎng)絡特性總線系統(tǒng)總線系統(tǒng)多級網(wǎng)絡多級網(wǎng)絡交叉開關交叉開關單位數(shù)據(jù)傳送的單位數(shù)據(jù)傳送的最小時延最小時延恒定恒定O(logkn)恒定恒定每臺處理機的帶寬每臺處理機的帶寬O(w/n)至至O(w)O(w)至至O(nw)O(w)至至O(nw)連線復雜性連線復雜性O(w)O(nwlogkn)O(n2w)開關復雜性開關復雜性O(n)O(nlogkn)O(n2)連接特性和尋徑性能連接特性和尋徑性能一

58、次只能一對一一次只能一對一只要網(wǎng)絡不阻塞，只要網(wǎng)絡不阻塞，可實現(xiàn)某些置換和廣播可實現(xiàn)某些置換和廣播全置換，全置換，一次一個一次一個典型計算機典型計算機Symmetry S1，Encore MultimaxBBNTC-2000IBM RP3Cray Y-MP/816Fujitsu VPP 500說明說明總線上假定有總線上假定有n臺處臺處理機；總線寬度為理機；總線寬度為w位位nn MIN采用采用kk開關，其線寬為開關，其線寬為w位位假定假定nn交叉交叉開關的線寬為開關的線寬為w位位8484/114/114 當源結點和目的結點之間沒有直接的連接時，消息需要經(jīng)過中間的結點進行傳遞。尋徑就是用來實現(xiàn)這種

59、傳遞的通信方法和算法。有的稱之為路由。9.5 消息傳遞機制1. 消息的格式 消息：結點之間進行通信的邏輯單位 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ù)片 消息、包和片的格式消息、包和片的格式 8686/114/1149.5 消息傳遞機制包：包含尋徑所需目

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