互聯(lián)網(wǎng)絡(luò)培訓(xùn)教程[2]

互聯(lián)網(wǎng)絡(luò)培訓(xùn)教程[2]

?5.廣播和選播

??? 廣播是一種一對全體的映射，選播是一個子集到另一子集(多對多)的映射。消息傳遞型多處理機一般有廣播信息機構(gòu)，廣播常常作為多處理機中的全局操作來處理。通過上面的討論，我們可概括出影響互連網(wǎng)絡(luò)性能的因素為：

??? (1) 功能特性——網(wǎng)絡(luò)如何支持路由、中斷處理、同步、請求/消息組合和一致性。

??? (2) 網(wǎng)絡(luò)時延——單位消息通過網(wǎng)絡(luò)傳送時最壞情況下的時間延遲。

??? (3) 帶寬——通過網(wǎng)絡(luò)的最大數(shù)據(jù)傳輸率，用MB/s表示。

??? (4) 硬件復(fù)雜性——諸如導(dǎo)線、開關(guān)、連接器、仲裁和接口邏輯等的造價。

??? (5) 可擴展性——在增加機器資源使性能可擴展的情況下，網(wǎng)絡(luò)具備模塊化可擴展的能力。

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

??? 靜態(tài)網(wǎng)絡(luò)使用直接鏈路，它一旦構(gòu)成后就固定不變。這種網(wǎng)絡(luò)比較適合于構(gòu)造通信模式可預(yù)測或可用靜態(tài)連接實現(xiàn)的計算機系統(tǒng)。 下面介紹幾種靜態(tài)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、網(wǎng)絡(luò)參數(shù)及其可擴展性。

?

?1.線性陣列(linear array)

　　這是一種一維的線性網(wǎng)絡(luò)，其中N個結(jié)點用N-1個鏈路連成一行(圖6.3.7)。內(nèi)部結(jié)點度為2，端結(jié)點度為1。直徑為N-1，N較大時，直徑就比較長。等分寬度為1。線性陣列是連接最簡單的拓撲結(jié)構(gòu)。這種結(jié)構(gòu)不對稱，當(dāng)N很大時，通信效率很低。

??? 在N很小的情況下，使用線性陣列是相當(dāng)經(jīng)濟和合理的。由于直徑隨N線性增大，因此當(dāng)N比較大時，就不應(yīng)使用這種方案了。

?2. 環(huán)和帶弦環(huán)(chordal ring)

??? 環(huán)是用一條附加鏈路將線性陣列的兩個端點連接起來而構(gòu)成的(圖6.3.8)。環(huán)可以單向工作，也可以雙向工作。它是對稱的，結(jié)點度是常數(shù)2。雙向環(huán)的直徑為N/2，單向環(huán)的直徑是N。

??? 如果將結(jié)點度由2提高至3或4，即可得到如圖6.3.9所示的兩種帶弦環(huán)。增加的鏈路愈多，結(jié)點度愈高，網(wǎng)絡(luò)直徑就愈小。16個結(jié)點的環(huán)(圖6.3.8)與兩個帶弦環(huán)(圖6.3.9)相比，網(wǎng)絡(luò)直徑分別由8減至5和3。在極端情況下，圖6.3.10 的全連接網(wǎng)絡(luò)(completely connected network)的結(jié)點度為15，直徑最短，為1。

??? 3. 循環(huán)移數(shù)網(wǎng)絡(luò)(barrel shifter)

??? 圖6.3.11所示的是一個循環(huán)移數(shù)網(wǎng)絡(luò)，其結(jié)點數(shù)N=16，它是通過在環(huán)上每個結(jié)點到所有與其距離為2的整數(shù)冪的結(jié)點之間都增加一條附加鏈而構(gòu)成的。這就是說,如果｜j-i｜=2r，r=0,1,2,…,n-1，網(wǎng)絡(luò)規(guī)模N=2n，則結(jié)點i與結(jié)點j連接。這種循環(huán)移數(shù)網(wǎng)絡(luò)的結(jié)點度為d=2n-1，直徑D=n/2。

4. 樹形和星形(tree and star)

??? 一棵5層31個結(jié)點的二叉樹如圖6.3.12所示

?

??? 一般說來，一棵k層完全平衡的二叉樹有N=2k-1個結(jié)點。最大結(jié)點度是3，直徑是2(k-1)。由于結(jié)點度是常數(shù)，因此二叉樹是一種可擴展的結(jié)構(gòu)，但其直徑較長。哥倫比亞大學(xué)于1987年研制成的DADO多處理機即采用10層二叉樹形式，有1023個結(jié)點。星形是一種2層樹，結(jié)點度較高，為d=N-1(圖6.3.13)。直徑較小，是一常數(shù)2。星形結(jié)構(gòu)一般用于有集中監(jiān)督結(jié)點的系統(tǒng)中。

5. 胖樹形

??? 1985年Leiserson提出將計算機科學(xué)中所用的一般樹結(jié)構(gòu)修改為胖樹形(fat tree)。叉胖樹結(jié)構(gòu)如圖6.3.14所示，胖樹的通道寬度從葉結(jié)點往根結(jié)點上行方向逐漸增寬，它更像真實的樹，愈靠近樹根的枝叉愈粗。

??? 使用傳統(tǒng)二叉樹的主要問題之一就是通向根結(jié)點的瓶頸問題，這是因為根部的交通最忙。胖樹的提出使該問題得到了緩解。

??? 6. 網(wǎng)格形和環(huán)網(wǎng)形

??? 圖6.3.15為一個3×3網(wǎng)格形網(wǎng)絡(luò)。這是一種比較流行的結(jié)構(gòu)，它已經(jīng)以各種變體形式在CM-2和Intel Paragon等機器中得到了實現(xiàn)。

一般說來，N=nk 個結(jié)點的k維網(wǎng)絡(luò)的內(nèi)部結(jié)點度為2k ，網(wǎng)絡(luò)直徑為k(n-1)。必須指出，圖6.3.15所示的純網(wǎng)絡(luò)形不是對稱的。邊結(jié)點和角結(jié)點的結(jié)點度分別為3或2。

??? 圖6.3.16所示的環(huán)形網(wǎng)可看做是直徑更短的另一種網(wǎng)格。這種拓撲結(jié)構(gòu)將環(huán)形和網(wǎng)格組合在一起，并能向高維擴展。環(huán)形網(wǎng)沿陣列每行和每列都有環(huán)形連接。一般說來，一個n×n二元環(huán)網(wǎng)的結(jié)點度為4，直徑為2*[n/2]。

??? 環(huán)網(wǎng)是一種對稱的拓撲結(jié)構(gòu)，所有附加的回繞連接可使其直徑比網(wǎng)格結(jié)構(gòu)減少二分之一。