Computing Execution Times with eXecution Decision Diagrams in the Presence of Out-Of-Order Resources

Zhenyu Bai (1, 2) , Hugues Cassé (1, 2, 3) , Thomas Carle (1, 2) , Christine Rochange (1, 2)

1 IRIT-TRACES - Groupe de Recherche en Architecture et Compilation pour les systèmes embarqués
2 UT3 - Université Toulouse III - Paul Sabatier
3 IRIT - Institut de recherche en informatique de Toulouse

We propose a precise and efficient pipeline analysis to tackle the problem of out-of-order resources in modern embedded microprocessors for the computation of the Worst-Case Execution Time (WCET). Such resources are prone to timing anomalies [1]. To remain sound, the timing analysis must either rely on huge timing over-estimations or consider all possible pipeline states which usually leads to a combinatorial blowup. To cope with this situation, we build an efficient computational model by leveraging the algebraic properties of the eXecution Decision Diagram [2] which is able to track precisely all pipeline states all along the execution paths of the analysed program while keeping the analysis time within acceptable range. We show how to apply this analysis at the Control Flow Graph (CFG) level, and how to account for a typical out-of-order resource: the shared memory bus between the instruction and data caches. We observe a gain in precision of the WCET ranging from 20% to 80% compared to the state-of-the-art pipeline analysis of the OTAWA WCET toolset. The analysis time shows that our approach scales to realistic benchmarks, making it appropriate for industrial applications.

Mots clés: real-time; WCET; static analysis; pipeline

Domaines: Informatique [cs]

Zhenyu Bai, Hugues Cassé, Thomas Carle, Christine Rochange. Computing Execution Times with eXecution Decision Diagrams in the Presence of Out-Of-Order Resources. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42 (11), pp.3665-3678. ⟨10.1109/TCAD.2023.3258752⟩. ⟨hal-04069420⟩