第7章 互連網(wǎng)絡計算機組成與結構

第7章互連網(wǎng)絡7.1 互連函數(shù)7.2 互連網(wǎng)絡的結構參數(shù)與性能指標7.3 靜態(tài)互連網(wǎng)絡7.4 動態(tài)互連網(wǎng)絡7.5 消息傳遞機制

互連網(wǎng)絡是一種由開關元件按照一定的拓撲結構和控制方式構成的網(wǎng)絡，用來實現(xiàn)計算機系統(tǒng)中節(jié)點之間的相互連接。節(jié)點：處理器、存儲模塊或其他設備。在拓撲上，互連網(wǎng)絡為輸入節(jié)點到輸出節(jié)點之間的一組互連或映射。SIMD計算機和MIMD計算機的關鍵組成部分。

3大要素：互連結構，開關元件，控制方式。

變量x：輸入（設x=0，1，…，N－1）

函數(shù)f(x)：輸出

通過數(shù)學表達式建立輸入端號與輸出端號的連接關系。即在互連函數(shù)f的作用下，輸入端x連接到輸出端f(x)?；ミB函數(shù)反映了網(wǎng)絡輸入數(shù)組和輸出數(shù)組之間對應的置換關系或排列關系。（有時也稱為置換函數(shù)或排列函數(shù)）7.1.1互連函數(shù)7.1互連函數(shù)7.1互連函數(shù)互連函數(shù)f(x)有時可以采用循環(huán)表示即：（x0x1x2

…xj-1）表示：f(x0)=x1，f(x1)=x2，…，f(xj-1)=x0

j稱為該循環(huán)的長度。設n=log2N，則可以用n位二進制來表示N個輸入端和輸出端的二進制地址，互連函數(shù)表示為：

f（xn-1xn-2…x1x0）7.1互連函數(shù)介紹幾種常用的基本互連函數(shù)及其主要特征。恒等函數(shù)恒等函數(shù)：實現(xiàn)同號輸入端和輸出端之間的連接。

I（xn-1xn-2…x1x0）=xn-1xn-2…x1x0

交換函數(shù)交換函數(shù)：實現(xiàn)二進制地址編碼中第k位互反的輸入端與輸出端之間的連接。7.1.2幾種基本的互連函數(shù)7.1互連函數(shù)主要用于構造立方體互連網(wǎng)絡和各種超立方體互連網(wǎng)絡。它共有n＝log2N種互連函數(shù)。

（N為節(jié)點個數(shù)）當N＝8時，n＝3，可得到常用的立方體互連函數(shù)：7.1互連函數(shù)變換圖形N=8的立方體交換函數(shù)

7.1互連函數(shù)立方體網(wǎng)絡7.1互連函數(shù)均勻洗牌函數(shù)均勻洗牌函數(shù)：將輸入端分成數(shù)目相等的兩半，前一半和后一半按類似均勻混洗撲克牌的方式交叉地連接到輸出端（輸出端相當于混洗的結果）。

也稱為混洗函數(shù)（置換）

函數(shù)關系

即把輸入端的二進制編號循環(huán)左移一位。7.1互連函數(shù)互連函數(shù)（設為s）的第k個子函數(shù)：把s作用于輸入端的二進制編號的低k位。互連函數(shù)（設為s）的第k個超函數(shù)：把s作用于輸入端的二進制編號的高k位。例如：對于均勻洗牌函數(shù)第k個子函數(shù)：σ(k)(xn-1…xk┆xk-1xk-2…x0)＝xn-1…xk┆xk-2…x0xk-1

即把輸入端的二進制編號中的低k位循環(huán)左移一位。第k個超函數(shù)：σ(k)(xn-1xn-2…xn-k┆xn-k-1…x1x0)＝xn-2…xn-kxn-1┆xn-k-1…x1x0

即把輸入端的二進制編號中的高k位循環(huán)左移一位。7.1互連函數(shù)

下列等式成立：

σ(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)右移一位而得到所連接的輸出端編號。7.1互連函數(shù)互連函數(shù)逆均勻洗牌是均勻洗牌的逆函數(shù)當N=8時，有：

σ(x2x1x0)＝x1x0x2σ(2)(x2x1x0)＝x2x0x1σ(2)(x2x1x0)＝x1x2x0σ-1(x2x1x0)＝x0x2x17.1互連函數(shù)N=8

的均勻洗牌和逆均勻洗牌函數(shù)

N=8的均勻洗牌函數(shù)7.1互連函數(shù)碟式函數(shù)

蝶式互連函數(shù)：把輸入端的二進制編號的最高位與最低位互換位置，便得到了輸出端的編號。

第k個子函數(shù)

β(k)(xn-1…xkxk-1xk-2…x1x0)＝xn-1…xkx0xk-2…x1xk-1

把輸入端的二進制編號的低k位中的最高位與最低位互換。第k個超函數(shù)

β(k)(xn-1xn-2…xn-k+1xn-kxn-k-1…x1x0)＝xn-kxn-2…xn-k+1xn-1xn-k-1…x1x0

把輸入端的二進制編號的高k位中的最高位與最低位互換。7.1互連函數(shù)下列等式成立

β(n)(X)＝β(n)(X)＝β(X)β(1)(X)＝β(1)(X)＝X當N=8時，有：

