Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributor.advisorWoei Linen_US
dc.contributor.authorYang, Che-Hsuanen_US
dc.identifier.citation[1] Foster, C. Kesselman, and S. Tuecke, “The Anatomy of the Grid: Enabling Scalable Virtual Organizations,” International Journal of High Performance Computing Applications, 15(3): pp. 200-222, 2001. [2] SETI@home website, [3] I. Foster and C. KEsselman, “Globus: A metacomputing infrastructure toolkit,” The International Journal of Supercomputer Applications and High Performance Computing, 11(2), pp. 115-158, 1997. [4] I. Foster, C. Kesselman, J. Nick, and S. Tuecke. “Grid Services for Distributed System Integration,” IEEE Computer, 35(6), pp. 37-46, 2002. [5] I. Foster, “What is the Grid? A Three Point Checklist 2002,” [6] H. Zhuge, “Semantics, resource and Grid,” editorial of the special issue of Future Generation Computer System, 20(1), pp. 1-5, 2004. [7] R. Gibbons, “A historical application profiler for use by parallel schedulers,” Lecture Notes on Computer Science, vol. 1297, pp. 58-75, Springer, Berlin, 1997. [8] W. Smith, “Resource management in metacomputing environments,” Ph.D. Thesis, Northwestern University, December 1999. [9] W. Smith, I. Foster and V. Taylor, “Scheduling with advanced reservations,” Proceedings of the 2000 International Parallel and Distributed Processing Symposium, May 2000. [10] W. Smith, V. Taylor and I. Foster, “Using run-time predictions to estimate queue wait times and improve scheduler performance,” Proceedings of the IPPS/SPDP'99 Workshop on job Scheduling Strategies for Parallel Processing, 1999. [11] A. Downey, “Predicting queue times on space-sharing parallel computers,” In Proceedings of the 11th International Parallel Processing Symposium, 1997. [12] Y. Gao, H. Rong and J. z. Huang, “Adaptive grid job scheduling with genetic algorithms,” Future Generation Computer Systems, pp.151-161, 2005. [13] Y. Zhang and W. Sun, “CPU Load Predictions on the Computational Grid,” IEICE TRANS. INE & SYST., Vol.E90-D, NO.1, JANUARY 2007. [14] W. Yongwei, H. Kai, Y. Yulai, and, Z. Weiming, “Adaptive Workload Prediction of Grid Performance in Confidence Windows,” Parallel and Distributed Systems IEEE Transactions , Vol. 21, Issue 7, pp. 925-938, 2009. [15] R. Prodan, and T. Fahringer, “Overhead analysis of scientific workflows in grid environments,” IEEE Trans. Parallel Distribution System, 19(3):378-393, 2008. [16] K. Huang, P. Shih and Y. Chung, “Adaptive Processor Allocation for Moldable Jobs in Computational Gird,” 10th International Journal of Grid and High Performance Computing, 1(1), 10-21, January-March 2009. [17] Y. Hong, “The System Composition and Architecture,” Grid. Journal of Southwest China Normal University (Natural Science Edition), Vol. 29, No. 4, pp. 586-560, 2004. [18] S. Krawczyk, and K. Bubendorfer, “Grid Resource Allocation: Allocation Mechanisms and Utilisation Patterns,” Proceedings of the sixth Australasian workshop on Grid computing and e-research, pp. 73-81, 2008 [19] I. Foster, C. Kesselman, J. Nick, and S. Tuecke, “The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration,” Proceedings of the 5th Global Grid Forum Workshop (GGF5), Vol. 55, No. 2, pp. 42-47, 2002. [20] W. Smith, Ian Foster and Valerie Taylor, “Predicting application run times with historical information,” J. Parallel distribution computer, 64, 1007-1016, 2004. [21] K. Krauter, R. Buyya and, M. Maheswaran, “A taxonomy and survey of Grid resource management systems for distributed computing,” Software-Practice and Experience, 2 ,135-164, 2002 [22] H. Dail, H. Casanova and F. Berman, “A modular scheduling approach for Grid application development environments,” UCSD CSE Technical Report CS20020708, 2002. [23] H. Casanova, and J. Dongarra. “NetSolve: a network-enabled server for solving computational science problems,” Intitual. Journal. Supercomputer Application High Performance Computer, 11 (3), 212-223, 1997. [24] Y. Yan and B. Chapman, “Scientific Workflow Scheduling in Computational Grids­Planning, Reservation, and Data/Network­Awareness,” 8th IEEE/ACM, International Conference on Grid Computing, pp. 18-25, 2007. [25] Fahringer et al, “Scientific Workflows for Grids, chapter ASKALON: A Development and Grid Computing Environment for Scientific Workflows,” Workflows for e-Science, Springer, Springer Verlag, pp. 530, 2007. [26] A. Sulistio, C. Yeo, and R. Buyya, “A taxonomy of computer-based simulations and its mapping to parallel and distributed systems simulation tools,” Software-Practice and Experience, Volume 34, Issue 7, pp.653-673, 2004. [27] F. Nadeem, and T. Fahringer, “Using Templates to Predict Execution Time of Scientific Workflow Applications in the Grid,” 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, 2009. [28] L. M. Khanli and M. Analoui, “Resource Scheduling in Desktop Grid by Grid-JQA,” GPC Workshops ''08, The 3rd International Conference, Grid and Pervasive Computing Workshops, 2008. [29] D. Feitelson and B. Nitzberg, “Job characteristics of a production parallel scientific workload on the NASA Ames iPSC/860,” Lecture Notes in Computer Science, vol. 949, Springer, Berlin, pp. 337-360, 1995. [30] Grid Workloads Archive. Available: [31] Beaumont, A. Legrand and Y. Robert, “Optimal algorithms for scheduling divisible workloads on heterogeneous systems,” Proceedings of the International Parallel and Distributed Processing Symposium, 2003. [32] J. K. Kim et al., “Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines,” Proceedings of the International Parallel and Distributed Processing Symposium, 2003. [33] AuverGrid Workload Report. [34] Grid''5000. ALADDIN-G5K:Ensuring the Development of Grid''5000. www.grid5000.frzh_TW
dc.description.abstract預測應用程式的執行時間,對網格架構而言是至關重要的。尤其對如何最佳化排程、預先資源保留的資源管理、系統負載分析。在網格環境中,為了最佳妥善使用資源及解決應用程式提出的要求,系統需要預測模型以預測每一個資源是否可被使用及預測應用程式結束時間。由於網格具有異質性資源和分散式節點的特性,使得預測應用程式的執行時間是一件難以解決的任務,因為涉及到工作流程中需要多個跨等級的資源、相互依賴的需求行動、網格的動態行為。 論文中,我們提出一個可適應混合模型利用相似模板來預測應用程式的執行時間。在工作數據裡的應用程式依照所定義的特性做分類。我們使用工作數據建立應用程式的特性表並成為我們演算法的部分組合,我們搜尋演算法對每一個應用程式用來發現符合資格的模板集合。預測模型使用歷史資料預測預測執行時間,為了改善效能,我們採用可適應技術。 模擬結果顯示,在不同分佈下預測模型預測執行時間能夠達到平均預測錯誤率小於0.12,我們並使用兩個真實網格工作數據:AuverGrid和Grid''5000,透過一系列模擬評估,使用相似模板在可適應混合模型下的成效,實驗結果指出我們的方法是有效果且有效率。zh_TW
dc.description.abstractApplication run time prediction for Grid architecture is of critical importance for optimization scheduling, advance reservations of resource management, and overhead analysis. To make the best use of the resources and to solve the applications request in the Grid environment, the system requires prediction model to make a prediction of available performance on each resource and the application terminal time. Predicting run time of application is a complex task, because heterogeneous resource nodes are involved several Grid resources in workflow execution, dependencies of request services and dynamic behavior of the Grid in a distributed environment. In this paper we present an adaptive hybrid model exploiting similarity templates to prediction run time of application. The applications are characterized considering the characteristics describing in the workload trace. Using the workload trace build the characteristic table into our algorithms. Our search algorithms are employed to find eligible template set for each application. Similarity template feeds in the prediction model. The prediction model predicts run time with historical data. In order to improve the performance, we use the adaptive technique. The experimental result shown that the prediction model can achieve average prediction error ratio less than 0.12 under various distributions to predict the execution time of a job. Through a series of simulations using two real-life workload trace on the AuverGrid and Grid''5000 in France, we evaluate the effectiveness of the adaptive hybrid prediction model using similarity templates.en_US
dc.description.tableofcontents誌謝 i 摘要 ii Abstract iii 目錄 iv 圖目錄 vi 表目錄 vii 第一章 緒論 1 1.1 簡介 1 1.2 研究動機、目的 2 1.3 論文架構 3 第二章 背景知識及相關研究 4 2.1 網格定義及特點 4 2.2 網格類型 5 2.3 網格架構 6 2.4 虛擬組織 8 2.5 開放式網格運算服務架構 8 2.6 Similarity 10 2.7 Similarity Template 11 2.8 Prediction Model 12 第三章 Adaptive Hybrid Model 14 3.1 Service Grid 14 3.1.1 Service Grid Architecture 14 3.1.2 工作執行特性 16 3.2 Similarity Templates 19 3.2.1 定義characteristic 20 3.2.2 定義Similarity Template 21 3.2.3 Greedy Algorithm 和 Candidate Algorithm 21 3.3 Prediction Model 26 3.3.1 Single service model 和 Multiple services model 27 3.3.1 Simple Prediction Model 28 3.3.2 Extended Prediction Model 31 3.3.3 Adaptive Hybrid Prediction model 33 第四章 模擬結果與分析 36 4.1 模擬環境介紹及參數設定 36 4.1.1 模擬環境介紹 36 4.1.2 參數設定 37 4.2 模擬Adaptive Hybrid Prediction Model結果分析 38 4.3 模擬Adaptive Hybrid Prediction Model with Template Set結果分析 47 第五章 結論與未來工作 55 參考文獻 56zh_TW
dc.subjectService Griden_US
dc.subjectSimilarity Templateen_US
dc.titleAn Adaptive Hybrid Model for Predicting Run Times of Service-Grid Applicationsen_US
dc.typeThesis and Dissertationzh_TW
item.openairetypeThesis and Dissertation-
item.fulltextno fulltext-
Appears in Collections:資訊科學與工程學系所
Show simple item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.