Bachelor and Master Theses

Title: Evaluation of a method for identifying timing models
Subject: Computer Science
Level: Advanced
Description: The Programming Languages research group at MDH has developed a method to identify timing models for source code. Such a model is valid for a certain combination of compiler and target hardware. The method uses a test suite of programs that are compiled and run on the target hardware. The execution time is measured for the different runs, and a linear cost model for the source code is then fit as to minimize the deviation of execution times predicted by the model from the real execution times. The cost model can then be used to predict the execution times for programs that are not yet compiled. In particular, the model can be used to make rough estimation of the Best- and Worst-Case Execution Times (BCET/WCET) of programs.

The model fitting can be done in different ways, including linear regression (the "Least-Squares" method), and Simulated Annealing.

The purpose of this project is to evaluate this method to build timing models, by evaluating the accuracy of the resulting timing models for a number of combinations of hardware architecure, and compiler with different levels of optimization. The models will be built using predefined suites of test programs, using both the Least-Squares method and some variations of Simulated Annealing. To ease the task of measuring execution times, the hardware simulator SimpleScalar will be used as target hardware rather than real hardware. SimpleScalar can be configured to simulate a variety of processor architectures, and a version of gcc exists that compiles C code to the SimpleScalar instruction set. This version of gcc allows to use a number of different optimization levels.

The timing models will be used in the WCET analysis tool SWEET to make an estimation of of the BCET and WCET for a number of benchmark C programs, assuming predefined ranges of possible input values. The accuracy of the resulting BCET/WCET estimates, and thus of the timing models, will be assessed by actually running the compiled benchmark problems on the SimpleScalar simulator for all possible combinations of imput values in the prescribed ranges.

This is a plan for the project:

1. Learn how to use SimpleScalar, linux, unix/linux scripts, SWEET, experimental toolset for identifying timing models, some very basics about underlying theory (linear regression, genetic algorithms, ...)

2. Set up the experimental environment on a linux system

3. select a number of combinations of SimpleScalar processor configurations, and compiler optimization settings

4. For each combination:

- identify timing models, using the different variations of model fitting
- For the best timing model, and each selected benchmark program:
- make a BCET/WCET estimation using the timing model with SWEET
- run SimpleScalar for each possible combination of input values, and record "real" BCET/WCET
- compare estimated and "real" BCET/WCET

5. Document the results, finish the report, present the project
Company: MDH/IDT, kontaktperson: Björn Lisper
Prel. end date: 2011-06-16
Presentation date: 2012-06-14
Student: Lidia Tesfazghi Kahsu
IDT supervisor: Björn Lisper, +46-21-151709

Rapport och bilagor


Senaste uppdatering



2012-08-06, 23:00

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