Mark Bartlett - Worst Case Execution Time

Using Learning to Support the Development of Embedded Systems

The EPSRC funded project Using Learning to Support the Development of Embedded Systems (headed by Iain Bate) seeks to investigate the application of techniques from artificial intelligence and software testing to build models upon which the analysis of real-time systems, specifically the Worst Case Execution Times (WCET) of tasks can be based.

Approaches developed for WCET analysis must give conservative bounds but the degree of pessimism is typically too great for many purposes. All such analysis tools must ultimately rely on information about hardware instruction execution. However, modern processors are becoming very complex and the information needed to calculate WCETs is typically unavailable. Current analysis work seems to lag well behind the real world. Several researchers have identified measurement based approaches as a promising candidate to cope with modern-day engineering demands. Measurements can be taken freely, however the weakness is ensuring the results are safe.

Rather than directly inferring bounds on WCETs from execution trace timings, this project looks at how to use the measurements to infer a model of the underlying system that can form an input into further WCET calculations. Since the problem is in essence a learning problem, we investigate how well leading edge machine learning approaches can be adopted or adapted to this end. We believe that it may be possible to choose tests whose execution trace measurements contain sufficient information to allow abstract system models needed for WCET analysis to be automatically inferred.

So far, my work has specifically focussed on learning the number of times a nested loop executes as a function of its parameters. In general this is an undecidable problem, therefore we restrict ourselves to considering the Presburger subset. Using Inductive Logic Programming (ILP), we have created a tool provably capable of learning the number of loop iterations from a defined number of program traces.

Adapted from the project webpage

Complete List of My Publications on Worst Case Execution Time

Learning Bayesian Networks for Improved Instruction Cache Analysis
Mark Bartlett, Iain Bate and James Cussens
Proc. of the 9th International Conference on Machine Learning and Applications (ICMLA), 2010
Accurate Determination of Loop Iterations for Worst-Case Execution Time Analysis
Mark Bartlett, Iain Bate and Dimitar Kazakov
IEEE Transactions on Computers, 59(11), pp1520–1532, 2010
Instruction Cache Prediction Using Bayesian Networks
Mark Bartlett, Iain Bate and James Cussens
Proc. of the 19th European Conference on Artificial Intelligence (ECAI 2010), 2010
Guaranteed Loop Bound Identification from Program Traces for WCET
Mark Bartlett, Iain Bate and Dimitar Kazakov
Proc. of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2009), 2009
Challenges in Relational Learning for Real-Time Systems Applications
Mark Bartlett, Iain Bate and Dimitar Kazakov
Proc. of the 18th International Conference on Inductive Programming (ILP 2008), Lecture Notes in Artficial Intelligence 5194, pp42–58, 2008
See the project webpage for a full list of publications related to this project