跳到主要內容

臺灣博碩士論文加值系統

(3.236.110.106) 您好!臺灣時間:2021/07/25 23:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:楊大猷
研究生(外文):Yang, Da-Yu
論文名稱:異質性網格計算環境中之工作排程與處理器配置
論文名稱(外文):Job Scheduling and Processor Allocation for Heterogeneous Grid Computing Environments
指導教授:賴冠州賴冠州引用關係
指導教授(外文):Lai, Kuan-Chou
學位類別:碩士
校院名稱:國立臺中教育大學
系所名稱:數位內容科技學系碩士班
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2007
畢業學年度:96
語文別:英文
論文頁數:63
中文關鍵詞:網格計算異質性傳輸花費模式工作排程
外文關鍵詞:grid computingheterogeneouscommunication cost modeljob scheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:144
  • 評分評分:
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
  在科技發達的現在,如何使用網格技術以及高效能的排程演算法,組合成龐大的分散式計算資源,以解決單一電腦無法快速求解的問題,已成為一項熱門的研究議題。本研究將在分散式且異質性資源的環境當中,加入不相等的網路速度,以考慮傳輸花費模式,並進行工作排程與處理器配置機制的演算法分析。因此,一件工作在遞交給網格排程者後,網格排程者會計算此工作在各個resource (or site)的(1)計算時間、(2)傳輸時間、(3) resource可以開始執行工作的時間、及(4)工作在各個resource的完成時間,作為網格排程演算法之設計依據。在計算過程當中,本論文將工作的工作長度單位MIPS,換算成需要多少個工作時間單位(job time unit),每一個resource所擁有的計算能力之單位MIPS,也換算成每秒能提供多少個工作時間單位(job time unit)。在以上幾點的考慮之下,網格排程者會依據工作在各個resource的完成時間來進行評估,從中挑選出一個可以最早完成工作的resource來進行工作的分配。藉由此種網格排程者集中式的接收系統中的工作要求,再透過本論文所提出的工作排程與處理器配置演算法,可得到工作及整個工作列表在網格系統當中的工作最早完成時間,且能縮短工作整體的執行長度。在網格系統當中,若無適當的使用工作排程及處理器配置演算法,雖然最後仍可將系統中的工作要求完成,但所得的執行時間長度過長,會造成系統中資源不必要的浪費。因此,為了使網格系統中的資源能充分利用且不造成浪費,使用工作排程及處理器配置演算法是必要的。
  最後,在研究結果中,將可看出「需要大量計算的」、「需要大量傳輸的」、「需要大量計算且大量傳輸的」等三種工作,在不同的meta-computer環境中,最佳化網格排程演算法的處理結果。
