mdh.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Simulation-Based Timing Analysis of Complex Real-Time Systems
Mälardalens högskola, Akademin för innovation, design och teknik.ORCID-id: 0000-0003-1597-6738
Mälardalens högskola, Akademin för innovation, design och teknik.ORCID-id: 0000-0002-7366-7186
Mälardalens högskola, Akademin för innovation, design och teknik.
Mälardalens högskola, Akademin för innovation, design och teknik.
Visa övriga samt affilieringar
2009 (Engelska)Ingår i: 2009 15TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS, 2009, s. 321-328Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
2009. s. 321-328
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
URN: urn:nbn:se:mdh:diva-9021DOI: 10.1109/RTCSA.2009.41ISI: 000276774500036Scopus ID: 2-s2.0-72349094831ISBN: 978-0-7695-3787-0 (tryckt)OAI: oai:DiVA.org:mdh-9021DiVA, id: diva2:301592
Konferens
15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications Location: Beijing, PEOPLES R CHINA Date: AUG 24-26, 2009
Tillgänglig från: 2010-03-03 Skapad: 2010-03-03 Senast uppdaterad: 2013-12-03Bibliografiskt granskad
Ingår i avhandling
1. Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems
Öppna denna publikation i ny flik eller fönster >>Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems
2010 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Västerås: Mälardalen University, 2010
Serie
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 122
Nationell ämneskategori
Datorteknik
Forskningsämne
datavetenskap
Identifikatorer
urn:nbn:se:mdh:diva-10318 (URN)978-91-86135-83-6 (ISBN)
Presentation
2010-10-01, Gamma, Västerås, 10:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2010-09-21 Skapad: 2010-09-20 Senast uppdaterad: 2018-01-12Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Bohlin, MarkusLu, YueNolte, Thomas

Sök vidare i DiVA

Av författaren/redaktören
Bohlin, MarkusLu, YueKraft, JohanKreuger, PerNolte, Thomas
Av organisationen
Akademin för innovation, design och teknik
Teknik och teknologier

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 120 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf