Advanced search
1 file | 1.32 MB Add to list

Online execution time prediction for computationally intensive applications with periodic progress updates

Maria Chtepen (UGent) , FHA Claeys, Bart Dhoedt (UGent) , Filip De Turck (UGent) , Jan Fostier (UGent) , Piet Demeester (UGent) and PA Vanrolleghem
(2012) JOURNAL OF SUPERCOMPUTING. 62(2). p.768-786
Author
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
    • |
    • PDF
    • |
    • 1.32 MB

Citation

Please use this url to cite or link to this publication:

MLA
Chtepen, Maria, FHA Claeys, Bart Dhoedt, et al. “Online Execution Time Prediction for Computationally Intensive Applications with Periodic Progress Updates.” JOURNAL OF SUPERCOMPUTING 62.2 (2012): 768–786. Print.
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.
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–786.
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.
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://dx.doi.org/10.1007/s11227-012-0748-z},
  volume       = {62},
  year         = {2012},
}

Altmetric
View in Altmetric
Web of Science
Times cited: