Abstract
在平行計算系統中支援高效率的通訊與可擴增性是兩項非常重要的議題。在本研究中，我們將探討如何在兩種不同的可擴增連結網路（Scalable Interconnection Networks）：二維網狀網路（2D Mesh Networks）及不規則網路（Irregular Networks）中，支援高效率的通訊。 首先，我們研究如何借由硬體架構的協助，在二維網狀網路中支援柵門式同步（Barrier Synchronization）運算。我們考慮在這種系統中的整個運算路徑，從程式設計界面到繞徑器的設計。我們討論的程式設計界面是MPI-1訊息傳遞界面標準。我們提出一個分散式的演算法來針對參與柵門式同步的所有處理單元建構出一棵群體同步樹（Collective Synchronization Tree）。在這棵群體同步樹的基礎上，我們設定了位於繞徑器內部的狀態暫存器（Status Register）；然後，同步訊息（Synchronization Messages）便可以在這些設定的幫助下快速地傳送。在效能評估的研究中，我們發現相較於以往的研究，利用群體同步樹來完成柵門式同步運算的方式提供了較佳的效率。並且它也較不易受到群體群組的大小以及起始延遲的影響。雖然這個方法必須花費一點時間來進行群體同步樹的建立，但是當這個柵門式同步被啟動許多次時，建立群體同步樹的時間花費是可以很容易被補償回來的。因此，這樣的方法特別適合被運用在平行重覆運算（Parallel Iterative Computation）中。 我們也將上面所提到的觀念加以擴充，以便在二維網狀網路中支援一般的多址傳送（Multicast）。同樣地，我們同時考慮程式設計界面與繞徑器硬體的設計，然後採用一個分散式的方式建立一棵四分支多址傳送樹（Quad-Branch Multicast Tree）。我們也提出相關的繞徑演算法來將多址訊息（Multicast Messages）藉由這棵四分支多址傳送樹傳送到目的地。效率模擬的結果顯示，利用我們所提出的方式來進行多址傳送可以得到較好的效率，並且也較不易受到一些系統參數變化的影響。同樣地，儘管我們需要花費一些時間來建立四分支多址傳送樹，但是當這樹所包含的資訊被重複地使用時，這些花費便可以很容易地得到補償。像是成堆式的多址傳送（Bulk Multicast）便具有這樣的特性。 最後，我們也研究在蛀蟲式不規則網路（Wormhole-Routed Irregular Network）中支援多路徑式繞徑法（Adaptive Routing）。在蛀蟲式不規則網路中，要達成免於死結（Deadlock）的繞徑法，有兩個主要的步驟：(1) 給予所有傳輸連結一個特定的方向設定，(2) 限制不能進行某些轉彎。我們提出並檢視不同的傳輸連結方向設定與不可進行轉彎的限制規則。經過效能模擬的結果，我們得到一個結論：如果能夠好好地選擇設定傳輸連結方向的方式，並且仔細地推敲該限制那些轉彎不可被進行；在大多數的時候，我們可以獲得最佳的結果，也就是最少的轉彎限制。這樣的結果和以前所提出的方法相較，在效能上毫不遜色；而在時間複雜度的考量上，它所花費的時間則能獲得很大的改善。