You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact webmaster@ide.mdh.se

A Modular Tool Architecture for Worst-Case Execution Time Analysis

Fulltext:


Note:

Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3502 Series: Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1104-2516 ; 45 Pages: 200 ISBN: 91-554-5671-5

Research group:


Publication Type:

Doctoral Thesis

Publisher:

Uppsala University: Acta Universitatis Upsaliensis


Abstract

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.

Bibtex

@phdthesis{Ermedahl414,
author = {Andreas Ermedahl},
title = {A Modular Tool Architecture for Worst-Case Execution Time Analysis},
note = {Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-3502 Series: Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1104-2516 ; 45 Pages: 200 ISBN: 91-554-5671-5},
month = {June},
year = {2003},
school = {Uppsala University: Acta Universitatis Upsaliensis},
url = {http://www.es.mdh.se/publications/414-}
}