第9章互連網(wǎng)絡(luò)1ppt課件9.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ī)制2ppt課件

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

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

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

通過數(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ù)）9.1.1互連函數(shù)9.1互連函數(shù)4ppt課件9.1互連函數(shù)互連函數(shù)f(x)有時(shí)可以采用循環(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個(gè)輸入端和輸出端的二進(jìn)制地址，互連函數(shù)表示為：

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

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

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

（N為結(jié)點(diǎn)個(gè)數(shù)）當(dāng)N＝8時(shí)，n＝3，可得到常用的立方體互連函數(shù)：7ppt課件9.1互連函數(shù)變換圖形N=8的立方體交換函數(shù)

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

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

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

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

即把輸入端的二進(jìn)制編號中的低k位循環(huán)左移一位。第k個(gè)超函數(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)左移一位。11ppt課件9.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)右移一位而得到所連接的輸出端編號。12ppt課件9.1互連函數(shù)互連函數(shù)逆均勻洗牌是均勻洗牌的逆函數(shù)當(dāng)N=8時(shí)，有：

σ(x2x1x0)＝x1x0x2σ(2)(x2x1x0)＝x2x0x1σ(2)(x2x1x0)＝x1x2x0σ-1(x2x1x0)＝x0x2x113ppt課件9.1互連函數(shù)N=8

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

N=8的均勻洗牌函數(shù)14ppt課件9.1互連函數(shù)碟式函數(shù)

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

第k個(gè)子函數(shù)

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