In the high-tech world, one of the most popular research topics would be to find the way to use Grid technologies that include highly efficient scheduling algorithms in a large distributed computing environment, to solve problems that a single computer cannot solve quickly. This research adds unequal network speeds into the distributed and heterogeneous resource environment to consider communication cost models, and conduct the algorithm analysis on job scheduling and processor allocation mechanisms. Therefore, when a job is submitted to the Grid scheduler, it will have to compute the following items regarding this job at every resource (or site) to serve as a basis for the design of Grid scheduling algorithms. These include (1) computation time, (2) communication time, (3) the job starting time at every resource, and (4) the job finishing time at every resource. In the computing process, this study will convert the unit “MIPS” of the job length into amounts of job time units; the unit “MIPS” of the computing ability of every resource will also be converted into amounts of job time units that resources can provide every second. Based on the above considerations, the Grid scheduler will estimate (according to the job finishing time at every resource) and select the resource that can finish the job the earliest to dispatch the job. By using this type of job request within the receiving system of a centralized Grid scheduler, we will be able to obtain the earliest job finishing time of the job and job lists within the Grid system, when the job scheduling and processor allocation algorithms proposed by this study are used. Therefore, the entire job execution length is shortened. In Grid systems, the job requests within a system can still be finished by using inadequate job scheduling and processor allocation algorithms, but the execution time will be extended and then unnecessary resource waste within the system will occur. Therefore, job scheduling and processor allocation algorithms are necessary if the resources in the Grid system are to be used fully and entirely.
Finally, the research results display the process results of optimized Grid scheduling algorithms in different meta-computer environments of three types of jobs. The three types of jobs include: “computation-intensive jobs”, “communication-intensive jobs”, or “both computation- and communication-intensive jobs”.
摘要 I
Abstract II
List of Tables II
List of Figures III
Chapter 1. Introduction 1
1.1 Motivation 1
1.2 Problems 3
1.3 Purposes 4
1.4 Restrictions 6
1.5 Notations 7
Chapter 2. Related Works 9
2.1 Job Scheduling Algorithms 10
2.2 Processor Allocation Algorithms 14
2.3 Cost Models 26
Chapter 3. Proposed Algorithm 32
3.1 Problem Definition 32
3.2 Proposed Algorithm 34
3.3 A Simple Example 37
Chapter 4. Simulation Environment 45
4.1 Introduction of GridSim 45
4.2 Simulation Environment 46
Chapter 5. Experimental Results 49
5.1 Experimental Arguments 49
5.2 Comparison Metrics 52
5.3 Influence Factors 57
Chapter 6. Conclusions and Future Works 59
References 61
[1]Bailey, D., et al., “The NAS parallel benchmarks,” RNR-94-007, NASA 1994.
[2]Buyya, R., and Murshed, M., “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 (CCPE), Volume 14, Issue 13-15, Wiley Press, Nov.-Dec., 2002.
[3]CFD Online, http://www.cfd-online.com/.
[4]Computational fluid dynamics, http://en.wikipedia.org/wiki/Computational_fluid_dynamics.
[5]Ernemann, C., Hamscher, V., Schwiegelshohn, U., Yahyapour, R., and Streit, A, 2002, “On Advantages of Grid Computing for Parallel Job Scheduling,” In Proceedings of the 2nd IEEE/ACM international Symposium on Cluster Computing and the Grid (May 21 - 24, 2002). CCGRID. IEEE Computer Society, Washington, DC, pp. 39-46.
[6]Foster, I., “What is the Grid? A Three Point Checklist,” GRIDToday, July 20, 2002.
[7]Foster, I., and Kesselman, C., The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, San Francisco, CA, 1999.
[8]Foster, I., Kesselman, C., and Tuecke, S., “The Anatomy of the Grid: Enabling Scalable Virtual Organizations,” The Intl. Journal of High Performance Computing Applications, 15(3): pp. 200-222, Fall 2001.
[9]Gehring, J., and Preiss, T., “Scheduling a Metacomputer with Uncooperative Sub-schedulers,” In Proceedings of the Job Scheduling Strategies For Parallel Processing, Lecture Notes on Computer Science Vol. 1659, pp. 179–201, San Juan, Puerto Rico, April 1999.
[10]GridCafe, “全世界的網格計畫,” http://www2.twgrid.org/gridcafe/projectworld/projects.htm.
[11]Guo Leitao, “Grid,” http://www.chinagrid.net/grid/paperppt/USTC/Ltguo.ppt.
[12]Hamscher, V., Schwiegelshohn, U., Streit, A., and Yahyapour, R., “Evaluation of Job-Scheduling Strategies for Grid Computing,” In Proceedings of the First IEEE/ACM international Workshop on Grid Computing, Lecture Notes on Computer Science Vol. 1971, pp. 191-202, Springer-Verlag, London, 2000.
[13]Howell F, and McNab, R., “SimJava: A discrete event simulation package for Java with applications in computer systems modelling,” Proceedings of the 1st International Conference on Web-based Modelling and Simulation, San Diego, CA. Society for Computer Simulation, 1998.
[14]Introduction to Computational Fluid Dynamics (ie CFD), http://www.cham.co.uk/website/new/cfdintro.htm.
[15]Introduction to quantum mechanics, http://en.wikipedia.org/wiki/Introduction_to_quantum_mechanics.
[16]LCG Project Overview, http://lcg.web.cern.ch/LCG/overview.html.
[17]Li, K., “Job scheduling and processor allocation for grid computing on metacomputers,” Journal of Parallel and Distributed Computing, Vol. 65, Issue. 11, pp. 1406-1418, November 2005.
[18]List scheduling - Wikipedia, the free encyclopedia, http://en.wikipedia.org/wiki/List_scheduling.
[19]Quantum computer, http://en.wikipedia.org/wiki/Quantum_computer.
[20]Quantum computing, http://eve.physics.ox.ac.uk/Personal/steane/qcomp.html.
[21]SETI@home, http://setiathome.berkeley.edu/.
[22]Silberschatz, A., Galvin, P. B., and Gagne, G., Operating System Principles, 7th ed, Hoboken, NJ : J. Wiley & Sons, Inc., 2006.
[23]SimJava, http://www.dcs.ed.ac.uk/home/hase/simjava/.
[24]Smarr, L., and Catlett, C.E., “Metacomputing,” Communications of the ACM, Vol. 35, Issue. 6, pp. 44-52, June 1992.
[25]Stibor, M., and Kutil, M., “Torsche Scheduling Toolbox: List Scheduling,” In Proceedings of Process Control 2006, Pardubice: University of Pardubice, June 13-16, 2006.
[26]Sulistio, A., Cibej ,U., Robic ,B., and Buyya, R., “A Tool for Modelling and Simulation of Data Grids with Integration of Data Storage, Replication and Analysis,” Technical Report, GRIDS-TR-2005-13, Grid Computing and Distributed Systems Laboratory, University of Melbourne, Australia, Nov. 8, 2005.
[27]Sulistio, A., Poduval, G., Buyya, R., and Tham, C. K., “On Incorporating Differentiated Levels of Network Service into GridSim,” Future Generation Computer Systems (FGCS), ISSN: 0167-739X, Volume 23, Issue 4, May 2007, Pages: 606-615 Elsevier Science, Amsterdam, The Netherlands, May 2007.
[28]Sulistio, A., Yeo, C. S., and Buyya, R., “A Taxonomy of Computer-based Simulations and its Mapping to Parallel and Distributed Systems Simulation Tools,” International Journal of Software: Practice and Experience, Volume 34, Issue 7, Pages: 653-673, Wiley Press, USA, June 2004.
[29]Taiwan UniGrid Project, http://www.unigrid.org.tw/index.html.
[30]Tanenbaum, A. S., and Woodhull, A. S., Operating Systems: Design and Implementation, 3rd ed, Upper Saddle River, N.J., Pearson Prentice Hall, 2006.
[31]The GRIDS Lab and the Gridbus Project, http://gridbus.csse.unimelb.edu.au/gridsim/.
[32]The Network Simulator - NS-2, http://nsnam.isi.edu/nsnam/index.php/Main_Page.
[33]The SimOS Home Page, http://simos.stanford.edu/.
[34]TIGER Grid Broker, http://gamma2.hpc.csie.thu.edu.tw/.
[35]TIGER Grid, http://gamma2.hpc.csie.thu.edu.tw/ganglia/.
[36]Wang, C.M., Chen, H.M., Chang, C.C., and Wu, J.J., “A High-Performance Virtual Storage System for Taiwan UniGrid,” Proceedings of the Third Workshop on Grid Technologies and Applications, CHU, Hsinchu, Taiwan December 7-8, 2006.
[37]Welcome to the SimGrid Project, http://simgrid.gforge.inria.fr/.
[38]World Wide Grid(WWG), http://www.gridbus.org/ecogrid/wwg/.
[39]Yahyapour, R., “Design and evaluation of job scheduling strategies for grid computing,” Doctoral Thesis, Computer Engineering Institute, Lehrstuhl für Datenverarbeitungssysteme, November 2002.
[40]Yang, C.T., and Ho, H.C., “A Shareable e-Learning Platform Using Data Grid Technology,” In Proceedings of the 2005 IEEE international Conference on E-Technology, E-Commerce and E-Service (Eee'05) on E-Technology, E-Commerce and E-Service, EEE, IEEE Computer Society, Washington, DC, pp. 592-595, March 29 - April 01, 2005.
[41]Yang, C.T., Chen, S.Y., Chen, T.T., Yeh, Y.C., and Chen, C.Y., “Design and Implementation of Monitoring and Information Services Using Ganglia and NWS for Grid Resource Broker,” Proceedings of the Third Workshop on Grid Technologies and Applications, CHU, Hsinchu, Taiwan December 7-8, 2006.
[42]林誠謙, 李世昌, 鄧炳坤, “下一代網際網路新紀元-全球網格(World Wide Grid),” 自然科學簡訊, 第十五卷第四期, pp. 123-124, November 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top