Improving the Performance of WCET Analysis in the Presence of Variable Latencies

Due to the dynamic behaviour of acceleration mechanisms such as caches and branch predictors, static Worst-Case Execution Time (WCET) analysis methods tend to scale poorly to modern hardware architectures. As a result, a tradeoff must be made between the duration and the precision of the analysis, leading to an overestimation of the WCET bounds. This in turn reduces the schedulability and resource usage of the system. In this talk, we present a new data structure to speed up the analysis: the eXecution Decision Diagram (XDD), which is an ad-hoc extension of Binary Decision Diagrams tailored for WCET analysis problems. We show how XDDs can be used to efficiently represent execution states and durations of instruction sequences on a modern hardware platform. We demonstrate in realistic applications how the use of an XDD substantially increases the scalability of WCET analysis.

Zhenyu Bai is a Doctoral Student in the TRACES team at University of Toulouse, France, where he also received his master’s degree. Currently, he is working on the OTAWA analyzer for the Worst-Case Execution Time (WCET) computation of critical real-time systems. His research interests include embedded systems architecture and static program analysis.