計算機互連網(wǎng)絡(luò)課件

本章內(nèi)容：介紹用于多機并行計算的各種網(wǎng)絡(luò)，它們統(tǒng)稱為互連網(wǎng)絡(luò)，縮寫符號是ICN（InterconnectionNetwork）。?互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓樸結(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來實現(xiàn)多處理機、多計算機之間或多個功能部件之間的連接，是多處理機、多計算機系統(tǒng)的核心。

?互連網(wǎng)絡(luò)的設(shè)計目標(biāo)：通過互連網(wǎng)絡(luò)連接的多個部件能實現(xiàn)靈活的連接變換、能提供部件間的通信的最大并行性。第七章互連網(wǎng)絡(luò)(P394)2003.3.11計算機系統(tǒng)結(jié)構(gòu)7.1目的與作用(1)當(dāng)前提高計算速度的主要措施，一是改進(jìn)器件，二是多處理單元并行計算。ICN是供多處理單元傳輸數(shù)據(jù)的高速通路，對并行計算時間影響很大。(2)ICN與處理單元的連接模型(3)ICN的主要操作：置換(N－N)，廣播(1－

N)，選播(1－

N’)。2003.3.12計算機系統(tǒng)結(jié)構(gòu)網(wǎng)絡(luò)規(guī)模 一般說來，網(wǎng)絡(luò)用圖來表示。其結(jié)點數(shù)稱為網(wǎng)絡(luò)規(guī)模。(2) 結(jié)點度 與結(jié)點相連接的邊(即鏈路或通道)的數(shù)目稱為結(jié)點度。在單向通道的情況下，進(jìn)入結(jié)點的通道數(shù)叫做入度，而從結(jié)點出來的通道數(shù)則稱為出度。結(jié)點度應(yīng)盡可能地小并保持恒定。(3) 距離

兩結(jié)點之間相連的最少邊數(shù)。(4) 網(wǎng)絡(luò)直徑 網(wǎng)絡(luò)中任意兩個結(jié)點間最短路徑長度的最大值稱為網(wǎng)絡(luò)直徑。網(wǎng)絡(luò)直徑應(yīng)當(dāng)盡可能地小。(5) 等分寬度 當(dāng)某一網(wǎng)絡(luò)被切成相等的兩半時，沿切口的最小邊數(shù)(通道)稱為通道等分寬度。(6) 路由 在網(wǎng)絡(luò)通信中對路徑的選擇與指定。通常見到的處理單元之間的數(shù)據(jù)路由功能有移數(shù)、混洗、交換、廣播(一對全體)、選播(多對多)等?；靖拍?003.3.13計算機系統(tǒng)結(jié)構(gòu)靜態(tài)網(wǎng)絡(luò)使用直接鏈路，它一旦構(gòu)成后就固定不變。靜態(tài)網(wǎng)絡(luò)（P402）在N很小的情況下，線性陣列相當(dāng)經(jīng)濟(jì)和合理的。由于直徑隨N線性增大，因此當(dāng)N比較大時，就不應(yīng)使用了。下面介紹幾種常用的靜態(tài)網(wǎng)絡(luò)。1.線性陣列2003.3.15計算機系統(tǒng)結(jié)構(gòu)環(huán)可以單向工作，也可以雙向工作。它是對稱的，結(jié)點度是常數(shù)2。雙向環(huán)的直徑為N/2，單向環(huán)的直徑是N。2.環(huán)與帶弦環(huán)2003.3.16計算機系統(tǒng)結(jié)構(gòu)3.循環(huán)移數(shù)網(wǎng)絡(luò)2003.3.17計算機系統(tǒng)結(jié)構(gòu)5.胖樹形2003.3.19計算機系統(tǒng)結(jié)構(gòu)6.網(wǎng)格形和環(huán)網(wǎng)形2003.3.110計算機系統(tǒng)結(jié)構(gòu)7.超立方體2003.3.111計算機系統(tǒng)結(jié)構(gòu)交叉開關(guān)網(wǎng)絡(luò)是單級網(wǎng)絡(luò)，它由交叉點上的一元開關(guān)構(gòu)成。通常，這類交叉開關(guān)網(wǎng)絡(luò)需要使用n×m個交叉點開關(guān)。正方形交叉開關(guān)網(wǎng)絡(luò)(n＝m)可以無阻塞地實現(xiàn)n!種置換。每個周期可以實現(xiàn)n個數(shù)據(jù)傳輸，與每個總線周期只傳一個數(shù)據(jù)相比，它的頻寬最高。對小型系統(tǒng)來說性能價格比較高。但是單級交叉開關(guān)網(wǎng)絡(luò)一旦構(gòu)成后將不能擴(kuò)充。2.交叉開關(guān)網(wǎng)絡(luò)2003.3.113計算機系統(tǒng)結(jié)構(gòu)總線的造價最低，但其缺點是可用的帶寬較窄，容易產(chǎn)生故障。由于交叉開關(guān)的硬件復(fù)雜性以n2上升，所以其造價最為昂貴。但是，交叉開關(guān)的帶寬和路由性能最好。如果網(wǎng)絡(luò)的規(guī)模較小，它是一種理想的倍選擇。多級網(wǎng)絡(luò)則是兩個極端之間的折衷。它的主要優(yōu)點在于采用模塊結(jié)構(gòu)，因而可擴(kuò)展性較好。然而，其時延隨網(wǎng)絡(luò)的級數(shù)而上升。另外，由于增加了連線和開關(guān)復(fù)雜性，價格也是一種限制因素。總線、多級網(wǎng)絡(luò)、交叉開關(guān)的對比2003.3.114計算機系統(tǒng)結(jié)構(gòu)特點：成本低，并行性差。(1)拓?fù)浣Y(jié)構(gòu)(硬件，P402-P407)：直線，單向環(huán)，雙向環(huán)，帶弦環(huán)，樹，星型（真星型，假星型），完全網(wǎng)。(2)傳輸協(xié)議(使用規(guī)則，軟件，P427-P435)：碰撞爭用，令牌協(xié)議，劍橋環(huán)。(3)主要參數(shù)(P399)：直徑，中剖寬度，結(jié)點的度，最長邊。示例：(4)典型代表：以太網(wǎng)，令牌網(wǎng)（環(huán)或直線）。7.2通用網(wǎng)2003.3.115計算機系統(tǒng)結(jié)構(gòu)定義：單級ICN只使用一級開關(guān)，如下圖所示。開關(guān)的每種接通組合方式可用一個互連函數(shù)表示。

