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

互聯(lián)網(wǎng)絡(luò)培訓教程[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-立方體的相應(yīng)結(jié)點互連組成，如圖6.3.17所示。一個n-立方體的結(jié)點度等于n，也就是網(wǎng)絡(luò)的直徑。實際上，結(jié)點度隨維數(shù)線性地增加，所以很難設(shè)想超立方體是一種可擴展結(jié)構(gòu)。8. k元n-立方體網(wǎng)絡(luò)環(huán)形、網(wǎng)絡(luò)形、環(huán)網(wǎng)形、二元n-立方體(超立方體)等網(wǎng)絡(luò)都是k元n-立方體網(wǎng)絡(luò)系統(tǒng)的拓撲同構(gòu)體。圖6.3.18所示就是一種4元3-立方體網(wǎng)絡(luò)。

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

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

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

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

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

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

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

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

??? 如果同時連接多個輸入輸出對時，可能會引起開關(guān)和通信鏈路使用上的沖突，我們把這種多級網(wǎng)絡(luò)稱為阻塞網(wǎng)絡(luò)(blocking network)。 阻塞網(wǎng)絡(luò)的實例有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)絡(luò)是等價的。實際上，大多數(shù)多級網(wǎng)絡(luò)都是阻塞網(wǎng)絡(luò)。在阻塞網(wǎng)絡(luò)中，為了建立某些輸入輸出之間的連接，可能需要多次通過網(wǎng)絡(luò)。

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

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

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

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

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

2.交叉開關(guān)網(wǎng)絡(luò)

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

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

?3．多端口存儲器

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

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

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

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

4.多級網(wǎng)絡(luò)

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

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

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

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

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