Pruning Infeasible Paths for Tight WCRT Analysis of Synchronous Programs

Sidharta Andalam (1) , Partha Roop (1) , Alain Girault (2)

1 ECE - Department of Electrical and Computer Engineering [Auckland ]
2 POP ART - Programming languages, Operating Systems, Parallelism, and Aspects for Real-Time

Synchronous programs execute in discrete instants, called ticks. For real-time implementations, it is important to statically determine the worst case tick length, also known as the worst case reaction time (WCRT). While there is a considerable body of work on the timing analysis of procedural programs, such analysis for synchronous programs has received less attention. Current state-of-the art analyses for synchronous programs use integer linear programming (ILP) combined with path pruning techniques to achieve tight results. These approaches first convert a concurrent synchronous program into a sequential program. ILP constraints are then derived from this sequential program to compute the longest tick length. In this paper, we use an alternative approach based on model checking. Unlike conventional programs, synchronous programs are concurrent and state-space oriented, making them ideal for model checking based analysis. We propose an analysis of the abstracted state-space of the program, which is combined with expressive data-flow information, to facilitate effective path pruning. We demonstrate through extensive experimentation that the proposed approach is both scalable and about 67% tighter compared to the existing approaches.

Domaines: Systèmes embarqués

Sidharta Andalam, Partha Roop, Alain Girault. Pruning Infeasible Paths for Tight WCRT Analysis of Synchronous Programs. DATE, Mar 2011, Grenoble, France. ⟨inria-00603287⟩