基于WCET分析的实时系统轨迹获取技术

时序约束是判断实时系统运行是否正确的重要规约.为了减小测试时由于对系统进行插装而产生的对实时系统行为的影响,提出了一种混合式监控方法.它对系统的时间干扰比纯软件方式小,并支持对系统的完全测试.此外,还提出一种基于WCET(worst-case execution time)分析技术的目标系统时间补偿方法,在精确地计算插入断言对目标系统的时间影响基础上,给出时间补偿.     

基于抽象解释技术的多层Cache分析的设计与实现

在WCET分析中,最重要的一类工作就是Cache分析。目前,大多数的基于抽象解释技术的Cache分析中,分析算法是作用于整个程序的,如果能够根据程序的层次结构,挖掘程序执行在Cache中的局部特性,那么就可以有效的提高WCET的分析精度。基于这一需求,本文主要研究基于抽象解释技术的多层Cache分析,研究的主要内容包括：程序层次结构的分析,基于抽象解释技术的多层Cache分析和整数线性规划问题的建模与WCET求解,采用多层Cache分析能有效的提高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自动分析工具

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

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

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

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

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

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

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

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

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

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

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

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

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

Timing Analysis for Instruction Caches

This paper contributes a comprehensive study of a framework to bound worst-case instruction cache performance for caches with arbitrary levels of associativity. The framework is formally introduced, operationally described and its correctness is shown. Results of incorporating instruction cache predictions within pipeline simulation show that timing predictions for set-associative caches remain just as tight as predictions for direct-mapped caches. The low cache simulation overhead allows interactive use of the analysis tool and scales well with increasing associativity.The approach taken is based on a data-flow specification of the problem and provides another step toward worst-case execution time prediction of contemporary architectures and its use in schedulability analysis for hard real-time systems.     

基于多级一致性协议的多核处理器WCET分析方法

由于多核处理器优越的计算性能,多核处理器现已广泛应用在嵌入式实时系统中. 相对于单核处理器,多核处理器存在资源共享竞争、并行任务干扰等因素,尤其是缓存（Cache）一致性问题,导致任务最坏情况执行时间（worst-case execution time,WCET）的预测更加困难.基于以上因素,提出基于多级一致性协议的多核处理器WCET分析方法.该方法针对多级一致性协议体系架构,提出多级一致性域的概念,将多核处理器的数据访问分为域内访问和跨域访问2个层次,根据Cache读写策略和MESI（modify exclusive shared invalid）一致性协议,得出一致性域内部和跨一致性域的Cache状态更新函数,从而实现多级一致性协议嵌套情况下的WCET分析.实验结果表明,在改变Cache配置参数的情况下,该方法分析结果与GEM5仿真结果的变化趋势一致,经过相关性分析,GEM5仿真结果与该方法分析结果相关性系数不低于0.98;在分析精度方面,该方法的平均过估计率为1.30,相比现有方法降低了0.78.     

基于优先级时间Petri网的实时嵌入式多核系统分析

已有的基于点区间优先级时间Petri网分析实时嵌入式多核系统的工作, 存在以下不足: (1)点区间优先级时间Petri网只考虑每个任务的执行时间是一个固定值的情况, 而更多的实际应用中每个任务的执行时间是在一个区间范围内, 因此不能模拟这些应用; (2)没有实现从任务依赖图到点区间优先级时间Petri网的自动转化, 不便于工程设计人员使用; (3)没有考虑任务间互斥访问共享变量的情况. 为此, 定义了优先级时间Petri网(Pri-TPN)以弥补第1个不足; 定义带有资源分配与优先级的任务依赖图(TDG-RAP)以弥补第3个不足; 给出从TDG-RAP到Pri-TPN的转化规则与算法以弥补第2个不足, 以及基于Pri-TPN分析任务最坏执行时间与系统死锁的算法; 开发工具软件, 方便工程设计人员使用.     

Code Analysis for Temporal Predictability

The execution time of software for hard real-time systems must be predictable. Further, safe and not overly pessimistic bounds for the worst-case execution time (WCET) must be computable. We conceived a programming strategy called WCET-oriented programming and a code transformation strategy, the single-path conversion, that aid programmers in producing code that meets these requirements. These strategies avoid and eliminate input-data dependencies in the code. The paper describes the formal analysis, based on abstract interpretation, that identifies input-data dependencies in the code and thus forms the basis for the strategies provided for hard real-time code development. This work has been supported by the ARTIST2 Network of Excellence on Embedded Systems Design of IST FP6. Raimund Kirner is an assistant professor in computer science in the Real-Time Systems Group of the Vienna University of Technology. He received a Master's degree in computer science and a doctoral degree in technical sciences both from the Vienna University of Technology in Austria in the years 2000 and 2003, respectively. His research interests include worst-case execution time analysis, compiler support for worst-case execution time analysis, and the verification of real-time systems. Peter Puschner is a professor in computer science at Vienna University of Technology. His main research focus is on worst-case execution time (WCET) analysis for real-time programs. Puschner has been working on WCET analysis for more than ten years and has strongly influenced the state of the art in this field. He has published numerous papers on WCET analysis and software/hardware architectures supporting temporal predictability. He was a guest editor for the special issue on WCET analysis of the Kluwer International Journal on Real-Time Systems and chaired the program committee of the IEEE International Symposium on Object-oriented Real-time distributed Computing in 2003 and the Euromicro Real-Time Systems Conference in 2004. In 2000/2001 Peter Puschner spent one year as a Marie-Curie research fellow at the University of York, England.     

Timing Analysis for Data and Wrap-Around Fill Caches

The contributions of this paper are twofold. First, an automatic tool-based approach is described to bound worst-case data cache performance. The approach works on fully optimized code, performs the analysis over the entire control flow of a program, detects and exploits both spatial and temporal locality within data references, and produces results typically within a few seconds. Results obtained by running the system on representative programs are presented and indicate that timing analysis of data cache behavior usually results in significantly tighter worst-case performance predictions. Second, a method to deal with realistic cache filling approaches, namely wrap-around-filling for cache misses, is presented as an extension to pipeline analysis. Results indicate that worst-case timing predictions become significantly tighter when wrap-around-fill analysis is performed. Overall, the contribution of this paper is a comprehensive report on methods and results of worst-case timing analysis for data caches and wrap-around caches. The approach taken is unique and provides a considerable step toward realistic worst-case execution time prediction of contemporary architectures and its use in schedulability analysis for hard real-time systems.     

Worst Case Execution Time Analysis for a Processor with Branch Prediction

The fundamental requirement for hard real-time systems is that task deadlines be never missed. As a consequence, knowing tasks worst case execution times (WCET) is crucial for such systems. Taking into account modern architectural features makes it possible to determine tighter WCET bounds than with program analysis that ignores such features. While effects of caches and pipelines on WCET analysis have been extensively studied, to our knowledge the effect of the branch prediction on WCET evaluation has not been studied yet. This paper describes a method for statically bounding the number of timing penalties due to erroneous branch predictions. The proposed method is based on static program analysis and branch target buffer modelling. It consists in collecting information on branch target buffer evolution by considering all possible execution paths of a program. Collected information can then be used to classify control transfer instructions so that their worst case branching cost can be estimated and incorporated into the program WCET. A method is also given to tightly predict the WCET of loops whose number of iterations depend on counter variables of outer loops. Experimental results show that the timing penalty due to wrong branch predictions estimated by the proposed technique is close to the real one, which demonstrates the practical applicability of our method.     

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

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