/ Home page of Thomas Lundqvist / Research

Current and previous research

I have mainly been doing research in the area of worst-case execution time (WCET). The goal was to develop timing analysis methods for programs running in real-time systems. My Ph.D supervisor was Per Stenström.

My publications.

WCET analysis

estimated WCET should be safe and tight

Programs for real-time systems must not only deliver the correct results. They must also deliver the results within a certain deadline. This is especially true in hard real-time systems, where something bad can happen if a program does not complete in time. When designing programs for these kind of systems, it is important to be able to certify that a program completes within a given deadline. To simplify this job, timing analysis methods are needed. Such a method is responsible for analyzing a given program running on a given hardware architecture and produce an estimate of the worst-case execution time (WCET) of the program. This estimate must be safe - the actual WCET should not be underestimated - and preferably tight - the over-estimation should be small in order to better utilize the processor.

Tight estimates of the WCET are possible by using both path and timing analyses. Path analysis is responsible for eliminating infeasible (non-executable) paths in the program. Timing analysis must deliver the time of the remaining, feasible, paths in the program. Consider for example the following C program:

  k = 30;

  for (i = 0 ; i<k ; i++)
    partA;
  if (k<0)
    partB;
  partC;

In this example, the statements in partB will never be executed and the program path going through partB is an infeasible path. This path should be identified by the path analysis. Furthermore, the automatic path analysis should not only identify infeasible paths but also automatically derive the number of iterations done in all loops. In the example above, partA is run 30 times. This fact should be derived automatically by the path analysis in order to avoid manual annotation of the program before doing timing analysis.

My research focus

For the Ph.D. thesis my focus was on developing a new approach for WCET estimation based on instruction-level symbolic simulation. This is all summarized in my thesis:
My Ph.D. Thesis
A WCET Analysis Method for Pipelined Microprocessors with Cache Memories

I successfully defended my Ph.D. thesis on June 14, 2002. Opponent was Prof. David Whalley, Florida State Univ. Graduating committee: Prof. John Hughes, Prof. Lars Lundberg, and Prof. Björn Lisper.

Recently (2008), I have also looked at a measurement-based timing analysis approach described in Towards a Practical WCET Analysis Approach Based on Testing.