面向WCET估计的Cache分析研究综述

实时系统时间分析的首要任务是估计程序的最坏情况执行时间(worst-case execution time,简称WCET).程序的WCET 通常受到硬件体系结构的影响,Cache则是其中最为突出的因素之一.对面向WCET计算的Cache分析研究进行了综述,介绍了经典Cache分析框架与Cache分析核心技术,并从循环结构分析、数据Cache分析、多级Cache分析、多核共享Cache分析、非LRU替换策略分析等角度介绍了Cache分析在不同维度上的研究问题与主要挑战,总结了现有技术的优缺点,展望了Cache分析研究的未来发展方向.     

WCET分析：建立实时系统可靠运行的技术

实时系统开发必须强调时间的重要性，为了保证系统安全运行，需要验证系统是否在时限内完成各个任务，因此，当设计和验证实时系统时。了解运行在系统中代码的最坏执行时间(WCET)是非常重要的。WCET静态分析(简称WCET分析)计算实时程序最坏执行时间的上界，而上界被用来为应用程序的任务分配正确的CPU时间，它们也是可调度分析工具的输入，因此，WCET分析是可靠建立实时系统安全正确运行的基础。介绍了WCET分析的概念。指出了传统测量存在的缺陷，剖析了WCET分析研究的关键技术，探讨了目前存在的问题和今后的发展方向。     

面向Web的WCET模式自动分析系统

针对传统的WCET(Worst-Case Execution Time)分析方法面临的精度不高和用户使用繁琐问题,提出一种自动分析程序模式的方法并据此设计实现了一个面向Web的WCET分析系统。首先在对源程序进行分析的基础上,利用程序控制流程图,通过数据流框架进行切片,获得依赖于输入变量的无循环控制流程图ICFG。然后,通过对ICFG每条路径求解,获得程序的模式及其输入表达式,并计算其对应的WCET。最后,将上述分析方法设计实现为针对C语言的动态链接库(DLL),并利用该DLL实现一个面向Web的WCET自动分析系统——WCET Mode Analyzer。WCET Mode Analyzer对基准程序的分析结果,验证了该方案的有效性和应用的简便性。     

实时系统程序最差情况执行时间(WCET)的分析

事先获知系统中程序最差情况的执行时间(Worst-CaseExecutionTime,WCET),是设计和验证实时系统调度及可调度性分析的前提,也是确定周期性任务是否满足其性能目标,从而发现系统性能瓶颈的基础。本文概述了程序WCET的分析方法,描述了WCET分析的定义和组成,重点总结其中的程序流事实分析方法,并指出程序流事实分析存在的问题和WCET分析的研究热点。     

包含依赖输入分支程序的符号化WCET分析

符号化WCET(worst-case execution time)分析是用符号表达式表示任务的最大执行时间:表达式中包含了参数.通过在运行时刻快速确定表达式值,符号化WCET分析可以更精确地估算WCET.提出了一种针对其分支直接依赖于输入数据的程序的符号化WCET分析方法.首先对Blieberger方法进行扩充,使得WCET符号表达式能够表达依赖输入分支,然后利用程序的控制依赖图对符号表达式进行化简,从而产生带条件的WCET符号表达式,即不同的条件对应不同的符号表达式.与已有方法不同,符号化WCET公式直接依赖于输入参数,使得运行时的WCET估算更加简单直接.     

WCET分析中面向对象程序多态性问题的解决方法

用面向对象建模语言(如统一建模语言UML)设计并用面向对象程序设计语言(如C )实现实时系统是实时系统开发领域的一个趋势,但面向对象的主要特征(如多态性)却使程序最差情况执行时间(Worst-Case ExecutionTi me,WCET)更加难以分析。本文通过把UML设计信息引入WCET分析来解决此问题。考虑到UML关联关系描述了两个或多个具体类之间的对应关系,因此本文要求指定关联角色的多重性,并假定能够建立关联关系与其在程序中表示的对应关系。在已知关联角色多重性的基础上,本文计算特定循环的执行计数并确定在超(虚)类调用位置上每个具体类的对象个数,该循环使用超类变量遍历统一表示的关联角色对象。通过和Corti等人方法的结合,本文方法能够自动计算具有多态性特征的面向对象程序的WCET。实验结果表明,本文研究的情形在面向对象程序中普遍存在。     

