Abstract
超級電腦可以是由傳統的大型主機電腦組成，或是由網路連接的分散式系統如叢集系統組成。現今趨勢已走向有成本效益的網路連接分散式系統，因為這些系統包含的元件如個人電腦及高速網路不必是客制或特殊的元件。因此，在叢集系統中的繞徑演算法會是主要的關鍵，要能提供高輸出以及低延遲的網路效能。我們將會針對不規則的以及規則的網路拓樸來提出解決方案。對於不規則的網路拓樸，我們提出了Tree-turn模型；此模型可做為發展繞徑演算法的工具。以Tree-turn模型基礎，我們衍生了對於不規則網路拓樸中無死結的繞徑演算法，Tree-turn繞徑。Tree-turn繞徑有三個步驟組成。第一，對於一個網路拓樸，建立一個座標樹。第二，基於網路拓樸及座標樹，建立一個通訊圖。第三，根據Tree-turn模型中的禁止轉彎以及通訊圖中的通訊管道的方向，用最短路徑演算法設定轉送表。對於規則的網路拓樸，我們在fat-tree以及二維陣列網路中提出了多點傳播演算法。此外，由於InfiniBand架構提供了硬體支援的多點傳播，我們的演算法也能利用這個特性來改進效能。我們提出的多點傳播方法有三個機制，包含了處理結點的定位機制，路徑選擇機制，以及轉送表設定機制。為了增進效能，我們也考慮了虛擬路徑以及服務層級對應虛擬路徑的機制。另外，當高效能計算系統的規模變大時，為了讓傳輸更有效率，從平行程式工作單元到實體處理器的對應方法也成為決定效能的關鍵之一。為了解決這個問題，我們提出了一個階層式的對應演算法。在這論文中，我們對於所提出的方法都有實驗來測試驗證並分析。對於連結網路以及高效計算中對應方法，結果都顯示我們所提的方法能達成好的效果。