Drawing Lines for Measurement-Based Probabilistic Timing Analysis

We describe DBL-MBPTA, a new approach for measurement-based probabilistic timing analysis (MBPTA). Unlike the usual MBPTA, which treats the time a program executes as a random variable, we consider both the number n of instructions executed in each measurement and the time $T(n)$ they took to execute. By taking tuples $(n, T(n))$, for various values of n, DBL-MBPTA allows for multiple execution path analysis. We show that $(n, T(n))$ can be bounded from below and above by two reference lines. The modeled random variable is the relative distance ($n, T(n)$) from these lines, which explains the term distance between lines (DBL) given to the approach. According to DBL-MBPTA, samples can be analyzed and improved, for which we employ deep neural networks. Once sample coverage is deemed representative, probabilistic bounds on execution time are estimated via the modeled relative distance. We evaluate our approach using both synthetic data and data collected through measurements on a multi-core platform. The results obtained demonstrate the effectiveness of DBL-MBPTA.