基于抽象解释自动导出针对WCET分析的程序流信息的方法

通过在通用单调数据流框架基础上使用基于抽象解释的变量值范围传播技术,本文提出了一种自动获取循环最大迭代次数和不可行路径的方法。该方法有利于精确计算实时程序最差情况下的执行时间（WCET）。     

一种基于抽象解释的WCET自动分析工具

利用基于抽象解释的变量值范围传播技术,提出了一种自动分析高级语言程序流信息的方法;并在白盒测试工具NPCA的基础上,利用该方法实现了WCET分析工具NPCA-WCET。     

一种实时Java程序的WCET分析新方法研究

软件的最坏执行时间是实时系统的时间可信基础,Java语言的动态特性使程序的最坏执行时间分析较悲观和难以预测,本文提出了一种基于Java字节码的面向实时Java程序的最坏执行时间分析新方法,该方法引入一个注释类对源程序进行注释,然后将编译产生的Java类文件作为方法的分析对象,解决了实时Java程序中由于动态分配问题带来的预测不确定的问题,实验表明,该方法可以使对实时Java程序的最坏情况执行时间预测更加安全和精确.     

面向WCET分析的实时多核体系结构研究

随着工艺技术的发展以及嵌入式实时应用范围的不断扩大和需求的不断提升,多核处理器必将凭其高性能和低功耗特性应用到嵌入式实时领域中。但是,多核处理器体系结构很难甚至无法满足实时系统的实时限制和对WCET的可预测性要求。从多核中的共享资源入手,分析多核中的片上共享资源（共享Cache、片上互连）和片外共享资源（片外存储）对WCET分析的影响,探讨了各种干扰下的WCET分析方法。介绍了两种多核WCET分析模型：多核静态WCET分析模型和多核混合WCET分析模型;同时,针对嵌入式实时应用提出了多核设计原则。     

可扩展和可配置事件通知服务体系结构

基于发布/订阅模式的事件通知服务,作为基本的通信与集成基础设施已广泛应用于分布式应用系统.由于日益增长的应用需求,事件通知服务需要应对各种来自不同应用领域的新需求.但在开发基于事件中间件的分布式应用时,开发者面临特殊化与通用化通知服务的两难选择.针对这种现状,提出了一种灵活的解决方法,设计一个动态可扩展和可配置的事件通知服务体系结构,允许针对不同应用领域定制不同的通知服务.该体系结构基于XML的可扩展订阅、事件、协议和配置语言,以配置管理和元服务管理的机制,提供了通知服务功能的动态扩展和定制以及非功能性特征的满足.     

多余处理器时间回收与最坏执行时间分析

通常的最坏执行时间分析方法的结果过于悲观(overpessimistic),根据这种结果进行调度将导致资源的极大浪费。面向对象的编程语言由于具有封装、继承、多态的特点,使得按照通常的方法获得的最坏执行时间更加悲观。解决这个问题的一个办法就是限制面向对象语言这些特点的使用,但这又导致最终的实时系统不够灵活,失去了面向对象语言的优点。文章以实时JAVA系统为例,介绍了将运行中赚取时间(gaintime)的回收与最坏执行时间分析相结合的方法,这种方法既提高了资源的使用率,又保证了系统的灵活性和性能。     

嵌入式实时操作系统的分析评测方法

使用WCET(Worst-case execution time)分析工具Bound-T,分析典型实时操作系统(RTMES和uClinux)的关键模块代码,在系统运行在硬件上之前分析其机器码,给出整体系统的最坏执行时间.在系统的WCET达到要求之后,再通过实验使用benchmark,评测操作系统的典型实时性能指标,给出两个嵌入式实时操作系统的实时性能对比,并分析RTEMS(Real Time Executive for Multiprocessor Systems)的优势所在.     

基于WCET的多核共享资源冲突分析与约束研究

