MRTC research projects
|
Response-time Calculations with Integer Linear Programming Methods |
||||||||||||||||
| ||||||||||||||||
Overview Classical response-time analysis for real-time systems is done by iterative methods. However, these iterative methods have the potential problem that it is hard to guarantee any bounds on computation time. There are cases where the computation time can be very long, or even where the iteration diverges. A possible alternative is then to reformulate the analysis problem as an integer linear programming (ILP) problem and solve it using methods for ILP from optimization theory. In this project we investigate this approach. A particularly interesting direction is a generalization of the theory to include priority assignments. We then obtain a quadratic IP problem. This formulation can be used for optimal scheduling of distributed RT systems, providing an alternative to holistic scheduling that yields provably optimal results. |
||||||||||||||||
|
|
||||||||||||||||
Results achieved The mathematical reformulation to ILP has been done. Some preliminary experiments have been carried out. The approach has also been extended to include priority selection, and we have shown that this can be formulated as a quadratic IP problem. This formulation is also valid for scheduling of distributed real-time systems. |
||||||||||||||||
Future work The project is currently dormant. In the future we may perform some experiments, solving the quadratic IP problem for some examples of distributed real-time systems, by local search methods. The research will then be carried out in cooperation with SICS. |
||||||||||||||||
- Mälardalen University |
- Box 883 |
- 721 23 Västerås/Eskilstuna |
- 021-101300, 016-153600 |
- webmaster |
- Latest update: 2012.08.24