哈工大并行計算課件第六章

第6章系統(tǒng)的互聯(lián)和千兆位網(wǎng)絡(luò)

1系統(tǒng)互連基礎(chǔ)

2靜態(tài)連接網(wǎng)絡(luò)

3動態(tài)連接網(wǎng)絡(luò)

4消息傳遞機(jī)制

5千兆位網(wǎng)絡(luò)技術(shù)

6ATM交換器和網(wǎng)絡(luò)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院

1

系統(tǒng)互連基礎(chǔ)一.網(wǎng)絡(luò)的分類方式靜態(tài)網(wǎng)絡(luò)動態(tài)網(wǎng)絡(luò)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院二.網(wǎng)絡(luò)特性和尋徑功能1.結(jié)點(diǎn)度包括出度和入度2.網(wǎng)絡(luò)直徑3.等分寬度當(dāng)某一網(wǎng)絡(luò)被切成相等的兩半時，沿切口的最小邊數(shù)(通道)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院4.數(shù)據(jù)尋徑功能

數(shù)據(jù)尋徑網(wǎng)絡(luò)用來進(jìn)行PE間數(shù)據(jù)交換。

通常見到的PE之間的數(shù)據(jù)尋徑功能有移數(shù)(shifting)、循環(huán)(rotation)、置換(一對一)、廣播(一對全體)、選播(多對多)、個人通信(一對多)、洗牌、交換等。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院5.置換對n個對象來說，有n！種置換，n個對象可照此重新排序。整個置換集合形成一個與復(fù)合運(yùn)算有關(guān)的置換群?？梢杂幂啌Q方法來描述置換功能。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例如，置換

＝(a，b，c)(d，e)即是以輪換形式表示的置換映射。(d，e)循環(huán)周期為2。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院三.互連函數(shù)（一）基本概念除了上述的置換表示，還有函數(shù)表示。1.互連函數(shù)：表示相互連接的輸出端號和輸入端號之間的一一對應(yīng)關(guān)系。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院互連函數(shù)有時可表示成為置換函數(shù)或排列函數(shù)。函數(shù)表示法用x表示輸入端變量，用f(x)表示互連函數(shù)。x還常用n位二進(jìn)制形式來表示:寫成xn-1，xn-2…x1x0。互連函數(shù)則對應(yīng)地表示為:f(xn-1，xn-2…x1x0)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.輸入輸出對應(yīng)表示法

優(yōu)點(diǎn)：更直觀哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院（二）常用的基本互連函數(shù)和特征1．恒等置換相同編號的輸入端與輸出端一一對應(yīng)互連所實(shí)現(xiàn)的置換。f(xn-1，xn-2…x1x0)=xn-1xn-2…x1x0哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.交換置換哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院3．方體置換是實(shí)現(xiàn)二進(jìn)制地址編號中第k位位值不同的輸入端和輸出端之間的連接。其表達(dá)式為：哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院如以N=8為例。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院4．均勻洗牌置換均勻洗牌置換將輸入端分成數(shù)目相等的兩半，前一半和后一半按序一個隔一個地從頭至尾依次與輸出端相連。這好比洗撲克牌時，將整副牌分成相等的兩疊來洗，以達(dá)到理想的一張隔一張的均勻情況，故稱為均勻洗牌置換，或簡稱為洗牌置換。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院其函數(shù)關(guān)系可表示為：由此表達(dá)式可見，洗牌變換是將輸入端二進(jìn)制地址循環(huán)左移一位即得到對應(yīng)的輸出端二進(jìn)制地址。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院還可以定義:子洗牌超洗牌:哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院逆均勻洗牌是均勻洗牌的逆函數(shù)，其函數(shù)表達(dá)式為：哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院5.蝶式置換蝶式置換的名稱源于FFT變換的實(shí)現(xiàn)時其圖形的形狀如蝴蝶式樣。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院可定義子蝶式:超蝶式哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院6.位序顛倒置換位序顛倒置換是將輸入端二進(jìn)制地址的位序顛倒過來求得相應(yīng)輸出的地址。其表達(dá):(k)(xn-1xn-2…x1x0)=x0x1…xn-1哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院7．移數(shù)置換移數(shù)置換是將輸入端數(shù)組循環(huán)移動一定的位置向輸出端傳輸。其函數(shù)表示式無需用二進(jìn)制編號來寫，可表達(dá)如下：d(X)＝(X+k)modN，0≤X≤Nk為常數(shù)，指移過的位置值，也可以將整個輸入數(shù)組分成若干個子數(shù)組。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院三、網(wǎng)絡(luò)性能(1)功能特性——這指的是網(wǎng)絡(luò)如何支持?jǐn)?shù)據(jù)尋徑、中斷處理、同步、請求／消息組合和一致性。(2)網(wǎng)絡(luò)時延——這是指單位消息通過網(wǎng)絡(luò)傳送時，最壞情況下的時間延遲。(3)帶寬——這是指通過網(wǎng)絡(luò)的最大數(shù)據(jù)傳輸率，用M字節(jié)／秒表示。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院(4)硬件復(fù)雜性——這是指諸如導(dǎo)線、開關(guān)、連接器、仲裁和接口邏輯等的造價。(5)可擴(kuò)展性——這是指在增加機(jī)器資源使性能可擴(kuò)展的情況下，網(wǎng)絡(luò)具備模塊化可擴(kuò)展的能力。

哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院

2靜態(tài)連接網(wǎng)絡(luò)靜態(tài)網(wǎng)絡(luò)的基本概念1.線性陣列

內(nèi)部結(jié)點(diǎn)度直徑等分寬度b＝1。

哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.環(huán)和帶弦環(huán)結(jié)點(diǎn)度是常數(shù)直徑雙向環(huán)單向環(huán)

哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院帶弦環(huán)可以提高結(jié)點(diǎn)度減小直徑哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院3.循環(huán)移數(shù)網(wǎng)絡(luò)一個循環(huán)移數(shù)網(wǎng)絡(luò)，其結(jié)點(diǎn)數(shù)N＝16，它是將環(huán)上每個結(jié)點(diǎn)到與其距離為2整數(shù)冪的結(jié)點(diǎn)之間增加一條附加鏈而構(gòu)成的。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院結(jié)點(diǎn)度：網(wǎng)絡(luò)直徑：哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院4.樹形和星形（1）樹形：結(jié)點(diǎn)數(shù)一棵k層完全平衡的二叉樹應(yīng)有N＝2k-1個結(jié)點(diǎn)。最大結(jié)點(diǎn)度直徑二叉樹是一種可擴(kuò)展的系統(tǒng)結(jié)構(gòu)由于結(jié)點(diǎn)度是常數(shù)，但其直徑相當(dāng)長。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院（2）星形如上圖所示直徑結(jié)點(diǎn)數(shù)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院5.胖樹形1985年Leiserson提出將計算機(jī)科學(xué)中所用的一般樹結(jié)構(gòu)修改為胖樹形(fattree)。二叉胖樹結(jié)構(gòu)的通道寬度從葉結(jié)點(diǎn)往根結(jié)點(diǎn)上行方向逐漸增寬，它更象真實(shí)的樹，其向樹根方向的枝叉變得愈來愈粗。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院解決了使用傳統(tǒng)二叉樹的主要問題；CM—5已采用胖樹結(jié)構(gòu)；胖樹體系結(jié)構(gòu)在ConnectionMachine的CM-5系統(tǒng)中實(shí)現(xiàn)。CM5采用4叉胖樹來構(gòu)造數(shù)據(jù)網(wǎng)絡(luò)，允許每個結(jié)點(diǎn)有4個子結(jié)點(diǎn)和2個或4個父結(jié)點(diǎn)。還可將二叉胖樹的思想推廣到多路胖樹。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院6.網(wǎng)格形和環(huán)網(wǎng)形(1)3X3網(wǎng)格如下圖所示：這是一種比較流行的結(jié)構(gòu)，它已以各種變體形式在ILLiac4、MPP、DAP、CM-2和IntelParagon中得到了實(shí)現(xiàn)。N＝nk結(jié)點(diǎn)的k維網(wǎng)格的內(nèi)部結(jié)點(diǎn)度為2k；可知邊界點(diǎn)度和角節(jié)點(diǎn)度；網(wǎng)格直徑為k(n-1)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院(2)Illiac4網(wǎng)格是一種可回繞連接的網(wǎng)格圖，如上圖所示。假定Illiac4系統(tǒng)采用8X8的這種Illiac網(wǎng)格，則其結(jié)點(diǎn)度為常數(shù)4，直徑為7。N＝16＝4X4構(gòu)型的Illiac網(wǎng)格與圖所示的結(jié)點(diǎn)度為4的帶弦環(huán)在拓?fù)渖鲜堑刃У?。一般說來，一個nXn的Illiac網(wǎng)格的直徑應(yīng)為d＝n-1，它僅為純網(wǎng)格直徑的一半。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院(3)環(huán)網(wǎng)形上圖所示,可看做是另一種直徑更短的網(wǎng)格。這種拓?fù)浣Y(jié)構(gòu)將環(huán)形和網(wǎng)格組合在一起，并能向高維擴(kuò)展。環(huán)網(wǎng)形沿陣列每行每列都有環(huán)形連接。一個n×n二元環(huán)網(wǎng)的結(jié)點(diǎn)度為4，直徑為2[n／2]。環(huán)網(wǎng)是一種對稱的拓?fù)浣Y(jié)構(gòu)，所有附加的回繞連接可使其直徑較之網(wǎng)格結(jié)構(gòu)減少1/2。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院7.搏動式陣列

這是一類為實(shí)現(xiàn)確定算法而設(shè)計的多維流水線陣列結(jié)構(gòu)。上圖所示就是為完成矩陣--矩陣相乘而專門設(shè)計的搏動式陣列。此例的內(nèi)部結(jié)點(diǎn)度為6。靜態(tài)搏動式陣列可在多個方向上使數(shù)據(jù)流變成以流水線方式工作。商用IntelWarp系統(tǒng)(Anaratone等，1986)就是用搏動式結(jié)構(gòu)設(shè)計而成的。自從1978年Kung和Leiserson提出搏動式陣列后，它已成為廣泛研究的領(lǐng)域。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院通過確定的互連和同步操作，搏動式陣列可與算法的通信結(jié)構(gòu)相匹配。針對信號/圖象處理等特殊應(yīng)用，可提供更好的性能／價格比。缺點(diǎn)：其結(jié)構(gòu)的實(shí)用性有限，而且編程難。有興趣的讀者可參考S．Y．Kung(1988)關(guān)于用搏動式和波前沿結(jié)構(gòu)實(shí)現(xiàn)VLSI陣列處理機(jī)的專著。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院8.超立方體

這是一種二元n-立方體結(jié)構(gòu)，它已在iPSC、nCUBE和CM-2系統(tǒng)中得到實(shí)現(xiàn)。一個n-立方體由N＝2n個結(jié)點(diǎn)組成，它們分布在n維上，每維有兩個結(jié)點(diǎn)。8個結(jié)點(diǎn)的3-立方體如下圖所示。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院9.帶環(huán)立方體這種結(jié)構(gòu)是從超立方體改進(jìn)而來的。如下圖所示，一個3-立方體可改成帶環(huán)3-立方體(CCC)。構(gòu)成的辦法是將3-立方體的角結(jié)點(diǎn)(頂角)用一個結(jié)點(diǎn)環(huán)來代替。

哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院可以從一個k-立方體構(gòu)成一個有n＝2k個結(jié)點(diǎn)環(huán)的帶環(huán)k—立方體；如下圖所示，所用的辦法是用k個結(jié)點(diǎn)的環(huán)取代k維超立方體的每個頂角。一個k—立方體可變?yōu)閗X2k個結(jié)點(diǎn)的k-CCC。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院如圖所示3-CCC的直徑為6，比原來3-立方體的直徑大一倍。一般說來，k-CCC的網(wǎng)絡(luò)直徑2k，CCC的主要改進(jìn)之處即在其結(jié)點(diǎn)度為常數(shù)3，與超立方體的維數(shù)無關(guān)。假設(shè)一超立方體有N=2n結(jié)點(diǎn)。一個有同樣N結(jié)點(diǎn)數(shù)的CCC一定是由低維k—立方體組成，即2n＝k·2k，其中k<n。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題：對應(yīng)于n＝6和k=4的情況；一個64結(jié)點(diǎn)的CCC可用4結(jié)點(diǎn)的環(huán)取代4—立方體的角結(jié)點(diǎn)組成。CCC的直徑為2k＝8；比6-立方體的6要長些。CCC的結(jié)點(diǎn)度為3，比6-立方體的結(jié)點(diǎn)度6要小。如果容許一定的時延，則CCC是一種構(gòu)造可擴(kuò)展系統(tǒng)的較好的結(jié)構(gòu)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院10.k元n-立方體網(wǎng)絡(luò)環(huán)形、網(wǎng)格形、環(huán)網(wǎng)形、二元n-立方體(超立方體)和?網(wǎng)絡(luò)都是k元n-立方體網(wǎng)絡(luò)系列的拓?fù)渫瑯?gòu)體。下圖所示是一種4元3-立方體網(wǎng)絡(luò)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院參數(shù)n是立方體的維數(shù)，k是基數(shù)或者說是沿每個方向的結(jié)點(diǎn)數(shù)(多重性)。這兩個數(shù)與網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)N的關(guān)系為：N＝kn，(k=N1/n，n＝logkN)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院k元n-立方體的結(jié)點(diǎn)可用基數(shù)為k的n位地址；A＝a0a1a2…an來表示，其中ai代表第i維結(jié)點(diǎn)的位置。為簡單起見，所有鏈路都認(rèn)為是雙向的。各結(jié)點(diǎn)之間的連線都是雙向鏈路。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院低維k元n-立方體稱為環(huán)網(wǎng)；而高維二元n-立方體則稱為超立方體。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院總結(jié)：大多數(shù)網(wǎng)絡(luò)的結(jié)點(diǎn)度都小于4，這是比較理想的。網(wǎng)絡(luò)直徑的變化范圍很大，直徑已不是一個嚴(yán)重問題。鏈路數(shù)會影響網(wǎng)絡(luò)價格，等分寬度將影響網(wǎng)絡(luò)的帶寬。對稱性會影響可擴(kuò)展性和尋徑效率?？陀^地說，網(wǎng)絡(luò)的總價格隨節(jié)點(diǎn)度和鏈路度增大而上升。直徑小仍然是一種優(yōu)點(diǎn)。結(jié)點(diǎn)間的平均距離可能是一種更好的量度指標(biāo)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院第6章系統(tǒng)的互聯(lián)和千兆位網(wǎng)絡(luò)

1互連網(wǎng)絡(luò)基礎(chǔ)

2靜態(tài)連接網(wǎng)絡(luò)

3動態(tài)連接網(wǎng)絡(luò)

4消息傳遞機(jī)制

5千兆位網(wǎng)絡(luò)技術(shù)

6ATM交換器和網(wǎng)絡(luò)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院

3動態(tài)連接網(wǎng)絡(luò)目的和種類：按照價格和性能增加的順序，動態(tài)連接網(wǎng)絡(luò)的排隊次序?yàn)椋憾嗵幚頇C(jī)的總線；交叉開關(guān)網(wǎng)絡(luò)。多級互連網(wǎng)絡(luò)(MIN)；哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院動態(tài)網(wǎng)絡(luò)的性能：可用網(wǎng)絡(luò)帶寬通過網(wǎng)絡(luò)的最大數(shù)據(jù)傳輸率，用M字節(jié)／秒表示數(shù)據(jù)傳輸速率網(wǎng)絡(luò)時延單位消息通過網(wǎng)絡(luò)傳送時最壞情況下的時間延遲

所用的通信模式哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院一.多處理機(jī)的總線定義：特點(diǎn)：數(shù)字總線已被稱為多個功能模塊間的爭用總線(contentionbus)或時分總線(time-sharingbus)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院二.開關(guān)模塊1.一個a×b開關(guān)模塊有a個輸入和b個輸出。一個二元開關(guān)則與a＝b＝2的2X2開關(guān)模塊相對應(yīng)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2X2交叉開關(guān)可有兩種連接模式：直送交叉哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.4X4的交叉開關(guān)的模塊哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院3.交叉開關(guān)網(wǎng)絡(luò)

特點(diǎn)：交叉開關(guān)網(wǎng)絡(luò)的帶寬和互連特性最好。可看作是一個單級開關(guān)網(wǎng)絡(luò)。交叉點(diǎn)開關(guān)能在對偶(源、目的)之間形成動態(tài)連接，每個交叉點(diǎn)開關(guān)在對偶間提供一條專用連接通路，開關(guān)可根據(jù)程序的要求動態(tài)地設(shè)置“開”或“關(guān)”。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題：下圖所示兩種交叉開關(guān)網(wǎng)絡(luò)(1)C.mmp多處理機(jī)可以在處理機(jī)和存儲模塊之間用交叉開關(guān)網(wǎng)絡(luò)構(gòu)成一個共享存儲型多處理機(jī)，實(shí)際上這是一個存儲器訪問網(wǎng)絡(luò)C.mmp多處理機(jī)已實(shí)現(xiàn)了一個16X16交叉開關(guān)網(wǎng)絡(luò)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院(2)Fujitsu公司(1992)制造的向量并行處理機(jī)還有一種交叉開關(guān)網(wǎng)絡(luò)可用于處理機(jī)間通信，如下圖所示。(VPP500)實(shí)際上就是采用了這種大型交叉開關(guān)網(wǎng)絡(luò)(224X224)其中PE為接有存儲器的處理機(jī)，CP代表控制處理機(jī)，用來監(jiān)控整個系統(tǒng)，包括交叉開關(guān)網(wǎng)絡(luò)的運(yùn)行。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院交叉開關(guān)網(wǎng)絡(luò)的局限性每臺處理機(jī)可以向多個存儲模塊發(fā)出請求。n×n的交叉開關(guān)網(wǎng)絡(luò)在每個存儲周期最多可為n臺處理機(jī)發(fā)送n個存儲字。交叉開關(guān)網(wǎng)絡(luò)每個存儲周期可以實(shí)現(xiàn)n個數(shù)據(jù)傳輸，與每個總線周期只傳一個數(shù)據(jù)相比，它的頻寬最高。由于所有必要的開關(guān)和解決沖突的邏輯都做在交叉點(diǎn)開關(guān)中，所以處理機(jī)接口和存儲器端口的邏輯就變得比較簡單，因而也比較便宜。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院交叉開關(guān)網(wǎng)絡(luò)對只有幾臺處理機(jī)訪問幾個存儲器模塊的小型多處理機(jī)系統(tǒng)來說性能價格比比較高。單級交叉開關(guān)網(wǎng)絡(luò)一旦構(gòu)成后將不能擴(kuò)充冗余或奇偶校驗(yàn)線可以做在每個交叉點(diǎn)開關(guān)中，以便增強(qiáng)交叉開關(guān)網(wǎng)絡(luò)的容錯性和可靠性除了用電子元件構(gòu)造交叉開關(guān)網(wǎng)絡(luò)外，科研機(jī)構(gòu)正在研究用光電元件構(gòu)造較大較快的網(wǎng)絡(luò)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院三.多級網(wǎng)絡(luò)

一種通用多級網(wǎng)絡(luò)如下圖所示；各種MIN的區(qū)別就在于：所用開關(guān)模塊和級間連接(ISC)模式的不同。最簡單的開關(guān)模塊是2×2開關(guān)。常用的ISC模式包括有均勻洗牌、蝶式、多路洗牌、縱橫交叉、立方體連接等。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院四.?網(wǎng)絡(luò)1.?網(wǎng)絡(luò)的構(gòu)造下圖所示的是一個16×16?網(wǎng)絡(luò)，共需4級2×2開關(guān)。網(wǎng)絡(luò)左側(cè)有16個輸入，右側(cè)有16個輸出ISC是對16個對象的均勻洗牌模式

哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院一個n輸入的?網(wǎng)絡(luò)需要log2n級2X2開關(guān)，每級要用n／2個開關(guān)模塊，?網(wǎng)絡(luò)共需nlog2n／2個開關(guān)。每個開關(guān)模塊采用單元控制方式。不同的開關(guān)狀態(tài)組合可實(shí)現(xiàn)各種置換、廣播或從輸入到輸出的其它連接哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.?網(wǎng)絡(luò)尋徑控制8個輸入端的Omega網(wǎng)絡(luò)如下圖所示。通常，n個輸入端的Omega網(wǎng)絡(luò)有l(wèi)ogan級(開關(guān)輸入a個）從輸入級到輸出級依次編號為:0到log2n-1哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院控制方法:目的地址控制法;通過檢查二進(jìn)制目的地址編碼來控制數(shù)據(jù)路徑。目的地址編碼從高位開始的第i位為0時，第i級的2X2開關(guān)的輸入端與上輸出端連接否則輸入端與下輸出端連接。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題：下圖的開關(guān)設(shè)置對應(yīng)于置換

1=(0，7，6，4，2)(1，3)(5)中的開關(guān)設(shè)置，

1的映射為0—7，7—6，6—4，4—2，2—0，1—3，3—1，5—5。觀察一個消息從輸入端001到輸出端011的路徑。它使用了開關(guān)A、B和C。實(shí)現(xiàn)

1的置換所要求的開關(guān)設(shè)置，不存在沖突。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院置換

2＝(0，6，4，7，3)(1，5)(2)。現(xiàn)在再來考察8個輸入端口的Omega網(wǎng)絡(luò)實(shí)現(xiàn)置換

2的情況。開關(guān)F、G和H的設(shè)置發(fā)生了沖突哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院F沖突---由000→110和100→111引起；G沖突---由011→000和111→011引起；H沖突---由101→001和011→000引起哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院Omega網(wǎng)絡(luò)是一種阻塞網(wǎng)絡(luò)。當(dāng)出現(xiàn)阻塞時，可以采用幾次通過的方法解決沖突。例如

2

，在第一次通過時實(shí)現(xiàn)連接000—110，001→101，010→010，101→001，110→100。在第二次通過時實(shí)現(xiàn)連接011→000，100→111，111→011。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院討論：如果采用2X2開關(guān)元件，n個輸入端Omega網(wǎng)絡(luò)一次通過可以實(shí)現(xiàn)nn／2個置換，但總共有n!個置換。n個輸入端的Omega網(wǎng)絡(luò)一次通過只能實(shí)現(xiàn)全部置換的nn／2/n!一般來說，n個輸入端的Omega網(wǎng)絡(luò)實(shí)現(xiàn)非阻塞連接最多需要通過的次數(shù)為log2n。在任何多級網(wǎng)絡(luò)中都不希望出現(xiàn)阻塞，阻塞將降低有效頻寬。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題：n＝8時：8個輸入端的Omega網(wǎng)絡(luò)一次通過只能實(shí)現(xiàn)全部置換的10．16％，即84／8！＝4096／40320＝0．1016＝10．16％。所有其它置換將引起阻塞。實(shí)現(xiàn)這些置換需要三次通過。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題如下圖所示，采用上播或下播開關(guān)設(shè)置，Omega網(wǎng)絡(luò)也可以從一個源將數(shù)據(jù)廣播給多個目的地。在輸人端001的消息通過二進(jìn)制樹的連接廣播到所有8個輸出端。

哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題：下圖是用4X4開關(guān)元件作為構(gòu)成塊的Omega網(wǎng)絡(luò)，級間是4路洗牌連接，而不是2路洗牌連接。16個輸入端的Omega網(wǎng)絡(luò)的級數(shù)為:log416＝2哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院4路洗牌相當(dāng)于把16個輸人端平均地分成4個子組，然后4個子組均勻地洗牌。當(dāng)采用是kXk開關(guān)元件時，則可以定義k路洗牌函數(shù)來構(gòu)造更大的級數(shù)為logkn的Omega網(wǎng)絡(luò)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院五.基準(zhǔn)網(wǎng)絡(luò)

Wu和Feng(1980)研究過多級互連網(wǎng)絡(luò)之間的關(guān)系。基準(zhǔn)網(wǎng)絡(luò)可如下圖所示遞歸生成。第一級為一個N×N模塊；第二級為兩個(N／2)X(N／2)子模塊，以C0和C1表示。以上構(gòu)成方法可遞歸用于子模塊，直至得到2×2的N／2子模塊為止。每個塊有兩個合法狀態(tài)：兩個輸出和輸入的直送和交叉。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院總結(jié)：總線的造價最低其缺點(diǎn)是每臺處理機(jī)可用的帶寬較窄?？偩€所存在的另一個問題是容易產(chǎn)生故障。交叉開關(guān)硬件復(fù)雜性以n2上升，所以其造價最為昂貴。但是，交叉開關(guān)的帶寬和尋徑性能最好。如網(wǎng)絡(luò)的規(guī)模較小，它是一種理想的選擇。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院多級網(wǎng)絡(luò)：則是兩個極端之間的折衷。它的主要優(yōu)點(diǎn)在于采用模塊結(jié)構(gòu)，因而可擴(kuò)展性較好。然而，其時延隨網(wǎng)絡(luò)的級數(shù)log2n而上升。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院第6章系統(tǒng)的互聯(lián)和千兆位網(wǎng)絡(luò)

1互連網(wǎng)絡(luò)基礎(chǔ)

2靜態(tài)連接網(wǎng)絡(luò)

3動態(tài)連接網(wǎng)絡(luò)

4消息傳遞機(jī)制

5千兆位網(wǎng)絡(luò)技術(shù)

6ATM交換器和網(wǎng)絡(luò)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院

4消息傳遞機(jī)制主要研究：存儲轉(zhuǎn)發(fā)；蟲蝕尋徑方法；它們的通信時延問題；針對無死鎖的消息尋徑確定的尋徑算法和自適應(yīng)兩種尋徑算法。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院一、

消息尋徑方式1.消息的格式（1）消息(message)是結(jié)點(diǎn)間通信的邏輯單位，它常常由任意數(shù)目的長度固定的包組成，因此它的長度是可變的。在消息傳遞網(wǎng)絡(luò)中通信的信息單位是：消息、包和片的格式。消息尋徑中的信息單位如下圖所示。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院（2）包(packet)是含尋徑目的地址的基本單位；每個包需要一個序號；不同的包可能異步地到達(dá)目的結(jié)點(diǎn)，以便把傳送的消息重新裝配起來。在采用存儲轉(zhuǎn)發(fā)尋徑方式的多計算機(jī)系統(tǒng)中，包是信息傳送的最小單位。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院包的長度取決于尋徑方式和網(wǎng)絡(luò)的實(shí)現(xiàn)方法。典型的包長度為64--512位。序號可能占用1--2個片，取決于消息的長度。包和片的大小還與通道頻寬、尋徑器設(shè)計以及網(wǎng)絡(luò)流量密度等有關(guān)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院（3）片：包可分成一些固定長度的數(shù)據(jù)片。尋徑信息(目的地址)和序號形成頭片，其余的片是數(shù)據(jù)。在采用蟲蝕尋徑網(wǎng)絡(luò)的多計算機(jī)中，包可進(jìn)一步分成片。片的長度往往受網(wǎng)絡(luò)大小的影響，256個結(jié)點(diǎn)的網(wǎng)絡(luò)需要片長為8位。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.存儲轉(zhuǎn)發(fā)尋徑定義：下圖說明了這一概念。在存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)中包是信息流的基本單位。存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)的時延與源和目的之間的距離(段數(shù))成正比。第一代多計算機(jī)系統(tǒng)采用這種尋徑方式。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院3.蟲蝕尋徑新型的計算機(jī)系統(tǒng)都采用蟲蝕尋徑方式，把包進(jìn)一步分成更小的片；與結(jié)點(diǎn)相連的硬件尋徑器中有片緩沖區(qū)。消息從源結(jié)點(diǎn)傳送到目的結(jié)點(diǎn)要經(jīng)過一系列尋徑器。同一個包中所有的片，象不可分離的同伴一樣以流水方式順序地傳送。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院特點(diǎn)：所有數(shù)據(jù)片必須跟著頭片。不同的包可交替地傳送，但不同包的片不能交叉。否則它們可能被送到錯誤的目的地。蟲蝕尋徑的時延幾乎與源和目的之間的距離無關(guān)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院4.異步流水采用如下圖所示的握手協(xié)議，可以實(shí)現(xiàn)一個包內(nèi)相繼片的異步流水運(yùn)行。異步流水的效率很高，所用的時鐘比同步流水的時鐘快，如果路徑中的片、緩沖片或后繼通道在某個周期不能使用的話，則流水線將出現(xiàn)阻塞。如果出現(xiàn)這種情況，則包可能要緩沖、阻塞、延緩或繞道通過。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院5.時延分析下圖是包通過存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)和蟲蝕網(wǎng)絡(luò)的時間比較情況其中：L是包的長度(位)W是通道頻寬(位／秒)D是距離(經(jīng)過的結(jié)點(diǎn)數(shù)-1)F是片的長度(位)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院存儲尋徑網(wǎng)絡(luò)的通信時延TSF可表示為：TSF＝L／W×(D+1)蟲蝕尋徑TWH：TWH

