近年來，在格網計算方面有越來越多的相關研究，但是大多都是將格網環境裡的資源皆視為同質性，這將造成挑選資源的盲點，因此在這篇論文我們提出一個基於開放格網服務架構並且可以支援平行工作的排程器。我們的排程器在設計上主要是針對格網環境的實際情況做考量為出發點，第一是在異質性節點的挑選方面，我們有去考慮到格網上並非所有節點都具有相同的計算能力，因此採用每個節點的處理器個數及速度來算出其節點的真正計算能力。第二是我們特別針對在格網上執行平行工作所追求的效能做考慮，所以提出了一個兩階段的排程演算法。階段一是計算能力的評分，階段二是通訊成本的評分。在這兩個階段的判斷，我們的排程演算法運用一個評分的公式來比較計算能力與通訊成本，並在經過排名之後成功挑選出最佳站台組合，因此我們不僅考慮了每個站台的計算能力更考慮若要跨站台以取得更佳計算能力的節點，在跨站台間所需的通訊成本付出是否值得。因此我們的排程器主要強調在能夠為使用者工作挑選到一個計算能力最強與能付出最少通訊成本的一種資源組合來縮短平行程式的執行時間並且提升系統效能。

In recent years, there are more and more correlation researches in Grid computing. However, most of them regard the resources of the Grid environment as homogeneous resources, and this situation may cause a blind spot of the resource selection. Therefore, in this thesis we propose a scheduler for parallel jobs based on open grid services architecture (OGSA). The design of our scheduler mainly aims at the actual situation of Grid environment to think over. First, in the selection of the heterogeneous resources, not all Grid nodes have the same computing power, so we take this problem into account and adopt the number and speed of processor in each node to calculate the actual computing power of every node. Second, we especially focus on the performance of the parallel jobs executed on the Grid, and consequently we propose a two-phase scheduling algorithm. Phase one is computing power scoring, while phase two is communication cost scoring. In the estimation of the two phases, our scheduling algorithm performs a scoring formula to analyze the computing power and communication cost, and then selects the best resource-combination after ranking. Therefore, we not only consider the computing power of every site but also consider the communication cost. We judge whether the communication cost for crossing sites is acceptable or not if needing to cross sites to access the resources with the more superior computing power. As a result, our scheduler emphasizes that it can select a site-combination with the highest computing power and the lowest communication cost for users to reduce the turnaround time of the parallel jobs and raise the system performance.

[1]. I. Foster, C. Kesselman, and S. Tuecke, “The anatomy of the Grid: Enabling scalable virtual organizations”. International Journal of Supercomputer Applications, 2001.

[2]. K. Kaneda, Y. Oyama, and A. Yonezawa. “Virtualizing a Multi-processor Machine on a Network of Computers”. In the 2nd Symposium on Global Dependable Information Infrastructure, March 2005

[3]. I. Foster, C. Kesselman, J. Nick, and S. Tueck, “The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration”, Web page, Jan. 2002.

[4]. I. Foster et al. “Modeling and Managing State in Distributed Systems: The Role of OGSI and WSRF”. Proceedings of the IEEE, 93(3):604-612, 2005.

[5]. Bray T,Paoli J,Sperberg-McQueen C M. “Extensible Markup Language (XML) 1.0 (Second. Edition),” W3C Recommendation, October 2000.

[6]. Kuo-Chan Huang, Po-Chi Shih, and Yeh-Ching Chung, “Towards Feasible and Effective Load Sharing in a Heterogeneous Computational Grid,” Proceedings of International Conference on Grid and Pervasive Computing (GPC), Lecture Notes in Computer Science (LNCS), France, May 2007.

[7]. C. Ernemann, V. Hamscher, U. Schwiegelshohn, A. Streit, R. Yahyapour, “On Advantages of Grid Computing for Parallel Job Scheduling”, Proceedings of 2nd IEEE International Symposium on Cluster Computing and the Grid (CC-GRID 2002), Berlin, Germany, 2002, pp. 39-46.

[8]. G. Sabin, R. Kettimuthu, A. Rajan and P. Sadayappan, “Scheduling of Parallel Jobs in a Heterogeneous Multi-Site Environment”, Proceedings of 9th Workshop on Job Scheduling Strategies for Parallel Processing, June 2003.

[9]. W. Zhang, A. M. K. Cheng, M. Hu, “Multisite Co-allocation Algorithms for Computational Grid”, Proceedings of the 20th International Parallel and Distributed Processing Symposium, April 2006, pp. 8-.

[10]. T.Y. Liang , C.Y. Wu, J.B. Chang, C.K. Shieh, “Teamster-G: A Grid-enabled Software DSM System”, In of the Proceeding of The 2005 International Workshop on Distributed Shared Memory on Clusters at the IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2005), Cardiff , UK, May 9-12, 2005 , pp. 905-912.

[11]. T.Y. Liang , C.Y. Wu, J.B. Chang, C.K. Shieh, “Enabling Software DSM System for Grid Computing”, In the Proceeding of International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN2005), Las Vegas, USA, Dec. 7-9, 2005 , pp. 428-435.

[12]. I. Foster, and C. Kesselman, “Globus: A Metacomputing Infrastructure Toolkit”. International Journal of Supercomputer Applications, 1998. 11(2): p. 115-129.

