Measurement Techniques in a Hybrid Approach for Deriving Tight Execution-time

A hybrid approach to deriving tight execution-time bounds of program segments was proposed very re-cently. This approach symbiotically combines analytical and measurement-based methods to find a tight execution-time bound falling between the maximum measured execu-tion time and an analytically derived loose bound. It also enables the estimation of the probability of the derived tight bound not being exceeded at run time. This paper provides a refined description of the hybrid approach and presents techniques for measuring the execu-tion times of acyclic-path segments (APSs), which are pos-sible execution sequences of instructions that contain no cy-cles and the basic units of analysis in the hybrid approach. In this paper, we also report the results of the hybrid ap-proach in the derivation of tight execution-time bounds of three algorithms frequently used in the evaluation of WCET analysis techniques.