You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact webmaster@ide.mdh.se

Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems

Authors:


Note:

http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-1031

Publication Type:

Licentiate Thesis

Publisher:

Mälardalen University Press Licentiate Theses, ISSN 1651-9256; 122


Abstract

To date, many industrial embedded systems are very large, flexible, and highly configurable software systems, containing millions of lines of code and consisting of hundreds of tasks, many with real-time constraints, being triggered in complex, nested patterns. Furthermore, the temporal dependencies between tasks in such systems are difficult to determine analytically, and they vary the execution time and response time of tasks greatly. We refer to such systems as Complex Real-Time Embedded Systems (CRTES). To maintain, analyze and reuse such CRTES is very difficult and expensive, which, nevertheless, offers high business value in response to great concern in industry. Moreover, in such context, not only the functional behavior of systems has to be assured, but also non-functional properties such as the temporal behavior, i.e., the Worst-Case Response Time (WCRT) of the adhering tasks in systems has to be known. However, due to high complexity of such systems and the nature of the problem, the exact WCRT of tasks is impossible to find in practice, but may only be bounded. In addition, the existing relatively well developed theories for modeling and analysis of real-time systems are having problems, which limit their application in the context. In this thesis, we address this challenge, and present a framework for approximate timing analysis of CRTES that provides a tight interval of WCRT estimates of tasks by the usage of three novel contributions. The first contribution is a statistical approach to WCRT analysis of CRTES. The proposed algorithm combines Extreme Value Theory with other statistical methods in order to produce a probabilistic WCRT estimate, using response time data from either Monte Carlo simulations of a detailed model of the system, or time-stamped traces of the real system execution. The focus of the method is to give a WCRT prediction with a given probability of being exceeded, which potentially could be considered as an upper bound on the WCRT estimate, especially in the case where conventional timing analysis methods cannot be applied. The second contribution is a concrete process of formally obtaining the exact value of both Worst-Case Execution Time (WCET) and WCRT of tasks by using upper-part binary search algorithms together with a timed model checker, after a semantic-preserving model transformation. The underline premise is that the size and complexity of CRTES have to be reduced such that they can be manageable by the model checking tool. The third contribution is the application of an optimization algorithm, in this case a meta-heuristic search algorithm, on top of the traditional Monte Carlo simulation. Combining optimization and simulation has shown to yield substantially better results with respect to tight lower bounds on WCRT estimates of tasks in CRTES. In addition, a number of tools have been implemented and used for the evaluation of the research results. These evaluations, using four simulation models depicting two fictive but representative industrial control applications, give clear indication that the proposed methods have the potential to be both applicable and useful in practice.

Bibtex

@misc{Lu1934,
author = {Yue Lu},
title = {Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems},
note = {http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-1031},
number = {122},
month = {October},
year = {2010},
publisher = {M{\"a}lardalen University Press Licentiate Theses, ISSN 1651-9256; 122},
url = {http://www.es.mdu.se/publications/1934-}
}