跳到主要內容

臺灣博碩士論文加值系統

(44.192.15.251) 您好!臺灣時間:2024/03/05 19:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:郭哲宏
研究生(外文):Zhe-Hung Kuo
論文名稱:非專屬分散式共享記憶體系統資源分配之研究
論文名稱(外文):A Study of Resource Allocation for Non-dedicated Distributed Shared Memory Systems
指導教授:謝錫堃謝錫堃引用關係梁廷宇
指導教授(外文):Ce-Kuen ShiehTyng-Yeu Liang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:60
中文關鍵詞:負載平衡分散式共享記憶體資源分配
外文關鍵詞:load balancingDSMschedulingresource allocation
相關次數:
  • 被引用被引用:1
  • 點閱點閱:143
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  之前的分散式平行計算的研究絕大多數都專注於專屬的環境條件上,系統通常依據各節點所擁有的運算資源來分配節點工作量,以求得分散式平行程式之負載平衡,從而提升程式之執行效能。然而在非專屬的分散式平行計算環境裡,同一個實體運算叢集可能有數個分散式平行程式在其中執行。因而有的節點可能同時為數個正在執行的平行程式所選用,讓不同的分散式平行程式彼此競爭有限的系統資源,從而破壞了原來預期的負載平衡,使的分散式平行程式之執行效能降低,連帶使系統總生產率低落。因此如何在非專屬的分散式平行計算環境裡,有效解決資源競爭的狀況,進而提升系統總生產率,便成為重要的課題。本篇論文試圖在非專屬分散式共享記憶體系統環境中,遵循動態空間共享的延伸概念,發展出一套適合的資源分配解決方法。這個方法在平行計算應用程式執行時期,可動態的搜尋較佳的資源分配解決方案,然後利用動態調整資源和平行程式執行緒分配之方式,來解決資源競爭的狀況。此方法在解決系統資源競爭狀況的同時,亦考量個別平行程式之負載平衡,並同時提升個別平行程式的效能以及系統總生產率。在實驗數據中可以看出,這個方法可以在非專屬分散式共享記憶體系統中有效的提升系統的總生產率,同時也使的個別的平行程式都達到其負載平衡之目的,從而提升平行程式的執行效能。
  In the early researches of distributed parallel computing, most of them focused on the dedicated computing environments. In order to improve the performance of the parallel applications, their systems usually allocate the application workload according to the resource volumes of each node in their working cluster. However, in the non-dedicated distributed parallel computing environments, there may be several parallel applications simultaneously executing in the same physical computing cluster. Therefore, some nodes may be selected by multiple parallel applications for their execution at the same time, and then the finite system resources on these nodes will be seriously contended by the different parallel applications. This kind of situations will obviously destroy the workload balance of each parallel application and make the application performance and system throughput decreased. So how to effectively eliminate resource contention in the non-dedicated environments becomes a significant research topic. In the thesis, we have developed a resource allocation method, which takes the extended concept of Dynamic Space Sharing (DSS), in the non-dedicated environment. Our proposed method can dynamically search the better resource allocation solutions while the parallel applications are in execution, and adjusts the thread and resource distribution of each parallel application to eliminate resource contention. In the meanwhile, our proposed method also considers the load balance of each application, and improves the performance of each application and system throughput. In the experimental results, we can see that the proposed method efficiently increases the system throughput, and makes each parallel application workload balance; moreover, it also improves the performance of each parallel application.