f(j入)=j出，0≤j≤N-1在互連函數(shù)中，記：

N──結(jié)點數(shù)

n=log2N──維數(shù)

j=Xn-1……X0──

結(jié)點 編號的二進(jìn)制形式，位數(shù)為n?；ミB函數(shù)族的組成必須使網(wǎng)絡(luò)成為連通圖。(2)單級ICN2003.3.117計算機系統(tǒng)結(jié)構(gòu)該網(wǎng)絡(luò)由立方體函數(shù)定義，立方體函數(shù)族有n個成員，分別是Cube0，Cube1，……，Cuben-1。立方體函數(shù)定義：Cubei的功能是對入端結(jié)點編號二進(jìn)制形式的第i位取反

Cubei(Xn-1…Xi+1XiXi-1…X0)=Xn-1…Xi+1XiXi-1…X0，其中0≤i≤n-1例如：Cube0(0)=1，Cube3(7)=15。

n=3的單級立方體網(wǎng)絡(luò)拓?fù)湫螤钊缬覉D所示。最壞情況下的傳輸需對輸入結(jié)點編號的全部n位取反。所以單級立方體網(wǎng)絡(luò)的直徑是n。

立方體函數(shù)性質(zhì)：結(jié)合律、交換律以及自反律（Cubei重復(fù)使用2次的結(jié)果與原始自變量相同）。單級立方體網(wǎng)（Cube網(wǎng)，P396第1行/P405第4行）2003.3.118計算機系統(tǒng)結(jié)構(gòu)該網(wǎng)絡(luò)由混洗函數(shù)（shuffle）與交換函數(shù)（exchange即Cube0）定義，或者說它的互連函數(shù)族只有這兩個成員。

