博碩士論文 etd-0723108-124114 詳細資訊


[回到前頁查詢結果 | 重新搜尋]

姓名 李世詠(Shih-Yung Li) 電子郵件信箱 E-mail 資料不公開
畢業系所 資訊管理學系研究所(Information Management)
畢業學位 碩士(Master) 畢業時期 96學年第2學期
論文名稱(中) 運用機率架構於資料密集網格環境之動態資源規劃
論文名稱(英) A Probability-based Framework for Dynamic Resource Scheduling in Data-Intensive Grid Environment
檔案
  • etd-0723108-124114.pdf
  • 本電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
    請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
    論文使用權限

    電子論文:校內一年後公開,校外永不公開

    論文語文/頁數 英文/56
    統計 本論文已被瀏覽 5351 次,被下載 7 次
    摘要(中) 隨著網格運算的盛行,有越來越多的研究針對如何分配網格資源給工作流程中的每個任務提出不同的解決方法。有許多因素會影響到分配的結果,其中之一便是工作流程是屬於計算密集型或是資料密集型,許多研究會針對其中一種環境來進行。在本篇論文中,我們將根據先前所提出的運用機率架構之動態資源規劃並加進資料傳輸的影響因素。我們的目標是希望能夠動態地分配資源給工作流程中的任務,進而使整個工作流程能夠在使用者所期望的時間內完成的機率最大化。我們提出兩種不同的演算法來處理網格環境下的動態資源規劃,包括largest deadline completion probability (LDCP) and smallest deadline completion probability (SDCP)。此外,為了改善資料傳輸的問題,我們提出了push-based的規劃演算法與先前研究中的pull-based與workflow-based的方法進行比較。我們將使用GridSim網格模擬器來建立網格環境,評估不同演算法之間的效能差異。
    摘要(英) Recent enthusiasm in grid computing has resulted in a tremendous amount of research in resource scheduling techniques for tasks in a (scientific) workflow. There are many factors that may affect the scheduling results, one of which is whether the application is computing-intensive or data-intensive. Most of the grid scheduling researches focus on a single aspect of the environments. In this thesis, we base on our previous work, a probability-based framework for dynamic resource scheduling, and consider data transmission overhead in our scheduling algorithms. The goal is to dynamically assign resources to tasks so as to maximize the probability of completing the entire workflow within a desired total response time. We propose two algorithms for the dynamic resource scheduling in grid environment, namely largest deadline completion probability (LDCP) and smallest deadline completion probability (SDCP). Furthermore, considering the data transmission overhead, we propose a suite of push-based scheduling algorithms, which schedule all the immediate descendant tasks when a task is completed. These are algorithms will be compared to the pull-demand scheduling algorithms in our previous work and workflow-based algorithms proposed by other researchers. We use GridSim toolkit to model the grid environment and evaluate the performance of the various scheduling algorithms.
    關鍵字(中)
  • 工作流程
  • 資源規劃
  • 機率
  • 網格
  • 關鍵字(英)
  • Grid
  • Probability
  • Resource Allocation
  • Workflow
  • 論文目次 List of Content
    CHAPTER 1 - Introduction 1
    1.1. Background 1
    1.2. Motivation 1
    CHAPTER 2 - Literature Review 3
    2.1. Grid architecture 3
    2.2. General grid environment and scheduling 4
    2.2.1. Static resource scheduling 4
    2.2.2. Dynamic Scheduling 6
    2.3. Stochastic scheduling 7
    2.3.1 Minimize expected flowtime 7
    2.3.2 Minimize expected makespan 8
    2.3.3 Others 8
    2.3.4 Comparison 8
    2.4. Issue in data dependency 10
    CHAPTER 3 - Problem Description 11
    3.1. System architecture 11
    3.2. Problem Description 13
    CHAPTER 4 - Scheduling Algorithms 15
    4.1 Autonomy of local site 15
    4.2. Dynamic Scheduling Algorithm 17
    4.2.1 When to schedule a task 17
    4.2.2 Scheduling policy 17
    CHAPTER 5 - Performance Evaluation 22
    5.1 Simulation Environment Settings 24
    5.1.1. Computing power 25
    5.1.2. Data dependency 25
    5.1.3. Local workload 28
    5.2 Experimental Result 28
    5.2.1. Data Dependency 28
    5.2.2. Resource Computing Power 34
    5.2.3. Resources local load 38
    5.2.4. Complicated Situation 40
    CHAPTER 6 - Conclusion 44
    References 45
    參考文獻 Afzal, A., Darlington, J., & McGough, A. S. (2006). Stochastic Workflow Scheduling with QoS Guarantees in Grid Computing Environments. International Conference on Grid and Cooperative Computing, (pp. 185-194).
    Alhusaini, A., Prasanna, V., & Raghavendra, C. (1999). A Unified Resource Scheduling Framework for Heterogeneous Computing Environments. 8th Heterogeneous Computing Workshop, (pp. 156-165).
    Blythe, J., Jain, S., & Deelman, E. (2005). Task Scheduling Strategies for Workflow-based Applications in Grids. Cluster Computing and the Grid, (pp. 759-767).
    Braun, T. D., Siegel, H. J., Beck, N., L. L., Maheswaran, M., Reuther, A. I., et al. (2001). A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing , 61 (6), pp. 810-837.
    Buyya, R., & Venugopal, S. (2005). A Gentle Introduction to Grid Computing and Technologies. CSI Communications , 9-19.
    Buyya, R., Broberg, J., Sulistio, A., & Assuncao, M. D. (n.d.). Retrieved from The Grid Computing and Distribution Systems Laboratory, Univerisity of Melbourn: http://www.gridbus.org/gridsim/
    Cao, J., Jarvis, S. A., Saini, S., & Nudd, G. R. (2003). GridFlow: Workflow Management for Grid Computing. Cluster Computing and the Grid, (pp. 198-205).
    Dong, F., & Akl, S. G. (2006). Scheduling Algorithms for Grid Computing: State of the Art and Open Problems.
    E. G. Coffman, J., Flatto, L., Garey, M. R., & Weber, R. R. (1987). Minimizing Expected Makespans on Uniform Processor Systems. Advances in Applied Probability , pp. 177-201.
    Foster, I. (2001). The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications , 15 (3), pp. 200-222.
    Foster, I., & Kesselman, C. (2003). The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann.
    Foster, I., Kesselman, C., & Tuecke, S. (2001). The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing , 15 (3), pp. 200-222.
    Lin, H.-y. (2007). Resource Scheduling for Workflows in an Autonomous Grid Environment.
    Maheswaran, M., & Siegel, H. J. (1998). A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems. 7th Heterogeneous Computing Workshop, (p. 57).
    Mandal, A., Kennedy, K., Koelbel, C., Marin, G., & Mellor, J. (2005). Scheduling Strategies for Mapping Application Workflows onto the Grid. IEEE International Symposium on High Performance Distributed, (p. 10).
    Ni˜no-Mora, J. (2005). Stochastic scheduling. In C. A. Floudas, & P. M. Pardalos, Updated version of article in Encyclopedia of Optimization (p. 10).
    Ranganathan, K., & Foster, I. (2002). Decoupling Computation and Data Scheduling in Distributed Data-Intensive Applications. 11th IEEE International Symposium on High Performance Distributed Computing, (pp. 352-361). Edinburgh, Scotland.
    Ross, S. (1983). Introduction to Stochastic Dynamic Programming.
    Weber, R. R. (1982). Scheduling Jobs with Stochastic Processing Requirements on Parallel Machines to Minimize Makespan or Flowtime. Journal of Applied Probability , 19 (1), pp. 167-182.
    Weber, R. R., P., V., & J., &. W. (1986). Scheduling Jobs with Stochastically Ordered Processing Times on Parallel Machines to Minimize Expected Flowtime. Journal of Applied Probability , 23 (3), pp. 841-847.
    Weiss, G., & Pinedo, M. (1980). Scheduling Tasks with Exponential Service Times on Non-Identical Processors to Minimize Various Cost Functions. Journal of Applied Probability , 17 (1), pp. 187-202.
    口試委員
  • 張德民 - 召集委員
  • 楊婉秀 - 委員
  • 黃三益 - 指導教授
  • 口試日期 2008-06-23 繳交日期 2008-07-23

    [回到前頁查詢結果 | 重新搜尋]


    如有任何問題請與論文審查小組聯繫