Computation of WCET using Program Slicing and Real-Time Model-Checking

Details Computation of WCET using Program Slicing and Real-Time Model-Checking Computation of WCET using Program Slicing and Real-Time Model-Checking

2011-05-09

arxiv.org/abs/1105.1633v3

Computer Science

Software Engineering

31 pages. Extended with slicing and other minor changes

Scientific paper

Computing accurate WCET on modern complex architectures is a challenging task. This problem has been devoted a lot of attention in the last decade but there are still some open issues. First, the control flow graph (CFG) of a binary program is needed to compute the WCET and this CFG is built using some internal knowledge of the compiler that generated the binary code; moreover once constructed the CFG has to be manually annotated with loop bounds. Second, the algorithms to compute the WCET (combining Abstract Interpretation and Integer Linear Programming) are tailored for specific architectures: changing the architecture (e.g. replacing an ARM7 by an ARM9) requires the design of a new ad hoc algorithm. Third, the tightness of the computed results (obtained using the available tools) are not compared to actual execution times measured on the real hardware. In this paper we address the above mentioned problems. We first describe a fully automatic method to compute a CFG based solely on the binary program to analyse. Second, we describe the model of the hardware as a product of timed automata, and this model is independent from the program description. The model of a program running on a hardware is obtained by synchronizing (the automaton of) the program with the (timed automata) model of the hardware. Computing the WCET is reduced to a reachability problem on the synchronised model and solved using the model-checker UPPAAL. Finally, we present a rigorous methodology that enables us to compare our computed results to actual execution times measured on a real platform, the ARM920T.

Affiliated with

Also associated with

No associations

Rating

Computation of WCET using Program Slicing and Real-Time Model-Checking does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computation of WCET using Program Slicing and Real-Time Model-Checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computation of WCET using Program Slicing and Real-Time Model-Checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-333813