Computing Execution Times With Execution Decision Diagrams in the Presence of Out-of-Order Resources

作     者：Bai, Zhenyu Casse, Hugues Carle, Thomas Rochange, Christine 

作者机构：Univ Toulouse IRIT CNRS Toulouse INPUT3 F-31062 Toulouse France 

出 版 物：《IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS》 (IEEE Trans Comput Aided Des Integr Circuits Syst)

年 卷 期：2023年第42卷第11期

页      面：3665-3678页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Pipeline real time static analysis worst-case execution time (WCET) 

摘      要：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 (Reineke et al., 2006). 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 (Bai et al., 2020) which is able to track precisely all pipeline states all along the execution paths of the analyzed 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.