Bachelor and Master Theses

Title: Using Iterative Simulation for Timing Analysis of Complex Real-Time Systems
Subject: Computer Science
Level: Advanced
Description: Many real-time systems existing in industry today can not be analyzed using existing analytical methods for response-time analysis, like rate monotonic analysis, or by using formal methods like model checking, since the models would be too complex for an exhaustive analysis.
We are therefore interrested in simulation-based analysis of real-time systems. The properties of interrest are timing properties, such as task response time, and utilization of logical resources, such as fixed size queues.
Simulation gives a good estimation of the system's typical behavior, but since not all behaviors of a model are explored (only a random subset), there is no way of knowing if the "worst case" of a model has been found, or if even more extreme behaviors are possible than the ones observed in the simulation.
Therefore, it would be of great value with a form of simulation that could do better than random simulation, but without having to search all possible behaviors of the model.

This thesis is therefore about investigating an improved simulation-based analysis technique, where simulation is used in an iterative manner:

1) Perform a large set of (random) simulations of the model
2) Select a fraction of these simulations with the most extreme values for some property, e.g. the 1 % with highest response time for task X.
3) In each selected simulation, use the state of the simulation at some appropriate points in time before the observed “extreme case” as starting states of new random simulation. This way the new simulations will explore similar behaviors which might lead to even more extreme cases.
4) Run new simulations of the model, from the selected starting states (i.e. back to step 1)
This process is repeated until an extreme case is found that is not surpassed in the next iteration of the process.

The thesis includes the following activities:

* A major literature study on real-time systems and simulation techniques for timing analysis of real-time systems, any existing works similar to the suggested iterative analysis method is especially of importance.

• Develop the details of the suggested technique, identify the important questions and propose solutions.

This thesis project is on 20 points, D-level (i.e. Masters’/Magister) and suitable for 2 persons.
Prel. end date: 2007-01-11
Presentation date: 2007-01-11
Student: Mohsin Qasim mqm05001@student.mdh.se
IDT supervisor: Johan Kraft
johan.kraft@mdh.se, 073-3196971
Examinator: Christer Norstrm
Christer Norstrm
christer.norstrom@sics.se, +46-21-101464

Rapport och bilagor

Size

Senaste uppdatering

TR0497.pdf

232880

2006-12-28, 21:32


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