(34.204.185.54) 您好!臺灣時間:2021/04/11 05:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蔡秉儒
研究生(外文):Bing-Ru Tsai
論文名稱:異質網路環境中廣播演算法之效能評估
論文名稱(外文):Performance Evaluation of Broadcasting Algorithms on Heterogeneous Networks with One Port Model
指導教授:許慶賢
指導教授(外文):Ching-Hsien Hsu
學位類別:碩士
校院名稱:中華大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:31
中文關鍵詞:廣播排程廣播演算法單埠異質網路分散式計算
外文關鍵詞:one-to-all broadcastatomic broadcastheterogeneous computingparallel processinggrid schedulingmessage forwarding tableone-port model
相關次數:
  • 被引用被引用:0
  • 點閱點閱:125
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著網路技術的進步,異質性網路計算已成為廣泛被接受的計算平台。在分散式的異質性環境中,資訊的廣播是一項重要且基本運作方式。因此設計一套有效率的廣播機制將有助於整體的運算效能。在本篇論文中,我們提出數個廣播演算法,應用於單埠(one-port model)的異質性分散式網路。在廣播演算法中,我們分為以圖形為基礎與最小生成樹為基礎的演算法,在圖形為基礎的演算法當中我們提出了Nearest Neighbor First和Maximum Degree Neighbor First演算法,為了避免圖形中產生迴圈造成重複資料的傳遞,我們提出了預先排程和建立訊息轉送表(Message Forwarding Table)來解決。在最小生成樹為基礎的演算法當中,我們依據網路拓僕建立了最小生成樹作為廣播的主要環境,以利執行較有效率的排程,並提出Nearest Neighbor First, Maximum Degree Neighbor First, Maximum Height Sub-tree First, Maximum Sub-Tree First and Maximum Weighted Sub-tree First等5個演算法。由於樹狀結構沒有迴圈,在高度異質的環境當中,Maximum Weighted Sub-tree First 顯示了優越的結果。在低異質的環境中,以最小生成樹為基礎的Nearest Neighbor First演算法得到最好結果。
With the emergence of the network technologies, heterogeneous computing has become a wide accept paradigm for distributed and network computing. In this thesis, we present various algorithms aiming to efficient perform atomic one-to-all broadcast in heterogeneous network with one port model. The proposed algorithms are divided into graph based and tree based ones. In graph based algorithms, we present Nearest Neighbor First and Maximum Degree Neighbor First Algorithms. In order to avoid redundant messages, we use the method of pre-scheduling and constructing Message Forwarding Table for runtime support. In the tree based algorithms, a minimum spanning tree is first built from the origin network topology for scheduling one-to-all broadcast. Five algorithms Nearest Neighbor First, Maximum Degree Neighbor First, Maximum Height Sub-tree First, Maximum Sub-Tree First and Maximum Weighted Sub-tree First are presented in this thesis. The simulation results show that the Maximum Weighted Sub-tree First performs best in high degree heterogeneous environments. On the contrary, with near homogeneous environments, the tree-based Nearest Neighbor First will be the best choice. Overall speaking, contribution of this study relies on informing significant suggestions for adapting proper broadcasting mechanism in different heterogeneous platforms.
Chienese Abstract
English Abstract
Acknowledgements
Table of Contents
List of Figures
List of Tables
1 Introduction
2 Related Work
3 Preliminaries
3.1 Research Architecture
3.2 Definitions
4 The Proposed Broadcasting Techniques
4.1 Graph Based Algorithms
4.1.1 Nearest Neighbor First algorithm
4.1.2 Maximum Degree Neighbor First (MDNF)
4.2 Minimal Spanning Tree (MST) Based Algorithms
5 Performance Evaluation
5.1 Random Graph Generator and Comparison Metrics
5.2 Simulation Results
6 Conclusions and Future Work
References
[1].Luiz Angelo, Barchet-Steffenel and Grégory Mounié, "Scheduling Heuristics for Efficient Broadcast Operations on Grid Environments", Proceedings of Parallel and Distributed Processing Symposium, pp. 8, 2006.
[2].Mohammad Banikazemi, Vijay Moorthy and Dhabaleswar K. Panda, “Efficient collective communication on heterogeneous networks of workstations”, Proceedings of International Conference on Parallel Processing pp. 460 - 467 Aug. 1998.
[3].O. Beaumont, A. Legrand, L. Marchal and Y. Robert, "Optimizing the Steady-State Throughput of Broadcasts on Heterogeneous Platforms Heterogeneous Platforms", In Technical Report RR-2003-34LIP, ENS Lyon, France, June 2003.
[4].O. Beaumont, A. Legrand, L. Marchal and Y. Robert, ”Complexity results and heuristics for pipelined multicast operations on heterogeneous platforms”, Proceedings of International Conference on ICPP 2004, pp. 267 -274, 2004
[5].O. Beaumont, A. Legrand, L. Marchal and Y. Robert, “Pipelining Broadcasts on Heterogeneous Platforms”, IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp. 300 – 313, April 2005
[6].O. Beaumont, L. Marchal and Y. Robert, "Broadcast Trees for Heterogeneous Platforms", Proceedings of 19th IEEE International Parallel and Distributed Processing Symposium, pp. 80b - 80b, 2005.
[7].P. Bhat, C. Raghavendra and V. Prasanna. "Efficient collective communication in distributed heterogeneous systems", Journal of Parallel and Distributed Computing, pp. 15 – 24, 2003.
[8].A. Faraj, P. Patarasuk and X. Yuan, "Bandwidth Efficient All-to-all Broadcast on Switched Clusters", The 2005 IEEE Cluster 2005, Sept. 27-30, 2005.
[9].M. R. Garey and D. S. Johnson, "Computers and Intractability, a Guide to the Theory of NP-Completeness", W. H. Freeman and Company, 1979.
[10].S. Lennart Johnsson and Ching-Tien Ho, "Optimum Broadcasting and Personalized Communication in Hypercubes", IEEE Trans. Computers,vol. 38, no. 9, pp. 1249-1268, Sept. 1989.
[11].S. Khuller and Y. Kim., "On broadcasting in heterogeneous networks", In Proceedings of the 16th Annual ACM Symposium on Parallel Architectures and Algorithms, 2004.
[12].V. Kumar, A. Grama, A. Gupta and G. Karypis. Introduction to Parallel Computing. The Benjamin/Cummings Publishing Company, Inc., 1994.
[13].Chao Lin, Yu-Chee Tseng and Jang-Ping Sheu, ”Efficient Single-node Broadcast in Switched-based Network of Workstations with Network Partitioning”, Proceedings of Tenth International Conference on Computer Communications and Networks, pp. 68-74, 2001.
[14].Chao Lin, “Efficient contention-free broadcast in heterogeneous network of workstation with multiple send and receive speeds”, Proceedings Eighth IEEE International Symposium on Computers and Communication, 2003 (ISCC 2003), pp. 1277 - 1284 vol.2 2003
[15].Chao Lin, "Efficient broadcast in a heterogeneous network of workstations using two sub-networks", Proceedings of 7th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 273 - 279, May 2004.
[16].Bruce B. Lowekamp and Adam Begueliny, "ECO: Efficient Collective Operations for Communication on Heterogeneous Networks", Proceedings of The 10th International Parallel Processing Symposium 15-19 pp. 399 - 405 April 1996
[17].P. Liu, "Broadcast scheduling optimization for heterogeneous cluster systems", Journal of Algorithms, Volume 42, Issue 1, Pages 135-152, January 2002.
[18].Victor E. Mendia and Dilip Sarkar, “Optimal Broadcasting on the Star Graph”, IEEE Trans. Parallel and Distributed Systems, vol. 3, no. 4, pp. 389 - 396, July 1992
[19].J. Moore and M. Quinn, “Generating an Efficient Broadcast Sequence Using Reflected Gray Codes, ”IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 11, pp. 1117-1122, Nov. 1997.
[20].F. Ooshita, S. Matsumae, T. Masuzawa and N. Tokura, "Scheduling for broadcast operation in heterogeneous parallel computing environments", Systems and Computers in Japan, Volume 35, Issue 5, pp. 44 - 54, May 2004.
[21].F. Ooshita, S. Matsumae and T. Masuzawa, "Efficient gather operation in heterogeneous cluster systems", Proceedings of 16th Annual International Symposium on High Performance Computing Systems and Applications, pp. 196-204, 2002.
[22].Pitch Patarasuk, Ahmad Faraj and Xin Yuan, "Pipelined Broadcast on Ethernet Switched Clusters", Proceedings of Parallel and Distributed Processing Symposium, pp. 10, 2006.
[23].Adele A. Rescigno, “Optimal Polling in Communication Networks”, IEEE Trans. on Parallel and Distributed System, vol. 8, no. 5, pp. 449 - 461 May 1997
[24].Fernando G. Tinetti and E. Luque, "Efficient Broadcasts and Simple Algorithms for Parallel Linear Algebra Computing in Clusters", International Proceeding of Parallel and Distributed Processing Symposium, pp. 8, 2003
[25].Fernando G. Tinetti and Andrés Barbieri "An Efficient Implementation for Broadcasting Data in Parallel Applications over Ethernet Clusters", Proceeding of 17th International Conference on Advanced Information Networking and Applications, pp. 593 - 596 March 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