Change search
ReferencesLink to record
Permanent link

Direct link
Parametric WCET Analysis
Mälardalen University, School of Innovation, Design and Engineering. (Programming Languages)ORCID iD: 0000-0001-9341-4031
2013 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In a real-time system, it is crucial to ensure that all tasks of the system hold their deadlines. A missed deadline in a real-time system means that the system has not been able to function correctly. If the system is safety critical, this could potentially lead to disaster. To ensure that all tasks keep their deadlines, the Worst-Case Execution Time (WCET) of these tasks has to be known.

Static analysis analyses a safe model of the hardware together with the source or object code of a program to derive an estimate of the WCET. This estimate is guaranteed to be equal to or greater than the real WCET. This is done by making calculations which in all steps make sure that the time is exactly or conservatively estimated. In many cases, however, the execution time of a task or a program is highly dependent on the given input. Thus, the estimated worst case may correspond to some input or configuration which is rarely (or never) used in practice. For such systems, where execution time is highly input dependent, a more accurate timing analysis which take input into consideration is desired.

In this thesis we present a method based on abstract interpretation and counting of semantic states of a program that gives a WCET in terms of some input to the program. This means that the WCET is expressed as a formula of the input rather than a constant. This means that once the input is known, the actual WCET may be more accurate than the absolute and global WCET. Our research also investigate how this analysis can be safe when arithmetic operations causes integers to wrap-around, where the common assumption in static analysis is that variables can take the value of any integer. Our method has been implemented as a prototype and as a part of a static WCET analysis tool in order to get experience with the method and to evaluate the different aspects. Our method shows that it is possible to obtain very complex and detailed information about the timing of a program, given its input.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2013. , 167 p.
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 138
Keyword [en]
WCET Analysis, parametric WCET Analysis, WCET, Timing
National Category
Computer Science
Research subject
Computer Science
URN: urn:nbn:se:mdh:diva-18770ISBN: 978-91-7485-109-0OAI: diva2:618332
Public defence
2013-06-04, Delta, Mälardalens högskola, Västerås, 13:00 (English)
Available from: 2013-04-29 Created: 2013-04-26 Last updated: 2013-12-03Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Bygde, Stefan
By organisation
School of Innovation, Design and Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 418 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: 570 hits
ReferencesLink to record
Permanent link

Direct link