把輸入端的二進(jìn)制編號的低k位中的最高位與最低位互換。第k個(gè)超函數(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位中的最高位與最低位互換。15ppt課件9.1互連函數(shù)下列等式成立

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

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

ρ(k)(xn-1…xkxk-1xk-2…x1x0)＝xn-1…xkx0x1…xk-2xk-1即把輸入端的二進(jìn)制編號的低k位中各位的次序顛倒過來。18ppt課件9.1互連函數(shù)第k個(gè)超函數(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時(shí)，有：

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

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

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

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

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

0≤x≤N－1，0≤i≤n－1，n＝log2N，N為結(jié)點(diǎn)數(shù)。PM2I互連網(wǎng)絡(luò)共有2n個(gè)互連函數(shù)。21ppt課件9.1互連函數(shù)當(dāng)N＝8時(shí)，有6個(gè)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）

22ppt課件9.1互連函數(shù)N=8的PM2I函數(shù)23ppt課件陣列計(jì)算機(jī)ILLIACⅣ

采用PM2±0和PM2±n/2構(gòu)成其互連網(wǎng)絡(luò)，實(shí)現(xiàn)各處理單元之間的上下左右互連。用移數(shù)函數(shù)構(gòu)成ILLIACⅣ陣列機(jī)的互連網(wǎng)絡(luò)24ppt課件9.1互連函數(shù)

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

（2）PM2+3

（3）PM2-0

（4）σ

（5）σ(σ)時(shí)，分別給出與第13號處理器所連接的處理器號。25ppt課件9.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。26ppt課件9.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雙向互連。27ppt課件網(wǎng)絡(luò)通常是用有向邊或無向邊連接有限個(gè)結(jié)點(diǎn)的圖來表示?；ミB網(wǎng)絡(luò)的主要特性參數(shù)有：網(wǎng)絡(luò)規(guī)模N：網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(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ù)28ppt課件9.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)進(jìn)入結(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)盡可能地小。等分寬度b：把由N個(gè)結(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)切成結(jié)點(diǎn)數(shù)相同（N/2）的兩半，在各種切法中，沿切口邊數(shù)的最小值。29ppt課件9.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)線等分寬度：B＝b×w其中：w為通道寬度（用位表示）該參數(shù)主要反映了網(wǎng)絡(luò)最大流量。對稱性：從任何結(jié)點(diǎn)看到的拓?fù)浣Y(jié)構(gòu)都是相同的網(wǎng)絡(luò)稱為對稱網(wǎng)絡(luò)。對稱網(wǎng)絡(luò)比較容易實(shí)現(xiàn)，編程也比較容易。30ppt課件9.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)評估互連網(wǎng)絡(luò)性能的兩個(gè)基本指標(biāo)：時(shí)延和帶寬通信時(shí)延指從源結(jié)點(diǎn)到目的結(jié)點(diǎn)傳送一條消息所需的總時(shí)間，它由以下4部分構(gòu)成：軟件開銷：在源結(jié)點(diǎn)和目的結(jié)點(diǎn)用于收發(fā)消息的軟件所需的執(zhí)行時(shí)間。主要取決于兩端端結(jié)點(diǎn)處理消息的軟件內(nèi)核。通道時(shí)延：通過通道傳送消息所花的時(shí)間。通路時(shí)延=消息長度/通道帶寬通常由瓶頸鏈路的通道帶寬決定。9.2.2互連網(wǎng)絡(luò)的性能指標(biāo)31ppt課件9.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)選路時(shí)延：消息在傳送路徑上所需的一系列選路決策所需的時(shí)間開銷。與傳送路徑上的結(jié)點(diǎn)數(shù)成正比。競爭時(shí)延：多個(gè)消息同時(shí)在網(wǎng)絡(luò)中傳送時(shí)，會(huì)發(fā)生爭用網(wǎng)絡(luò)資源的沖突。為避免或解決爭用沖突所需的時(shí)間就是競爭時(shí)延。很難預(yù)測，它取決于網(wǎng)絡(luò)的傳輸狀態(tài)。網(wǎng)絡(luò)時(shí)延通道時(shí)延與選路時(shí)延的和。它是由網(wǎng)絡(luò)硬件特征決定的，與程序行為和網(wǎng)絡(luò)傳輸狀態(tài)無關(guān)。32ppt課件9.2互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)端口帶寬對于互連網(wǎng)絡(luò)中的任意一個(gè)端口來說，其端口帶寬是指單位時(shí)間內(nèi)從該端口傳送到其他端口的最大信息量。在對稱網(wǎng)絡(luò)中，端口帶寬與端口位置無關(guān)。網(wǎng)絡(luò)的端口帶寬與各端口的端口帶寬相同。非對稱網(wǎng)絡(luò)的端口帶寬則是指所有端口帶寬的最小值。聚集帶寬網(wǎng)絡(luò)從一半結(jié)點(diǎn)到另一半結(jié)點(diǎn)，單位時(shí)間內(nèi)能夠傳送的最大信息量。33ppt課件9.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)的切平面中，所有邊合起來單位時(shí)間所能傳送的最大信息量。34ppt課件互連網(wǎng)絡(luò)通?？梢苑譃閮纱箢悾红o態(tài)互連網(wǎng)絡(luò)各結(jié)點(diǎn)之間有固定的連接通路、且在運(yùn)行中不能改變的網(wǎng)絡(luò)。動(dòng)態(tài)互連網(wǎng)絡(luò)由交換開關(guān)構(gòu)成、可按運(yùn)行程序的要求動(dòng)態(tài)地改變連接狀態(tài)的網(wǎng)絡(luò)。下面介紹幾種靜態(tài)互連網(wǎng)絡(luò)。（其中：N表示結(jié)點(diǎn)的個(gè)數(shù)）9.3靜態(tài)互連網(wǎng)絡(luò)35ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)線性陣列一種一維的線性網(wǎng)絡(luò)，其中N個(gè)結(jié)點(diǎn)用N-1個(gè)鏈路連成一行。端結(jié)點(diǎn)的度：1其余結(jié)點(diǎn)的度：2直徑：N－1等分寬度b=1

36ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)37ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)對稱結(jié)點(diǎn)的度：2雙向環(huán)的直徑：N/2單向環(huán)的直徑：N

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

環(huán)和帶弦環(huán)環(huán)用一條附加鏈路將線性陣列的兩個(gè)端點(diǎn)連接起來而構(gòu)成?？梢詥蜗蚬ぷ?，也可以雙向工作。38ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)帶弦環(huán)增加的鏈路愈多，結(jié)點(diǎn)度愈高，網(wǎng)絡(luò)直徑就愈小。39ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)全連接網(wǎng)絡(luò)結(jié)點(diǎn)度：15直徑最短，為1。40ppt課件循環(huán)移數(shù)網(wǎng)絡(luò)通過在環(huán)上每個(gè)結(jié)點(diǎn)到所有與其距離為2的整數(shù)冪的結(jié)點(diǎn)之間都增加一條附加鏈而構(gòu)成。N=16結(jié)點(diǎn)度：7直徑：2