β(x2x1x0)＝x0x1x2β(2)(x2x1x0)＝x2x0x1β(2)(x2x1x0)＝x1x2x0蝶式變換與交換變換的多級組合可作為構成方體多級網(wǎng)絡的基礎。7.1互連函數(shù)N=8的蝶式函數(shù)和反位序函數(shù)7.1互連函數(shù)反位序函數(shù)反位序函數(shù)：將輸入端二進制編號的位序顛倒過來求得相應輸出端的編號?；ミB函數(shù)第k個子函數(shù)

ρ(k)(xn-1…xkxk-1xk-2…x1x0)＝xn-1…xkx0x1…xk-2xk-1即把輸入端的二進制編號的低k位中各位的次序顛倒過來。7.1互連函數(shù)第k個超函數(shù)

ρ(k)(xn-1xn-2…xn-k+1xn-kxn-k-1…x1x0)＝xn-kxn-k+1…xn-2xn-1xn-k-1…x1x0即把輸入端的二進制編號的高k位中各位的次序顛倒過來。下列等式成立

ρ(n)(X)＝ρ(n)(X)＝ρ(X)ρ(1)(X)＝ρ(1)(X)＝X當N=8時，有：

ρ(x2x1x0)＝x0x1x2ρ(2)(x2x1x0)＝x2x0x1ρ(2)(x2x1x0)＝x1x2x0移數(shù)函數(shù)移數(shù)函數(shù)：將各輸入端都錯開一定的位置（模N）后連到輸出端。函數(shù)式

α(x)=（x±k）modN1≤x≤N-1，1≤k≤N-1

7.1互連函數(shù)PM2I函數(shù)P和M分別表示加和減，2I表示2i。該函數(shù)又稱為“加減2i”函數(shù)。

PM2I函數(shù)：一種移數(shù)函數(shù)，將各輸入端都錯開一定的位置（模N）后連到輸出端。互連函數(shù)

PM2+i(x)＝x＋2imodNPM2-i(x)＝x－2imodN其中：

0≤x≤N－1，0≤i≤n－1，n＝log2N，N為節(jié)點數(shù)。PM2I互連網(wǎng)絡共有2n個互連函數(shù)。7.1互連函數(shù)當N＝8時，有6個PM2I函數(shù)：PM2+0

：（01234567）PM2-0

：（76543210）PM2+1

：（0246）（1357）PM2-1

：（6420）（7531）PM2+2：（04）（15）（26）（37）

PM2-2：（40）（51）（62）（73）

7.1互連函數(shù)N=8的PM2I函數(shù)陣列計算機ILLIACⅣ

采用PM2±0和PM2±n/2構成其互連網(wǎng)絡，實現(xiàn)各處理單元之間的上下左右互連。用移數(shù)函數(shù)構成ILLIACⅣ陣列機的互連網(wǎng)絡7.1互連函數(shù)

例7.1現(xiàn)有16個處理器，編號分別為0，1，…，15，用一個N=16的互連網(wǎng)絡互連。處理器i的輸出通道連接互連網(wǎng)絡的輸入端i，處理器i的輸入通道連接互連網(wǎng)絡的輸出端i。當該互連網(wǎng)絡實現(xiàn)的互連函數(shù)分別為：（1）Cube3

（2）PM2+3

（3）PM2-0

（4）σ

（5）σ(σ)時，分別給出與第13號處理器所連接的處理器號。7.1互連函數(shù)

解：（1）由，得Cube3（1101）=0101，即處理器13連接到處理器5。令Cube3（x3x2x1x0

）=1101，得x3x2x1x0=0101，故與處理器13相連的是處理器5。所以處理器13與處理器5雙向互連。（2）由PM2+3=j+23mod16，得PM2+3

（13）=13+23=5，即處理器13連接到處理器5。令PM2+3（j）=j+23mod16=13，得j=5，故與處理器13相連的是處理器5。所以處理器13與處理器5雙向互連。（3）由PM2-0（j）=j-20mod16，得PM2-0（13）=13-20=12，即處理器13連接到處理器12。令PM2-0（j）=j-20mod16=13，得j=14，故與處理器13相連的是處理器14。所以處理器13連至處理器12，而處理器14連至處理器13。7.1互連函數(shù)

