之前的分散式平行計算的研究絕大多數都專注於專屬的環境條件上，系統通常依據各節點所擁有的運算資源來分配節點工作量，以求得分散式平行程式之負載平衡，從而提升程式之執行效能。然而在非專屬的分散式平行計算環境裡，同一個實體運算叢集可能有數個分散式平行程式在其中執行。因而有的節點可能同時為數個正在執行的平行程式所選用，讓不同的分散式平行程式彼此競爭有限的系統資源，從而破壞了原來預期的負載平衡，使的分散式平行程式之執行效能降低，連帶使系統總生產率低落。因此如何在非專屬的分散式平行計算環境裡，有效解決資源競爭的狀況，進而提升系統總生產率，便成為重要的課題。本篇論文試圖在非專屬分散式共享記憶體系統環境中，遵循動態空間共享的延伸概念，發展出一套適合的資源分配解決方法。這個方法在平行計算應用程式執行時期，可動態的搜尋較佳的資源分配解決方案，然後利用動態調整資源和平行程式執行緒分配之方式，來解決資源競爭的狀況。此方法在解決系統資源競爭狀況的同時，亦考量個別平行程式之負載平衡，並同時提升個別平行程式的效能以及系統總生產率。在實驗數據中可以看出，這個方法可以在非專屬分散式共享記憶體系統中有效的提升系統的總生產率，同時也使的個別的平行程式都達到其負載平衡之目的，從而提升平行程式的執行效能。

　　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.

[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.