41ppt課件9.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連接。結(jié)點(diǎn)度：2n－1直徑：n/2網(wǎng)絡(luò)規(guī)模N=2n42ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)樹形和星形一棵5層31個(gè)結(jié)點(diǎn)的二叉樹一般說來，一棵k層完全平衡的二叉樹有N=2k-1個(gè)結(jié)點(diǎn)。最大結(jié)點(diǎn)度：3直徑：2(k-1)等分寬度b=1

星形結(jié)點(diǎn)度較高，為N－1。直徑較小，是一常數(shù)2。等分寬度b=N/2

可靠性比較差，只要中心結(jié)點(diǎn)出故障，整個(gè)系統(tǒng)就會(huì)癱瘓。

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

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

。46ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)Illiac網(wǎng)絡(luò)

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

把2維網(wǎng)格形網(wǎng)絡(luò)的每一列的兩個(gè)端結(jié)點(diǎn)連接起來，再把每一行的尾結(jié)點(diǎn)與下一行的頭結(jié)點(diǎn)連接起來，并把最后一行的尾結(jié)點(diǎn)與第一行的頭結(jié)點(diǎn)連接起來。一個(gè)規(guī)模為n×n的Illiac網(wǎng)絡(luò)所有結(jié)點(diǎn)的度d=4網(wǎng)絡(luò)直徑D=n-1Illiac網(wǎng)絡(luò)的直徑只有純網(wǎng)格形網(wǎng)絡(luò)直徑的一半。等分寬度：2n47ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)環(huán)網(wǎng)形可看作是直徑更短的另一種網(wǎng)格。把2維網(wǎng)格形網(wǎng)絡(luò)的每一行的兩個(gè)端結(jié)點(diǎn)連接起來，把每一列的兩個(gè)端結(jié)點(diǎn)也連接起來。將環(huán)形和網(wǎng)格形組合在一起，并能向高維擴(kuò)展。一個(gè)n×n的環(huán)網(wǎng)形網(wǎng)結(jié)點(diǎn)度：4網(wǎng)絡(luò)直徑：2×n/2等分寬度b=2n48ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)（a）網(wǎng)格形（b）Illiac網(wǎng)（c）環(huán)網(wǎng)形49ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)超立方體一種二元n-立方體結(jié)構(gòu)一般來說，一個(gè)二元n-立方體由N=2n

個(gè)結(jié)點(diǎn)組成，它們分布在n維上，每維有兩個(gè)結(jié)點(diǎn)。

例

8個(gè)結(jié)點(diǎn)的3維立方體

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

。

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

把3-立方體的每個(gè)結(jié)點(diǎn)換成一個(gè)由3個(gè)結(jié)點(diǎn)構(gòu)成的環(huán)而形成的。帶環(huán)k-立方體（簡稱k-CCC）k-立方體的變形，它是通過用k個(gè)結(jié)點(diǎn)構(gòu)成的環(huán)取代k-立方體中的每個(gè)結(jié)點(diǎn)而形成的。網(wǎng)絡(luò)規(guī)模為N=k×2k網(wǎng)絡(luò)直徑為D=2k-1+k/2比k-立方體的直徑大一倍等分寬度為b=N/（2k）52ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)1234

k

k-15k

k-112345(b)將k-立方體的每個(gè)結(jié)點(diǎn)用由k個(gè)結(jié)點(diǎn)的環(huán)來代替，組成帶環(huán)k-立方體組成53ppt課件9.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é)點(diǎn)個(gè)數(shù)。

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

55ppt課件網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度B對稱性網(wǎng)絡(luò)規(guī)格說明線線陣列2N-1N-11非N個(gè)結(jié)點(diǎn)環(huán)形2[N/2]N2是N個(gè)結(jié)點(diǎn)全連接N-11N(N-1)/2(N/2)2是N個(gè)結(jié)點(diǎn)二叉樹32(h-1)N-11非樹高h(yuǎn)=[log2N]星形N-12N-1[N/2]非N個(gè)結(jié)點(diǎn)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個(gè)結(jié)點(diǎn)，n=[log2N]（維數(shù)）CCC32k-1+[k/2]3N/2N/(2k)是N=k×2k結(jié)點(diǎn)環(huán)長k≥3k元n-立方體2nn[k/2]nN2kn-1是N=kn個(gè)結(jié)點(diǎn)靜態(tài)互連網(wǎng)絡(luò)特征一覽表

56ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)

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

PM2+2（X）=（X+22）modN=（X+4）mod1657ppt課件9.3靜態(tài)互連網(wǎng)絡(luò)

傳送方向?yàn)槟鏁r(shí)針的4個(gè)單向環(huán)的循環(huán)互連函數(shù)可表示為：

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

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

傳送方向?yàn)槟鏁r(shí)針的單向環(huán)的循環(huán)互連函數(shù)可表示為：

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

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

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

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

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

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

71ppt課件9.4動(dòng)態(tài)互連網(wǎng)絡(luò)各種多級互連網(wǎng)絡(luò)的區(qū)別在于所用開關(guān)模塊、控制方式和級間互連模式的不同。控制方式：對各個(gè)開關(guān)模塊進(jìn)行控制的方式。級控制：每一級的所有開關(guān)只用一個(gè)控制信號控制，只能同時(shí)處于同一種狀態(tài)。單元控制：每一個(gè)開關(guān)都有一個(gè)獨(dú)立的控制信號，可各自處于不同的狀態(tài)。部分級控制：第i級的所有開關(guān)分別用i＋1個(gè)信號控制，0≤i≤n－1，n為級數(shù)。常用的級間互連模式：均勻洗牌、蝶式、多路洗牌、縱橫交叉、立方體連接等72ppt課件9.4動(dòng)態(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)時(shí)，實(shí)現(xiàn)的是Cubei互連函數(shù)。

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

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

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

77ppt課件級控制信號k2k1k0連接的輸出端號序列（入端號序列：01234567）實(shí)現(xiàn)的分組交換實(shí)現(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＋Cube278ppt課件當(dāng)STARAN網(wǎng)絡(luò)用作移數(shù)網(wǎng)絡(luò)時(shí)，采用部分級控制，控制信號的分組和控制結(jié)果。部分級控制信號連接的輸出端號序列（入端號序列：01234567）所實(shí)現(xiàn)的移數(shù)功能第0級第1級第2級ABCDEGFHIJKL10010101101100010010011100000110000001000012345670234567014567012312305674230167451032547601234567移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移全等79ppt課件Omega網(wǎng)絡(luò)一個(gè)8×8的Omega網(wǎng)絡(luò)每級由4個(gè)4功能的2×2開關(guān)構(gòu)成級間互連采用均勻洗牌連接方式

80ppt課件9.4動(dòng)態(tài)互連網(wǎng)絡(luò)一個(gè)N輸入的Omega網(wǎng)絡(luò)有l(wèi)og2N級，每級用N/2個(gè)2×2開關(guān)模塊，共需要Nlog2N/2個(gè)開關(guān)。每個(gè)開關(guān)模塊均采用單元控制方式。不同的開關(guān)狀態(tài)組合可實(shí)現(xiàn)各種置換、廣播或從輸入到輸出的其它連接。N=8的多級立方體互連網(wǎng)絡(luò)的另一種畫法81ppt課件9.4動(dòng)態(tài)互連網(wǎng)絡(luò)0011223344556677ABCDEGFHIJKL級0級1級282ppt課件9.4動(dòng)態(tài)互連網(wǎng)絡(luò)9.4.4動(dòng)態(tài)互連網(wǎng)絡(luò)的比較網(wǎng)絡(luò)特性總線系統(tǒng)多級網(wǎng)絡(luò)交叉開關(guān)單位數(shù)據(jù)傳送的最小時(shí)延恒定O(logkn)恒定每臺(tái)處理機(jī)的帶寬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ò)不阻塞，可實(shí)現(xiàn)某些置換和廣播全置換，一次一個(gè)典型計(jì)算機(jī)SymmetryS1，EncoreMultimaxBBNTC-2000IBMRP3CrayY-MP/816FujitsuVPP500說明總線上假定有n臺(tái)處理機(jī)；總線寬度為w位n×nMIN采用k×k開關(guān)，其線寬為w位假定n×n交叉開關(guān)的線寬為w位83ppt課件

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

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

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

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

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

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

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

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

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

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

101ppt課件9.5消息傳遞機(jī)制把第二個(gè)包暫存在緩沖區(qū)

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

所在的列x2；然后再沿Y軸方向前進(jìn)，直到找到目標(biāo)結(jié)點(diǎn)（x2，y2）。104ppt課件9.5消息傳遞機(jī)制

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