Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19726
標題: 一個用以預測服務網格應用執行時間的可調適混合模型
An Adaptive Hybrid Model for Predicting Run Times of Service-Grid Applications
作者: 楊哲璿
Yang, Che-Hsuan
關鍵字: Service Grid;服務網格;Prediction;Similarity;Similarity Template;Prediction;預測;相似;相似模板;測預模型
出版社: 資訊科學與工程學系所
引用: [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, http://setiathome.berkeley.edu/. [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,”http://www.gridtoday.com. [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: http://gwa.ewi.tudelft.nl/ [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. http://gwa.ewi.tudelft.nl/pmwiki/pmwiki.php?n=Workloads.Gwa-t-4 [34] Grid''5000. ALADDIN-G5K:Ensuring the Development of Grid''5000. www.grid5000.fr
摘要: 
預測應用程式的執行時間,對網格架構而言是至關重要的。尤其對如何最佳化排程、預先資源保留的資源管理、系統負載分析。在網格環境中,為了最佳妥善使用資源及解決應用程式提出的要求,系統需要預測模型以預測每一個資源是否可被使用及預測應用程式結束時間。由於網格具有異質性資源和分散式節點的特性,使得預測應用程式的執行時間是一件難以解決的任務,因為涉及到工作流程中需要多個跨等級的資源、相互依賴的需求行動、網格的動態行為。
論文中,我們提出一個可適應混合模型利用相似模板來預測應用程式的執行時間。在工作數據裡的應用程式依照所定義的特性做分類。我們使用工作數據建立應用程式的特性表並成為我們演算法的部分組合,我們搜尋演算法對每一個應用程式用來發現符合資格的模板集合。預測模型使用歷史資料預測預測執行時間,為了改善效能,我們採用可適應技術。
模擬結果顯示,在不同分佈下預測模型預測執行時間能夠達到平均預測錯誤率小於0.12,我們並使用兩個真實網格工作數據:AuverGrid和Grid''5000,透過一系列模擬評估,使用相似模板在可適應混合模型下的成效,實驗結果指出我們的方法是有效果且有效率。

Application 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.
URI: http://hdl.handle.net/11455/19726
其他識別: U0005-2707201010500700
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


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