Statistical regression models for WCET estimation

Abstract

1. Problem Statement. Worst Case Execution Time (WCET) is the upper bound of the execution time of a real-time task running on a particular hardware platform. The estimation of WCET is of significant importance to the correctness of schedulability analysis and thus the reliability of real-time applications. 2. Approach. Traditionally, WCET is often estimated based on static analysis techniques. However, advanced architectural features make the static analysis of WCET extremely complicated. As a result, measurement-based approaches become popular in practice. Despite its popularity, this type of approach would require running a task with a large number of input settings to obtain safe and accurate WCET estimates. To solve this challenge, we develop statistical regression models on a set of benchmark tasks to connect task execution time with some selected features. Our models can be used to estimate the WCET of new tasks without running a large number of sample executions. 3. Results. Our fitted regression models show that the execution times are highly related to the selected feature factors ‘Load’ and ‘Missing Rate’. Through a comparison study, we evaluate different measurement-based approaches from both safe and accurate perspectives. The comparison results are summarized to give general guidelines in searching good measurement-based WCET estimation approaches.

Keywords:

• Worst case execution time
• linear regression model
• quantile regression model
• extreme value theory

Acknowledgements

The authors would like to thank the editor and two reviewers for their valuable comments and suggestions.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was funded in part by the NSF [grant number CNS-1421577].