最坏执行时间分析中的时序异常问题  

Timing Anomalies Issue in WCET Analysis

作　　者：蒋滨泽 朱钇宣 陈香兰[1,2] 龚小航 高银康 李曦 Jiang Binze;Zhu Yixuan;Chen Xianglan;Gong Xiaohang;Gao Yinkang;Li Xi(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)

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027 [2]中国科学技术大学苏州高等研究院,江苏苏州215004

出　　处：《计算机研究与发展》2025年第4期1033-1049,共17页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(62102383,61976200,62172380);江苏省自然科学基金项目(BK20210123)。

摘　　要：时序异常是一种程序在最坏执行时间(worst-case execution time,WCET)分析中反直觉的时间行为,其特征在于,尽管局部执行速度更快,但整体的执行时间可能会增加,因此WCET分析必须以保守的态度考虑所有可能的执行情况,以确保分析结果的安全性,这使得WCET分析变得非常困难.相反地,如果能够确保要分析的程序与平台不存在时序异常,将大大减少WCET分析需要考虑的状态以及所花费的时间.因此,时序异常问题是WCET分析中的关键挑战.然而,尽管历经20多年的研究,学术界对时序异常问题仍未形成统一的定义和共识.自时序异常概念提出以来,学术界涌现出了各种文献描述时序异常,对于这些定义,可以根据定义方式和描述内容对它们进行分类,并分析它们各自的优劣.进一步地,如果对导致时序异常的原因进行研究,可以将其归结为调度策略、高速缓存以及组件影响这3个方面.此外,目前也有一些验证与消除时序异常的相关研究工作,这些工作也存在一些问题和不足.WCET分析的未来应当以分析方式为基础进行时序异常相关的研究,以更好地解决时序异常问题.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.

关 键 词：最坏执行时间 处理器架构 时序异常 时间可预测 实时系统 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]