臺灣博碩士論文加值系統

過去對於複雜的計算如科學、工程或者是商業計算，超級電腦都是唯一的選擇。現今個人電腦和網路的速度提升使得超級電腦的優越性不再。格網的技術可以連接許多高速個人電腦以執行複雜的計算。格網的種類可以被區分為三種，分別為資料格網、計算格網和存取格網。在本篇論文我們主要集中在計算格網。
在計算格網的環境中，工作排程演算法是相當重要的。工作排程必須根據
使用者的需求來尋找可用資源，並分配工作到需求的資源去執行。當在資源負載
較重的情況下，有可能發生所有效能較好的資源全部被佔用，使得剩餘的工作不
得不被分配到效能較差的資源來執行。假如接下來的工作的工作量相當大，並且被分配到效能較差的資源執行，這會造成工作執行時間大幅的增加。在這篇論文中，我們提出將工作分配到合適的資源執行的工作排程演算法來解決以上的問題。
有些工作排程演算法在靜態的環境中有較好的效能，如FPLTF (Fastest
Processor to Largest Task First)。但是當把這些演算法應用到動態的環境時，這些
排程演算法就不會有好的效能。由實驗結果可以看出，我們提出的演算法不管在
靜態還是動態的環境中，都可以保持較好的效能。

In the past, supercomputer is the only choice for complex computations in science, engineering and business computing. With the speed-up of personal computers and networks, the superiority of supercomputer is no longer ture. The grid technology, which connects a set of personal computers with high speed networks, can provide more powerful computing than the best supercomputer today. The grid environment can be classified into three types: data grid, computing grid, and access grid. We focus on computing grid in this thesis.
In computing grid, the task scheduling to discover resources for user’s requirements is important. In general, task scheduler assigns tasks to proper resource node for execution, and the resource nodes with better performance would be assigned first. When task loading is heavy and all resource nodes with better performance are assigned, other tasks might be assigned to the resource nodes with normal or worse performance. If a task is heavy loaded but assigned to the resource node without proper performance, the overall execution time will increase obviously.
To solve this problem, a task scheduling algorithm which searches the proper resource for task is proposed in this thesis.
Moreover, some scheduling algorithms, such as FPLTF (Fastest Processor to Largest Task First), work well only in static environment. In this thesis, simulation results show the proposed algorithm works well in both static and dynamic environments.

Table of Contents
Acknowledgement…………………………………………………………………I
摘要………………………………………………………………………………….II
Abstract…..…………………………………………………………………….III
Table of Contents…………………………………………………………………...IV
List of Figures………………………………………………………………………VI
List of Tables…………………………………………………………………..VII
Chapter 1 Introduction...................................................................................................1
Chapter 2 Background…………………………………………………………………4
2.1 Computing Grid……………………………………………………………4
2.2 Data Grid………………..…………………………………………………5
2.3 Access Grid…………….……..……………………………………………7
2.4 Grid Architecture….………………….………………………………..11
2.5 Overview of Globus Toolkit…………………………………………. 13
2.5.1 Grid Security Infrastructure……………….………………………. 14
2.5.2 Grid Resource Information Service…………..……………..…….. 15
2.5.3 Resource Management……………….……..……………………. 16
2.5.4 Data Management…………………………………………………. 18
Chapter 3 Related Work……………………………………………………………...23
3.1 Static Scheduling Algorithm……….……………………………………...23
3.1.1 Round Robin Scheduling Algorithm……………………………..23
3.1.2 Fastest Processor to Largest Task First Algorithm……………..23
3.1.3 Workqueue with Replication Algorithm………………………….24
3.1.4 Min-min Algorithm……………………………………………….25
3.1.5 Max-min Algorithm…………………….…………………………25
3.2 Dynamic Scheduling Algorithm…………………………………………..25
3.2.1 Most Fit Task First Algorithm……………………………………25
3.2.2 The QoS Guided Min-min heuristic Algorithm…………………..26
3.2.3 The Segmented Min-min Algorithm………….……………………28
Chapter 4 A New Task Scheduling Algorithm………………………………….……30
4.1 The Proposed Architecture…………………..…….………………………30
4.2 The Propose Algorithm………………...…………………………………32
4.3 Example for Proposed Algorithm…………………………………………34
Chapter 5 Simulation Analysis………………………………………………………39
5.1 Simulation Tool……………………….………………..…………………39
5.2 Experiment Environment and Result Analysis……………..……………41
5.3 Summary.…………………………………….…………………………….45
Chapter 6 Conclusions and Future Work…………………………………………...46
References…………………………………………………………………………..48












