第7章 互連網(wǎng)絡(luò)計算機組成與結(jié)構(gòu)

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

互連網(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)元件，控制方式。

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

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

通過數(shù)學(xué)表達(dá)式建立輸入端號與輸出端號的連接關(guān)系。即在互連函數(shù)f的作用下，輸入端x連接到輸出端f(x)。互連函數(shù)反映了網(wǎng)絡(luò)輸入數(shù)組和輸出數(shù)組之間對應(yīng)的置換關(guān)系或排列關(guān)系。（有時也稱為置換函數(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)的長度。設(shè)n=log2N，則可以用n位二進(jìn)制來表示N個輸入端和輸出端的二進(jì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)二進(jìn)制地址編碼中第k位互反的輸入端與輸出端之間的連接。7.1.2幾種基本的互連函數(shù)7.1互連函數(shù)主要用于構(gòu)造立方體互連網(wǎng)絡(luò)和各種超立方體互連網(wǎng)絡(luò)。它共有n＝log2N種互連函數(shù)。

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

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

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

函數(shù)關(guān)系

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

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

即把輸入端的二進(jìn)制編號中的高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ù)：將輸入端的二進(jìn)制編號循環(huán)右移一位而得到所連接的輸出端編號。7.1互連函數(shù)互連函數(shù)逆均勻洗牌是均勻洗牌的逆函數(shù)當(dāng)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ù)：把輸入端的二進(jìn)制編號的最高位與最低位互換位置，便得到了輸出端的編號。

第k個子函數(shù)

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

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

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

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

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

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

ρ(k)(xn-1…xkxk-1xk-2…x1x0)＝xn-1…xkx0x1…xk-2xk-1即把輸入端的二進(jìn)制編號的低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即把輸入端的二進(jìn)制編號的高k位中各位的次序顛倒過來。下列等式成立

ρ(n)(X)＝ρ(n)(X)＝ρ(X)ρ(1)(X)＝ρ(1)(X)＝X當(dāng)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）后連到輸出端?；ミB函數(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)絡(luò)共有2n個互連函數(shù)。7.1互連函數(shù)當(dāng)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構(gòu)成其互連網(wǎng)絡(luò)，實現(xiàn)各處理單元之間的上下左右互連。用移數(shù)函數(shù)構(gòu)成ILLIACⅣ陣列機的互連網(wǎng)絡(luò)7.1互連函數(shù)

例7.1現(xiàn)有16個處理器，編號分別為0，1，…，15，用一個N=16的互連網(wǎng)絡(luò)互連。處理器i的輸出通道連接互連網(wǎng)絡(luò)的輸入端i，處理器i的輸入通道連接互連網(wǎng)絡(luò)的輸出端i。當(dāng)該互連網(wǎng)絡(luò)實現(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)絡(luò)通常是用有向邊或無向邊連接有限個節(jié)點的圖來表示。互連網(wǎng)絡(luò)的主要特性參數(shù)有：網(wǎng)絡(luò)規(guī)模N：網(wǎng)絡(luò)中節(jié)點的個數(shù)。表示該網(wǎng)絡(luò)所能連接的部件的數(shù)量。節(jié)點度d：與節(jié)點相連接的邊數(shù)（通道數(shù)），包括入度和出度。7.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)7.2.1互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)7.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)進(jìn)入節(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)盡可能地小。等分寬度b：把由N個節(jié)點構(gòu)成的網(wǎng)絡(luò)切成節(jié)點數(shù)相同（N/2）的兩半，在各種切法中，沿切口邊數(shù)的最小值。7.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)線等分寬度：B＝b×w其中：w為通道寬度（用位表示）該參數(shù)主要反映了網(wǎng)絡(luò)最大流量。對稱性：從任何節(jié)點看到的拓?fù)浣Y(jié)構(gòu)都是相同的網(wǎng)絡(luò)稱為對稱網(wǎng)絡(luò)。對稱網(wǎng)絡(luò)比較容易實現(xiàn)，編程也比較容易。7.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)評估互連網(wǎng)絡(luò)性能的兩個基本指標(biāo)：時延和帶寬通信時延指從源節(jié)點到目的節(jié)點傳送一條消息所需的總時間，它由以下4部分構(gòu)成：軟件開銷：在源節(jié)點和目的節(jié)點用于收發(fā)消息的軟件所需的執(zhí)行時間。主要取決于兩端端節(jié)點處理消息的軟件內(nèi)核。通道時延：通過通道傳送消息所花的時間。通路時延=消息長度/通道帶寬通常由瓶頸鏈路的通道帶寬決定。7.2.2互連網(wǎng)絡(luò)的性能指標(biāo)7.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)選路時延：消息在傳送路徑上所需的一系列選路決策所需的時間開銷。與傳送路徑上的節(jié)點數(shù)成正比。競爭時延：多個消息同時在網(wǎng)絡(luò)中傳送時，會發(fā)生爭用網(wǎng)絡(luò)資源的沖突。為避免或解決爭用沖突所需的時間就是競爭時延。很難預(yù)測，它取決于網(wǎng)絡(luò)的傳輸狀態(tài)。網(wǎng)絡(luò)時延通道時延與選路時延的和。它是由網(wǎng)絡(luò)硬件特征決定的，與程序行為和網(wǎng)絡(luò)傳輸狀態(tài)無關(guān)。7.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)端口帶寬對于互連網(wǎng)絡(luò)中的任意一個端口來說，其端口帶寬是指單位時間內(nèi)從該端口傳送到其他端口的最大信息量。在對稱網(wǎng)絡(luò)中，端口帶寬與端口位置無關(guān)。網(wǎng)絡(luò)的端口帶寬與各端口的端口帶寬相同。非對稱網(wǎng)絡(luò)的端口帶寬則是指所有端口帶寬的最小值。聚集帶寬網(wǎng)絡(luò)從一半節(jié)點到另一半節(jié)點，單位時間內(nèi)能夠傳送的最大信息量。7.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)

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

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

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

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

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

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

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