随着片上多核处理器在嵌入式实时系统中的应用,片上共享资源给任务的WCET分析带来诸多挑战,使得对多核共享资源冲突问题的研究变得非常重要。依据研究的目标,可以把目前已有的研究分为面向共享资源冲突分析和面向共享资源冲突约束两大类。对于面向共享资源冲突分析问题,探讨了不同共享资源冲突产生的原因,概括和比较了典型的冲突分析方法的优势和局限性;对于面向共享资源冲突约束问题,给出了其主要的研究内容,并评述和分析了几种主流的冲突约束方法。最后针对目前的研究状况指出了一些研究方向。     

Symbolic Cache Analysis for Real-Time Systems

Caches impose a major problem for predicting execution times of real-time systems since the cache behavior depends on the history of previous memory references. Too pessimistic assumptions on cache hits can obtain worst-case execution time estimates that are prohibitive for real-time systems. This paper presents a novel approach for deriving a highly accurate analytical cache hit function for C-programs at compile-time based on the assumption that no external cache interference (e.g. process dispatching or DMA activity) occurs. First, a symbolic tracefile of an instrumented C-program is generated based on symbolic evaluation, which is a static technique to determine the dynamic behavior of programs. All memory references of a program are described by symbolic expressions and recurrences and stored in chronological order in the symbolic tracefile. Second, a cache hit function for several cache architectures is computed based on a cache evaluation technique. Our approach goes beyond previous work by precisely modelling program control flow and program unknowns, modelling large classes of cache architectures, and providing very accurate cache hit predictions. Examples for the SPARC architecture are used to illustrate the accuracy and effectiveness of our symbolic cache prediction.     

一种可行的容错实时系统可调度性分析

针对容错实时系统中容错优先级两种分配策略存在的不足,通过对容错实时任务进行基于最坏响应时间的可调度性分析,提出了允许容错优先级降低的分配策略以提高系统的容错能力.经过深入的分析和实验证明,这种容错优先级的分配策略能够在以前两种分配策略无法提高系统容错能力的情况下,有效地提高系统的容错能力,设计并实现了改进的最佳容错优先级分配因子的搜索算法,并通过模拟实验进行了验证.     

Modeling out-of-order processors for WCET analysis

Estimating the Worst Case Execution Time (WCET) of a program on a given processor is important for the schedulability analysis of real-time systems. WCET analysis techniques typically model the timing effects of micro-architectural features in modern processors (such as pipeline, cache, branch prediction) to obtain safe and tight estimates. In this paper, we model out-of-order superscalar processor pipelines for WCET analysis. The analysis is, in general, difficult even for a basic block (a sequence of instructions with single-entry and single-exit points) if some of the instructions have variable latencies. This is because the WCET of a basic block on out-of-order pipelines cannot be obtained by assuming maximum latencies of the individual instructions. Our timing estimation technique for a basic block proceeds by a fixed-point analysis of the time intervals at which the instructions enter/leave a pipeline stage. To extend our estimation to whole programs, we use Integer Linear Programming (ILP) to combine the timing estimates for basic blocks. Timing effects of instruction cache and branch prediction are also modeled within our pipeline analysis framework. This forms a combined timing analysis framework that captures out-of-order pipeline, cache, branch prediction as well as the mutual interaction among these micro-architectural features. The accuracy of our analysis is demonstrated via tight estimates obtained for several benchmarks. Preliminary version of parts of this paper has previously been published as Li et al. (2004). Abhik Roychoudhury received his B.E. in Computer Engineering from Jadavpur University (India) in 1995 and his M.S. / Ph.D. degrees (both in Computer Science) from the State University of New York at Stony Brook in 1997 and 2000 respectively. Since 2001 he has been an Assistant Professor at National University of Singapore. His research interests are in models and methods for reliable development of embedded software and systems, with specific focus on software validation, analysis and comprehension. Xianfeng Li is a postdoctoral researcher in the Department of Computer Science and Technology at Peking University, China. He received his Ph.D. from National University of Singapore in 2005. His research interests include real-time systems, modeling and evaluation of computer architecture, and System-on-Chips. Tulika Mitra is an Assistant Professor in School of Computing at National University of Singapore from January 2001. She received her PhD in Computer Science from SUNY at Stony Brook in December 2000. Tulika received M.E in Computer Science and Automation from Indian Institute of Science in 1997 and her B.E. in Computer Engineering from Jadavpur University, India in 1995. Her current research focuses on design and analysis of embedded and real-time systems.