Timing Anomalies Issue in WCET Analysis

Jiang Binze; Zhu Yixuan; Chen Xianglan; Gong Xiaohang; Gao Yinkang; Li Xi

doi:10.7544/issn1000-1239.202331014

Journal of Computer Research and Development > 2025 > Corrected proof > DOI: 10.7544/issn1000-1239.202331014 CSTR: 32373.14.issn1000-1239.202331014

Jiang Binze, Zhu Yixuan, Chen Xianglan, Gong Xiaohang, Gao Yinkang, Li Xi. Timing Anomalies Issue in WCET Analysis[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202331014

Citation:

PDF (1291 KB)

Timing Anomalies Issue in WCET Analysis

School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027
Suzhou Institute for Advanced Research, University of Science and Technology of China, Suzhou Jiangsu 215004

Funds: This work was supported by the National Natural Science Foundation of China (62102383, 61976200, 62172380) and the Natural Science Foundation of Jiangsu Province (BK20210123).

More Information

Author Bio:
Jiang Binze: born in 2000. Master candidate. His main research interest includes computer architecture

Zhu Yixuan: born in 1998. Master candidate. His main research interest includes computer architecture

Chen Xianglan: born in 1977. PhD. Her main research interest includes system software

Gong Xiaohang: born in 1999. Master candidate. His main research interest includes computer architecture

Gao Yinkang: born in 1998. PhD. His main research interest includes computer architecture

Li Xi: born in 1963. Professor. His main research interest includes computer architecture
Received Date: December 13, 2023
Revised Date: August 13, 2024
Accepted Date: September 02, 2024
Available Online: December 11, 2024

Graphical Abstract

Abstract

Abstract

Timing anomalies are counter-intuitive behaviors observed in worst-case execution time (WCET) analysis. A key aspect of these anomalies is that a locally faster execution does not necessarily lead to a reduction in the overall program execution time. Therefore, WCET analysis must examine all possible execution states conservatively to ensure the safety of the analysis results, making the process extremely challenging. On the contrary, if it can be ensured that there are no timing anomalies in the program and platform to be analyzed, the number of states and the time required for WCET analysis can be significantly reduced. Consequently, addressing timing anomalies is a critical challenge in WCET analysis. However, despite more than 20 years of research, the academic community has not reached a unified definition and consensus on the problem of timing anomalies. This article reviews various perspectives from the literature since the concept of timing anomalies was first introduced. We classify these viewpoints based on their definitions and descriptions, and evaluate their respective strengths and weaknesses. Additionally, we investigate the causes of timing anomalies and identify three main factors: scheduling strategies, cache behavior, and component interactions. Furthermore, we explore current research efforts aimed at detecting and eliminating timing anomalies, highlighting the issues and limitations of these approaches. Finally, we suggest that future research on timing anomalies should be integrated with WCET analysis methods to more effectively address these challenges.
- worst case execution time (WCET),
- processor architecture,
- timing anomaly,
- time predictable,
- real time system

FullText(HTML)

References (43)

References

[1]	Rochange C, Sainrat P. A Context-Parameterized Model for Static Analysis of Execution Times[M]. Berlin: Springer, 2009: 222−241
[2]	Puschner P, Burns A. Guest editorial: A review of worst-case execution-time analysis[J]. Real-Time Systems, 2000, 18(2): 115−128
[3]	Wilhelm R, Engblom J, Ermedahl A, et al. The worst-case execution-time problem—Overview of methods and survey of tools[J]. ACM Transactions on Embedded Computing Systems, 2008, 7(3): 1−53
[4]	Li Y T, Malik S, Wolfe A. Efficient microarchitecture modeling and path analysis for real-time software[C]//Proc of the 16th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 1995: 298−307
[5]	Healy C, Whalley D, Harmon M. Integrating the timing analysis of pipelining and instruction caching[C]//Proc of the 16th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 1995: 288−297
[6]	Lim S S, Bae Y H, Jang G T, et al. An accurate worst case timing analysis technique for RISC processors[C]//Proc of the 15th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 1994: 97−108
[7]	Lim S S, Han J H, Kim J, et al. A worst case timing analysis technique for multiple-issue machines[C]//Proc of the 19th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 1998: 334−345
[8]	Lundqvist T, Stenström P. An integrated path and timing analysis method based on cycle-level symbolic execution[J]. Real-Time Systems, 1999, 17(2): 183−207
[9]	Greger O. Worst-case execution time analysis for modern hardware architectures[C]//Proc of the 2nd ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems. New York: ACM, 1997: 47−55
[10]	Theiling H, Ferdinand C. Combining abstract interpretation and ILP for microarchitecture modelling and program path analysis [C]//Proc of the 19th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 1998: 144−153
[11]	Lundqvist T, Stenström P. Timing anomalies in dynamically scheduled microprocessors[C]//Proc of the 20th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 1999: 12−21
[12]	Reineke J, Wachter B, Thesing S, et al. A definition and classification of timing anomalies[C/OL]//Proc of the 6th Int Workshop on Worst-Case Execution Time Analysis. 2006[2023-05-19]. http://drops.dagstuhl.de/opus/volltexte/2006/671
[13]	Binder B, Asavoae M, Hedia B B, et al. Is this still normal? Putting definitions of timing anomalies to the test[C]//Proc of the 27th Int Conf on Embedded and Real-Time Computing Systems and Applications (RTCSA). Piscataway, NJ: IEEE, 2021: 139−148
[14]	Binder B, Asavoae M, Brandner F, et al. The role of causality in a formal definition of timing anomalies[C]//Proc of the 28th Int Conf on Embedded and Real-Time Computing Systems and Applications (RTCSA). Piscataway, NJ: IEEE, 2022: 91−102
[15]	Gebhard G. Timing anomalies reloaded[C/OL]//Proc of the 10th Int Workshop on Worst-Case Execution Time Analysis (WCET 2010). 2010[2023-12-01]. http://drops.dagstuhl.de/opus/volltexte/2010/2820
[16]	Cassez F, Hansen R R, Olesen M C. What is a timing anomaly? [C/OL]//Proc of the 12th Int Workshop on Worst-Case Execution Time Analysis (WCET’2012). 2012[2023-05-23]. http://drops.dagstuhl.de/opus/volltexte/2012/3552
[17]	Graham R L. Bounds for certain multiprocessing anomalies[J]. Bell System Technical Journal, 1966, 45(9): 1563−1581 doi: 10.1002/j.1538-7305.1966.tb01709.x
[18]	Wenzel I, Kirner R, Puschner P, et al. Principles of timing anomalies in superscalar processors[C]//Proc of the 5th Int Conf on Quality Software (QSIC’05). Piscataway, NJ: IEEE, 2005: 295−303
[19]	Jan M, Asavoae M, Schoeberl M, et al. Formal semantics of predictable pipelines: A comparative study[C]//Proc of the 25th Asia and South Pacific Design Automation Conf (ASP-DAC). Piscataway, NJ: IEEE, 2020: 103−108
[20]	Kirner R, Kadlec A, Puschner P. Worst-case execution time analysis for processors showing timing anomalies[R]. Wien, Austria: Institut für Technische Informatik, 2009
[21]	Hahn S, Reineke J, Wilhelm R. Towards compositionality in execution time analysis: Definition and challenges[J]. ACM SIGBED Review, 2015, 12(1): 28−36 doi: 10.1145/2752801.2752805
[22]	Wilhelm R, Grund D, Reineke J, et al. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(7): 966−978 doi: 10.1109/TCAD.2009.2013287
[23]	Schneider J. Combined Schedulability and WCET Analysis for Real-time Operating Systems[M]. Maastricht, Germany: Shaker, 2003
[24]	Berg C. PLRU cache domino effects[C/OL]//Proc of the 6th Int Workshop on Worst-Case Execution Time Analysis (WCET’06). 2006[2023-05-23]. http://drops.dagstuhl.de/opus/volltexte/2006/672
[25]	Kirner R, Kadlec A, Puschner P. Precise worst-case execution time analysis for processors with timing anomalies[C]//Proc of the 21st Euromicro Conf on Real-Time Systems. Piscataway, NJ: IEEE, 2009: 119−128
[26]	Pedersen M R, Bacci G, Larsen K G. A faster-than relation for semi- Markov decision processes[J]. Electronic Proceedings in Theoretical Computer Science, 2020, 312: 29−42
[27]	Binder B, Asavoae M, Brandner F, et al. Formal modeling and verification for amplification timing anomalies in the superscalar TriCore architecture[J]. International Journal on Software Tools for Technology Transfer, 2022, 24(3): 415−440 doi: 10.1007/s10009-022-00655-1
[28]	Lundqvist T. A WCET analysis method for pipelined microprocessors with cache memories[D]. Västra Götaland, Sweden: Chalmers University of Technology, 2002
[29]	Hahn S, Reineke J. Design and analysis of SIC: A provably timing-predictable pipelined processor core[C]//Proc of the 39th IEEE Real-Time Systems Symp (RTSS). Piscataway, NJ: IEEE, 2018: 469−481
[30]	Gruin A, Carle T, Rochange C, et al. MINOTAuR: A timing predictable RISC-V core featuring speculative execution[J]. IEEE Transactions on Computers, 2023, 72(1): 183−195 doi: 10.1109/TC.2022.3200000
[31]	Asavoae M, Hedia B B, Jan M. Formal executable models for automatic detection of timing anomalies[C/OL]//Proc of the 18th Int Workshop on Worst-Case Execution Time Analysis (WCET’2018). 2018[2023-05-29]. http://drops.dagstuhl.de/opus/volltexte/2018/9748
[32]	Thesing S. Safe and precise WCET determination by abstract interpretation of pipeline models[D]. Saarland, Germany: Saarland University, 2004
[33]	Eisinger J, Polian I, Becker B, et al. Automatic identification of timing anomalies for cycle-accurate worst-case execution time analysis[C]//Proc of the 9th IEEE Design and Diagnostics of Electronic Circuits and Systems. Piscataway, NJ: IEEE, 2006: 13−18
[34]	Biere A, Heule M, Maaren H. Handbook of Satisfiability[M]. Amsterdam: IOS Press, 2009
[35]	Binder B, Asavoae M, Brandner F, et al. Scalable detection of amplification timing anomalies for the superscalar tricore architecture[C]//Proc of the 25th Formal Methods for Industrial Critical Systems. Berlin: Springer, 2020: 151−169
[36]	Liu I, Reineke J, Lee E A. A PRET architecture supporting concurrent programs with composable timing properties[C]//Proc of the 44th Asilomar Conf on Signals, Systems and Computers. Piscataway, NJ: IEEE, 2010: 2111−2115
[37]	Schoeberl M, Abbaspour S, Akesson B, et al. T-CREST: Time predictable multi-core architecture for embedded systems[J]. Journal of Systems Architecture, 2015, 61(9): 449−471 doi: 10.1016/j.sysarc.2015.04.002
[38]	Dinechin B, Amstel D, Poulhies M, et al. Time-critical computing on a single-chip massively parallel processor[C/OL]//Proc of the 21st Design, Automation & Test in Europe Conf & Exhibition (DATE). Piscataway, NJ: IEEE, 2014[2023-10-23]. http://ieeexplore.ieee.org/document/6800311
[39]	Hahn S, Reineke J, Wilhelm R. Toward Compact Abstractions for Processor Pipelines[M]. Berlin: Springer, 2015
[40]	陈香兰,李曦,汪超,等. 实时机模型及时间语义指令集研究[J]. 计算机工程与科学,2021,43(4):571−578 doi: 10.3969/j.issn.1007-130X.2021.04.001 Chen Xianglan, Li Xi, Wang Chao, et al. Reasearch on real-time machine model and instruction set with time semantics[J]. Computer Engineering and Science, 2021, 43(4): 571−578 (in Chinese) doi: 10.3969/j.issn.1007-130X.2021.04.001
[41]	Liu I, Reineke J, Broman D, et al. A PRET microarchitecture implementation with repeatable timing and competitive performance[C]//Proc of the 30th IEEE Int Conf on Computer Design (ICCD). Piscataway, NJ: IEEE, 2012: 87−93
[42]	Zimmer M, Broman D, Shaver C, et al. FlexPRET: A processor platform for mixed-criticality systems[C]//Proc of the 19th IEEE Real-Time and Embedded Technology and Applications Symp (RTAS). Piscataway, NJ: IEEE, 2014: 101−110
[43]	汪超,陈香兰,章博,等. 一种具有时间语义的实时处理器模型[J]. 计算机研究与发展,2021,58(6):1176−1191 doi: 10.7544/issn1000-1239.2021.20210157 Wang Chao, Chen Xianglan, Zhang Bo, et al. A real-time processor model with timing semantics[J]. Journal of Computer Research and Development, 2021, 58(6): 1176−1191(in Chinese) doi: 10.7544/issn1000-1239.2021.20210157

[1]	Gong Xiaohang, Jiang Binze, Chen Xianglan, Gao Yinkang, Li Xi. Survey of Real-Time Computer System Architecture[J]. Journal of Computer Research and Development, 2023, 60(5): 1021-1036. DOI: 10.7544/issn1000-1239.202220731
[2]	Zhu Yi’an, Shi Xianchen, Yao Ye, Li Lian, Ren Pengyuan, Dong Weizhen, Li Jiayu. A WCET Analysis Method for Multi-Core Processors with Multi-Tier Coherence Protocol[J]. Journal of Computer Research and Development, 2023, 60(1): 30-42. DOI: 10.7544/issn1000-1239.202111244
[3]	Wang Chao, Chen Xianglan, Zhang Bo, Li Xi, Wang Chao, Zhou Xuehai. A Real-Time Processor Model with Timing Semantics[J]. Journal of Computer Research and Development, 2021, 58(6): 1176-1191. DOI: 10.7544/issn1000-1239.2021.20210157
[4]	Zhu Yi, Xiao Fangxiong, Zhou Hang, Zhang Guangquan. Method for Modeling and Analyzing Software Energy Consumption of Embedded Real-Time System[J]. Journal of Computer Research and Development, 2014, 51(4): 848-855.
[5]	Zhou Hang, Huang Zhiqiu, Zhu Yi, Xia Liang, Liu Linyuan. Real-Time Systems Contact Checking and Resolution Based on Time Petri Net[J]. Journal of Computer Research and Development, 2012, 49(2): 413-420.
[6]	Zhou Hang, Huang Zhiqiu, Hu Jun, Zhu Yi. Real-Time System Resource Conflict Checking Based on Time Petri Nets[J]. Journal of Computer Research and Development, 2009, 46(9): 1578-1585.
[7]	Guo Meng, Jian Fangjun, Zhang Qin, Xu Bin, Wang Zhensong, Han Chengde. FPGA-Based Real-Time Imaging System for Spaceborne SAR[J]. Journal of Computer Research and Development, 2007, 44(3).
[8]	Hu Xiao, Li Xi, and Gong Yuchang. High-Level Low-Power Synthesis of Real-Time Systems Using Time Petri Nets[J]. Journal of Computer Research and Development, 2006, 43(1): 176-184.
[9]	Li Guohui, Wang Hongya, Liu Yunsheng. Updates Dissemination in Mobile Real-Time Database Systems[J]. Journal of Computer Research and Development, 2005, 42(11): 2004-2009.
[10]	Zhu Xiangbin and Tu Shiliang. Analysis and Research of a Window-Constrained Real-Time System with Constraints[J]. Journal of Computer Research and Development, 2005, 42(8): 1445-1451.