＝L／W+F／W×D顯然：TSF與D成正比；如果L》F，那么TWH=L／W，距離D對尋徑延時的影響可忽略不計。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院典型的TSF值約在2000至6000

s之間，而典型的TWH值只有5

s或者更小。存儲轉(zhuǎn)發(fā)尋徑往往由軟件控制，而蟲蝕尋徑則完全用硬件尋徑器以流水方式工作。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院二、死鎖和虛擬通道1.虛擬通道虛擬通道是兩個結(jié)點(diǎn)間的邏輯鏈，它由源結(jié)點(diǎn)的片緩沖區(qū)、結(jié)點(diǎn)間的物理通道以及接收結(jié)點(diǎn)的片緩沖區(qū)組成。下圖說明了四條虛擬通道共享一條物理通道的概念。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院通道的特點(diǎn)：兩個端點(diǎn)增加了緩沖區(qū)和用來控制虛擬通道狀態(tài)的R／A線。實(shí)現(xiàn)虛擬通道需要用交叉開關(guān)控制、多路選擇器和多路分配器。物理通道由所有的虛擬通道分時地共享。以片傳遞為基礎(chǔ)的分時方法可使一組虛擬通道共享一條物理通道。用某些通道狀態(tài)(如R／A信號)來表示不同的虛擬通道，控制源緩沖區(qū)存放等待使用通道片。通道(電纜或光纖)是它們之間的通信媒介哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題

通道上的循環(huán)等待引起的死鎖如下圖所示，有兩類死鎖是由緩沖區(qū)或通道上的循環(huán)等待引起的。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院如下圖采用蟲蝕尋徑的網(wǎng)格形網(wǎng)絡(luò)中，四條消息沿四個通道同時傳送也會產(chǎn)生通道死鎖(channeldeadlock)

4個消息的4個片同時占用了4個通道。如果循環(huán)中沒有一個通道被釋放，死鎖狀態(tài)將持續(xù)下去哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.死鎖的避免通過增加兩條虛擬通道V3和V4，可以打破死鎖循環(huán)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院雙向通道與單項(xiàng)通道的實(shí)現(xiàn)比較虛擬通道可以用單向通道或者雙向通道實(shí)現(xiàn)。把兩條單向通道組合可以構(gòu)成一條雙向通道；雙向通道中的仲裁要復(fù)雜一點(diǎn)。單向通道相比較，雙向通道由于要做方向仲裁，因而增加了延遲，又由于控制復(fù)雜，因而還增加了成本。網(wǎng)絡(luò)的流量不大時，雙向通道效率比較高。確定虛擬通道數(shù)目時，需要對網(wǎng)絡(luò)吞吐量和通信時延折衷考慮。實(shí)現(xiàn)數(shù)目很大的虛擬通道需要用高速的多路選擇開關(guān)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院三、流控制策略1.問題的提出：當(dāng)兩個或更多的包在某個結(jié)點(diǎn)為競爭緩沖區(qū)或通道資源而發(fā)生沖突時，必須確定如何解決沖突的策略。針對一對一通信尋徑算法和自適應(yīng)尋徑算法進(jìn)行討論。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.包沖突的解決

必須具備三個條件：(1)源緩沖區(qū)已存有該片；(2)通道已分配好；(3)接收緩沖區(qū)準(zhǔn)備接收該片哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院另外還存在：當(dāng)兩個包到達(dá)同一個結(jié)點(diǎn)時，它們可能會請求用同一個接收緩沖區(qū)或者要用同一個輸出通道，因此必須對兩個問題做出仲裁：(1)把通道分配給哪個包?(2)沒有分配到通道的包做什么事?哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院3.兩個包爭用的主要解決方法：虛擬直通尋徑緩沖方法虛擬直通方法是存儲轉(zhuǎn)發(fā)和蟲蝕兩種尋徑方法的折衷。當(dāng)不發(fā)生沖突時，就如同蟲蝕尋徑方法一樣工作，效果與存儲轉(zhuǎn)發(fā)尋徑方法相同。阻塞策略蟲蝕尋徑在出現(xiàn)沖突時就采用阻塞策略。第2個包被阻塞不再前進(jìn)，但并沒有被揚(yáng)棄。某些多計算機(jī)網(wǎng)絡(luò)綜合了以上某些流控制策略的優(yōu)點(diǎn)，采用混合策略。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院4.維序?qū)桨鼘娇梢詺w結(jié)為確定和自適應(yīng)兩類。確定尋徑通信路徑完全由源和目的地址確定。維序?qū)叫枰环N按照多維網(wǎng)絡(luò)維序的特定順序來選擇后繼通道。在二維網(wǎng)格網(wǎng)絡(luò)中稱為X—Y尋徑，首先沿著X維方向確定路徑，然后沿著Y維方向選擇路徑。代表是E立方體尋徑(E—cuberouting)方法哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院超立方體網(wǎng)絡(luò)的E立方體尋徑

