Using Learning to Support the Development
of Embedded Systems

Investigators
Principal Investigator
Dr Iain Bate Webpage Email
Co-Investigators
Dr Dimitar Kazakov Webpage Email
Professot John Clark Webpage Email
Research Associate
Mark Bartlett Webpage Email
Research Student
Alex Wood Webpage Email
Sitsofe Wheeler Webpage Email
Publications
D. Kazakov and I. Bate, Towards New Methods for Developing Real-Time Systems: Automatically Deriving Loop Bounds Using Machine Learning.
In Proceedings of the 11th IEEE International Conference on Emerging Technologies and Factory Automation. 2006.
D. Kazakov and I. Bate, Learning Worst-Case Execution Time Loop Bounds with Inductive Logic Programming.
In Proceedings of the 16th International Conference on Inductive Logic Programming. 2006.
I. Bate and D. Kazakov, New Directions in Worst-Case Execution Time Analysis.
In Proceeding of the 2008 IEEE World Congress on Computational Intelligence. 2008.
M. Bartlett, I. Bate and D. Kazakov, Challenges in Relational Learning for Real Time Systems Applications.
In Proceedings of the 18th International Conference on Inductive Logic Programming. 2008.
M. Bartlett, I. Bate and D. Kazakov, Guaranteed Loop Bound Identification from Program Traces for WCET.
In Proceeding of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium. 2009.
M. Bartlett, I. Bate and J. Cussens, Instruction Cache Prediction Using Bayesian Networks.
In Proceeding of the 19th European Conference on Artificial Intelligence. 2010.
M. Bartlett, I. Bate and D. Kazakov, Accurate Determination of Loop Iterations for Worst-Case Execution Time Analysis.
In IEEE Transactions on Computers 59(11). 2010.
M. Bartlett, I. Bate and J. Cussens, Learning Bayesian Networks for Improved Instruction Cache Analysis.
In Proceedings of the 9th International Conference on Machine Learning and Applications. 2010.

This project 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.

Reasoning about the timing properties of many modern systems is crucial. Examples include anti-lock braking systems, air-bag deployment systems, air traffic collision avoidance systems, share-dealing systems and even medical applications such as X-ray dosage delivery equipment. Reasoning about response times of such systems has been the subject of much research [2]. In particular, a great deal of scheduling theory has been developed to provide bounds on worst case response times. Such work assumes that the timing properties of individual components in the system are well understood. In particular, the Worst Case Execution Time (WCET) for an individual task is an input to all forms of real-time scheduling theory. The derivation of such WCETs therefore underpins our efforts to guarantee response times in critical systems. The real-time systems community recognises this as a major challenge [2].

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 (e.g. internals of processors are commercially confidential). Where such information is provided, it has often proved to be wrong [4]. Current analysis work seems to lag well behind the real world.

What can be done about this? Several researchers have identified measurement based approaches as a promising candidate to cope with modern-day engineering demands [1,3]. 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, why not use the measurements to infer a model of the underlying system that can form an input into further WCET calculations? Our project addresses this very question. Since the problem is in essence a learning problem, we propose to investigate how well leading edge machine learning approaches can be adopted or adapted to this end. Our research hypothesis is 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.

This hypothesis leads to the following research questions:

Fusing ideas from real-time systems, machine learning and testing has the potential to make a major contribution to the way critical systems are developed and analysed. We believe that the techniques investigated have great application potential. WCET determination is a challenging yet tractable real-world application, serving as proof of concept.

References

[1] G. Bernat, A. Colin and S. Petters. WCET analysis of probabilistic hard real-time systems . In Proceedings of the 23rd Real-Time Systems Symposium, pages 279-288, 2002.

[2] B. Bouyssounouse and J. Sifakis, editors. Embedded Systems Design: The ARTIST Roadmap for Research and Development. Lecture Notes in Computer Science. Springer, 2005.

[3] L. David and I. Puaut. Static determination of probabilistic execution times. In Proceedings of the 16th Euromicro Conference on Real-Time Systems, pages 223-230, 2004.

[4] J. Engblom. Analysis of the execution time unpredictability caused by dynamic branch prediction. In Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 152-159, 2003.