劉邦鋒臺灣大學：資訊工程學研究所張瑞賢Chang, Juih-SienJuih-SienChang2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53779平行計算中所有處理器往往需要同時彼此傳輸資料。這種通訊模式即稱為集體通訊。在異質(heterogeneous)網路架構下設計此種通訊最佳化的演算法變的極為複雜，因為我們不能假設處理器或網路有相同的效能。這在大型叢集計算機或是網際網路都構成同樣的問題，所以異質網路架構中通訊最佳化的研究在叢集計算或是網際網路上均有重要應用。 廣播排程問題(broadcast scheduling problem)是集體通訊相關的一個討論問題。在異質環境中本篇論文提出一個通訊架構為同步通訊(synchronous communication model)。在此架構下，訊息傳送者與接收者都必須等到傳輸結束後才可以開始進行各自的下一個訊息傳輸。針對異質環境的同步架構，我們提出一個廣播排程的方法為“貪婪演算法(Greedy Algorithm)”。我們證明貪婪演算法是廣播排程問題的一個有效率的三倍近似演算法而其時間複雜度為O(n log n)。Network of workstation (NOW) is a cost-effective alternative to massively parallel supercomputers. As commercially available off-the-shelf processors become cheaper and faster, it is now possible to build a PC or workstation cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors and this heterogeneity within a cluster complicates the design of efficient collective communication protocols. This paper introduces a synchronous communication model where the communication cost is deter-mined by both sender and receiver. In this synchronous model both sender and receiver of a message must wait until the current communication finishes. Although this synchronous broadcast scheduling problem is NP-hard, we propose a greedy algorithm with a competitive ratio 3. The time complexity of the greedy algorithm is bounded by O(n log n) where n is the number of processors.1 Introduction 2 Communication Model 2.1 Broadcast Schedule 3 Greedy Algorithm 4 Theoretical Results 4.1 An Upper Bound of Greedy Algorithm 4.2 An Lower Bound of The Optimal Schedule 4.2.1 Zero Sending Time 4.3 Competitive Ratio 5 Conclusion179112 bytesapplication/pdfen-US廣播排程異質環境同步Broadcast ScheduleHeterogeneous EnvironmentSynchronousthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53779/1/ntu-95-R93922098-1.pdf