哈工大并行計(jì)算課件第六章

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

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

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

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

4消息傳遞機(jī)制

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

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

1

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

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

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

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

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

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

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

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

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

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

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

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

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

4消息傳遞機(jī)制

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

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

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

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

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

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

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

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

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

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

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

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

2

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

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

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

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

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

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

4消息傳遞機(jī)制

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

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

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

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

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

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

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

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

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

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

假設(shè)有一N＝2n個(gè)結(jié)點(diǎn)的n方體。每個(gè)結(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ì)算機(jī)科學(xué)與技術(shù)學(xué)院將n維表示成i＝1，2，…n，其中第i維對(duì)應(yīng)于結(jié)點(diǎn)地址中的第i-1位。設(shè)v=vn-1vn-2…v1v0是路徑中的任一結(jié)點(diǎn)。路徑可以根據(jù)以下方法唯一地確定。①計(jì)算方向位ri＝si-1

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

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

i+1。如果i≤n，則轉(zhuǎn)第2步，否則退出。哈爾濱工業(yè)大學(xué)計(jì)算機(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，因此就可以跳過(guò)維i＝3這一步。由于r4＝1，因此v＝0101就尋徑到v

23＝1101＝d。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計(jì)算機(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開(kāi)始，首先沿x方向前進(jìn)一直到d所在的第y2列為止，然后沿y方向前進(jìn)直到d。

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院例題：二維網(wǎng)格連接多計(jì)算機(jī)的X—Y尋徑下圖中有4個(gè)(源，目的)對(duì)，可用以說(shuō)明二維網(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ì)算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院6.自適應(yīng)尋徑方法

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

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

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

0111和0101

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

1111，1101

1100和0111

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

1110，1111

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

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

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

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

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

4消息傳遞機(jī)制

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

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

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

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