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

?5.廣播和選播

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

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

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

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

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

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

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

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

?

?1.線性陣列(linear array)

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

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

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

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

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

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

??? 圖6.3.11所示的是一個(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)成的。這就是說,如果｜j-i｜=2r，r=0,1,2,…,n-1，網(wǎng)絡(luò)規(guī)模N=2n，則結(jié)點(diǎn)i與結(jié)點(diǎn)j連接。這種循環(huán)移數(shù)網(wǎng)絡(luò)的結(jié)點(diǎn)度為d=2n-1，直徑D=n/2。

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

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

?

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

5. 胖樹形

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

??? 使用傳統(tǒng)二叉樹的主要問題之一就是通向根結(jié)點(diǎn)的瓶頸問題，這是因?yàn)楦康慕煌ㄗ蠲ΑＥ謽涞奶岢鍪乖搯栴}得到了緩解。

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

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

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

??? 圖6.3.16所示的環(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ì)稱的拓?fù)浣Y(jié)構(gòu)，所有附加的回繞連接可使其直徑比網(wǎng)格結(jié)構(gòu)減少二分之一。