互連網路設計

並行機器中的互連網路負責在任意源節點與任意目標節點之間傳輸資訊。此任務應以儘可能小的延遲完成。它應該允許大量此類傳輸同時進行。此外，與機器其餘部分的成本相比，它應該價格低廉。

網路由鏈路和交換機組成，有助於將資訊從源節點發送到目標節點。網路由其拓撲結構、路由演算法、交換策略和流量控制機制指定。

組織結構

互連網路由以下三個基本元件組成：

• 鏈路 − 鏈路是一根或多根光纖或電線的電纜，每端都連線到交換機或網路介面埠的聯結器。透過它，模擬訊號從一端傳輸，在另一端接收以獲得原始數字資訊流。

• 交換機 − 交換機由一組輸入和輸出埠、連線所有輸入和所有輸出的內部“交叉開關”、內部緩衝區和控制邏輯組成，以在每個時間點實現輸入輸出連線。通常，輸入埠的數量等於輸出埠的數量。

• 網路介面 − 網路介面的行為與交換機節點大不相同，並且可以透過專用鏈路連線。網路介面格式化資料包並構建路由和控制資訊。與交換機相比，它可能具有輸入和輸出緩衝區。它可以執行端到端錯誤檢查和流量控制。因此，其成本受其處理複雜性、儲存容量和埠數量的影響。

互連網路

互連網路由交換元件組成。拓撲結構是將各個交換機連線到其他元件（如處理器、儲存器和其他交換機）的模式。網路允許在並行系統中的處理器之間交換資料。

• 直接連線網路 − 直接網路在相鄰節點之間具有點對點連線。這些網路是靜態的，這意味著點對點連線是固定的。直接網路的一些示例包括環形網路、網格網路和超立方體網路。

• 間接連線網路 − 間接網路沒有固定的鄰居。通訊拓撲可以根據應用程式的需求動態更改。間接網路可以細分為三個部分：匯流排網路、多級網路和交叉開關。

  • 匯流排網路 − 匯流排網路由許多位線組成，許多資源連線到這些位線上。當匯流排使用相同的物理線路進行資料和地址傳輸時，資料線和地址線是時間複用的。當有多個匯流排主控連線到匯流排時，需要仲裁器。

  • 多級網路 − 多級網路由多個交換機級組成。它由“axb”交換機組成，這些交換機使用特定的級間連線模式 (ISC) 連線。小的 2x2 交換元件是許多多級網路的常見選擇。級數決定了網路的延遲。透過選擇不同的級間連線模式，可以建立各種型別的多級網路。

  • 交叉開關 − 交叉開關包含一個簡單的交換元件矩陣，這些元件可以開啟和關閉以建立或斷開連線。開啟矩陣中的交換元件，就可以在處理器和儲存器之間建立連線。交叉開關是非阻塞的，也就是說所有通訊排列都可以無阻塞地執行。

評估網路拓撲中的設計權衡

如果主要關注的是路由距離，則必須最大化維度並構建超立方體。在儲存轉發路由中，假設交換機的度數和鏈路數量不是重要的成本因素，並且鏈路數量或交換機度數是主要成本，則必須最小化維度並構建網格。

在每個網路的最壞情況流量模式下，最好使用高維網路，其中所有路徑都很短。在每個節點僅與一個或兩個附近的鄰居通訊的模式中，最好使用低維網路，因為實際上只使用少數維度。

路由

網路的路由演算法決定了從源到目標的哪些可能路徑用作路由，以及如何確定每個特定資料包遵循的路由。維度順序路由限制了合法路徑的集合，以便從每個源到每個目標都只有一條路由。該路由首先在高階維度上行進正確的距離，然後是下一個維度，依此類推。

路由機制

算術、基於源的埠選擇和表格查詢是高速交換機用來根據資料包報頭中的資訊確定輸出通道的三種機制。所有這些機制都比在傳統區域網和廣域網路由器中實現的通用路由計算更簡單。在平行計算機網路中，交換機需要在每個週期內為所有輸入做出路由決策，因此該機制需要簡單快捷。

確定性路由

如果訊息所走的路由完全由其源和目標決定，而不是由網路中的其他流量決定，則路由演算法是確定性的。如果路由演算法只選擇通向目標的最短路徑，則它是最小化的，否則是非最小化的。

無死鎖

死鎖可能發生在各種情況下。當兩個節點試圖相互發送資料並且每個節點都在另一個節點接收之前開始傳送時，可能會發生“對頭”死鎖。另一種死鎖情況是，當有多個訊息在網路內競爭資源時。

證明網路無死鎖的基本技術是清除由於訊息透過網路移動而可能在通道之間發生的依賴關係，並表明整體通道依賴圖中沒有迴圈；因此，沒有可能導致死鎖的流量模式。執行此操作的常用方法是對通道資源進行編號，以便所有路由都遵循特定的遞增或遞減序列，從而避免出現依賴迴圈。

交換機設計

網路的設計取決於交換機的設計以及交換機的連線方式。交換機的度數、其內部路由機制及其內部緩衝區決定了可以支援哪些拓撲以及可以實現哪些路由演算法。與計算機系統的任何其他硬體元件一樣，網路交換機包含資料路徑、控制和儲存。

埠

引腳總數實際上是輸入和輸出埠總數乘以通道寬度。由於晶片的周長比面積增長緩慢，因此交換機往往受到引腳限制。

內部資料路徑

資料路徑是每組輸入埠和每個輸出埠之間的連線。它通常被稱為內部交叉開關。非阻塞交叉開關是指每個輸入埠可以同時連線到任意排列中的不同輸出的交叉開關。

通道緩衝區

交換機內緩衝儲存的組織對交換機效能有重要影響。傳統的路由器和交換機傾向於在交換機結構外部具有大型 SRAM 或 DRAM 緩衝區，而在 VLSI 交換機中，緩衝區位於交換機內部，並與資料路徑和控制部分來自相同的矽預算。隨著晶片尺寸和密度的增加，可用的緩衝區更多，網路設計人員有更多選擇，但緩衝區空間仍然是首要選擇，其組織非常重要。

流量控制

當網路中的多個數據流嘗試同時使用相同的共享網路資源時，必須採取一些措施來控制這些流。如果我們不想丟失任何資料，則必須阻塞某些流，而其他流則繼續進行。

流量控制問題出現在所有網路和許多級別。但它在平行計算機網路中的性質與在區域網和廣域網中的性質有本質區別。在平行計算機中，網路流量需要像跨匯流排的流量一樣準確地交付，並且在非常短的時間範圍記憶體在大量並行流。