混洗函數(shù)定義： 2jmod（N-1），當(dāng)j<N-1 shuffle（j）= N-1 ，當(dāng)j=N-1

例如：當(dāng)N=8時，shuffle（0）=0，shuffle（1）=2，shuffle（7）=7。n=3的混洗函數(shù)開關(guān)狀態(tài)如P397圖7.6(a)所示，其連接規(guī)律就像洗牌。

性質(zhì)1：shuffle（Xn-1Xn-2……X0）=Xn-2……X0Xn-1（循環(huán)左移）

性質(zhì)2：shufflen（j）=j

n=3的混洗網(wǎng)絡(luò)拓?fù)湫螤钊缦聢D綠線所示，可以看出它不是一個連通圖，所以還需要增加一個交換函數(shù)（圖中紅線所示），才能構(gòu)成完整的單級混洗—交換網(wǎng)絡(luò)。單級混洗—交換網(wǎng)絡(luò)的直徑是2n-1。單級混洗-交換網(wǎng)（P396倒數(shù)第8行）2003.3.119計算機系統(tǒng)結(jié)構(gòu)該網(wǎng)絡(luò)由PM2I函數(shù)定義，PM2I函數(shù)共有n對成員，分別是PM2±0，PM2±1，……，PM2±(n-1)。PM2I函數(shù)定義：PM2±i的功能是對入端結(jié)點編號加或減2i，然后再作模N運算

PM2+i（j）=j+2imodN PM2-i（j）=j-2imodN其中j=0～N-1，i=0～n-1。例如：當(dāng)N=8時，PM2+0（0）=0+20=1，PM2+0（1）=1+20=2，PM2+0（7）=7+20=0，PM2+1（0）=0+21=2。N=8的PM2+1（j）函數(shù)開關(guān)狀態(tài)如右圖所示，其連接規(guī)律是把各入端結(jié)點編號加上相同的增量21（modN），獲得出端結(jié)點編號。單級加減2i網(wǎng)（PM2I網(wǎng)，移數(shù)網(wǎng)，P398倒數(shù)第2行）2003.3.121計算機系統(tǒng)結(jié)構(gòu)

N=8的PM2+i網(wǎng)絡(luò)拓?fù)湫螤钊缦聢D所示，可以看出它包含多個強連通子圖（即除去若干邊以后仍能保證任何一對結(jié)點互相可達(dá)），所以這2n個函數(shù)并不是實現(xiàn)互連網(wǎng)的最小集合。實際應(yīng)用中為了降低造價，人們往往取它們的一個子集來構(gòu)造互連網(wǎng)。

性質(zhì)1：對相同的i值，PM2+i與PM2-i函數(shù)的傳送路徑相同，方向相反（右圖中所有箭頭反向即為PM2-1的拓?fù)湫螤睿?/p>

性質(zhì)2：PM2+(n-1)=PM2-(n-1)。

根據(jù)性質(zhì)2，我們知道單級PM2I網(wǎng)絡(luò)實際上只能實現(xiàn)2n-1種不同的置換。單級PM2I網(wǎng)絡(luò)的直徑是。2003.3.122計算機系統(tǒng)結(jié)構(gòu)各種互連函數(shù)總結(jié)

E(Xn-1Xn-2…X1X0)=Xn-1Xn-2…X1X0，

其中0≤i≤n-1交換置換函數(shù)定義Cubei(Xn-1…Xi+1XiXi-1…X0)=Xn-1…Xi+1XiXi-1…X0，其中0≤i≤n-1立方體函數(shù)定義：Cubei的功能是對入端結(jié)點編號二進(jìn)制形式的第i位取反均勻洗牌shuffle（Xn-1Xn-2……X0）=Xn-2……X0Xn-1（循環(huán)左移）PM2I函數(shù)定義：PM2±i的功能是對入端結(jié)點編號加或減2i，然后再作模N運算

