Abstract
在複式電腦中，處理器之間的通訊與同步一般是以傳遞訊息的方式來完成。 這種傳遞的方式通常造成非常大的負荷。此外，因為在許多的平行程式中需求多個源頭與多個目的地的通訊，於是在複式電腦中支援群體通訊是一個重要的課題。具備群體通訊一方面可以簡化寫平行程式的複雜度，另一方面也可以降低通訊所需的時間。在本論文中，我們專注在兩種類型的群體通訊：一對多通訊(multicast) 和柵門式同步(barriersynchronization)。在一對多通訊中，源頭節點將相同的訊息傳送給任意個目的地節點。而在柵門式同步中，必須所有參與同步的節點執行到柵門，然後這些節點才可以繼續執行。柵門式同步一般是用多對一收集(reduction)和一對多的傳送來實現。在本論文中我們將探討架構在蟲繞式網路的複式電腦中，如何有效地支援這兩種類型的群體通訊。論文的第一部份是研究在蟲繞式網狀網路中如何有效地支援一對多通訊。 而此網路的繞徑方式是用轉角模式(turn model)。我們提出一種節點分組的方法稱為轉角分組法(turn grouping)。這個方法能系統化地將目的地節點做分組且產生適當的排程來傳送訊息。我們所提的方法是採用多目的地訊息傳送技術。此外，我們也利用轉角分組法來實現柵門式同步。我們提出兩個演算法來達到分組之間的多對一收集和一對多通訊的訊息傳送。我們用模擬的方式來看在蟲繞式網狀網路中利用轉角分組法來支援一對多的傳送和柵門式同步的效能。模擬的結果證實我們所提的方法比以前的來得好。接著在論文的第二部份我們探討在蟲繞式交換器組成的網路中(wormhole-routed switch-based networks)如何有效地支援一對多的通訊。蟲繞式交換器組成的網路是複式電腦的一個特例而且用它來當作平行處理的平台變得愈來愈受歡迎。主要的原因在於高頻寬低延遲的交換器出現，例如Myrinet switch， Servernet switch和 Gigabit Ethernet switch。另一方面，蟲繞式交換器組成的網路的通常是以不規則的方式來連接而且交換器內部的結構也有多種。在本論文中，我們探討三種不同的交換器內部的結構。它們分別是 crossbar、mesh 和 MIN。對每一種不同交換器結構組成的網路中，我們提出一個一對多通訊的演算法。所提出來的方法是用unicast-based。它是用軟體的方式且不需要硬體的支援。我們所提出來的三個一對多通訊演算法所需要的起始延遲(startup delay)是最少的並且它們都不會有通道競爭。此外，我們也用模擬的方法來研究各種不同的參數對於我們所提出的一對多通訊演算法之效能影響。在論文的第三部份我們提出一種新的平行處理平台稱為蟲繞式交換器組成的工作站與處理器群集網路(wormhole-routed switch-based networks of workstationsand processor clusters)。在這種平台中，交換器的每一個接埠可以連接一台工作站或是處理器群集。處理器群集可以是共享記憶體多重處理機，二維網狀複式電腦等。在此論文中，我們研究如何在此種新的平行處理的平台上有效地支援一對多通訊。欲達到此目地有兩個步驟：(一)源頭點將訊息送給連在交換器上的目的地工作站以及參與一對多通訊的每個處理器群集之代表(二) 每個處理器群集的代表送訊息給在同一個群集內的其它目的地。我們提出兩個一對多通訊演算法。第一個演算法先做步驟(一)再做步驟(二)。而第二個演算法同時做兩個步驟。效能模擬的結果證實第二個演算法較好。