（4）由σ(x3x2x1x0)=x2x1x0x3，得σ(1101)=1011，即處理器13連接到處理器11。令σ(x3x2x1x0)=1101，得x3x2x1x0=1110，故與處理器13相連的是處理器14。所以處理器13連至處理器11，而處理器14連至處理器13。（5）由σ(σ(x3x2x1x0))=x1x0x3x2，得σ(σ(1101))=0111，即處理器13連接到處理器7。令σ(σ(x3x2x1x0))=1101，得x3x2x1x0=0111，故與處理器13相連的是處理器7。所以處理器13與處理器7雙向互連。網(wǎng)絡通常是用有向邊或無向邊連接有限個節(jié)點的圖來表示?；ミB網(wǎng)絡的主要特性參數(shù)有：網(wǎng)絡規(guī)模N：網(wǎng)絡中節(jié)點的個數(shù)。表示該網(wǎng)絡所能連接的部件的數(shù)量。節(jié)點度d：與節(jié)點相連接的邊數(shù)（通道數(shù)），包括入度和出度。7.2互連網(wǎng)絡的結構參數(shù)與性能指標7.2.1互連網(wǎng)絡的結構參數(shù)7.2互連網(wǎng)絡的結構參數(shù)與性能指標進入節(jié)點的邊數(shù)叫入度。從節(jié)點出來的邊數(shù)叫出度。節(jié)點距離：對于網(wǎng)絡中的任意兩個節(jié)點，從一個節(jié)點出發(fā)到另一個節(jié)點終止所需要跨越的邊數(shù)的最小值。網(wǎng)絡直徑D：網(wǎng)絡中任意兩個節(jié)點之間距離的最大值。網(wǎng)絡直徑應當盡可能地小。等分寬度b：把由N個節(jié)點構成的網(wǎng)絡切成節(jié)點數(shù)相同（N/2）的兩半，在各種切法中，沿切口邊數(shù)的最小值。7.2互連網(wǎng)絡的結構參數(shù)與性能指標線等分寬度：B＝b×w其中：w為通道寬度（用位表示）該參數(shù)主要反映了網(wǎng)絡最大流量。對稱性：從任何節(jié)點看到的拓撲結構都是相同的網(wǎng)絡稱為對稱網(wǎng)絡。對稱網(wǎng)絡比較容易實現(xiàn)，編程也比較容易。7.2互連網(wǎng)絡的結構參數(shù)與性能指標評估互連網(wǎng)絡性能的兩個基本指標：時延和帶寬通信時延指從源節(jié)點到目的節(jié)點傳送一條消息所需的總時間，它由以下4部分構成：軟件開銷：在源節(jié)點和目的節(jié)點用于收發(fā)消息的軟件所需的執(zhí)行時間。主要取決于兩端端節(jié)點處理消息的軟件內(nèi)核。通道時延：通過通道傳送消息所花的時間。通路時延=消息長度/通道帶寬通常由瓶頸鏈路的通道帶寬決定。7.2.2互連網(wǎng)絡的性能指標7.2互連網(wǎng)絡的結構參數(shù)與性能指標選路時延：消息在傳送路徑上所需的一系列選路決策所需的時間開銷。與傳送路徑上的節(jié)點數(shù)成正比。競爭時延：多個消息同時在網(wǎng)絡中傳送時，會發(fā)生爭用網(wǎng)絡資源的沖突。為避免或解決爭用沖突所需的時間就是競爭時延。很難預測，它取決于網(wǎng)絡的傳輸狀態(tài)。網(wǎng)絡時延通道時延與選路時延的和。它是由網(wǎng)絡硬件特征決定的，與程序行為和網(wǎng)絡傳輸狀態(tài)無關。7.2互連網(wǎng)絡的結構參數(shù)與性能指標端口帶寬對于互連網(wǎng)絡中的任意一個端口來說，其端口帶寬是指單位時間內(nèi)從該端口傳送到其他端口的最大信息量。在對稱網(wǎng)絡中，端口帶寬與端口位置無關。網(wǎng)絡的端口帶寬與各端口的端口帶寬相同。非對稱網(wǎng)絡的端口帶寬則是指所有端口帶寬的最小值。聚集帶寬網(wǎng)絡從一半節(jié)點到另一半節(jié)點，單位時間內(nèi)能夠傳送的最大信息量。7.2互連網(wǎng)絡的結構參數(shù)與性能指標

例如，HPS是一種對稱網(wǎng)絡網(wǎng)絡規(guī)模N的上限：512

端口帶寬：40MB/sHPS的聚集帶寬：（40MB/s×512）/2＝10.24GB/s

等分帶寬與等分寬度對應的切平面中，所有邊合起來單位時間所能傳送的最大信息量。互連網(wǎng)絡通?？梢苑譃閮纱箢悾红o態(tài)互連網(wǎng)絡各節(jié)點之間有固定的連接通路、且在運行中不能改變的網(wǎng)絡。動態(tài)互連網(wǎng)絡由交換開關構成、可按運行程序的要求動態(tài)地改變連接狀態(tài)的網(wǎng)絡。下面介紹幾種靜態(tài)互連網(wǎng)絡。（其中：N表示節(jié)點的個數(shù)）7.3靜態(tài)互連網(wǎng)絡7.3靜態(tài)互連網(wǎng)絡線性陣列一種一維的線性網(wǎng)絡，其中N個節(jié)點用N-1個鏈路連成一行。端節(jié)點的度：1其余節(jié)點的度：2直徑：N－1等分寬度b=1

7.3靜態(tài)互連網(wǎng)絡7.3靜態(tài)互連網(wǎng)絡對稱節(jié)點的度：2雙向環(huán)的直徑：N/2單向環(huán)的直徑：N

環(huán)的等分寬度b=2

環(huán)和帶弦環(huán)環(huán)用一條附加鏈路將線性陣列的兩個端點連接起來而構成?？梢詥蜗蚬ぷ?，也可以雙向工作。7.3靜態(tài)互連網(wǎng)絡帶弦環(huán)增加的鏈路愈多，節(jié)點度愈高，網(wǎng)絡直徑就愈小。7.3靜態(tài)互連網(wǎng)絡全連接網(wǎng)絡

節(jié)點度：15直徑最短，為1。循環(huán)移數(shù)網(wǎng)絡通過在環(huán)上每個節(jié)點到所有與其距離為2的整數(shù)冪的節(jié)點之間都增加一條附加鏈而構成。N=16節(jié)點度：7直徑：2

