ILP_c: a novel approach for scalable timing analysis of synchronous programs

Synchronous programs have been widely used in the design of safety critical systems such as the flight control of Airbus A-380. To validate the implementations of synchronous programs, it is necessary to map the program's logical time (measured in logical ticks) to physical time (the execution time on a given processor). The static computation of the worst-case execution time of logical ticks is called Worst Case Reaction Time (WCRT) analysis. Several approaches for WCRT analysis exist: max-plus algebra, model checking, reachability and integer linear programming (ILP). Of these approaches, reachability, model checking and ILP provide reasonably precise worst case estimates at the expense of longer analysis time. Apart from max-plus based approaches, which can produce large overestimates, the existing approaches suffer from the state space explosion problem. In this paper, we develop a new ILP based approach, called ILP_c, which exploits the concurrency explicitly in the ILP formulation to avoid the state space explosion problem. Through extensive benchmarking we demonstrate the efficacy of the approach: for complex programs, ILP_c is often orders of magnitude faster compared to the existing approaches, while achieving same level of precision. Thus, this paper paves the way for scalable WCRT analysis of complex embedded systems designed using the synchronous approach.