List of Figures
Figure 1-1:The grid system conception model………………………………………...2
Figure 2-1:The important components in computing grid system…………………….5
Figure 2-2:Most important components in data grid model…………………………...6
Figure 2-3:The access grid architecture………………………………………………8
Figure 2-4:Venue client architecture……….………………………………………..9
Figure 2-5:The node service architecture…………………………………………...10
Figure 2-6:Open shared application workflow……….....................…………………11
Figure 2-7:The layered grid architecture……………..………………………………12
Figure 2-8:The view of GT4 component……………..……………………………...14
Figure 2-9:Overview of globus toolkit integration architecture……………………..15
Figure 2-10:MDS hierarchy architecture……………...……………………………..16
Figure 2-11GRAM architecture in globus toolkit………..…………………………17
Figure 2-12:Parallel transfer vs. Striping.....................................................................18
Figure 2-13:Third-part of data transfer workflow………………………………...….20
Figure 2-14:The structure of replica catalog………………...……………………….21
Figure 2-15:Replica catalog structure…………………………….………………….22
Figure 3-1:The Qos guide min-min algorithm…………..……………...…………..27
Figure 3-2:The Segmented min-min algorithm……………………………………..29
Figure 4-1:The proposed architecture for assigning tasks to resource nodes……….31
Figure 4-2:The 7 levels in example………………………………………………….35
Figure 4-3:Process steps in SFRRU……………………………………...………….37
Figure 5-1:GridSim architecture………………...…………………………………..40
Figure 5-2:The closeness value comparing for deviation time…………...………….42
Figure 5-3 Average execution time for different scheduling algorithms……………..44

List of Tables
Table 4-1:The resource nodes in grid environment…………………………………..34
Table 4-2:The every resource nodes PET above LB level………………….………..36
Table 5-1:Simulation parameters for experiment…………………………………….42
Table 5-2:Simulation parameters to compare task scheduling algorithms…...………44

