Hide/Show Apps

Hybrid probabilistic timing analysis with extreme value theory and copulas

Bekdemir, Levent.
The primary challenge of time-critical systems is to ensure that a task completes its execution before its deadline. In order to ensure that the underlying system comply with stringent timing requirements, designers ought to analyze the timing behavior of the software and its sub-components. Worst-Case Execution Time (WCET) represents the maximum length of time an individual software unit takes to execute and is the most essential value for schedulability analysis in safety-critical systems. Recent studies focus on statistical approaches which augments measurement-based timing analysis with probabilistic confidence level by applying stochastic methods. Common approaches either utilize Extreme Value Theory(EVT) for end-to-end measurements or convolution techniques for a group of program units to derive absolute upper distributional bound of the whole program. The former method lacks insurance of path coverage while the latter one suffers from ignoring possible extreme cases of program units. Furthermore, current state-of-the-art convolution method that is being implemented by a commercial WCET analysis tool overestimates the results under the assumption of worst dependence between the basic blocks. In this thesis, we propose a hybrid probabilistic timing analysis framework based on modeling the program units with EVT to capture extreme cases and Copulas to model the dependency between the units to derive tighter distributional bounds to mitigate the effects of comonotonic assumptions. The proposed framework also offers a way to minimize the instrumentation probe effects which is essential to obtain fine grained execution time traces on COTS platforms.