7.3靜態(tài)互連網(wǎng)絡(luò)一般地，如果｜j-i｜=2r（r=0,1,2,…,n-1，n=log2N），則節(jié)點i與節(jié)點j連接。節(jié)點度：2n－1直徑：n/2網(wǎng)絡(luò)規(guī)模N=2n7.3靜態(tài)互連網(wǎng)絡(luò)樹形和星形一棵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)絡(luò)7.3靜態(tài)互連網(wǎng)絡(luò)胖樹形7.3靜態(tài)互連網(wǎng)絡(luò)網(wǎng)格形和環(huán)網(wǎng)形網(wǎng)格形一個3×3的網(wǎng)格形網(wǎng)絡(luò)一個規(guī)模為N=n×n的2維網(wǎng)格形網(wǎng)絡(luò)內(nèi)部節(jié)點的度d=4邊節(jié)點的度d=3角節(jié)點的度d=2網(wǎng)絡(luò)直徑D=2（n-1）等分寬度b=n一個由N=nk

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

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

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

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

n/2

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

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

例

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

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

。

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

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

k/2

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

k

k-15k

k-112345(b)將k-立方體的每個節(jié)點用由k個節(jié)點的環(huán)來代替，組成帶環(huán)k-立方體組成7.3靜態(tài)互連網(wǎng)絡(luò)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=a1a2…an來表示。其中ai表示該節(jié)點在第i維上的位置通常把低維k元n-立方體稱為環(huán)網(wǎng)，而把高維k元n-立方體稱為超立方體。7.3靜態(tài)互連網(wǎng)絡(luò)4元3-立方體網(wǎng)絡(luò)

