PROGRESS publications
|
Best-Effort Simulation-Based Timing Analysis using Hill-Climbing with Random Restarts |
||||||
|
||||||
|
Abstract Today, many companies developing real-time systems have no means for accurate timing analysis, as the soft- ware violates the assumptions of traditional analytical methods for response-time analysis, and are too complex for exhaustive analysis using e.g. model checking. This paper presents an efficient best-effort approach for timing analysis targeting such systems, where simulations of a detailed system model are controlled by a simple yet novel optimization algorithm, based on hill climbing with ran- dom restarts (HCRR). Using a simulation-based approach implies that the result is not guaranteed to be the worst- case response time, but on the other hand, the method can handle in principle any software design. Unlike previous approaches, the new algorithm directly manipulates sim- ulation parameters such as execution times, arrival jitter and input stimulus. A thorough evaluation is also presented, where HCRR is compared to Monte Carlo simulation (the current state- of-practice) and a previously proposed method. The eval- uation is performed using a set of simulation models con- structed from existing systems in the robotics and vehicular domain, and shows that for the three models investigated, the proposed method was 4-11% more accurate and vastly more efficient than the other methods. In our evaluation, HCRR found the second-best result on average 42 times faster than the second-best method. For the largest model, HCRR used only 7.6 % of the simulations needed by the second-best method to reach the same result, implying that HCRR scales to larger systems. For the most realistic model, our new method found the highest-known response time 1 628 times faster than the second-best method. |
||||||
|
BibTeX entry @techreport{Bohlin_1665:2009, |
- Mälardalen University |
- Box 883 |
- 721 23 Västerås/Eskilstuna |
- 021-101300, 016-153600 |
- webmaster |
- Latest update: 2009.11.03