Logotype Mälardalenn University

MRTC research projects



Worst-Case Execution Time Analysis of Parallel Systems

Leader: Björn Lisper
Members: Björn Lisper, Andreas Gustavsson, Jan Gustafsson
Research group:Programming Languages
Status: finished , start date: 2009-01-01 , End date: 2011-12-31
Funding: VR

 

Overview

Worst-Case Execution Time (WCET) analysis finds safe upper bounds for the execution time of code fragments. Reliable WCET estimates are essential in the development of safety-critical hard real-time systems, where failures to meet deadlines can have catastrophic consequences.

This project targets WCET analysis of parallel systems. Compared to WCET analysis of sequential processors, research in WCET analysis for parallel systems is almost non-existent. In the light of the current hardware revolution, where multicore processors rapidly are becoming standard, this is a glaring omission. In a few years also hard real-time applications will run on multicores, and then current WCET analysis methods and tools will become obsolete. The goal of the project is to find suitable models and methods for WCET analysis of parallel systems, mainly multicore and MPSoC’s. The emphasis is on basic models taking parallelism into account, mainly for flow analysis and calculation. We aim to produce seminal results of the same dignity as the original works on timing schemas and IPET for sequential programs.

 

Latest project publications [ Show all publications ]


Practical experiences of applying source-level WCET flow analysis to industrial code, Björn Lisper, Andreas Ermedahl (former), Dietmar Schreiner (external), Peter Gliwa (external), Jens Knoop (external), International Journal on Software Tools for Technology Transfer, vol 15, nr 1, p53-63, Springer, February, 2013

Toward Static Timing Analysis of Parallel Software, Andreas Gustavsson, Jan Gustafsson, Björn Lisper, 12th International Workshop on Worst-Case Execution-Time Analysis, p 38-47, Schloss Dagstuhl, Pisa, Italy, Editor(s):Tullio Vardanega, July, 2012

Toward Static Timing Analysis of Parallel Software - Technical Report, Andreas Gustavsson, Jan Gustafsson, Björn Lisper, Technical Report, MRTC, April, 2012
 

Results achieved

We have developed an algorithm for WCET analysis of parallel threads with global shared memory, synchronizing via locks. The algorithm is an extension of our abstract execution algorithm for flow analysis, which has been augmented to keep track of timing information as well as to handle concurrent threads. Abstract execution is based on abstract interpretation, and the algorithm is based on an abstract domain for which we have proved that there is a Galois connection to the underlying, concrete domain describing the possible behaviours of the concurrent threads. This ensures that the algorithm is safe, and thus never will underestimate the WCET.
 

Future work

We will continue to investigate WCET analysis for parallel software in the RALF3 project, where we plan to focus on software for GPUs.


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