Chapter 1 Introduction 1
Chapter 2 Related Works 5
Chapter 3 Resource Allocation for Non-dedicated DSM Systems 8
3.1 Method Overview 8
3.2 Resource Allocation with Extended Dynamic Space Sharing (EDSS) 11
3.3 The Definition of Throughput 17
3.4 The Prediction Formula 18
Chapter 4 Implementation 22
4.1 Implementation of our approach 23
4.2 System Architecture of Teamster 26
4.3 Resource Manager 28
4.4 Information Collection and Display 30
4.3.1 Standard Output Redirection 31
4.3.2 Runtime Information Collection 33
4.5 Dynamic Workload Re-distribution 35
Chapter 5 Experimental Results 37
5.1 Experimental Applications 37
5.1.1 Successive-Over-Relaxation (SOR) 37
5.1.2 N-Body 38
5.2 Experimental Environments 41
5.3 Experimental Results of Resource Allocation Method 43
5.3.1 Experimental Results 43
5.3.2 Summary 55
Chapter 6 Conclusions and Future Works 43
Bibliography 58
[1] L.A. Belady and C. J. Kuehner, “Dynamic Space-Sharing in Computer Systems”, Communication of the ACM, Volume 12, Number 5, May, 1969.
[2] B. B. Zhou, R.P. Brent, D. Walsh, and k. Suzaki, “Job Scheduling Strategies for Networks of Workstations”, Workshop on Job Scheduling Strategies for Parallel Processing, 1998, LNCS 1459, pp.143157
[3] Abdur Chowdhury, Lisa D. Nicklas, Sanjeev K. Setia, and Elizabeth L. White, “Supporting Dynamic Space-sharing on Clusters of Non-dedicated Workstations”, Proceedings of the 17th International conference on distributed computing, 1997.
[4] Kritchalach Thitikamol and Peter Keleher, “Thread Migration and Load Balancing in Non-Dedicated Environments”, Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International , 1-5 May 2000 ,Pages:583 – 588.
[5] Weisong Shi, Zhimin Tang, “Dynamic computation scheduling for load balancing in home-based software DSMs,” Parallel Architectures, Algorithms, and Networks, 1999. (I-SPAN '99) Proceedings. Fourth International Symposium on, 1999.
[6] Thitikamol K, Keleher P,” Thread migration and load balancing in non-dedicated environments,” Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International, 2000.
[7] Jyh-Chang Ueng, Ce-Kuen Shieh, Wu-Hwa Liu, and Chi-Chang Lin, "Proteus: a runtime reconfigurable distributed shared memory system," High Performance Distributed Computing, 1999. Proceedings. The Eighth International Symposium on Page(s): 347 -348, 1999.
[8] Zhuang, Y.C., Ce-Kuen Shieh, Tyng-Yue Liang, Jun-Qi Lee, and Li-Ming Tseng, “A group-based load balance method for software distributed shared memory systems,” Cluster Computing and the Grid, 2001. Proceedings. First IEEE/ACM International Symposium on, 2001.
[9] Tyng-Yue Liang, Ce-Kuen Shieh, Jun-Qi Li, “An effective selection policy for load balancing in software DSM,” Parallel Processing, 2000. Proceedings. 2000 International Conference on. 2000.
[10] Chi-Chung Liao, "Communication Minimization of Progressive Multi-layer Reconfiguration on Teamster," Master thesis, Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, R.O.C, 2001
[11] M.J. Litzkow, M. Livny, and M.W. Mutka, “Condor --- A hunter of Idle Workstations,” Proc. Eighth lnt’l Conf. Distributed Computing Systems, IEEE CS Press, Los Alamitos, Calif., Order No. 865, 1988, pp. 104-111.
[12] Hollingsworth, J.K.; Keleher, P.J. “Prediction and adaptation in Active Harmony,” High Performance Distributed Computing, 1998. Proceedings. The Seventh International Symposium on , 28-31 Jul 1998
[13] Thitikamol K, Keleher P,” Thread migration and load balancing in non-dedicated environments,” Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International, 2000.
[14] Xiaodong Zhang, Yanxia Qu, and Li Xiao, “Improving Distributed Workload Performance by Sharing Both CPU and Memory Resources,” Proceedings of 20th International Conference on Distributed and Computing Systems, 2000
[15] Songqing Chen, Li Xiao, and Xiaodong Zhang, “Dynamic Load Sharing with Unknown Memory Demands in Clusters,” Proceedings of the 21th International Conference on Distributed and Computing Systems, 2001
[16] Li Xiao, Songqing Chen, and Xiaodong Zhang, “Dynamic Cluster Resource Allocations for Jobs with Known and Unknown Memory Demands,” IEEE Transactions on Parallel and Distributed Systems, Vol.13, No.3, March 2002.
[17] J. K. Ousterhout, “Scheduling Techniques for Concurrent Systems”, Proceedings of 3rd International Conference on Distributed Computing Systems, page 22-30, 1982
[18] D. G. Feistelson and L. Rudolph, “Gang Scheduling Performance Benefits for Fine-grained Synchronisation”, Journal of Parallel and Distributed Computing, Dec. 1992, pp.306-318
[19] Annop Gupta, Andrew Tucker, and Shigeru Urushibara, “The Impact of Operating System Scheduling Policies and Synchronization Methods on the Performance of Parallel Applications”, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems.
[20] Francesc Gine, Francesc Solsona, Porfidio Hernadez and Emilio Luque, “Co-scheduling under memory Constraints in a NOW Environment”, 7th Workshop on Job Scheduling Strategies for Parallel Processing.
[21] Patrick G. Sobalvarro, Scott Pakin, William E. Weihl and Andrew A. Chien, “Dynamic Co-scheduling on Workstation Clusters”, 12th Annual International Parallel Processing Symposium & 9th Symposium on Parallel and Distributed Processing (IPPS/SPDP).
[22] The Grid Forum, http://www.gridforum.org
[23] Vijay Subramani, Rajkumar Kettimuthu, Srividya Srinivasan and P. Sadayappan, “Distributed Job Scheduling on Computational Grids using Multiple Simultaneous Requests”, International Symposium on High Performance Distributed Computing 2002.
[24] Marcio Faerman, Alan Su, Richard Wolski, and Francine Berman, “Adaptive Performance Prediction for Distributed Data-Intensive Applications”, proceedings of the 1999 ACM/IEEE conference on Supercomputing.
[25] Ming Wu and Xian-He Sun , “A General Self-adaptive task Scheduling System for non-dedicated Heterogeneous Computing”, Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on, 1-4 Dec. 2003 Pages:354 - 361
[26] M. Arora, S.K. Das and R. Biswas, “A De-centralized Scheduling and Load balancing Algorithm for Heterogeneous Grid Environments”, Parallel Processing Workshops, 2002. Proceedings. International Conference on, 18-21 Aug. 2002 Pages: 499 – 505
[27] Prasad Jogalekar and Murray Woodside, “Evaluating the Scalability of Distributed Systems”, IEEE Transactions on Parallel and Distributed Systems, Vol. 11 NO. 6 June 2000.
[28] Chi-Ting Huang, Tyng-Yue Liang and Ce-Kuen Shieh, “A Resource-Oriented Workload Distribution Method for Software Distributed Shared Memory Systems,” Master thesis, Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, R.O.C., 2003.
[29] Jim Mauro and Richard McDougall, “Solaris Internals: Core Kernel Components”, Sun Microsystems Press, 2001, ISBN: 0-13-022496-0
[30] Vincent W. Freeh, David K. Lowenthal, and Gregory R. Andrews. Distributed Filaments: Efficient Fine-Grain Parallelism on A Cluster of Workstations. In Proceedings of First Symposium on Operating Systems Design and Implementation, p. 201-212, 1994.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top