7.3靜態(tài)互連網(wǎng)絡一般地，如果｜j-i｜=2r（r=0,1,2,…,n-1，n=log2N），則節(jié)點i與節(jié)點j連接。節(jié)點度：2n－1直徑：n/2網(wǎng)絡規(guī)模N=2n7.3靜態(tài)互連網(wǎng)絡樹形和星形一棵5層31個節(jié)點的二叉樹一般說來，一棵k層完全平衡的二叉樹有N=2k-1個節(jié)點。最大節(jié)點度：3直徑：2(k-1)等分寬度b=1

星形

節(jié)點度較高，為N－1。直徑較小，是一常數(shù)2。等分寬度b=

N/2

可靠性比較差，只要中心節(jié)點出故障，整個系統(tǒng)就會癱瘓。

7.3靜態(tài)互連網(wǎng)絡7.3靜態(tài)互連網(wǎng)絡胖樹形7.3靜態(tài)互連網(wǎng)絡網(wǎng)格形和環(huán)網(wǎng)形網(wǎng)格形一個3×3的網(wǎng)格形網(wǎng)絡一個規(guī)模為N=n×n的2維網(wǎng)格形網(wǎng)絡內(nèi)部節(jié)點的度d=4邊節(jié)點的度d=3角節(jié)點的度d=2網(wǎng)絡直徑D=2（n-1）等分寬度b=n一個由N=nk

個節(jié)點構成的k維網(wǎng)格形網(wǎng)絡（每維n個節(jié)點）的內(nèi)部節(jié)點度d=2k，網(wǎng)絡直徑D=k(n-1)

。7.3靜態(tài)互連網(wǎng)絡Illiac網(wǎng)絡

名稱來源于采用了這種網(wǎng)絡的IlliacⅣ計算機

把2維網(wǎng)格形網(wǎng)絡的每一列的兩個端節(jié)點連接起來，再把每一行的尾節(jié)點與下一行的頭節(jié)點連接起來，并把最后一行的尾節(jié)點與第一行的頭節(jié)點連接起來。一個規(guī)模為n×n的Illiac網(wǎng)絡所有節(jié)點的度d=4網(wǎng)絡直徑D=n-1Illiac網(wǎng)絡的直徑只有純網(wǎng)格形網(wǎng)絡直徑的一半。等分寬度：2n7.3靜態(tài)互連網(wǎng)絡環(huán)網(wǎng)形可看作是直徑更短的另一種網(wǎng)格。把2維網(wǎng)格形網(wǎng)絡的每一行的兩個端節(jié)點連接起來，把每一列的兩個端節(jié)點也連接起來。將環(huán)形和網(wǎng)格形組合在一起，并能向高維擴展。一個n×n的環(huán)網(wǎng)形網(wǎng)節(jié)點度：4網(wǎng)絡直徑：2×

n/2

等分寬度b=2n7.3靜態(tài)互連網(wǎng)絡（a）網(wǎng)格形（b）Illiac網(wǎng)（c）環(huán)網(wǎng)形7.3靜態(tài)互連網(wǎng)絡超立方體一種二元n-立方體結構一般來說，一個二元n-立方體由N=2n

個節(jié)點組成，它們分布在n維上，每維有兩個節(jié)點。

例

8個節(jié)點的3維立方體

4維立方體為實現(xiàn)一個n-立方體，只要把兩個（n－1）立方體中相對應的節(jié)點用鏈路連接起來即可。共需要2n-1條鏈路。n-立方體中節(jié)點的度都是n，直徑也是n，等分寬度為b=N/2

。

7.3靜態(tài)互連網(wǎng)絡7.3靜態(tài)互連網(wǎng)絡帶環(huán)立方體（簡稱3-CCC）

把3-立方體的每個節(jié)點換成一個由3個節(jié)點構成的環(huán)而形成的。帶環(huán)k-立方體（簡稱k-CCC）k-立方體的變形，它是通過用k個節(jié)點構成的環(huán)取代k-立方體中的每個節(jié)點而形成的。網(wǎng)絡規(guī)模為N=k×2k網(wǎng)絡直徑為D=2k-1+

k/2

比k-立方體的直徑大一倍等分寬度為b=N/（2k）7.3靜態(tài)互連網(wǎng)絡1234

k

k-15k

k-112345(b)將k-立方體的每個節(jié)點用由k個節(jié)點的環(huán)來代替，組成帶環(huán)k-立方體組成7.3靜態(tài)互連網(wǎng)絡k元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ù)，即每一維上的節(jié)點個數(shù)。

N=kn，（，n=logkN）k元n-立方體的節(jié)點可以用基數(shù)為k的n位地址A=a1a2…an來表示。其中ai表示該節(jié)點在第i維上的位置通常把低維k元n-立方體稱為環(huán)網(wǎng)，而把高維k元n-立方體稱為超立方體。7.3靜態(tài)互連網(wǎng)絡4元3-立方體網(wǎng)絡

網(wǎng)絡類型節(jié)點度d網(wǎng)絡直徑D鏈路數(shù)l等分寬度B對稱性網(wǎng)絡規(guī)格說明線線陣列2N-1N-11非N個節(jié)點環(huán)形2[N/2]N2是N個節(jié)點全連接N-11N(N-1)/2(N/2)2是N個節(jié)點二叉樹32(h-1)N-11非樹高h=[log2N]星形N-12N-1[N/2]非N個節(jié)點2D網(wǎng)格42(r-1)2N-2rr非r×r網(wǎng)格，Illiac網(wǎng)4r-12N2r非與的帶弦環(huán)等效

