互聯網絡培訓教程[3]

?7. 超立方體

??? 這是一種二元n-立方體結構，它已在nCUBE和CM-2等系統中得到了實現。 一般說來，一個n-立方體由N=2n 個結點組成，它們分布在n維上，每維有兩個結點。8個結點的3-立方體如圖6.3.17所示。

??? 4-立方體可通過將兩個3-立方體的相應結點互連組成，如圖6.3.17所示。一個n-立方體的結點度等于n，也就是網絡的直徑。實際上，結點度隨維數線性地增加，所以很難設想超立方體是一種可擴展結構。8. k元n-立方體網絡環形、網絡形、環網形、二元n-立方體(超立方體)等網絡都是k元n-立方體網絡系統的拓撲同構體。圖6.3.18所示就是一種4元3-立方體網絡。

參數n是立方體的維數，k是基數或者說是沿每個方向的結點數(多重性)。這兩個數與網絡中結點數N的關系為

??? k元n-立方體的結點可用基數為k的n位地址A=a0a1a2…an-1來表示，其中ai代表第 i 維結點的位置。為簡單起見，所有鏈路都認為是雙向的。網絡中每條線代表兩個通信通道，每個方向一個。圖6.3.18中各結點之間的連線都是雙向鏈路。 按照慣例，低維k元n-立方體稱為環網，而高維二元n-立方體則稱為超立方體。

