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 Modular Tool Architecture for Worst-Case Execution Time Analysis
Mälardalen University, Department of Computer Science and Electronics.
2003 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

Estimations of the Worst-Case Execution Time (WCET) are required in providing guarantees for timing of programs used in computer controlled products and other real-time computer systems. To derive program WCET estimates, both the properties of the software and the hardware must be considered. The traditional method to obtain WCET estimates is to test the system and measure the execution time. This is labour-intensive and error-prone work, which unfortunately cannot guarantee that the worst case is actually found. Static WCET analyses, on the other hand, are capable of generating safe WCET estimates without actually running the program. Such analyses use models of program flow and hardware timing to generate WCET estimates. This thesis includes several contributions to the state-of-the-art in static WCET analysis: (1) A tool architecture for static WCET analysis, which divides the WCET analysis into several steps, each with well-defined interfaces. This allows independent replacement of the modules implementing the different steps, which makes it easy to customize a WCET tool for particular target hardware and analysis needs. (2) A representation for the possible executions of a program. Compared to previous approaches, our representation extends the type of program flow information possible to express and handle in WCET analysis. (3) A calculation method which explicitly extracts a longest program execution path. The method is more efficient than previously presented path-based methods, with a computational complexity close to linear in the size of the program. (4) A calculation method using integer linear programming or constraint programming techniques for calculating the WCET estimate. The method extends the power of such calculation methods to handle new types of flow and timing information. (5) A calculation method that first uses flow information to divide the program into smaller parts, then calculates individual WCET estimates for these parts, and finally combines these into an overall program WCET. This novel approach avoids potential complexity problems, while still providing high precision WCET estimates. We have additionally implemented a prototype WCET analysis tool based on the proposed architecture. This tool is used for extensive evaluation of the precision and performance of our proposed methods. The results indicate that it is possible to perform WCET analysis in a modular fashion, and that this analysis produces high quality WCET estimates.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 2003. , p. 200
Series
Uppsala dissertations from the Faculty of Science and Technology, ISSN 1104-2516 ; 45
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-2089ISBN: 91-554-5671-5 (print)OAI: oai:DiVA.org:mdh-2089DiVA, id: diva2:114752
Note

Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3502 

Available from: 2008-11-11 Created: 2008-11-11 Last updated: 2013-02-18Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3502

Search in DiVA

By author/editor
Ermedahl, Andreas
By organisation
Department of Computer Science and Electronics
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

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