mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Metaheuristic Approach for Best Effort Timing Analysis targeting Complex Legacy Real-Time Systems
Mälardalen University, School of Innovation, Design and Engineering.
Mälardalen University, School of Innovation, Design and Engineering.ORCID iD: 0000-0002-7366-7186
Mälardalen University, School of Innovation, Design and Engineering.ORCID iD: 0000-0003-2855-9220
Mälardalen University, School of Innovation, Design and Engineering.
2008 (English)In: PROCEEDINGS OF THE 14TH IEEE REAL-TIME AND EMBEDDED TECHNOLOGY AND APPLICATIONS SYMPOSIUM, 2008, p. 258-269Conference paper, Published paper (Refereed)
Abstract [en]

Many companies developing real-time systems today have today no means for response time analysis, as their systems violate the assumptions of traditional analytical methods for response-time analysis and are too complex for exhaustive analysis using model checking.

This paper presents a novel approach for best effort response time analysis targeting such systems, where probabilistic simulation is guided by a search algorithm of metaheuristic type, similar to genetic algorithms.

The best effort approach means that the result is not guaranteed to be the worst-case response time, but also that the method scales to large industrial systems.

The proposed method should be regarded as a form of testing, focusing on timing properties.

An evaluation is presented which indicates that the proposed approach is significantly more efficient than traditional probabilistic simulation in finding extreme task response times. The paper also presents a method for finding good parameters for the search algorithm, in order to improve its efficiency.

Place, publisher, year, edition, pages
2008. p. 258-269
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-7110DOI: 10.1109/RTAS.2008.25ISI: 000257883200024Scopus ID: 2-s2.0-51249095448ISBN: 978-0-7695-3146-5 (print)OAI: oai:DiVA.org:mdh-7110DiVA, id: diva2:237120
Conference
14th IEEE Real-Time and Embedded Technology and Applications Symposium Location: St Louis, MO Date: APR 22-24, 2008
Available from: 2009-09-25 Created: 2009-09-25 Last updated: 2013-12-03Bibliographically approved
In thesis
1. Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems
Open this publication in new window or tab >>Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems
2010 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

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., 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 novel statistical approach to WCRT analysis of CRTES. The proposed algorithm combines Extreme Value Theory (EVT) 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 in systems, especially in the case where conventional timing analysis methods cannot be applied.

The second contribution is to introduce a concrete process of formally obtaining the exact value of both Worst-Case Execution Time (WCET) and WCRT of tasks in the system model 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 to apply an optimization algorithm, in this case a meta-heuristic search algorithm, on top of the traditional Monte Carlo simula-tion, which yields 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.

Place, publisher, year, edition, pages
Västerås: Mälardalen University, 2010
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 122
National Category
Computer Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-10318 (URN)978-91-86135-83-6 (ISBN)
Presentation
2010-10-01, Gamma, Västerås, 10:15 (English)
Opponent
Supervisors
Available from: 2010-09-21 Created: 2010-09-20 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Lu, YueNorström, Christer

Search in DiVA

By author/editor
Kraft, JohanLu, YueNorström, ChristerWall, Anders
By organisation
School of Innovation, Design and Engineering
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 49 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf