請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/32305
標題: | 在異質環境中同步廣播之近似演算法 An Approximation Algorithm for Synchronous Broadcast in Heterogeneous Environments |
作者: | Juih-Sien Chang 張瑞賢 |
指導教授: | 劉邦鋒(Pangfeng Liu) |
關鍵字: | 廣播排程,異質環境,同步, Broadcast Schedule,Heterogeneous Environment,Synchronous, |
出版年 : | 2006 |
學位: | 碩士 |
摘要: | 平行計算中所有處理器往往需要同時彼此傳輸資料。這種通訊模式即稱為集體通訊。在異質(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/32305 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 174.91 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。