Online execution time prediction for computationally intensive applications with periodic progress updates
- Author
- Maria Chtepen (UGent) , FHA Claeys, Bart Dhoedt (UGent) , Filip De Turck (UGent) , Jan Fostier (UGent) , Piet Demeester (UGent) and PA Vanrolleghem
- Organization
- Abstract
- The effectiveness of distributed execution of computationally intensive applications (jobs) largely depends on the quality of the applied scheduling approach. However, most of the existing non-trivial scheduling algorithms rely on prior knowledge or on prediction of application parameters, such as execution time, size of input and output, dependencies, etc., to assign applications to the available computational resources. A major issue is that these parameters are hard to determine in advance, especially if the end user does not possess an extensive history of previous application runs. In this work we propose an online method for execution time prediction of applications, for which execution progress can be collected at run-time. Using dynamic progress information, the total job execution time can be predicted using extrapolation. However, the predictions achieved by extrapolation are far from precise and often vary over time as a result of changing application dynamics and varying resource load. Therefore, to compute the actual job execution time we match a number of predefined prediction evolution models against the consecutive extrapolations, by adopting nonlinear curve-fitting. The "best-fit" coefficients allow for more accurate execution time prediction. The predictions made are used to enhance a dynamic scheduling algorithm for workflows introduced in our earlier work. The scheduling algorithm is run with and without curve-fitting, showing a performance improvement of up to 15% in the former case.
- Keywords
- IBCN, Execution time prediction, Optimization, Application distributed execution, PERFORMANCE
Downloads
-
(...).pdf
- full text
- |
- UGent only
- |
- |
- 1.32 MB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-3206454
- MLA
- Chtepen, Maria, et al. “Online Execution Time Prediction for Computationally Intensive Applications with Periodic Progress Updates.” JOURNAL OF SUPERCOMPUTING, vol. 62, no. 2, 2012, pp. 768–86, doi:10.1007/s11227-012-0748-z.
- APA
- Chtepen, M., Claeys, F., Dhoedt, B., De Turck, F., Fostier, J., Demeester, P., & Vanrolleghem, P. (2012). Online execution time prediction for computationally intensive applications with periodic progress updates. JOURNAL OF SUPERCOMPUTING, 62(2), 768–786. https://doi.org/10.1007/s11227-012-0748-z
- Chicago author-date
- Chtepen, Maria, FHA Claeys, Bart Dhoedt, Filip De Turck, Jan Fostier, Piet Demeester, and PA Vanrolleghem. 2012. “Online Execution Time Prediction for Computationally Intensive Applications with Periodic Progress Updates.” JOURNAL OF SUPERCOMPUTING 62 (2): 768–86. https://doi.org/10.1007/s11227-012-0748-z.
- Chicago author-date (all authors)
- Chtepen, Maria, FHA Claeys, Bart Dhoedt, Filip De Turck, Jan Fostier, Piet Demeester, and PA Vanrolleghem. 2012. “Online Execution Time Prediction for Computationally Intensive Applications with Periodic Progress Updates.” JOURNAL OF SUPERCOMPUTING 62 (2): 768–786. doi:10.1007/s11227-012-0748-z.
- Vancouver
- 1.Chtepen M, Claeys F, Dhoedt B, De Turck F, Fostier J, Demeester P, et al. Online execution time prediction for computationally intensive applications with periodic progress updates. JOURNAL OF SUPERCOMPUTING. 2012;62(2):768–86.
- IEEE
- [1]M. Chtepen et al., “Online execution time prediction for computationally intensive applications with periodic progress updates,” JOURNAL OF SUPERCOMPUTING, vol. 62, no. 2, pp. 768–786, 2012.
@article{3206454, abstract = {{The effectiveness of distributed execution of computationally intensive applications (jobs) largely depends on the quality of the applied scheduling approach. However, most of the existing non-trivial scheduling algorithms rely on prior knowledge or on prediction of application parameters, such as execution time, size of input and output, dependencies, etc., to assign applications to the available computational resources. A major issue is that these parameters are hard to determine in advance, especially if the end user does not possess an extensive history of previous application runs. In this work we propose an online method for execution time prediction of applications, for which execution progress can be collected at run-time. Using dynamic progress information, the total job execution time can be predicted using extrapolation. However, the predictions achieved by extrapolation are far from precise and often vary over time as a result of changing application dynamics and varying resource load. Therefore, to compute the actual job execution time we match a number of predefined prediction evolution models against the consecutive extrapolations, by adopting nonlinear curve-fitting. The "best-fit" coefficients allow for more accurate execution time prediction. The predictions made are used to enhance a dynamic scheduling algorithm for workflows introduced in our earlier work. The scheduling algorithm is run with and without curve-fitting, showing a performance improvement of up to 15% in the former case.}}, author = {{Chtepen, Maria and Claeys, FHA and Dhoedt, Bart and De Turck, Filip and Fostier, Jan and Demeester, Piet and Vanrolleghem, PA}}, issn = {{0920-8542}}, journal = {{JOURNAL OF SUPERCOMPUTING}}, keywords = {{IBCN,Execution time prediction,Optimization,Application distributed execution,PERFORMANCE}}, language = {{eng}}, number = {{2}}, pages = {{768--786}}, title = {{Online execution time prediction for computationally intensive applications with periodic progress updates}}, url = {{http://doi.org/10.1007/s11227-012-0748-z}}, volume = {{62}}, year = {{2012}}, }
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: