互聯網絡培訓教程[2]

?5.廣播和選播

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

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

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

??? (3) 帶寬——通過網絡的最大數據傳輸率，用MB/s表示。

??? (4) 硬件復雜性——諸如導線、開關、連接器、仲裁和接口邏輯等的造價。

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

??? 6.3.2靜態連接網絡

??? 靜態網絡使用直接鏈路，它一旦構成后就固定不變。這種網絡比較適合于構造通信模式可預測或可用靜態連接實現的計算機系統。 下面介紹幾種靜態網絡的拓撲結構、網絡參數及其可擴展性。

?

?1.線性陣列(linear array)

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

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

?2. 環和帶弦環(chordal ring)

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

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

??? 3. 循環移數網絡(barrel shifter)

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

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

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

?

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

5. 胖樹形

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

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

??? 6. 網格形和環網形

??? 圖6.3.15為一個3×3網格形網絡。這是一種比較流行的結構，它已經以各種變體形式在CM-2和Intel Paragon等機器中得到了實現。

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

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

??? 環網是一種對稱的拓撲結構，所有附加的回繞連接可使其直徑比網格結構減少二分之一。