Game-Theoretic Timing Analysis

Sanjit A. Seshia and Alexander Rakhlin. Game-Theoretic Timing Analysis. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 575–582, IEEE Press, November 2008.

Download

[HTML] 

Abstract

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 paper, we present a new, game-theoretic approach to estimating WCET based on performing directed 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. We present both theoretical and experimental results demonstrating 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.

BibTeX

@InProceedings{seshia-iccad08,
  author = 	 {Sanjit A. Seshia and Alexander Rakhlin},
  title = 	 {Game-Theoretic Timing Analysis},
  booktitle = 	 {Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD)},
  pages = 	 {575--582},
  month = {November},
  year = 	 {2008},
  publisher = {IEEE Press},
  abstract = {
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 paper, we present a new, game-theoretic approach to estimating WCET based on performing directed 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. We present both theoretical and experimental results demonstrating 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. 
  },
}

Generated by bib2html.pl (written by Patrick Riley ) on Thu Aug 26, 2010 14:53:27