Guaranteed Loop Bound Identification from Program Traces for WCET
M. Bartlett, I. Bate and D. Kazakov
Static analysis can be used to determine safe estimates of Worst Case Execution Time. However, overestimation of the number of loop iterations, particularly in nested loops, can result in substantial pessimism in the overall estimate. This paper presents a method of determining exact parametric values of the number of loop iterations for a particular class of arbitrarily deeply nested loops. It is proven that values are guaranteed to be correct using information obtainable from a finite and quantifiable number of program traces. Using the results of this proof, a tool is constructed and its scalability assessed.
BibTex Entry
@inproceedings{Bartlett2009,
address = {San Francisco, CA, United States},
author = {M. Bartlett and I. Bate and D. Kazakov},
booktitle = {Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)},
month = {apr},
title = {Guaranteed Loop Bound Identification from Program Traces for WCET},
year = {2009}
}