Bachelor and Master Theses

Title: Master Thesis - Constraint Programming Techniques in WCET Analysis
Subject: Computer Science
Level: Advanced
Description: This thesis project will be done as a collaboration between the Programming Languages research group at IDT/MDH, and Swedish Institute of Computer Science (SICS).

Worst-Case Execution Time (WCET) analysis estimates the worst-case running time of a program running on a certain hardware. For hard real-time systems it is important that the estimate is safe, i.e., that it never underestimates the real WCET. WCET analysis methods typically first compute the possible program flows, then the execution times for small program fragments, and finally this information is used to calculate a WCET estimate. Usually, the calculation is done by solved a Integer Linear Programming (ILP) maximization problem.

The Programming Languages group does research in WCET analysis. They have developed a prototype WCET analysis tool SWEET (SWEdish Execution Time tool).

Constraint programming refers to a collection of techniques to solve search or optimization problems with constraints. These techniques often have a more heuristic nature than stringent optimization techniques such as ILP, and will then find a solution that is "good enough" without necessarily being optimal. On the other hand it is more qeneral, and allows for a greater freedom in selecting constraints.

The Industrial Applications and Methods Lab at SICS have expertise in constraint programming and its applications. They also have good knowledge of other optimization tools, like for instance ILP solvers.

The aim of this thesis project is to investigate how current WCET analysis techniques can be improved by using constraint programming techniques and/or better tools for ILP. The project has the following main parts:

1. An ILP problem has a number of linear constraints. Many of these constraints are often redundant, that is: they provide no extra information, and can therefore be dropped when solving the problem. Dropping redundant constraints can speed up the ILP solution process considerably. A constraint solver can be used to detect when linear constraints are redundant. In this part of the project, a constraint solver will be integrated as a "filter" in SWEET to remove redundant constraints before making the final calculation using an ILP solver.

2. The current version of SWEET uses the public domain ILP solver lp_solve, However, there are a number of public domain ILP solvers available. In this part of the project, an investigation will be made which of the available solvers actually is the best to use in SWEET, with respect to such aspects as solution time, flexibility, etc.
Company: SICS, kontaktperson: Per Kreuger
Proposed: 2008-12-19
Prerequisites: Prerequisites: besides basic knowledge in computer science, programming, and mathematics, the project requires some knowledge in optimization theory (preferrably linear programming, or combinatorial optimization). It is also desirable, although not absolutely necessary, to have knowledge of compiler theory since some of the work may require that translations between different formats are implemented.
IDT supervisor: Björn Lisper
bjorn.lisper@mdh.se, +46-21-151709

Rapport och bilagor

Size

Senaste uppdatering


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