博碩士論文 985202039 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:6 、訪客IP:54.81.220.239
姓名 張彥然(Yen-jan Chang)  查詢紙本館藏   畢業系所 資訊工程學系
論文名稱 線性相關工作與非相關工作的探索式排程策略
(Heuristic Scheduling Strategies for Linear-Dependent and Independent Tasks)
相關論文
★ 以伸展樹為基礎的Android Binder Driver★ 一個建立在平行工作系統上的動態全球計算平台
★ 用權重參照計數演算法執行主動物件垃圾收集★ 一個動態負載平衡之最大可能性估算計算架構
★ 利用多項系統負載資訊進行動態P2P系統重組的策略研究★ 基於Hadoop系統的雲端應用程式特徵擷取與計算監測架構
★ 適用於大型動態分散式系統的調適性計算模型★ 一個提供彈性虛擬資料中心的雲端服務平台
★ 雲端彈性虛擬機房服務平台之資源控管中心★ 一個適用於自動供應雲端系統的動態調適計算架構
★ 適用於大資料集高效率的分散式階層分群演算法★ 混合雲端環境上的多重代理人動態調適計算管理架構
★ 基於圖形的平行化最小生成樹分群演算法★ 基於密度的超立方體覆蓋之啟發式演算法
★ 利用 Cache 改善雲端虛擬機器啟動之研究★ 植基於分散式粒化運算的決策產生
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 由於網際網路的發展和計算機的取得越來越容易,分散式計算已經變成新一代計算機科學上主要的研究領域。分散式計算其中一個主要的動機是期望它能夠整合分散在各地的計算資源並且提供強大的計算服務給使用者。為了達到這樣的目的,在分散式計算系統中一種有效率的排程演算法是不可或缺的一部分。因為最佳化排程已經被證明是屬於NP-Hard,所以這篇論文主要的研究目標是探索式的排程演算法。探索式演算法能避免為了追求最佳解所需的大量運算的時間,而以近似的解來取代最佳解並且省去了大量的計算時間。
在這篇論文中我們會先介紹一些常用於排程的探索式的方法,包括優點、缺點以及它們的虛擬碼。然後利用網格模擬器GridSim[1]去模擬在工作間具有線性相依性和不具有相依性的情況下各個探索式的方法的效能表現,並討論其模擬的結果。最後在根據各個探索式方法模擬出來的結果整合出一個混合式的方法。這個混合式的方法可以避免單一探索式的方法在特定情況下所遇到的問題。我們也會去檢驗混合式的方法在job間具有相依性、job間不具有相依性和job間具有隨機的相依性的情況下表現出來的效能。
摘要(英) Thanks to advances in wide-area network technologies and the low cost of computing resources, grid computing came into being an active research area. One motivation of grid computing is to aggregate the power of widely distributed resources, and to provide non-trivial services to the users. To minimize the total completion time (makespan), an efficient grid scheduling mechanism must be used in a grid system to dispatch computing tasks to computing resources effectively. However, it has been proved that the optimal scheduling algorithm is NP-hard. Therefore, many people turn to use heuristic approaches for grid scheduling. In this thesis, we introduce eleven common scheduling heuristics to schedule a combination of linear dependent jobs and independent jobs. Then, we use a grid simulator, namely GridSim[1], to evaluate the performance of these heuristic approaches. According to the simulation results, we propose a novel hybrid heuristic approach that can avoid the drawbacks of the eleven heuristic approaches under different situations. Further simulation results confirm that the proposed hybrid approach is among the best heuristic approaches under most circumstances.
關鍵字(中) ★ 工作排程
★ 網格計算
★ 探索式方法
★ 工作相依性
關鍵字(英) ★ Job scheduling
★ Grid computing
★ Heuristics
★ Job dependency.
論文目次 目錄
摘要: IV
Abstract V
致謝 VI
目錄 VII
圖目錄 IX
表目錄 X
第1章 緒論 1
第2章 背景 4
2.1 網格的形式 4
2.2 基本概念 5
2.3 通用的定義 6
2.4 網格排程的程序 9
2.5 網格排程的類型 10
2.5.1 獨立的排程 11
2.5.2 網格工作流(Grid workflows) 11
2.5.3 集中式、階層式、非集中式排程 11
2.5.4 靜態與動態排程 12
2.5.5 立即排程與批次排程 12
2.5.6 適應性排程 13
2.5.7 資料網格排程 13
2.6 排程的目標(Objective functions) 13
2.6.1 完成時間(Makespan) 13
2.6.2 流程時間(Flowtime) 14
2.6.3 資源利用率(Resource utilization) 14
2.6.4 相配接近(Matching Proximity) 14
2.6.5 計算時間(Computation Time) 15
第3章 網格排程的探索式方法 16
3.1 Opportunistic Load Balancing(OLB) 16
3.2 最小執行時間Minimum Execution Time(MET) 16
3.3 最小完成時間Minimum Completion Time(MCT) 17
3.4 Min-min 18
3.5 Max-min 18
3.6 Longest Job First 20
3.7 Shortest Job First 20
3.8 Suffrage 21
3.9 Average Execution Time (AET) 21
3.10 Work Queue(WQ) 23
3.11 Min-max 23
第4章 模擬與討論 24
4.1 GridSim系統架構 24
4.2 模擬環境 25
4.3 獨立工作的模擬結果 26
4.4 工作間具相依性的模擬結果 28
4.5 隨機工作鏈長度的模擬結果 30
4.6 常態分佈的工作鏈長度模擬與討論 31
4.7 混合型的探索式方法 32
4.8 各種探索式方法在同質性處理器下的模擬 36
4.9 各種比例的線性相依性關係模擬 40
第5章 相關研究 48
5.1 資源可取得時間的限制 48
5.2 QoS的要求 48
5.3 工作流應用程式(Workflow Application) 49
第6章 結論 50
References 51
附錄一 Gridsim 54
GridSim 54
Gridsim Main Features 56
Gridsim功能概觀: 56
參考文獻 References
[1] A. Sulistio, U. Cibej, S. Venugopal, B. Robic, and R. Buyya, “A toolkit for modelling and simulating data Grids: an extension to GridSim,” Concurr. Comput. : Pract. Exper., vol. 20, Sep. 2008, pp. 1591–1609.
[2] D. Jewitt., “Project Pan-STARRS and the Outer Solar System.,” Earth, Moon and Planets., 2004.
[3] “Globus Toolkit,” http://www.globus.org/toolkit/.
[4] R. Raman, M. Solomon, A. Roy, and M. Livny, “The classads language,” Grid Resource Management: State of the Art and Future Trends.
[5] R. Armstrong, D. Hensgen, and T. Kidd, “The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions,” IN 7TH IEEE HETEROGENEOUS COMPUTING WORKSHOP (HCW ’98, vol. 79, 1998, p. 79--87.
[6] C. Simatos, “Making Simjava count,” MSc. Project report, The University of Edinburgh, 2002.
[7] J.D. Ullman, “NP-complete scheduling problems,” Journal of Computer and System Sciences, vol. 10, Jun. 1975, pp. 384–393.
[8] Garey, M. and Johnson, D., “A Guide to the Theory of NP-Completeness,” WH Freeman and Co, New York, 1979.
[9] J. Du, J.Y.-T. Leung, and G.H. Young, “Scheduling chain-structured tasks to minimize makespan and mean flow time,” Information and Computation, vol. 92, Jun. 1991, pp. 219-236.
[10] T.D. Braun, H.J. Siegel, N. Beck, L.L. Bölöni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys, B. Yao, D. Hensgen, and R.F. Freund, “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems,” Journal of Parallel and Distributed Computing, vol. 61, Jun. 2001, pp. 810–837.
[11] P.-Y. Lin and P. Liu, “Job Scheduling Techniques for Distributed Systems with Temporal Constraints,” Advances in Grid and Pervasive Computing, P. Bellavista, R.-S. Chang, H.-C. Chao, S.-F. Lin, and P.M.A. Sloot, Eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 280-289.
[12] R.J. Al-Ali, K. Amin, G. Laszewski, O.F. Rana, D.W. Walker, M. Hategan, and N. Zaluzec, “Analysis and Provision of QoS for Distributed Grid Applications,” Journal of Grid Computing, vol. 2, Jun. 2004, pp. 163-182.
[13] K. Krauter, R. Buyya, and M. Maheswaran, “A Taxonomy and Survey of Grid Resource Management Systems,” SOFTWARE PRACTICE AND EXPERIENCE, vol. 32, 2002, p. 135--164.
[14] “Scheduling with advanced reservations,” 2000, pp. 127-132.
[15] A. Sulistio and R. Buyya, “A Grid Simulation Infrastructure Supporting Advance Reservation,” 2004.
[16] A.S. Mcgough, A. Afzal, J. Darlington, N. Furmento, A. Mayer, and L. Young, “Making the Grid Predictable through Reservations and Performance Modelling,” The Computer Journal, vol. 48, May. 2005, pp. 358–368.
[17] M. Wieczorek, M. Siddiqui, A. Villazon, R. Prodan, and T. Fahringer, “Applying Advance Reservation to Increase Predictability of Workflow Execution on the Grid,” Washington, DC, USA: IEEE Computer Society, 2006, p. 82–.
[18] “On the Design of Online Scheduling Algorithms for Advance Reservations and QoS in Grids,” Mar. 2007, pp. 1-10.
[19] “Efficient resource management using advance reservations for heterogeneous Grids,” Apr. 2008, pp. 1-12.
[20] G. Singh, C. Kesselman, and E. Deelman, “A provisioning model and its comparison with best-effort for performance-cost optimization in grids,” New York, NY, USA: ACM, 2007, pp. 117–126.
[21] H. Dail, O. Sievert, F. Berman, H. Casanova, A. YarKhan, S. Vadhiyar, J. Dongarra, C. Liu, L. Yang, D. Angulo, and I. Foster, “Grid resource management,” J. Nabrzyski, J.M. Schopf, and J. Weglarz, Eds., Kluwer Academic Publishers, 2004, pp. 73–98.
[22] J. Yu, R. Buyya, and K. Ramamohanarao, “Workflow Scheduling Algorithms for Grid Computing.”
[23] Scheduling Algorithms, Berlin, Heidelberg: Springer Berlin Heidelberg, 2007.
[24] W.H. Bell, D.G. Cameron, L. Capozza, A.P. Millar, K. Stockinger, and F. Zini, “Simulation of Dynamic Grid Replication Strategies in OptorSim,” Grid Computing — GRID 2002, M. Parashar, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 46-57.
[25] C.Mihai Dobre and C. Stratan., “MONARC simulation framework,” Proc. of the RoEduNet International Conference, 2004.
[26] “ChicSim - the Chicago Grid Simulator,” http://people.cs.uchicago.edu/~krangana/ChicSim.html, 2007.
[27] A. Legrand, L. Marchal, and É.N. Supérieuredelyon, “Scheduling Distributed Applications: The SimGrid Simulation Framework,” IN PROCEEDINGS OF THE THIRD IEEE INTERNATIONAL SYMPOSIUM ON CLUSTER COMPUTING AND THE GRID (CCGRID’03, 2003, p. 138--145.
[28] “The MicroGrid: a Scientific Tool for Modeling Computational Grids,” Nov. 2000, pp. 53- 53.
指導教授 王尉任(Wei-Jen Wang) 審核日期 2011-7-26
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明