互聯(lián)網(wǎng)絡概述

由開關元件按一定拓撲結構和控制方式構成的網(wǎng)絡以實現(xiàn)計算機系統(tǒng)內(nèi)部多個處理機或多個功能部件間的相互連接。在并行處理計算機系統(tǒng)、分布計算機系統(tǒng)和計算機網(wǎng)等由多個處理機或多個功能部件組成的各種系統(tǒng)中，都會遇到機間互連問題?；ミB必須遵循一定的拓撲結構，通過開關元件來完成，以一定的控制方式實現(xiàn)機間通信。因此，互連網(wǎng)絡是這些系統(tǒng)的重要組成部分，它對系統(tǒng)的性能指標有決定性的影響?；ミB網(wǎng)絡具有三大要素，即結點間互連拓撲(包含連接通路)、開關元件和控制方式。在不同的系統(tǒng)中，開關元件所處的物理位置可能是不同的。在采用集中式結構的系統(tǒng)中，互連網(wǎng)絡可以是一個獨立的部件，由一組開關元件構成，位于被連接的處理機或功能部件結點之間，在一定的控制方式作用下，按照互連拓撲的要求建立結點間的各條連接通路，以實現(xiàn)各個結點對的相互通信。但是，在許多采用分布式結構的系統(tǒng)(特別是計算機網(wǎng))中，開關元件可能分散地隱含在各個結點內(nèi)部，從外面只能看到由結點間連接通路所代表的互連拓撲，因而互連網(wǎng)絡并不是以一個獨立部件的形式出現(xiàn)的，這是一種對互連網(wǎng)絡的廣義理解，是隨著分布式系統(tǒng)結構的日益流行而確立起來的。按照這種廣義理解，公共總線是互連網(wǎng)絡的一個特例。

通過縱橫交換結構(crossbar switch fabric)進行交換的交換機構常稱為互連網(wǎng)絡(interconnection network)?；ミB網(wǎng)絡有2N條總線，可以是N個輸入端口和N個輸出端口相連接，這取決于相應的交叉結點是使水平總線和垂直總線接通還是斷開。

互連網(wǎng)絡的直接作用是建立機間連接通路?；ミB網(wǎng)絡有兩種形式。一種是非共享連接通路，即結點與結點直接相連，非直接相連的結點之間的通信經(jīng)過中間結點轉送。這是多數(shù)計算機網(wǎng)的連接情況。另一種是共享連接通路，即多個結點相互間經(jīng)過開關元件相連，以建立可變的連接通路，同一路徑段通過開關元件的選擇在不同時刻可為不同的結點對服務，達到共享的目的。這是總線型局部區(qū)域網(wǎng)和集中式多處理機的連接情況?；ミB網(wǎng)絡的功能是完成計算機系統(tǒng)中的數(shù)據(jù)傳送和變換。在單指令流多數(shù)據(jù)流計算機系統(tǒng)中，互連網(wǎng)絡實現(xiàn)多個處理單元與多個存儲單元之間的數(shù)據(jù)變換，又稱為數(shù)據(jù)變換網(wǎng)絡，其概念化功能模型如圖1。在多指令流多數(shù)據(jù)流計算機系統(tǒng)中，互連網(wǎng)絡既可實現(xiàn)處理機與共享存儲器模塊間的連接，稱為集中式結構(圖2a)，也可實現(xiàn)帶本地存儲器的處理機結點相互之間的連接，稱為分布式結構(圖2b)，還可二者結合，既有共享存儲器，也有本地存儲器。

互連網(wǎng)絡分為靜態(tài)互連網(wǎng)絡和動態(tài)互連網(wǎng)絡兩類。靜態(tài)互連網(wǎng)絡的每一個開關元件固定地與一個結點相連，以建立該結點與鄰近結點之間的被動連接通路。它一般用于分布計算機系統(tǒng)和計算機網(wǎng)，實現(xiàn)計算機結點之間的總點連接。動態(tài)互連網(wǎng)絡的結點只與互連網(wǎng)絡邊界上的開關元件連接，在所有開關元件共同參與下，建立結點間主動可控的通信路徑。它一般用于多處理機系統(tǒng)實現(xiàn)并行進程間的相互通信。

這類網(wǎng)絡如用結點和邊組成的圖來表示，則須滿足下列要求：①網(wǎng)絡每個結點的相連邊數(shù)(稱為度)要小，且在各結點處最好都相等，而與網(wǎng)絡的大小無關;②在任意二結點間循最短路徑通信所經(jīng)過邊數(shù)的最大值(稱為直徑)要小，且隨結點數(shù)目增多而緩慢增大;③對稱性要好，以達到信息流量分布均勻;④通過對各結點的合理編址，能實現(xiàn)高效路徑算法;⑤有較高的路徑冗余度，以滿足堅固性要求;⑥增量擴展性要好，即每次只擴展一個或少數(shù)幾個結點，仍能保持原有互連拓撲特性。靜態(tài)互連網(wǎng)絡有多種形式，但基本圖形為環(huán)形、主方體形、樹形(含星形)、網(wǎng)格形和總線型等幾種(圖3)。其他各種復雜的靜態(tài)互連拓撲可用下列方法產(chǎn)生：①直接對基本圖形進行改進，例如合理地增加圖中邊的數(shù)目，成帶弦形等(圖4a)。②不同基本圖形相結合，形成例如立方體連接環(huán)(圖4b)和多樹結構(圖4c)。③基本圖形多次遞歸，產(chǎn)生新的復雜圖形。④用地址映像函數(shù)確定網(wǎng)絡拓撲，即先對結點號進行編碼，然后規(guī)定邊的末端結點號為始端結點號的某一(組)映像函數(shù)。⑤用啟發(fā)式方法對網(wǎng)絡拓撲進行尋優(yōu)?；ミB網(wǎng)絡。