Best-Effort Simulation-Based Timing Analysis using Hill-Climbing with Random Restarts

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.