[13]. T. Zang, W. Jie, T. Hung, Z. Lei, Turner, SJ, W. Cai, “The Design and Implementation of an OGSA-based Grid Information Service”. Proceedings of the IEEE International. Conference on Web Services (ICWS’04), 2004.

[14]. W. Cai, G. Coulson, P. Grace, Blair, G.S., L. Mathy, Yeung, W.K., “The Gridkit Distributed Resource Management Framework”, Proceedings of the European Grid Conference, Amsterdam, The Netherlands, February 2005.

[15]. I. Foster, C. Kesselman, J. Nick, and S. Tuecke, “Grid Services for Distributed Systems Integration”. IEEE Computer, 2002, 35 (6). 37-46.

[16]. R. Chinnici, M. Gudgin, J.-J. Moreau, and S. Weerawarana, “WebServices description language (WSDL) Version 1.2” W3C Working Draft, 3 March 2003.

[17]. A. Nadalin, et al. “Web Service Security: Soap Message Security 1.0.” Technical report, OASIS, March 2004.

[18]. I. Foster. “Globus Toolkit Version 4: Software for Service-Oriented Systems.” IFIP International Conference on Network and Parallel Computing, Springer-Verlag LNCS 3779, 2005, pp 2-13.
[19]. P. Luksch, U. Maier, S. Rathmayer, M. Weidmann, and F. Unger. “Software engineering methods for parallel applications in scientific computing”, Project SEMPA. IEEE Concurrency, July-September 1997.

[20]. S. Wiriyaprasit and V. Muangsin, “The impact of Local Priority Policies on Grid Scheduling Performance and an Adaptive policy-based Grid Scheduling Algorithm.”, 7th International Conference on High Performance Computing and Grid in Asia Pacific Region, 2004.

[21]. T. Arts and J. J. S. Penas. “Global Scheduler Properties Derived from Local”. In Proceedings of the ACM Sigplan Erlang Workshop (Pittsburgh, USA), October 2002.

[22]. J. P. J., editor. “PBS Pro 5.3 Administrator Guide”. Altair Grid Technologies, 2003

[23]. D. Thain, T. Tannenbaum, and M. Livny, “Distributed Computing in Practice: The Condor Experience” Concurrency and Computation: Practice and Experience, Vol. 17, No. 2-4, February-April, 2005, pages 323-356.

[24]. Sun Microsystems, Inc. “N1 Grid Engine 6 Administration Guide”, 2004.

[25]. K. Nadiminti, S. Venugopal, H. Gibbins, T. Ma and R. Buyya, “The Gridbus Grid Service Broker and Scheduler (2.4.4) User Guide”, Technical Report, GRIDS-TR-2005-15, Grid Computing and Distributed Systems Laboratory, University of Melbourne, Australia, May 30, 2006.

[26]. E. Speight and J.K. Bennett. “Brazos: A third generation DSM system”. Proceedings of the 1997 USENIX Windows/NT Workshop, 1997, pp. 95-106.

[27]. C. Amza, A.L. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, W. Zwaenepoel, “TreadMarks: Shared Memory Computing on Networks of Workstations”. IEEE computer, 29 (2), 1996, pp. 18-28.

[28]. J.B. Carter, J.K. Bennett and W. Zwaenepoel. “Implementation and Performance of Munin”. In Proceedings of 13th ACM Symposium on Operating System Principles, 1991, p. 152-164.

[29]. K. Li. “IVY. A shared virtual memory system for parallel computing”. In Proceedings of the 1988 International Conference on Parallel Processing (ICPP'88), 1988, pp. 94-101.

[30]. M.L. Massie, B.N. Chun, D.E. Cueller, “The Ganglia Distributed Monitoring System:. Design, Implementation, and Experience,” Parallel Computing, Volume 30, Issue 7,. July 2004, pp817-840.

[31]. R. Wolski, N. Spring, J. Hayes, “The network weather service: A distributed resource performance forecasting service for metacomputing”. Future Generation Computing Systems, 1999,15(5-6):757-768.

[32]. J. H. Abawajy, S. P. Dandamudi, “Time/Space Sharing Distributed Job Scheduling Policy in a Workstation Cluster Environment”. PARELEC 2000: 116-120

[33]. K. Nadiminti, S. Venugopal, H. Gibbins, T. Ma and R. Buyya, “The Gridbus Grid Service Broker and Scheduler (2.4.4) User Guide”, Technical Report, GRIDS-TR-2005-15, Grid Computing and Distributed Systems Laboratory, University of Melbourne, Australia, May 30, 2006.

[34]. Message Passing Interface Forum. “MPI: A message-passing interface standard. International”. Journal of Supercomputer Applications, 1994, 8(3/4):165{414.

[35]. M. Carson, D. Santay, “NIST Net: a Linux-based Network Emulation Tool”, ACM SIGCOMM Computer Communication Review, Volume 33, Issue 3, July 2003,. pp. 111 - 126.

[36]. I. Foster, and C. Kesselman, “Computational grids”. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann. San Mateo, CA.,1998, pp. 15-51.

[37]. J. H. Abawajy, S. P. Dandamudi. “Parallel Job Scheduling on Multicluster Computing Systems”, cluster, IEEE International Conference on Cluster Computing (CLUSTER'03), 2003, p.11.