網(wǎng)絡(luò)類型節(jié)點度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度B對稱性網(wǎng)絡(luò)規(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(yuǎn)=[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)絡(luò)特征一覽表

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

例7.2已知有16臺個處理器用Illiac網(wǎng)絡(luò)互連，寫出Illiac網(wǎng)絡(luò)的互連函數(shù)，給出表示任何一個處理器PUi（0≤i≤15）與其他處理器直接互連的一般表達(dá)式。解：Illiac網(wǎng)絡(luò)連接的節(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)絡(luò)

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

PM2-2（X）=（X-22）modN=（X–4）mod1616個處理器由Illiac網(wǎng)絡(luò)的水平螺線互連為一個雙向環(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)絡(luò)的互連函數(shù)有4個：

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

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

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

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

2×2開關(guān)的4種連接方式

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

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

7.4動態(tài)互連網(wǎng)絡(luò)STARAN網(wǎng)絡(luò)采用級控制和部分級控制。采用級控制時，所實現(xiàn)的是交換功能；采用部分級控制時，則能實現(xiàn)移數(shù)功能。間接二進(jìn)制n方體網(wǎng)絡(luò)則采用單元控制。具有更大的靈活性。交換將有序的一組元素頭尾對稱地進(jìn)行交換。例如：對于由8個元素構(gòu)成的組，各種基本交換的圖形：7.4動態(tài)互連網(wǎng)絡(luò)8個元素的基本交換圖形7.4動態(tài)互連網(wǎng)絡(luò)3級STARAN網(wǎng)絡(luò)在各種級控制信號的情況下所實現(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當(dāng)STARAN網(wǎng)絡(luò)用作移數(shù)網(wǎng)絡(luò)時，采用部分級控制，控制信號的分組和控制結(jié)果。部分級控制信號連接的輸出端號序列（入端號序列：01234567）所實現(xiàn)的移數(shù)功能第0級第1級第2級ABCDEGFHIJKL10010101101100010010011100000110000001000012345670234567014567012312305674230167451032547601234567移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移全等Omega網(wǎng)絡(luò)一個8×8的Omega網(wǎng)絡(luò)每級由4個4功能的2×2開關(guān)構(gòu)成級間互連采用均勻洗牌連接方式

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

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

7.5消息傳遞機制包：包含尋徑所需目的地址的基本單位。一條消息中的各個包都依次被分配一個序號以便這些包到達(dá)目的節(jié)點后能重新組裝出消息。包可以進(jìn)一步分成一些更小的固定長度的單位，稱為“片”。尋徑信息和包序列號形成頭片，其余的是數(shù)據(jù)片。包的長度主要是由尋徑方案和網(wǎng)絡(luò)的具體實現(xiàn)所決定的典型的長度是64～512位不等片的長度經(jīng)常是受網(wǎng)絡(luò)大小的影響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é)點到達(dá)目的節(jié)點。要求：所經(jīng)過的每個中間節(jié)點都要設(shè)置一個包緩沖器，用于保存所傳遞的包。當(dāng)一個包到達(dá)某個中間節(jié)點時，該節(jié)點先把這個包全部存儲起來，然后在出口鏈路可用、而且下一個節(jié)點的包緩沖器也可用的情況下，傳遞給下一個節(jié)點。7.5消息傳遞機制源節(jié)點目的節(jié)點包緩沖……中間節(jié)點（a）存儲轉(zhuǎn)發(fā)源節(jié)點片緩沖……中間節(jié)點目的節(jié)點（b）蟲蝕方式7.5消息傳遞機制網(wǎng)絡(luò)的時延與源和目的地之間的距離（跳數(shù)）成正比缺點包緩沖區(qū)大，不利于VLSI實現(xiàn)；網(wǎng)絡(luò)時延大，與節(jié)點距離成正比。虛擬直通：對存儲轉(zhuǎn)發(fā)方式的一種改進(jìn)，減少了網(wǎng)絡(luò)時延。基本思想：沒有必要等到信息包全部放入緩沖器后再作路由選擇，只要接收到用作尋徑的包頭，就可作出判斷。7.5消息傳遞機制如果節(jié)點的輸出鏈路空閑，信息包可以不必存儲在該節(jié)點的緩沖器中，而是立即傳送到下一個節(jié)點。如果整條鏈路都空閑，包就可以立即直達(dá)目的節(jié)點。在輸出鏈路不空閑時，要用緩沖器進(jìn)行存儲。通信時延Lh：信息包尋徑頭部的長度一般來說，L>>Lh×（D+1），所以T≈L/B。7.5消息傳遞機制當(dāng)出現(xiàn)尋徑阻塞時，虛擬直通方式需要將整個信息包全部存儲在尋徑節(jié)點中，要求每個節(jié)點都有足夠大的緩沖區(qū)。（不利于VLSI的實現(xiàn)）蟲蝕方式：把信息包“切割”成更小的單位——“片”，而且使信息包中各片的傳送按流水方式進(jìn)行?？梢詼p少節(jié)點中緩沖器的容量，縮短傳送延遲時間。在新型的多計算機系統(tǒng)中得到了廣泛的應(yīng)用。處理的最小信息單位是“片”。當(dāng)一個節(jié)點把頭片送到下一個節(jié)點后，那么接下來就可以把后面的各個片也依次送出。7.5消息傳遞機制一個節(jié)點一旦開始傳送一個包中的頭片后，這個節(jié)點就必須等待這個包的所有片都送出去后，才能傳送其他包。不同包的片不能混合在一起傳送。與虛擬直通的不同之處當(dāng)輸出通路忙時，節(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)絡(luò)傳輸延遲；通道共享性好，利用率高；易于實現(xiàn)選播和廣播通信模式。缺點當(dāng)消息的一片被阻塞時，整個消息的所有片都將被阻塞在所在節(jié)點，占用了節(jié)點資源。7.5消息傳遞機制虛擬通道：兩個節(jié)點間的邏輯鏈接，它由源節(jié)點的片緩沖區(qū)、節(jié)點間的物理通道以及接收節(jié)點的片緩沖區(qū)組成。

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

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

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

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

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

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

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

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