PM2+i（X）=X+2imodN PM2-i（X）=X-2imodN其中X=0～N-1，i=0～n-1。2003.3.123計算機系統(tǒng)結(jié)構(gòu)多級混洗—交換網(wǎng)絡(luò)（P410/P436）多級混洗—交換網(wǎng)絡(luò)又稱為Omega網(wǎng)。多級混洗—交換網(wǎng)絡(luò)結(jié)構(gòu)：它由n級構(gòu)成，每一級包含一個無條件混洗拓?fù)渚€路和一列可控的二元交換開關(guān)，前后重復(fù)，便于制造。如P436圖7.43所示。各級編號是n-1，……，0，即按降序排列。在多級混洗—交換網(wǎng)絡(luò)中，單獨一級混洗拓?fù)渚€路可完成一次數(shù)據(jù)混洗（shuffle），而單獨一列二元交換開關(guān)在處于“交換”狀態(tài)時可完成一次交換操作（Cube0）。如果各級二元交換開關(guān)都處于“直連”狀態(tài)，N個結(jié)點的數(shù)據(jù)通過網(wǎng)絡(luò)僅經(jīng)過n次混洗操作，排列順序最終恢復(fù)輸入狀態(tài)（混洗函數(shù)性質(zhì)2）；如果各級二元交換開關(guān)都處于“交換”狀態(tài)，則N個結(jié)點的數(shù)據(jù)在每次混洗之后緊接著一次交換（Cube0），也就是地址碼的最低位取反，最后n位地址均被取反。程序員根據(jù)數(shù)據(jù)置換或復(fù)制的需要，可以靈活地設(shè)置各開關(guān)的狀態(tài)。2003.3.125計算機系統(tǒng)結(jié)構(gòu)多級混洗—交換網(wǎng)絡(luò)尋徑算法（路由算法）目的：根據(jù)給定的輸入/輸出對應(yīng)關(guān)系，確定各開關(guān)的狀態(tài)。名稱：源-目的地址異或法操作：將任一個輸入地址與它要到達(dá)的輸出地址作異或運算，其結(jié)果的biti位控制數(shù)據(jù)到達(dá)的第i級開關(guān)，“0”表示“直連”，“1”表示“交換”。例如給定傳輸101B→011B，二者異或結(jié)果為110B，于是從101B號輸入端開始，把它遇到的第2級開關(guān)置為“交換”，第1級開關(guān)置為“交換”，第0級開關(guān)置為“直連”。如下圖紅線所示。2003.3.126計算機系統(tǒng)結(jié)構(gòu)7.4.2四種尋徑方式對應(yīng)的總時間（P415）(1)線路交換T=(Lt/B)×D+L/B其中：Lt是為建立路徑所需的小信息包的長度，(2)存儲轉(zhuǎn)發(fā)T=(L/B)×D+L/B=(D+1)×L/B(3)虛擬直通T=(Lh/B)×D+L/B=(Lh×D+L)/B其中：Lh是消息的尋徑頭部的長度，(4)蟲蝕尋徑T=Tf×D+L/B=(Lf/B)×D+L/B=(Lf×D+L)/B其中：Lf是片的長度，2003.3.129計算機系統(tǒng)結(jié)構(gòu)7.5廣播與選播算法（P425）廣播是將一個結(jié)點的數(shù)據(jù)復(fù)制到全部N個結(jié)點；選播是將一個結(jié)點的數(shù)據(jù)復(fù)制到多個（N'個）結(jié)點，1≤N'≤N。

