互聯(lián)網(wǎng)絡培訓教程[3]

?7. 超立方體

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

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

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

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

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

?6.3.3動態(tài)連接網(wǎng)絡

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

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

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

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

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

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

?1.總線系統(tǒng)

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

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

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

2.交叉開關網(wǎng)絡

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

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

?3．多端口存儲器

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

??? 圖6.3.21所示為典型的多端口存儲器結(jié)構(gòu)。

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

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

4.多級網(wǎng)絡

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

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

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

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

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