References
[1] B. Allcock, J. Bester, J. Bresnahan, Ann L. Chervenak, I. Foster, C. Kesselman, S. Meder, V. Nefedova, D. Quesnel, and S. Tuecke, “Data Management and Transfer in High-Performance Computational Grid Environments,” Parallel Computing, Vol. 28 (5), pp.749-771, May 2002.
[2] R. Buyya, M. Murshed, “GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing,” The Journal of Concurrency and Computation: Practice and Experience, Volume 14, pp. 1175-1220, 2002.
[3] G. Bugra, L. Ling, “A scalable peer-to-peer architecture for distributed information monitoring applications,” IEEE Transactions on Computers, Volume 54, Issue 6, Jun 2005 pp. 767 – 782.
[4] Y. Chang, “A Novel Replica Management Scheme with Multicasting in Data Grids”, July 2005, National Dong Hwa University, Hualien, Taiwan, ROC.
[5] A. Chervenak, L. Foster, C. Kesselman, C. Salisbury, and S. Tueckem, “The Data Grid: Towards an Architecture for the Distributed Management and Analysis of Large Scientific Data Sets,” Journal on Network and Computer Applications, Vol.23 (3), pp.187-200, July 2000.
[6] C. Chen , R. Wang, H. Chi, H. Chao, R. Chang, “Experiences of Using Access Grid over IPv6 Network,“ The Second Workshop on Grid Technologies and Applications, December 2005.
[7] O. H, IBARRA, CHUAL E, KIM “Heuristic algorithms for scheduling independent tasks on nonidentical processors,” Journal of the Association for Computing Machinery, Vol 24, No 2, pp. 280-289 April 1977.
[8] Casanova H, Legrand A, Zagorodnov D, and Berman F, “Heuristics for scheduling parameter sweep applications in grid environments,” Heterogeneous Computing Workshop, pp. 349-363, 1 May 2000.
[9] Z. Li, D. Huang, Z. Liu, J. Huang, “Research of peer-to-peer network architecture,” International Conference on Communication Technology , Vol 1, pp. 312 - 315, April 2003.
[10] S. Lin, “Data replication and job scheduling on cluster grid for data-intensive application,” July 2005, National Dong Hwa University, Hualien, Taiwan, ROC.
[11] Ripeanu, Matei, “Peer-to-peer architecture case study: Gnutella network,” Proceedings First International Conference on Peer-to-Peer Computing, pp. 99 – 100, Aug 2001.
[12] M. Maheswaran, S. Ali, H. Siegel, D. Hensgen, Richard F, Freund, “Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems,” Journal of Parallel and Distributed Computing, Volume 59, pp. 107-131, 1999.
[13] A.Singh, M. Haahr, “A Peer-to-Peer Reference Architecture,” Comsware First International Conference on Communication System Software and Middleware, pp. 1 – 10, Jan 2006.
[14] H. Sunaga, T. Oka, K. Ueda, H. Matsumura, “P2P-based grid architecture for homology searching,” Fifth IEEE International Conference on Peer-to-Peer Computing, pp. 148 – 149, 31 Aug 2005.
[15] D. Saha, D. Menasce, and S. Porto et al, “Static and Dynamic Processor Scheduling Disciplines in Heterogeneous Parallel Architectures,” Journal of Parallel and Distributed Computing, vol. 28, no. 1, pp. 1-18, 1995.
[16] D. Silva, W. Cirne and F. Brasileiro,“ Trading cycle for information: using replication to scheduling bag of tasks application on computational grids,” Proceeding in Ruro-Par, Aug. 2003.
[17] A. Sulistio, C.Yeo, and R. Buyya, “Visual Modeler and Simulation Toolkit,” International Conference on Computational Science, pp. 1123–1132, 2003.
[18] S. Wang, I. Hsu, and Z. Huang,“Dynamic Scheduling Method for Computational Grid Environments,” Proceedings of the International Conference on Parallel and Distributed Systems, pp. 22-28, July 2005.
[19] M. Wu, W. Shu, H. Zhang, “Segmented Min-Min: A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems,” Heterogeneous Computing Workshop Proceedings, pp. 375-385, 2000.
[20] HE Xiaoshan, X. Sun, G.Laszewski, “QoS Guided Min-Min Heuristic for Grid Task Scheduling,” Journal of Computer Science and Technology, Volume 18, pp. 442-451, 2003.
[21] The Globus Alliance, http://www.globus.org/
[22] Overview of the Gridsecurity Infrastructure, http://www.globus.org/security
[23] GT Information Service:Monitoring and Discovery System(MDS), http://www.globus.org/toolkit/mds/
[24] Overview of the GRAM, http://www-fp.globus.org/gram/overview.html
[25] GT GridFTP, http://www-unix.globus.org/toolkit/docs/4.0/data/gridftp/
[26] 王明習, 朱來憶, “使用於Access Grid之主持人會議控管模組之研製,” The Second Workshop on Grid Technologies and Applications, December 2005.
[27] 龔續揚, 吳明耀, 黃菁雅, “Mobile Learning Framework and System Design based on Access Grid Technology,” The Second Workshop on Grid Technologies and Applications, December 2005. December 2005.
[28] University College London, Robust Audio Tool, http://www-mice.cs.ucl.ac.uk/multimedia/software/rat/
[29] 嚴國慶, 王淑卿, 張秋萍, “在格網的環境中以有效的排程演算法避免飢餓的現象發生,” Proceedings of the First Workshop on Grid Technologies and Applications, 2004.