2D環(huán)網(wǎng)42[r/2]2N2r是r×r環(huán)網(wǎng)，超立方體nnnN/2N/2是N個節(jié)點，n=[log2N]（維數(shù)）CCC32k-1+[k/2]3N/2N/(2k)是N=k×2k節(jié)點環(huán)長k≥3k元n-立方體2nn[k/2]nN2kn-1是N=kn個節(jié)點靜態(tài)互連網(wǎng)絡特征一覽表

7.3靜態(tài)互連網(wǎng)絡

例7.2已知有16臺個處理器用Illiac網(wǎng)絡互連，寫出Illiac網(wǎng)絡的互連函數(shù)，給出表示任何一個處理器PUi（0≤i≤15）與其他處理器直接互連的一般表達式。解：Illiac網(wǎng)絡連接的節(jié)點數(shù)N=16，組成4×4的陣列。每一列的4個處理器互連為一個雙向環(huán)，第1列～第4列的雙向環(huán)可分別用循環(huán)互連函數(shù)表示為：（04812） （12840）（15913） （13951）（261014） （141062）（371115） （151173）其中，傳送方向為順時針的4個單向環(huán)的循環(huán)互連函數(shù)可表示為：

PM2+2（X）=（X+22）modN=（X+4）mod167.3靜態(tài)互連網(wǎng)絡

傳送方向為逆時針的4個單向環(huán)的循環(huán)互連函數(shù)可表示為：

PM2-2（X）=（X-22）modN=（X–4）mod1616個處理器由Illiac網(wǎng)絡的水平螺線互連為一個雙向環(huán)，用循環(huán)互連函數(shù)表示為：（0123456789101112131415）（1514131211109876543210）其中，傳送方向為順時針的單向環(huán)的循環(huán)互連函數(shù)可表示為：

PM2+0（X）=（X+20）modN=（X+1）mod16

傳送方向為逆時針的單向環(huán)的循環(huán)互連函數(shù)可表示為：

PM2-0（X）=（X–20）modN=（X–1）mod16所以，N=16的Illiac網(wǎng)絡的互連函數(shù)有4個：

PM2±0（X）和PM2±2（X）7.3靜態(tài)互連網(wǎng)絡由互連函數(shù)可得任何一個處理器i直接與下述4個處理器雙向互連：

i±1mod16i±4mod16由一組導線和插座構成，經(jīng)常被用來實現(xiàn)計算機系統(tǒng)中處理機模塊、存儲模塊和外圍設備等之間的互連。每一次總線只能用于一個源（主部件）到一個或多個目的（從部件）之間的數(shù)據(jù)傳送。多個功能模塊之間的爭用總線或時分總線特點結構簡單、實現(xiàn)成本低、帶寬較窄7.4.1總線網(wǎng)絡7.4動態(tài)互連網(wǎng)絡7.4動態(tài)互連網(wǎng)絡一種由總線連接的多處理機系統(tǒng)7.4動態(tài)互連網(wǎng)絡系統(tǒng)總線在處理機、I/O子系統(tǒng)、主存儲器以及輔助存儲設備（磁盤、磁帶機等）之間提供了一條公用通路。系統(tǒng)總線通常設置在印刷電路板底板上。處理器板、存儲器板和設備接口板都通過插座或電纜插入底板。解決總線帶寬較窄問題：采用多總線或多層次的總線多總線是設置多條總線有兩種做法：為不同的功能設置專門的總線重復設置相同功能的總線多層次的總線是按層次的架構設置速度不同的總線，使得不同速度的模塊有比較適合的總線連接。7.4動態(tài)互連網(wǎng)絡單級開關網(wǎng)絡交叉點開關能在對偶（源、目的）之間形成動態(tài)連接，同時實現(xiàn)多個對偶之間的無阻塞連接。帶寬和互連特性最好。一個n×n的交叉開關網(wǎng)絡，可以無阻塞地實現(xiàn)n!種置換。對一個n×n的交叉開關網(wǎng)絡來說，需要n2套交叉點開關以及大量的連線。當n很大時，交叉開關網(wǎng)絡所需要的硬件數(shù)量非常巨大。7.4.2交叉開關網(wǎng)絡7.4動態(tài)互連網(wǎng)絡C.mmp多處理機的互連結構用16×16的交叉開關網(wǎng)絡把16臺PDP-11處理機與16個存儲模塊連在一起最多可同時實現(xiàn)16臺處理機對16個不同存儲模塊的并行訪問每個存儲模塊一次只能滿足一臺處理機的請求當多個請求要同時訪問同一存儲模塊時，交叉開關就必須分解所發(fā)生的沖突，每一列只能接通一個交叉點開關。為了支持并行（或交叉）存儲器訪問，可以在同一行中接通幾個交叉點開關。7.4動態(tài)互連網(wǎng)絡7.4動態(tài)互連網(wǎng)絡Fujitsu公司制造的向量并行處理機VPP500所采用的大型交換開關網(wǎng)絡（224×224）

