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

?7. 超立方體

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

??? 4-立方體可通過(guò)將兩個(gè)3-立方體的相應(yīng)結(jié)點(diǎn)互連組成，如圖6.3.17所示。一個(gè)n-立方體的結(jié)點(diǎn)度等于n，也就是網(wǎng)絡(luò)的直徑。實(shí)際上，結(jié)點(diǎn)度隨維數(shù)線性地增加，所以很難設(shè)想超立方體是一種可擴(kuò)展結(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)的拓?fù)渫瑯?gòu)體。圖6.3.18所示就是一種4元3-立方體網(wǎng)絡(luò)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?3．多端口存儲(chǔ)器

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

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

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

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

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

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

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

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

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

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