Zachariah Wasson

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2014-132

May 30, 2014

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-132.pdf

Execution time analysis is central to the design and verification of real-time embedded systems. One approach to this problem is GameTime, a toolkit for timing analysis, which predicts the timing of various program paths using platform measurements of a special subset of paths. This thesis explores extensions to GameTime to handle two common sources of data-dependent timing behavior: instructions with variable timing and load/store dependencies. We present a technique for automatically learning a model of the data dependencies and encoding this model into the code under analysis for processing by GameTime. Using these extensions, we show that GameTime more accurately predicts the timing for a variety of benchmarks.

Unfortunately, the complexity of modern architectures and platforms has made it very difficult to obtain accurate and efficient timing estimates. To deal with this, there have been recent proposals to re-architect platforms to make execution time of instructions more repeatable. There is however no systematic formalization of what timing repeatability means. In this thesis, we also propose formal models of timing repeatability. We give an algorithmic approach to evaluate parameters of these formal models. Using GameTime along with the data-dependent extensions discussed in this thesis, we objectively evaluate the timing repeatability of a representative sample of platforms with respect to a program of interest.

Advisors: Sanjit A. Seshia

---

BibTeX citation:

@mastersthesis{Wasson:EECS-2014-132,
    Author= {Wasson, Zachariah},
    Title= {Analyzing Data-Dependent Timing and Timing Repeatability with GameTime},
    School= {EECS Department, University of California, Berkeley},
    Year= {2014},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-132.html},
    Number= {UCB/EECS-2014-132},
    Abstract= {Execution time analysis is central to the design and verification of real-time embedded systems. One approach to this problem is GameTime, a toolkit for timing analysis, which predicts the timing of various program paths using platform measurements of a special subset of paths. This thesis explores extensions to GameTime to handle two common sources of data-dependent timing behavior: instructions with variable timing and load/store dependencies. We present a technique for automatically learning a model of the data dependencies and encoding this model into the code under analysis for processing by GameTime. Using these extensions, we show that GameTime more accurately predicts the timing for a variety of benchmarks.

Unfortunately, the complexity of modern architectures and platforms has made it very difficult to obtain accurate and efficient timing estimates. To deal with this, there have been recent proposals to re-architect platforms to make execution time of instructions more repeatable. There is however no systematic formalization of what timing repeatability means. In this thesis, we also propose formal models of timing repeatability. We give an algorithmic approach to evaluate parameters of these formal models. Using GameTime along with the data-dependent extensions discussed in this thesis, we objectively evaluate the timing repeatability of a representative sample of platforms with respect to a program of interest.},
}

EndNote citation:

%0 Thesis
%A Wasson, Zachariah 
%T Analyzing Data-Dependent Timing and Timing Repeatability with GameTime
%I EECS Department, University of California, Berkeley
%D 2014
%8 May 30
%@ UCB/EECS-2014-132
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-132.html
%F Wasson:EECS-2014-132