PE：帶存儲器的處理機CP：控制處理機每一行和每一列只能接通一個交叉點開關7.4動態(tài)互連網(wǎng)絡PE220發(fā)送PE222CP001斷開CP002PE001…PE219PE221PE222PE221PE220PE219PE001CP002CP001接通接收…7.4動態(tài)互連網(wǎng)絡多級互連網(wǎng)絡的構成MIMD和SIMD計算機都采用多級互連網(wǎng)絡MIN（MultistageInterconnectionNetwork）一種通用的多級互連網(wǎng)絡由a×b開關模塊和級間連接構成的通用多級互連網(wǎng)絡結構每一級都用了多個a×b開關a個輸入和b個輸出在理論上，a和b不一定相等，然而實際上a和b經(jīng)常選為2的整數(shù)冪，即a＝b＝2k，k≥1。相鄰各級開關之間都有固定的級間連接7.4.3多級互連網(wǎng)絡7.4動態(tài)互連網(wǎng)絡7.4動態(tài)互連網(wǎng)絡幾種常用的開關模塊模塊大小合法狀態(tài)置換連接2×2424×4256248×81677721640320n×nnn

n!7.4動態(tài)互連網(wǎng)絡最簡單的開關模塊：2×2開關

2×2開關的4種連接方式

7.4動態(tài)互連網(wǎng)絡各種多級互連網(wǎng)絡的區(qū)別在于所用開關模塊、控制方式和級間互連模式的不同?？刂品绞剑簩Ω鱾€開關模塊進行控制的方式。級控制：每一級的所有開關只用一個控制信號控制，只能同時處于同一種狀態(tài)。單元控制：每一個開關都有一個獨立的控制信號，可各自處于不同的狀態(tài)。部分級控制：第i級的所有開關分別用i＋1個信號控制，0≤i≤n－1，n為級數(shù)。常用的級間互連模式：均勻洗牌、蝶式、多路洗牌、縱橫交叉、立方體連接等7.4動態(tài)互連網(wǎng)絡多級立方體網(wǎng)絡多級立方體網(wǎng)絡包括STARAN網(wǎng)絡和間接二進制n方體網(wǎng)絡等。兩者僅在控制方式上不同，在其他方面都是一樣的。都采用二功能（直送和交換）的2×2開關。當?shù)趇級（0≤i≤n-1）交換開關處于交換狀態(tài)時，實現(xiàn)的是Cubei互連函數(shù)。

一個N輸入的多級立方體網(wǎng)絡有l(wèi)og2N級，每級用N/2個2×2開關模塊，共需要log2N×N/2個開關。一個8個入端的多級立方體網(wǎng)絡7.4動態(tài)互連網(wǎng)絡多級立方體網(wǎng)絡

7.4動態(tài)互連網(wǎng)絡STARAN網(wǎng)絡采用級控制和部分級控制。采用級控制時，所實現(xiàn)的是交換功能；采用部分級控制時，則能實現(xiàn)移數(shù)功能。間接二進制n方體網(wǎng)絡則采用單元控制。具有更大的靈活性。交換將有序的一組元素頭尾對稱地進行交換。例如：對于由8個元素構成的組，各種基本交換的圖形：7.4動態(tài)互連網(wǎng)絡8個元素的基本交換圖形7.4動態(tài)互連網(wǎng)絡3級STARAN網(wǎng)絡在各種級控制信號的情況下所實現(xiàn)的入出端連接以及所實現(xiàn)的交換函數(shù)和功能。其中：K2k1k0：控制信號，ki（i=0，1，2）為第i級的級控制信號。從表中可以看出

下面的4行中每一行所實現(xiàn)的功能可以從級控制信號為其反碼的一行中所實現(xiàn)的功能加上1組8元變換來獲得。例如：級控制信號為110所實現(xiàn)的功能是其反碼001所實現(xiàn)的4組2元交換再加上1組8元交換來獲得。

級控制信號k2k1k0連接的輸出端號序列（入端號序列：01234567）實現(xiàn)的分組交換實現(xiàn)的互連函數(shù)00001234567恒等I001103254764組2元交換Cube0010230167454組2元交換＋2組4元交換Cube1011321076542組4元交換Cube0＋Cube1100456701232組4元交換＋1組8元交換Cube2101547610324組2元交換＋2組4元交換＋1組8元交換Cube0＋Cube2110674523014組2元交換＋1組8元交換Cube1＋Cube2111765432101組8元交換Cube0＋Cube1＋Cube2當STARAN網(wǎng)絡用作移數(shù)網(wǎng)絡時，采用部分級控制，控制信號的分組和控制結果。部分級控制信號連接的輸出端號序列（入端號序列：01234567）所實現(xiàn)的移數(shù)功能第0級第1級第2級ABCDEGFHIJKL10010101101100010010011100000110000001000012345670234567014567012312305674230167451032547601234567移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移全等Omega網(wǎng)絡一個8×8的Omega網(wǎng)絡每級由4個4功能的2×2開關構成級間互連采用均勻洗牌連接方式

