臺灣博碩士論文加值系統

網格運算將分散於世界各地的有效資源整合成一部虛擬的超級電腦並將其強大的運算能力提供於科學方面的應用。為了讓資源在網格環境發揮出應有的效能，一個適用於網格運算環境的排程演算法就顯得極為重要。網格運算環境具有兩種特性：(1)資源動態性以及(2)資源異質性。到目前為止，已經有許多針對網格運算的工作排程演算法被提出。然而，大多數的工作排程演算法專注於解決網格資源異質性的問題。在本論文中，我們提出一個動態排程演算法稱為AROF。AROF工作排程演算法在分配工作時不僅會考慮到工作在異質環境中最快的完成時間，同時也會將可利用資源會變化的情況納入考量。AROF排程演算法主要包括了三個重要的模組，分別為︰(1)工作選擇模組、(2)權重分配模組以及(3)工作分配模組。我們透過多組不同參數設定的實驗來比較AROF工作排程演算法與兩個在網格運算中知名的工作排程演算法：HEFT以及GS工作排程演算法。因為實驗環境的限制以及比較上的需求，HEFT以及GS在本篇中有經過修改。實驗結果顯示AROF工作排程演算法在動態運算資源環境中的效能較修改版本的HEFT以及GS要好。

Grid computing integrates the worldwide available resources into a virtual supercomputer to support the requirement of huge computing power needed by scientifc applications. To achieve high performance computing, an e±cient task scheduling strategy is important. Grid computing environment has two significant characteristics: (1)resource heterogeneity and (2)availability variation. A lot of task scheduling algorithms for grid computing have been proposed. However, most of them focus on resource heterogeneity of a grid. In this thesis, a dynamic scheduling algorithm called AROF is proposed. In order to minimize the completion time of a work°ow application, AROF not only considers resource heterogeneity but also takes availability variation into consideration. AROF consists of three major modules: (1)selection module, (2)ranking module, and (3)mapping module. Experiments with various parameter settings for comparing AROF with the modified versions of well-known scheduling algorithms HEFT and GS are given. The experimental results show that AROF outperforms HEFT and GS in most cases.

Contents
Abstract(In English) i
Abstract(In Chinese) ii
Acknowledgement iii
Contents iv
List of Figures vi
List of Tables vii
1 Introduction 1
1.1 Background 1
1.2 Motivation 3
1.3 Thesis organization 4
2 Model 5
2.1 Task Model 5
2.2 Computing Model 6
3 Related work 10
3.1 Ranking attributes 10
3.2 Hybrid Heuristic 11
3.3 HEFT 12
3.4 CPOP 12
3.5 Hybrid Remapper 13
3.6 GS 15
3.7 Anticipated Distributed Task Scheduling(ADTS) 16
3.8 DCP 16
3.9 MCP 17
3.10 GSTR 18
3.11 DAGMap 18
3.12 Minmin and Maxmin 19
3.13 Suferage algorithm 21
4 AROF: an scheduling algorithm for dynamic grids 21
4.1 Problem definition 21
4.2 Scheduling algorithm 23
4.2.1 Selection module 23
4.2.2 Ranking module 27
4.2.3 Mapping module 28
4.2.4 The complete algorithm 29
5 Experimental results and analysis 33
5.1 The parameter settings of the computing model 34
5.2 The parameter settings of the task model 34
5.3 Experimental results 36
6 Conclusions and future work 42

