Logotype Mälardalenn University
This web site has been moved.
Please visit our new and improved web site at: http://www.es.mdh.se/
Startpage www.mdh.se

PROGRESS research projects

PG-CBD-StatA – Static Timing Analysis of Component-Based Systems

Leader: Björn Lisper
Members: Björn Lisper, Stefan Bygde
Former: Andreas Ermedahl, Marcelo Santos, Adam Betts, Amine Marref
Research group:Programming Languages
Status: finished , start date: 2006-10-01 , End date: 2010-12-31
Funding: SSF, Progress



The goal of this project is to develop theory and methods for timing analysis, especially WCET analysis, of component-based systems. Timing properties are important in real-time systems, and any component technology for software development of such systems must have some means to estimate the timing behaviour. Depending on the kind of real-time constraints, either approximate or absolute upper bounds for the execution time are needed.

Timing analysis of component-based systems naturally divides into two distinct parts: intra-component analysis, and inter-component analysis. The first part concerns possible execution times of tasks executing code fully contained within a component, and the second part concerns tasks which execute code from different components. We will study both parts, in two subprojects.

Components are typically designed to be reusable. Thus, they are likely to exhibit a highly parameterized timing behaviour, where execution time bounds depend heavily on input parameters to the component. In the first subproject, we will therefore develop methods for parametric timing analysis where the execution time bounds are expressed as a formula in some parameters rather than a single number.

When components are composed into systems, it may well happen that the code of some components is not available: they may, for instance be commercial components where license agreements forbid reverse-engineering of the code. However, the vendor may have analyzed the component before shipping it, and may have shipped also the analysis results. A composable analysis could then take the analysis results for individual components, and produce inter-component execution time bounds. Thus, the second, inter-component analysis subproject will focus on the issue of ai>composability of timing analysis.


Latest project publications [ Show all publications ]

Sequential Composition of Execution Time Distributions by Convolution, Marcelo Santos (former), Björn Lisper, George Lima (external), Veronica Lima (external), Proc. 4th Workshop on Compositional Theory and Technology for Real‐Time Embedded Systems (CRTS 2011), p 30-37, Vienna, Austria, Editor(s):Robert Davis and Linh Thi Xuan Phan, November, 2011

Fully-Automatic Derivation of Exact Program-Flow Constraints for a Tighter Worst-Case Execution-Time Analysis, Amine Marref (former), Proceedings of the 11th IEEE International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XI), IEEE, Samos, Greece, July, 2011

Deriving WCET Bounds by Abstract Execution, Andreas Ermedahl (former), Jan Gustafsson, Björn Lisper, Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011), Austrian Computer Society (OCG), Porto, Portugal, Editor(s):Chris Healy, July, 2011


Results achieved

  • Methods to do advanced program flow analysis in order to automate WCET analysis. Implementation in our research prototype WCET analysis tool SWEET.
  • A method to perform parametric WCET analysis + prototype implementation. Such methods are interesting for analysing reusable components in isolation.
  • Results on composability of timing models, especially the influence of hardware features on the composability.
  • A compositional WCET analysis, based on constraint logic programming, which takes dependencies between components into regard.
  • A method for source-level WCET estimation that can be used in to pinpoint potential timing problems in early stages of system design.
  • A method for approximate hydrid WCET analysis that is entirely trace-based, and thus suitable for analyzing third-party components where the code is protected by IPR.

Future work

Techniques to refine the parametric WCET analysis are being pursued in the APARTS project.

  • Mälardalen University |
  • Box 883 |
  • 721 23 Västerås/Eskilstuna |
  • 021-101300, 016-153600 |
  • webmaster |
  • Latest update: 2013.02.25