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
Approximation Techniques for Timing 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
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: urn:nbn:se:mdh:diva-10318ISBN: 978-91-86135-83-6 (print)OAI: oai:DiVA.org:mdh-10318DiVA, id: diva2:352398
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
List of papers
1. Statistical-based Response-Time Analysis of Systems with Execution Dependencies between Tasks
Open this publication in new window or tab >>Statistical-based Response-Time Analysis of Systems with Execution Dependencies between Tasks
2009 (English)In: Proceedings of the Work-In-Progress (WIP) track of the 30th IEEE Real-Time Systems Symposium (RTSS'09), Washington, DC, USA, 2009, p. 73-76Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Washington, DC, USA: , 2009
Identifiers
urn:nbn:se:mdh:diva-9102 (URN)
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2013-12-03Bibliographically approved
2. A Statistical Approach to Response-Time Analysis of Complex Real-Time Embedded Systems
Open this publication in new window or tab >>A Statistical Approach to Response-Time Analysis of Complex Real-Time Embedded Systems
2010 (English)In: Proceedings of the 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2010), 2010, p. 153-160Conference 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.

Research subject
Computer Science; Computer Science
Identifiers
urn:nbn:se:mdh:diva-10323 (URN)
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
3. Timing Analyzing for Systems with Execution Dependencies between Tasks
Open this publication in new window or tab >>Timing Analyzing for Systems with Execution Dependencies between Tasks
2010 (English)In: Proceedings of the ACM Symposium on Applied Computing 201, 2010, p. 357-358Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, a novel approach to timing analysis of complex real-time systems with intricate execution dependencies between tasks, such as asynchronous message-passing and globally shared state variables, is presented. By applying the method to a model taken from a real robotic control system, we show the benefit, in terms of reduced pessimism, when compared to a combination of standard static WCET analysis and Response-Time Analysis.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-9097 (URN)10.1145/1774088.1774164 (DOI)2-s2.0-77954717654 (Scopus ID)978-160558638-0 (ISBN)
Conference
25th Annual ACM Symposium on Applied Computing, SAC 2010; Sierre; Switzerland; 22 March 2010 through 26 March 2010
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2013-12-19Bibliographically approved
4. A Metaheuristic Approach for Best Effort Timing Analysis targeting Complex Legacy Real-Time Systems
Open this publication in new window or tab >>A Metaheuristic Approach for Best Effort Timing Analysis targeting Complex Legacy Real-Time Systems
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.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-7110 (URN)10.1109/RTAS.2008.25 (DOI)000257883200024 ()2-s2.0-51249095448 (Scopus ID)978-0-7695-3146-5 (ISBN)
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
5. Simulation-Based Timing Analysis of Complex Real-Time Systems
Open this publication in new window or tab >>Simulation-Based Timing Analysis of Complex Real-Time Systems
Show others...
2009 (English)In: 2009 15TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS, 2009, p. 321-328Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents an efficient best-effort approach for simulation-based timing analysis of complex real- time systems. The method can handle in principle any software design that can be simulated, and is based on controlling simulation input using a simple yet novel hill- climbing algorithm. Unlike previous approaches, the new algorithm directly manipulates simulation parameters such as execution times, arrival jitter and input. An evaluation is presented using six different simulation models, and two other simulation methods as reference: Monte Carlo simulation and MABERA. The new method proposed in this paper was 4-11% more accurate while at the same time 42 times faster, on average, than the reference methods.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-9021 (URN)10.1109/RTCSA.2009.41 (DOI)000276774500036 ()2-s2.0-72349094831 (Scopus ID)978-0-7695-3787-0 (ISBN)
Conference
15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications Location: Beijing, PEOPLES R CHINA Date: AUG 24-26, 2009
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2013-12-03Bibliographically approved

Open Access in DiVA

fulltext(1466 kB)1165 downloads
File information
File name FULLTEXT02.pdfFile size 1466 kBChecksum SHA-512
cf027ae3f210f4571a05e5f745e91e8b646d3aac8311d4418bf4431ed1a224be263a005f1010a34cb965154d3b722d1be577b86c0bd49edf67232ac1a4b21f5e
Type fulltextMimetype application/pdf

Authority records BETA

Lu, Yue

Search in DiVA

By author/editor
Lu, Yue
By organisation
School of Innovation, Design and Engineering
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 1165 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 319 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