??? 低維網絡在負載不均勻情況下運行較好，因為它們有較多的資源共享。在高維網絡中，連線常分配給指定的維，各維之間不能共享。例如，在二元n-立方體中，可能有的線已達到飽和，而物理上分配給其它維的相鄰的連線卻都還空閑。網絡直徑的變化范圍很大。但隨著硬件路由技術的不斷革新(如蟲孔方式），路由已不是一個嚴重問題，因為任意兩結點間的通信延遲在高度流水線操作下幾乎是固定不變的。鏈路數會影響網絡價格，等分寬度將影響網絡的帶寬。對稱性會影響可擴展性和路由效率。

?6.3.3動態連接網絡

??? 為了達到多用或通用的目的，我們需要采用動態連接網絡，它能根據程序要求實現所需的通信模式。它不用固定連接，而是沿著連接通路使用開關或仲裁器以提供動態連接特性。按照價格和性能增加的順序，動態連接網絡的排隊次序為總線系統、多級互連網絡(MIN)和交叉開關網絡。

??? 采用動態網絡的多處理機的互連是在程序控制下實現的。定時、開關和控制是動態互連網絡的三個主要操作特征。定時可以用同步方式，也可以用異步方式來進行。同步網絡由一個全局時鐘來控制，用它來同步網絡的全部動作。異步網絡利用握手機制來協調需要使用的同一網絡內各種設備。

??? 根據級間連結方式，單級網絡(single-stage network)也稱循環網絡(recirculating network), 因為數據項在到達最后目的地之前可能在單級網絡中循環多次。單級網絡的成本比較低，但在建立某種連接時可能需要多次通過網絡。交叉開關和多端口存儲器結構都屬于單級網絡。

??? 多級網絡由一級以上的開關元件構成。這類網絡可以把任一輸入與任一輸出相連。級間連接模式的選擇取決于網絡連接特性。不同級的連接模式可能相同也可能不相同，這與所設計的網絡的類型有關。Omega網、Flip網和Baseline網都是多級網絡。

??? 如果同時連接多個輸入輸出對時，可能會引起開關和通信鏈路使用上的沖突，我們把這種多級網絡稱為阻塞網絡(blocking network)。 阻塞網絡的實例有Omeage網(Lawrie,1975)、Baseline網(Wu和Feng,1980)、Banyan網(Goke和lipovski,1973)和Delta網(Patel,1979)。經過圖形轉換后，可以證明一些阻塞網絡是等價的。實際上，大多數多級網絡都是阻塞網絡。在阻塞網絡中，為了建立某些輸入輸出之間的連接，可能需要多次通過網絡。

??? 如果多級網絡通過重新安排連接方式可以建立所有可能的輸入輸出之間的連接，則稱之為非阻塞網絡(nonblocking network)。這類網絡中，任何輸入輸出對之間總可以建立連接通路。Benes網絡(Benes,1965)具有這種功能，但是它的級數比一般阻塞網絡增加一倍才實現了非阻塞連接。如果增加級數或者限制連接模式，某些阻塞網絡也可以成為非阻塞網絡。下面根據級數和阻塞或非阻塞來討論幾類主要的開關網絡。首先介紹總線、交叉網絡和多端口存儲器結構，然后討論多級網絡。

?1.總線系統

??? 總線系統實際上是一組導線和插座，用于處理與總線相連的處理器、存儲模塊和外圍設備間的數據業務。總線只用于源(主部件)和目的(從部件)之間處理業務。在多個請求情況下，總線仲裁邏輯必須每次能將總線服務分配或重新分配給一個請求。基于這一原因，數字總線已被稱為多個功能模塊間的爭用總線(contention bus)或時分總線(time-sharing bus)。總線系統價格較低，帶寬較窄。它有很多可用的工業和IEEE總線標準。

??? 圖6.3.19所示的是一種總線連接的多處理機系統。

??? 主動設備或主設備(處理機或I/O子系統)產生訪問存儲器的請求，被動設備或從設備(存儲器或外圍設備)則響應請求。公用總線是在分時基礎上工作的。總線研制中的重要問題有總線仲裁、中斷處理、一致性協議和總線事務的處理等。

2.交叉開關網絡

??? 在交叉開關網絡中，每個輸入端通過一個交叉點開關可以無阻塞地與一個空閑輸出端相連。交叉開關網絡是單級網絡，它由交叉點上的一元開關構成。交叉網絡主要用于中小型系統。從存儲器讀出的數據一旦可用時，該數據通過同一交叉開關回送給請求的處理器。通常，這類交叉開關網絡需要使用n×m個交叉點開關。正方形交叉開關網絡(n＝m)可以無阻塞地實現n!種置換。

??? 交叉開關網絡每個周期可以實現n個數據傳輸，與每個總線周期只傳一個數據相比，它的頻寬最高。交叉開關網絡對小型多處理機系統來說性能價格比較高。但單級交叉開關網絡一旦構成后將不能擴充。

?3．多端口存儲器

??? 由于大型系統使用交叉開關網絡的成本無法承受，所以許多大型的多處理機系統都采用多端口存儲器結構。其主要思想是將所有交叉點仲裁邏輯和跟每個存儲器模塊有關的開關功能移到存儲器控制器中。

??? 圖6.3.21所示為典型的多端口存儲器結構。

??? 多端口存儲器結構是一個折衷方案，它介于低成本低性能的總線系統和高成本高帶寬的交叉開關系統之間。總線被所有處理器和與之相連的設備模塊分時地共享。多端口存儲器則負責分解各臺處理器的請求沖突。

??? 當m和n值很大時，這種多端口存儲器結構將變得十分昂貴。典型的多處理機應用配置是四臺處理機和16個存儲器模塊。多端口存儲器結構的多處理機系統也不能擴展，因為端口數目一旦固定后，如果不重新設計存儲控制器就無法再增加處理器了。還有一個缺點是當系統配置很大時，需要大量的互連電纜和連接器。

4.多級網絡

??? 多級網絡可用于構造大型多處理機系統。一種通用多級網絡如圖6.3.22所示，其中每一級都用了多個a×b開關，相鄰級開關之間都有固定的級間連接。為了在輸入和輸出之間建立所需的連接，可用動態設置開關的狀態來實現。

??? 各種多級網絡的區別就在于所用開關模塊和級間連接模式的不同。一個a×b開關模塊有a個輸入和b個輸出。一個二元開關與a=b=2的2×2開關模塊相對應。在理論上a與b不一定要相等，但實際上a和b經常選為2的整數冪，即a=b=2k，k≥1。最簡單的開關模塊是2×2開關(圖6.3.23)。常用的級間連接模式包括混洗、交叉、立方體連接等。這里我們只介紹Omega網絡，它已經應用于現在的機器。

?圖6.3.24所示的是一個16×16 Omega網絡，共需4級2×2開關。網絡左側有16個輸入，右側有16個輸出。形成對16個對象的均勻混洗模式。

??? 一般說來，一個n輸入的Omega網絡需要log2n級2×2開關，每級要用n/2個開關模塊，網絡共需nlog2n/2個開關。每個開關模塊采用單元控制方式。不同的開關狀態組合可實現各種置換、廣播或從輸入到輸出的其他連接。

??? 構成動態網絡的總線、多級網絡、交叉開關中，總線的造價最低，但其缺點是每臺處理器可用的帶寬較窄。總線所存在的另一個問題是容易產生故障。有些容錯系統，如用于事務處理的Tandem多處理機等，常采用雙總線以防止系統產生簡單的故障。由于交叉開關的硬件復雜性以n2上升，所以其造價最為昂貴。但是，交叉開關的帶寬和路由性能最好。如果網絡的規模較小，它是一種理想的倍選擇。多級網絡則是兩個極端之間的折衷。它的主要優點在于采用模塊結構，因而可擴展性較好。然而，其時延隨網絡的級數而上升。另外，由于增加了連線和開關復雜性，價格也是一種限制因素。幾種靜態拓撲結構針對一些特定的應用，其可擴展性比較好。隨著光技術和微電子技術迅速發展，大規模多級網絡和交叉開關網絡在建立通用計算機的動態連接時也會變得更加經濟合理。