7.4動態(tài)互連網(wǎng)絡一個N輸入的Omega網(wǎng)絡有l(wèi)og2N級，每級用N/2個2×2開關模塊，共需要Nlog2N/2個開關。每個開關模塊均采用單元控制方式。不同的開關狀態(tài)組合可實現(xiàn)各種置換、廣播或從輸入到輸出的其他連接。N=8的多級立方體互連網(wǎng)絡的另一種畫法7.4動態(tài)互連網(wǎng)絡0011223344556677ABCDEGFHIJKL級0級1級27.4動態(tài)互連網(wǎng)絡7.4.4動態(tài)互連網(wǎng)絡的比較網(wǎng)絡特性總線系統(tǒng)多級網(wǎng)絡交叉開關單位數(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)連接特性和尋徑性能一次只能一對一只要網(wǎng)絡不阻塞，可實現(xiàn)某些置換和廣播全置換，一次一個典型計算機SymmetryS1，EncoreMultimaxBBNTC-2000IBMRP3CrayY-MP/816FujitsuVPP500說明總線上假定有n臺處理機；總線寬度為w位n×nMIN采用k×k開關，其線寬為w位假定n×n交叉開關的線寬為w位

當源節(jié)點和目的節(jié)點之間沒有直接的連接時，消息需要經(jīng)過中間的節(jié)點進行傳遞。尋徑就是用來實現(xiàn)這種傳遞的通信方法和算法。有的稱之為路由。7.5消息傳遞機制消息的格式消息：節(jié)點之間進行通信的邏輯單位由若干個“包”組成包的長度是固定的，一條消息中所包含的包的個數(shù)是可變的，消息的長度是不定長的。7.5.1消息尋徑方案7.5消息傳遞機制消息、包和片的格式

7.5消息傳遞機制包：包含尋徑所需目的地址的基本單位。一條消息中的各個包都依次被分配一個序號以便這些包到達目的節(jié)點后能重新組裝出消息。包可以進一步分成一些更小的固定長度的單位，稱為“片”。尋徑信息和包序列號形成頭片，其余的是數(shù)據(jù)片。包的長度主要是由尋徑方案和網(wǎng)絡的具體實現(xiàn)所決定的典型的長度是64～512位不等片的長度經(jīng)常是受網(wǎng)絡大小的影響7.5消息傳遞機制四種尋徑方式線路交換：在線路交換方式下，在傳遞一個信息之前，需要先建立一條從源節(jié)點到目的節(jié)點的物理通路，然后再傳遞信息。傳輸時延T

其中：L：信息包的長度（位數(shù)）Lt

：建立路徑所需的小信息包的長度D：經(jīng)過的中間節(jié)點個數(shù)B：帶寬7.5消息傳遞機制優(yōu)點：傳輸帶寬較大，平均傳輸時延較小，而且使用的緩沖區(qū)小。適合于具有動態(tài)和突發(fā)性的大規(guī)模并行處理數(shù)據(jù)的傳送。缺點：需要頻繁地建立源節(jié)點到目的節(jié)點的物理通路，時間開銷會很大。存儲轉(zhuǎn)發(fā)：最簡單的分組交換方式。包是信息傳遞的基本單位。包從源節(jié)點經(jīng)過一系列中間節(jié)點到達目的節(jié)點。要求：所經(jīng)過的每個中間節(jié)點都要設置一個包緩沖器，用于保存所傳遞的包。當一個包到達某個中間節(jié)點時，該節(jié)點先把這個包全部存儲起來，然后在出口鏈路可用、而且下一個節(jié)點的包緩沖器也可用的情況下，傳遞給下一個節(jié)點。7.5消息傳遞機制源節(jié)點目的節(jié)點包緩沖……中間節(jié)點（a）存儲轉(zhuǎn)發(fā)源節(jié)點片緩沖……中間節(jié)點目的節(jié)點（b）蟲蝕方式7.5消息傳遞機制網(wǎng)絡的時延與源和目的地之間的距離（跳數(shù)）成正比缺點包緩沖區(qū)大，不利于VLSI實現(xiàn)；網(wǎng)絡時延大，與節(jié)點距離成正比。虛擬直通：對存儲轉(zhuǎn)發(fā)方式的一種改進，減少了網(wǎng)絡時延?；舅枷耄簺]有必要等到信息包全部放入緩沖器后再作路由選擇，只要接收到用作尋徑的包頭，就可作出判斷。7.5消息傳遞機制如果節(jié)點的輸出鏈路空閑，信息包可以不必存儲在該節(jié)點的緩沖器中，而是立即傳送到下一個節(jié)點。如果整條鏈路都空閑，包就可以立即直達目的節(jié)點。在輸出鏈路不空閑時，要用緩沖器進行存儲。通信時延Lh：信息包尋徑頭部的長度一般來說，L>>Lh×（D+1），所以T≈L/B。7.5消息傳遞機制當出現(xiàn)尋徑阻塞時，虛擬直通方式需要將整個信息包全部存儲在尋徑節(jié)點中，要求每個節(jié)點都有足夠大的緩沖區(qū)。（不利于VLSI的實現(xiàn)）蟲蝕方式：把信息包“切割”成更小的單位——“片”，而且使信息包中各片的傳送按流水方式進行。可以減少節(jié)點中緩沖器的容量，縮短傳送延遲時間。在新型的多計算機系統(tǒng)中得到了廣泛的應用。處理的最小信息單位是“片”。當一個節(jié)點把頭片送到下一個節(jié)點后，那么接下來就可以把后面的各個片也依次送出。7.5消息傳遞機制一個節(jié)點一旦開始傳送一個包中的頭片后，這個節(jié)點就必須等待這個包的所有片都送出去后，才能傳送其他包。不同包的片不能混合在一起傳送。與虛擬直通的不同之處當輸出通路忙時，節(jié)點是把一個片存儲到緩沖器中。由于片的大小比包小很多，所以能有效地減少緩沖器的容量，使得它易于用VLSI實現(xiàn)。通信時延Lf：“片”的長度Tf：片經(jīng)過一個節(jié)點所需時間，L>>Lf×D

