Game-Theoretic Timing Analysis
Sanjit A. Seshia
National Science Foundation
Estimating the worst-case execution time (WCET) of tasks is a key step in the design of reliable real-time software and systems. In this project, we have developed a new, game-theoretic approach to estimating WCET based on performing guided measurements on the target platform. We model the estimation problem as a game between our algorithm (player) and the environment of the program (adversary), where the player seeks to find the longest path through the program while the adversary sets environment parameters to thwart the player. Theoretical and experimental results demonstrate the utility of our approach. On the theoretical side, we prove that our algorithm can converge to find the longest path with high probability. Experimental results indicate that our approach is competitive with an existing technique based on static analysis and integer programming. Moreover, the approach can be easily applied to even complex hardware/software platforms.
- S. A. Seshia and A. Rakhlin, "Game-Theoretic Timing Analysis," Proc. ICCAD, 2008 (to appear).