假設(shè)有一N＝2n個結(jié)點(diǎn)的n方體。每個結(jié)點(diǎn)的二進(jìn)制編碼為:b＝bn-1bn-2…b1b0。源結(jié)點(diǎn)為s＝sn-1ssn-2…s1s0目的結(jié)點(diǎn)d＝dn-1sdn-2…d1d0要確定一條從s到d的步數(shù)最小的路徑。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院將n維表示成i＝1，2，…n，其中第i維對應(yīng)于結(jié)點(diǎn)地址中的第i-1位。設(shè)v=vn-1vn-2…v1v0是路徑中的任一結(jié)點(diǎn)。路徑可以根據(jù)以下方法唯一地確定。①計算方向位ri＝si-1

di-1，其中i＝1，2，…，n。使i＝1，v＝s，開始以下步驟。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院②如果ri=1，則從當(dāng)前結(jié)點(diǎn)v尋徑到下一結(jié)點(diǎn)：v

2i-1。如果ri=0則跳過這步；③i

i+1。如果i≤n，則轉(zhuǎn)第2步，否則退出。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題4維超立方體網(wǎng)絡(luò)的正方體尋徑n＝4，s＝0110，d＝1101，因而r＝r4r3r2r1＝1011。由于r1＝0

1＝1，因此s就尋徑到s

20＝0111。由于r2＝1

0＝1，因此v＝0111就尋徑到v

21＝0101。由于r3＝1

1＝0，因此就可以跳過維i＝3這一步。由于r4＝1，因此v＝0101就尋徑到v

23＝1101＝d。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院5.二維網(wǎng)格網(wǎng)絡(luò)的X-Y尋徑X-Y尋徑共有四種模式。東—北、東—南、西—北和西—南的路徑方向假定從任意源結(jié)點(diǎn)s＝(x1,y1)到任意目的結(jié)點(diǎn)d＝(x2,y2);尋徑從s開始，首先沿x方向前進(jìn)一直到d所在的第y2列為止，然后沿y方向前進(jìn)直到d。

哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題：二維網(wǎng)格連接多計算機(jī)的X—Y尋徑下圖中有4個(源，目的)對，可用以說明二維網(wǎng)格的4種尋徑模式。從結(jié)點(diǎn)(2，1)到結(jié)點(diǎn)(7，6)需要一條東—北路徑。從結(jié)點(diǎn)(0，7)到結(jié)點(diǎn)(4，2)要建立一條東—南路徑。從結(jié)點(diǎn)(5，4)到結(jié)點(diǎn)(2，0)需要一條西—南路徑。從結(jié)點(diǎn)(6，3)到結(jié)點(diǎn)(1，5)需要一條西—北方向路徑。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院6.自適應(yīng)尋徑方法

采用自適應(yīng)尋徑的主要目的是避免死鎖。采用的方法--虛擬通道哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題使用虛擬通道的自適應(yīng)X-Y尋徑這是一個用X—Y尋徑的網(wǎng)格網(wǎng)絡(luò)示例，在Y維上用了2對虛擬通道。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院四、選播尋徑算法1.通信模式多計算機(jī)網(wǎng)絡(luò)中可能會出現(xiàn)四類通信模式一個源結(jié)點(diǎn)和一個目的結(jié)點(diǎn)的一對一的單播(Unicast)模式哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院選播(Multicast)模式：對應(yīng)于一到多的通信情況，即一個源結(jié)點(diǎn)發(fā)送同一個消息到多個目的結(jié)點(diǎn)。廣播(Broadcast)模式：對應(yīng)于一到全體的通信情況。會議(Conference)模式是多到多的通信。實(shí)現(xiàn)這些多目的模式必須使用特殊的硬件或?qū)椒椒?。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.尋徑效率常用的兩個參數(shù)是通道流量和通信時延。通道流量：任何時刻的傳輸有關(guān)消息所使用的通道數(shù)來表示。通信時延：包的最長傳輸時間來表示。優(yōu)化的尋徑網(wǎng)絡(luò)應(yīng)能以最小流量和最小時延實(shí)現(xiàn)有關(guān)通信模式。在存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)中時延是最重要的問題；在蟲蝕尋徑網(wǎng)絡(luò)中流量對效率的影響更大。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題網(wǎng)格連接計算機(jī)中的選播和廣播

下圖是在3X3網(wǎng)格上實(shí)現(xiàn)的選播尋徑。源結(jié)點(diǎn)用S表示，傳送一個包到標(biāo)號為n的s個目的結(jié)點(diǎn)。這里，i＝1，2，…，5。目的為5個的選播可以用5次單播來實(shí)現(xiàn)，如下圖所示。X-Y尋徑的流量需要用1+3+4+3+2=13條通道，到D3的路徑最長，所以時延是4。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院例題超立方體計算機(jī)上選播和廣播

為在n方體上實(shí)現(xiàn)廣播，可用類似的生成樹時延不超過n就能到達(dá)所有結(jié)點(diǎn)。下圖是一個根結(jié)點(diǎn)為0000的4-立方體。超立方體廣播樹的流量最小。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院可以得到一棵貪婪選播樹，可從結(jié)點(diǎn)0101發(fā)送包到7個目的結(jié)點(diǎn)。這個貪婪選播算法的基本思想是向那些可達(dá)最多剩余目的結(jié)點(diǎn)的維方向發(fā)送包。從源結(jié)點(diǎn)S＝0101開始，由維2方向可以到達(dá)2個目的結(jié)點(diǎn)，由維4方向可以到達(dá)5個目的結(jié)點(diǎn)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院第一層所用的通道是0101

0111和0101

