互連網路

在并行處理計算機系統、分佈計算機系統和計算機網等由多個處理機或多個功能部件組成的各種系統中，都會遇到機間互連問題。互連必須遵循一定的拓撲結構，通過開關元件來完成，以一定的控制方式實現機間通信。因此，互連網路是這些系統的重要組成部分，它對系統的性能指標有決定性的影響。

互連網路具有三大要素，即結點間互連拓撲(包含連接通路)、開關元件和控制方式。在不同的系統中，開關元件所處的物理位置可能是不同的。在採用集中式結構的系統中，互連網路可以是一個獨立的部件，由一組開關元件構成，位於被連接的處理機或功能部件結點之間，在一定的控制方式作用下，按照互連拓撲的要求建立結點間的各條連接通路，以實現各個結點對的相互通信。但是，在許多採用分散式結構的系統(特別是計算機網)中，開關元件可能分散地隱含在各個結點內部，從外面只能看到由結點間連接通路所代表的互連拓撲，因而互連網路並不是以一個獨立部件的形式出現的，這是一種對互連網路的廣義理解，是隨著分散式系統結構的日益流行而確立起來的。按照這種廣義理解，公共匯流排是互連網路的一個特例。

作用 互連網路的直接作用是建立機間連接通路。互連網路有兩種形式。一種是非共享連接通路，即結點與結點直接相連，非直接相連的結點之間的通信經過中間結點轉送。這是多數計算機網的連接情況。另一種是共享連接通路，即多個結點相互間經過開關元件相連，以建立可變的連接通路，同一路徑段通過開關元件的選擇在不同時刻可為不同的結點對服務，達到共享的目的。這是匯流排型局部區域網和集中式多處理機的連接情況。互連網路的功能是完成計算機系統中的數據傳送和變換。在單指令流多數據流計算機系統中，互連網路實現多個處理單元與多個存儲單元之間的數據變換，又稱為數據變換網路，其概念化功能模型如圖1。在多指令流多數據流計算機系統中，互連網路既可實現處理機與共享存儲器模塊間的連接，稱為集中式結構（圖2a）, 也可實現帶本地存儲器的處理機結點相互之間的連接，稱為分散式結構（圖2b），還可二者結合，既有共享存儲器，也有本地存儲器。類型 互連網路分為靜態互連網路和動態互連網路兩類。靜態互連網路的每一個開關元件固定地與一個結點相連，以建立該結點與鄰近結點之間的被動連接通路。它一般用於分佈計算機系統和計算機網，實現計算機結點之間的總點連接。動態互連網路的結點只與互連網路邊界上的開關元件連接，在所有開關元件共同參與下，建立結點間主動可控的通信路徑。它一般用於多處理機系統實現并行進程間的相互通信。

靜態互連網路 這類網路如用結點和邊組成的圖來表示，則須滿足下列要求：①網路每個結點的相連邊數（稱為度）要小，且在各結點處最好都相等，而與網路的大小無關；②在任意二結點間循最短路徑通信所經過邊數的最大值（稱為直徑）要小，且隨結點數目增多而緩慢增大;③對稱性要好，以達到信息流量分佈均勻；④通過對各結點的合理編址，能實現高效路徑演演算法；⑤有較高的路徑冗餘度，以滿足堅固性要求；⑥增量擴展性要好，即每次只擴展一個或少數幾個結點，仍能保持原有互連拓撲特性。靜態互連網路有多種形式，但基本圖形為環形、主方體形、樹形(含星形)、網格形和匯流排型等幾種(圖3)。其他各種複雜的靜態互連拓撲可用下列方法產生：①直接對基本圖形進行改進，例如合理地增加圖中邊的數目，成帶弦形等（圖4a）。②不同基本圖形相結合，形成例如立方體連接環（圖4b）和多樹結構（圖4c）。③基本圖形多次遞歸，產生新的複雜圖形。④用地址映像函數確定網路拓撲，即先對結點號進行編碼，然後規定邊的末端結點號為始端結點號的某一(組)映像函數。⑤用啟髮式方法對網路拓撲進行尋優。動態互連網路 這類網路可按不同方面的特性分為多種形式。①按輸入端和輸出端的布置劃分，有雙邊、單邊和摺疊網路。②按連接能力劃分，有阻塞、重安排和無阻塞網路。③按互連類型劃分，有連接器、集中器、擴展器和分組器。④按開關元件類型劃分，有交叉開關、交換開關和細胞開關。

完全交叉開關（圖5a）向模塊化方向演變，可產生基準全排列網路(圖5b），它代表很大一類由交換開關構成的多級動態互連網路。另一類重安排網路是細胞互連陣列（圖5c），它是一種更適合大規模集成的結構形式。動態互連網路的技術性能主要用連接能力和級數來衡量，這綜合反映了它的頻寬指標；而其價格指標則用開關點數來表示。