Please use this identifier to cite or link to this item:
標題: 一個用以預測服務網格應用執行時間的可調適混合模型
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, [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.

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.
其他識別: U0005-2707201010500700
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


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