1101。從結(jié)點(diǎn)1101，由維2方向可以到達(dá)3個目的結(jié)點(diǎn)，由維1方向可以到達(dá)4個目的結(jié)點(diǎn)。第二層所用的通道是1101

1111，1101

1100和0111

0110。第三層所用的通道是1111

1110，1111

1011，1100-1000和0110-0010。第四層所用的通道是1110

1010。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院所生成的樹不是唯一的在擴(kuò)充選播樹時，首先應(yīng)該比較所有各維方向的可達(dá)性(reachability)，然后選擇某些維使剩余目的結(jié)點(diǎn)的集合最小。兩維之間有連線，那么選擇其中任何一維都可以。已經(jīng)證明貪婪選播算法所需的通道數(shù)與多次單播或廣播樹相比要少。在蟲蝕尋徑網(wǎng)絡(luò)中，實(shí)現(xiàn)選播操作時，每個結(jié)點(diǎn)的尋徑器應(yīng)有復(fù)制片緩沖區(qū)中數(shù)據(jù)的能力。為了與選播樹或廣播樹的增長同步，樹中同一層的所有輸出通道必須在傳輸向前推進(jìn)一層之前處于就緒狀態(tài)，否則中間結(jié)點(diǎn)需要增加緩沖區(qū)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院第6章系統(tǒng)互聯(lián)和千兆位網(wǎng)絡(luò)

1互連網(wǎng)絡(luò)基礎(chǔ)

2靜態(tài)連接網(wǎng)絡(luò)

3動態(tài)連接網(wǎng)絡(luò)

4消息傳遞機(jī)制

5千兆位網(wǎng)絡(luò)技術(shù)

6ATM交換器和網(wǎng)絡(luò)哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院

5千兆位網(wǎng)絡(luò)技術(shù)一、問題的提出1.機(jī)群系統(tǒng)如下圖哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院1.機(jī)群系統(tǒng)5個體系結(jié)構(gòu)概念融為一個機(jī)群，它是全體計算機(jī)(結(jié)點(diǎn))的互連集。這些互連的計算機(jī)能集體地工作，尤如一個單一系統(tǒng)，以提供不會被中斷(可用性)和有效的(性能)服務(wù)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院解釋：機(jī)群是全體計算機(jī)(結(jié)點(diǎn))的集合，這些計算機(jī)由高性能網(wǎng)絡(luò)或局域網(wǎng)(LAN)物理地互連典型情況下，每個計算機(jī)結(jié)點(diǎn)是一臺SMP服務(wù)器、一臺工作站或是一臺PC計算機(jī)所有機(jī)群結(jié)點(diǎn)必須能一起集體工作，如同一個單一集成的計算資源，除了滿足由交互用戶單獨(dú)地使用每個結(jié)點(diǎn)的協(xié)定任務(wù)之外哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2.特征計算機(jī)機(jī)群特征（一）COW的每個結(jié)點(diǎn)是一個完整工作站，但沒有某些外圍設(shè)備(如監(jiān)視器、鍵盤、鼠標(biāo)等)。有時稱這類結(jié)點(diǎn)為“無頭工作站”。一個結(jié)點(diǎn)也可以是一臺SMP或是一臺PC。結(jié)點(diǎn)通過低廉的商品化網(wǎng)絡(luò)，如以太網(wǎng)、FDDI、光通道和ATM開關(guān)實(shí)現(xiàn)互連，雖然在某些商用機(jī)群中也使用專用網(wǎng)絡(luò)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院計算機(jī)機(jī)群特征（二）網(wǎng)絡(luò)接口與結(jié)點(diǎn)中的I/O總線松耦合相連。與此相反，MPP中則用緊耦合網(wǎng)絡(luò)接口,它與處理結(jié)點(diǎn)的存儲器總線連接?？傆幸粋€局部磁盤，而在MPP結(jié)點(diǎn)中可能沒有在每個結(jié)點(diǎn)上駐留有完整的操作系統(tǒng)，而在某些MPP的結(jié)點(diǎn)中只有操作系統(tǒng)的微核哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院總之：COW的操作系統(tǒng)是相同的工作站UNIX，加上一個附加軟件層以支持單一系統(tǒng)映像、可用性、并行性、通信以及負(fù)載平衡現(xiàn)在MPP和COW之間的界限正變得日益模糊。IBMSP2被認(rèn)為是一個MPP。但除了用作通信網(wǎng)絡(luò)的專用高性能開關(guān)之外，它是機(jī)群體系結(jié)構(gòu)與MPP相比，機(jī)群具有許多成本/性能優(yōu)點(diǎn)。機(jī)群化正成為開發(fā)可擴(kuò)展并行計算機(jī)的趨向。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院二、千兆位的光纖通道和FDDI環(huán)……哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院

6ATM交換器和網(wǎng)絡(luò)異步傳輸模式(ATM)由ATM論壇(成立于1991年)和ITU標(biāo)準(zhǔn)定義。大多數(shù)計算機(jī)公司都有它們的ATM組網(wǎng)技術(shù)以支持企業(yè)和局域網(wǎng)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院一、ATM技術(shù)ATM是一種獨(dú)立于介質(zhì)的消息傳輸協(xié)議，它將消息段傳輸轉(zhuǎn)變成更短的固定長度為53字節(jié)的報元傳輸。這種技術(shù)是基于片交換機(jī)制。ATM的目的是將實(shí)時(也就是延時敏感的)和突發(fā)數(shù)據(jù)(也就是非延時敏感的)兩個方面的傳輸變成統(tǒng)一的網(wǎng)絡(luò)技術(shù)。哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院1.ATM報元格式如圖所示，長報文在傳輸經(jīng)過ATM網(wǎng)絡(luò)之前，必須分成多個報元。使用小報元、虛路徑和虛通道使