研究廣播與選播算法的目的是盡量利用互連網(wǎng)的并行傳輸能力，尋找花費時間最少或者動用信道次數(shù)（又稱"流量"或"通道數(shù)"）最少的方案。這里所說的并行傳輸，是指多個結(jié)點向同一方向的相鄰結(jié)點發(fā)送自己的數(shù)據(jù)副本。向不同方向進(jìn)行的發(fā)送不能同時進(jìn)行（具有這種能力的互連網(wǎng)不屬于現(xiàn)在的討論范圍）。顯然對不同的網(wǎng)絡(luò)，適用的廣播與選播算法也不同。下面舉幾個具體實例。2003.3.130計算機系統(tǒng)結(jié)構(gòu)7.5.1廣播算法(1)單級立方體網(wǎng)絡(luò)廣播算法算法：按任意順序使用Cube0～Cuben-1各一次，每一步都從當(dāng)前擁有數(shù)據(jù)的所有結(jié)點同時發(fā)往等量的無數(shù)據(jù)結(jié)點，也就是將網(wǎng)絡(luò)中擁有數(shù)據(jù)的結(jié)點數(shù)加倍。如圖6.9所示（圖中實線箭頭表示一個數(shù)據(jù)的一次實際傳送，虛線指出上一步已有數(shù)據(jù)的結(jié)點）。這種算法的時間和流量是由結(jié)點數(shù)N決定的常量。時間流量

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

2301

6745單級立方體網(wǎng)絡(luò)廣播算法實例從節(jié)點0開始，順序是cube0－>cube2

042615370000000000000010111110010110011010100101101002003.3.132計算機系統(tǒng)結(jié)構(gòu)單級立方體網(wǎng)絡(luò)廣播算法實例2003.3.133計算機系統(tǒng)結(jié)構(gòu)7.5.2選播算法選播算法的設(shè)計目標(biāo)有3種：時間最少、流量最少、在時間最少的多個方案中選取流量最少方案。選播時間最少算法是通過單播時間最少算法裁剪而成（教材P426圖7.36(a)→(b)）。選播流量最少算法是最小成本生成樹算法，具體操作順序既可以是先短邊后長邊“長樹”，也可以是先長邊后短邊“砍樹”（教材P426圖7.36(c)）。

實現(xiàn)第3種目標(biāo)的一種重要算法是貪婪算法（教材P426圖7.36(b)）。不論對何種網(wǎng)絡(luò)，貪婪算法總是重復(fù)使用一個固定的操作規(guī)則：從當(dāng)前擁有數(shù)據(jù)的結(jié)點出發(fā)，向需要數(shù)據(jù)的結(jié)點數(shù)最多的方向并行傳送一步，如此循環(huán)，直至傳遍所有需要數(shù)據(jù)的結(jié)點。如果最后發(fā)現(xiàn)某個通道（即一次數(shù)據(jù)發(fā)送操作）不在通往給定目標(biāo)結(jié)點的路徑上，則應(yīng)將其刪去。2003.3.134計算機系統(tǒng)結(jié)構(gòu)(1)單級網(wǎng)格網(wǎng)（Mash網(wǎng)）貪婪算法算法：以教材P426圖7.36為例，小圖(a)指出總共有1個源結(jié)點S和5個目的結(jié)點。小圖(b)指出從S出發(fā)，首先應(yīng)向右鄰結(jié)點發(fā)送數(shù)據(jù)，因為S的左方只有1個目的結(jié)點、上方有3個目的結(jié)點、右方有４個目的結(jié)點；第二步從這２個擁有數(shù)據(jù)的結(jié)點出發(fā)，可以再向右發(fā)送（有3個目的結(jié)點），也可以改向上發(fā)送（也有3個目的結(jié)點），……。只要每步遵守貪婪算法的規(guī)則，最后形成的不同路徑樹的時間和流量都是相同的。2003.3.135計算機系統(tǒng)結(jié)構(gòu)(2)單級立方體網(wǎng)絡(luò)貪婪算法算法：以教材P426圖7.37為例。小圖(a)指出廣播算法的時間是4，流量是15。Cube0～Cuben-1的使用順序?qū)V播算法的時間和流量沒有影響，但對小圖(b)的選播算法的時間