Reference
[1] http://www.twgrid.org/
[2] A. Abdullah, M. Othman, M. N. Sulaiman, H. Ibrahim and A. T. Othman, "Towards a scalable Scienti¯c Data Grid model and services," Int'l Conference on Computerand Communication Engineering (ICCCE '08), pp. 20-25, 2008.
[3] S. Baskiyar and P. C. SaiRanga, "Scheduling Directed A-cyclic Task Graphs on Heterogeneous Network of Workstations to Minimize Schedule Length," Proceedings of the 2003 International Conference on Parallel Processing Workshops (ICPPW'03), pp. 97-103, 2003.
[4] C. Blanchet, C. Combet and G. Del¶eage, "Integrating Bioinformatics Resources on the EGEE Grid Platform," Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid Workshops (CCGRIDW '06), vol. 2, pp. 41-48, 2006.
[5] H. Cao, H. Jin, X. Wu, S. Wu and X. Shi, "DAGMap: E±cient Scheduling for DAG Grid Work°ow Job," 2008 9th IEEE/ACM International Conference on Grid Computing, pp. 17{24, 2008.
[6] B. R. Carter, D. W. Watson, R. F. Freund, E. Keith, F. Mirabile and H. J. Siegel, "Generational Scheduling for Dynamic Task Management in Heterogeneous Computing Systems," Journal of Information Sciences, vol. 106, pp. 219-236, 1998.
[7] J.-Y. Chang and H.-L. Chen, "Dynamic-Grouping Bandwidth Reservation Scheme for Multimedia Wireless Networks," IEEE Journal on Selected Areas in Communi- cations, vol. 21, pp. 1566-1574, 2003.
[8] Jeremy Coles, "The Evolving Grid Deployment and Operations Model within EGEE, LCG and GridPP," Proceedings of the First International Conference on e-Science and Grid Computing (e-Science '05), pp. 60-97, 2005.
[9] R. F. Freund et al, "Scheduling Resources in Multi-user, Heterogeneous, Computing Environments with SmartNet," Proceedings of Heterogeneous Computing Workshop (HCW '98), pp. 184-199, 1998.
[10] I. Foster and C. Kesselman, The Grid 2: Blueprint for a New Blueprint for a Future Computing Infrastructure, Morgan Kaufmann Publishers, 1998.
[11] I. Foster, "Globus Toolkit Version 4: Software for Service-Oriented Systems," IFIP International Conference on Network and Parallel Computing, pp. 2-13, 2006.
[12] F. Gagliardi and M.-E. Begin, "EGEE - Providing a Production Quality Grid for e-Science," Local to Global Data Interoperability - Challenges and Technologies, pp. 88-92, 2005.
[13] W. Hoschek, J. J. Martinez, A. Samar, H, Stockinger and K. Stockinger, "Data Management in an International Data Grid Projec," Proceedings of the ¯rst IEEE/ACM International Workshop on Grid Computing, pp. 77{90, 2000.
[14] E. Ilavarasan, P. Thambidurai and R. Mahilmannan, "Performance E®ective Task Scheduling Algorithm for Heterogeneous Computing System," The 4th International Symposium on Parallel and Distributed Computing (ISPDC '05), 2005.
[15] Y.-K. Kwok and I. Ahmad, "Dynamic CriticalPath Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors," IEEE Transactions on Parallel and Distributed Systems, vol. 7, pp. 506-521, 1996.
[16] Y. C. Lee and A. Y. Zomaya, "Practical Scheduling of Bag-of-Tasks Applications on Grids with Dynamic Resilience," IEEE Transactions on Parallel and Distributed Systems, vol. 56, pp. 815-825, 2007.
[17] Fabiano de O. Lucchese, Eduardo J. Huerta Yero, Francisco S. Sambatti and Marco A. A. Henriques, "An Adaptive Scheduler for Grids," Journal of Grid Computing, vol. 4, pp. 1-17, 2006.
[18] M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen and R. F. Freund, "Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing System," Journal of Parallel and Distributed Computing, vol. 59, pp. 107-131, 1999.
[19] M. Maheswaran and H. J. Siegel, "A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems," Proceedings of 7th Heterogeneous Computing Workshop (HCW '98), pp. 57-69, 1998.
[20] A. Pfei®er, L. Moneta, V. Innocente, H. C. Lee, and W. L. Ueng, "The LCG PI Project: Using Interfaces for Physics Data Analysis," IEEE Transcations On Nuclear Science, vol. 52, pp. 2823-2826, 2005.
[21] T. Rauber and G. RÄunger, "Anticipated Distributed Task Scheduling for Grid Environments," Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS '06), 2006.
[22] S. Roiser and A. Pfei®er, "Con¯guration, Build and Distribution of LCG Applications Area Software for the LHC Experiments," Nuclear Science Symposium Conference Record, vol. 3, pp. 1918-1922, 2007.
[23] R. Sakellariou and H. Zhao, "A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems," Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS '04), 2004.
[24] H. Topcuoglu, S. Hariri and M.-Y. Wu, "Performance-E®ective and Low-Complexity Task Scheduling for Heterogeneous Computing," IEEE Transactions on Parallel and Distributed Systems, vol. 13, pp. 260-274, 2003.
[25] M. Tsiknakis et al, "A Semantic Grid Infrastructure Enabling Integrated Access and Analysis of Multilevel Biomedical Data in Support of Postgenomic Clinical Trials on Cancer," IEEE Transactions on Information Technology in Biomedicine, vol. 12, pp. 205-217, 2008.
[26] L. Wang, H. J. Siegel, V. P. Roychowdhury and A. A. Maciejewski, "Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic- Algorithm-Based Approach," Journal of Parallel and Distributed Computing, vol. 47, pp. 8-22, 1997.
[27] M.-Y. Wu and D. D. Gajski, "Hypertool: A Programming Aid for Message-Passing Systems," IEEE Transactions on Parallel and Distributed Systems, vol. 1, pp. 330-343, 1990.
[28] M. Yanga, Y. Huanga, J. Kimb, M. Lee, T. Suda and M. Daisuked, "An End-to-End QoS Framework with On-Demand Bandwidth Recon¯guration," in Proc. INFOCOM 2004, vol. 3, pp. 2072-2083, 2004.