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 Statistical Approach to Response-Time Analysis of Complex Real-Time Embedded Systems
Mälardalen University, School of Innovation, Design and Engineering. (Complex Real-Time Embedded Systems)ORCID iD: 0000-0002-7366-7186
Mälardalen University, School of Innovation, Design and Engineering. (Complex Real-Time Embedded)ORCID iD: 0000-0001-6132-7945
Mälardalen University, School of Innovation, Design and Engineering. (Complex Real-Time Embedded Systems)
SICS.ORCID iD: 0000-0003-2855-9220
2010 (English)In: Proceedings of the 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2010), 2010, 153-160 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents RapidRT, a novel statistical approach to Worst-Case Response-Time (WCRT) analysis targeting complex embedded real-time systems. The proposed algorithm combines Extreme Value Theory (EVT) and other statistical methods in order to produce a probabilistic WCRT estimate. This estimate is calculated using response time data from either Monte Carlo simulations of a detailed model of the system, or from response-time measurements of the real system. The method could be considered as a pragmatic approach intended for complex industrial systems with real-time requirements. The target systems contain tasks with many intricate dependencies in theirtemporal behavior, which violates the assumptions of traditional analytical methods for response time analysis and thereby makes them overly pessimistic. An evaluation ispresented using two simulation models, inspired by an industrial robotic control system, and five other methods as reference.

Place, publisher, year, edition, pages
2010. 153-160 p.
Research subject
Computer Science; Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-10323OAI: oai:DiVA.org:mdh-10323DiVA: diva2:352562
Conference
16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2010)
Projects
PROGRESS
Note
©2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEAvailable from: 2010-09-21 Created: 2010-09-21 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: 2013-12-03Bibliographically approved

Open Access in DiVA

fulltext(180 kB)790 downloads
File information
File name FULLTEXT01.pdfFile size 180 kBChecksum SHA-512
c2ca4a721c6074e363790945a60906f5048777c0512409ec9d123ef5efeb90e7391a492fa1bc0d0c42aad9fa6994621cf8cfc50f05216d0fd369631637eccfab
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lu, YueNolte, ThomasKraft, JohanNorström, Christer
By organisation
School of Innovation, Design and Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 790 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 84 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