。7.5消息傳遞機制N1TSFL/B數(shù)據(jù)包頭時間N2N3N4（a）存儲轉(zhuǎn)發(fā)TWHL/BN1N2N3N4時間（b）蟲蝕方式存儲轉(zhuǎn)發(fā)與蟲蝕方式的時間比較

7.5消息傳遞機制優(yōu)點每個節(jié)點的緩沖器較小，易于VLSI實現(xiàn)；有較小的網(wǎng)絡傳輸延遲；通道共享性好，利用率高；易于實現(xiàn)選播和廣播通信模式。缺點當消息的一片被阻塞時，整個消息的所有片都將被阻塞在所在節(jié)點，占用了節(jié)點資源。7.5消息傳遞機制虛擬通道：兩個節(jié)點間的邏輯鏈接，它由源節(jié)點的片緩沖區(qū)、節(jié)點間的物理通道以及接收節(jié)點的片緩沖區(qū)組成。

4條虛擬通道共享一條物理通道源節(jié)點和接收節(jié)點各有4個片緩沖區(qū)。當物理通道分配給某對緩沖區(qū)時，這一對的源緩沖區(qū)和接收緩沖區(qū)就形成了一條虛擬通道。物理通道是由所有的虛擬通道分時地共享。虛擬通道也可以用雙向通道實現(xiàn)。把兩條單向通道組合在一起可以構成一條雙向通道。增加了利用率，使通道的帶寬加倍。7.5.2死鎖與虛擬直通7.5消息傳遞機制物理通道源節(jié)點中的片緩沖區(qū)目的節(jié)點中的片緩沖區(qū)4條虛擬通道以片傳遞為基礎分時地共享一條物理通道7.5消息傳遞機制

避免死鎖緩沖區(qū)或通道上的循環(huán)等待會引起死鎖。例如：圖（a）：出現(xiàn)循環(huán)的通道相關而產(chǎn)生死鎖

圖（b）：利用虛擬通道方法可以避免這個死鎖，可以增加兩條虛擬通道V3和V4。

圖（c）：避免了死鎖增加虛擬通道可能會使每個請求可用的有效通道帶寬降低。為此，當實現(xiàn)數(shù)目很大的虛擬通道時需要用高速的多路選擇開關。7.5消息傳遞機制C4ABDCC1C2C4C3（a）通道死鎖ABDCC1C2（b）增加虛擬通道C4C3V4V3C2V4（c）利用虛擬通道后的通道相關圖C1C3V3利用虛擬通道減少死鎖7.5消息傳遞機制包沖突的解決為了通過通道在兩個相鄰節(jié)點之間傳送一個片，要同時具備3個條件：源緩沖區(qū)已存有該片；通道已分配好；接收緩沖區(qū)準備接收該片。當兩個包到達同一個節(jié)點時，它們可能都在請求同一個接收緩沖器或者同一個輸出通道，這時必須對兩個問題進行仲裁。7.5.3流控制策略把通道分配給哪個包？如何處理被通道拒絕的包？4種解決方案

7.5消息傳遞機制把第二個包暫存在緩沖區(qū)

優(yōu)點:不會浪費已經(jīng)分配了的資源，但它要求節(jié)點中有一個足夠大的緩沖器來存放整個信息包。阻塞第二個包丟棄第二個包有可能會造成嚴重的資源浪費，而且要求重新進行被丟棄包的傳輸與確認。繞道在包尋徑方面提供了更多的靈活性，但為了到達目的節(jié)點，可能要花費超過實際需要的通道資源，造成浪費。7.5消息傳遞機制確定性尋徑和自適應尋徑確定性尋徑：通信路徑完全由源節(jié)點地址和目的地址來決定，也就是說，尋徑路徑是預先唯一地確定好了的，而與網(wǎng)絡的狀況無關。自適應尋徑：通信的通路每一次都要根據(jù)資源或者網(wǎng)絡的情況來選擇?？梢员荛_擁擠的或者有故障的節(jié)點，使網(wǎng)絡的利用率得到改進。兩種確定性尋徑算法都是建立在維序概念之上的對于一個多維網(wǎng)來說，維序?qū)揭髮罄^通道的選擇是按照各維的順序來進行的。7.5消息傳遞機制對于二維的網(wǎng)格網(wǎng)絡來說，這種尋徑方法被稱為X-Y尋徑。先沿X維方向進行尋徑，然后再沿Y維方向?qū)ふ衣窂?。對于超立方體來說，這種尋徑方法被稱為E-cube尋徑。二維網(wǎng)格網(wǎng)絡的X-Y尋徑任意一個源節(jié)點：s=（x1，y1）任意一個目的節(jié)點：d=（x2，y2）從s出發(fā)，先沿X軸方向前進，直到找到d

所在的列x2；然后再沿Y軸方向前進，直到找到目標節(jié)點（x2，y2）。7.5消息傳遞機制

例7.3對于圖所示的二維網(wǎng)格，確定以下4組“源節(jié)點-目的結點”所需要的路經(jīng)。（2，1）到（7，6）（0，7）到（4，5）（6，4）到（2，0）（5，3）到（1，5）解所需要的路徑如圖所示。其中：（2，