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

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

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

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

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

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

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

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

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

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

服务体执行流模型中消息通信的时间可预测性分析

Minicore是基于服务体执行流模型的新型微内核,它有效的将操作系统中的存储模型和运行模型相分离.微内核的高度模块化的设计使Minicore对服务体(Minicore的基本单元)间的消息通信的依赖度极高.于是对于Minicore操作系统的时间可预测性分析也无可避免的依赖于通信模块的时间可预测性.本文的工作即是通过计算Minicore通信模块的WCET,分析消息通信的时间可预测性,为未来实现时间可预测的通信机制并分析Minicore的时间可预测性提供基础.对通信模块的WCET分析计算采用静态WCET分析中的基于路径的算法,应用到Minicore系统的通信模块,包括四个阶段:提取目标代码片段,程序控制流分析,处理器特征分析和WCET计算.基于WCET计算结果本文定义配置相关的时间可预测性(CIPr)作为评估消息通信时间可预测性的指标.     

基于知识处理的电路符号分析

本文介绍基于知识处理的电路符号分析程序SYMBANA.利用输入电路结构和符号参数,程序自动输出电路函数(例如,电压放大系数Av=v_0/vi)的符号公式和指定参数Pi的敏感度?Av/?Pi的符号表达式.SYMBANA运用知识处理技术和演绎方法,进行电路符号公式和参数敏感度的推导.SYMBANA是用micro-prolog写成,运行于IBM PC/XT,AT及各种兼容机.SYMBANA可用于各种电路分析、优化设计和计算机辅助学习.     

实时控制系统程序模式的WCET自动分析方法

基于源程序获取实时控制系统的模式,不仅能够验证实现的模式与设计是否一致,还可使程序的最差情况执行时间(WCET)计算更为精准。为此,提出一种自动分析实时控制系统程序模式的方法。通过分析C语言源程序生成程序控制流图,对输入变量相关节点进行切片,形成依赖输入变量的控制流图(ICFG),建立ICFG每条路径的线性规划问题并求解,从而获得潜在的程序模式。在此基础上,计算指定模式下针对现代RISC处理器程序的WCET。在基准程序上的实验结果验证了该方法的可行性和有效性。     

符号执行中的循环依赖分析方法

符号执行方法处理循环时存在路径爆炸的问题。为此,提出一种基于归纳变量的循环依赖分析方法。通过识别循环归纳变量及符号表达式,结合边界约束条件生成可达归纳变量分支的路径约束,并采用符号化映射方法分析嵌套循环归纳变量依赖问题,从而在不展开循环的情况下生成覆盖归纳变量分支的测试用例。对开源工具Libxml2进行实验,该方法能发现其中2个while循环所引发的数组访问越界错误。     

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

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

A comparison of instruction memories from the WCET perspective

Hard real-time systems demand high performance in combination with a timing predictable program execution. The performance of a system in the worst-case, represented by its worst case execution time (WCET), highly depends on the design of the memory subsystem. In this paper we focus on the instruction memory hierarchy and quantify the impact of different on-chip instruction memories on the worst-case timing of the system. A function-based dynamic instruction scratchpad (D-ISP), an instruction cache, and static instruction scratchpads using basic-block-based and function-based assignment algorithms are compared. Therefore, we provide WCET bounds for systems with different on-chip instruction memories and different off-chip memory timings.We show that for small memory sizes a static instruction scratchpad usually outperforms the other memories in terms of the WCET estimate. However, with increasing memory sizes the D-ISP is able to reach lower WCET bounds. An instruction cache can only provide lower WCET bounds than the other memories, if no suitable assignment for the static instruction scratchpads is found or if the D-ISP suffers from thrashing or frequently loads unused code.     

Worst-case execution-time analysis for embedded real-time systems

In this article we give an overview of the worst-case execution time (WCET) analysis research performed by the WCET group of the ASTEC Competence Centre at Uppsala University. Knowing the WCET of a program is necessary when designing and verifying real-time systems. The WCET depends both on the program flow, such as loop iterations and function calls, and on hardware factors, such as caches and pipelines. WCET estimates should be both safe (no underestimation allowed) and tight (as little overestimation as possible). We have defined a modular architecture for a WCET tool, used both to identify the components of the overall WCET analysis problem, and as a starting point for the development of a WCET tool prototype. Within this framework we have proposed solutions to several key problems in WCET analysis, including representation and analysis of the control flow of programs, modeling of the behavior and timing of pipelines and other low-level timing aspects, integration of control flow information and low-level timing to obtain a safe and tight WCET estimate, and validation of our tools and methods. We have focussed on the needs of embedded real-time systems in designing our tools and directing our research. Our long-term goal is to provide WCET analysis as a part of the standard tool chain for embedded development (together with compilers, debuggers, and simulators). This is facilitated by our cooperation with the embedded systems programming-tools vendor IAR Systems.     

Data-Flow Frameworks for Worst-Case Execution Time Analysis

The purpose of this paper is to introduce frameworks based on data-flow equations which estimate the worst-case execution time (WCET) of real-time programs. These frameworks allow several different WCET analysis techniques with various precisions, which range from naïve approaches to exact analysis, provided exact knowledge on the program behavior is available. In addition, data-flow frameworks can also be used for symbolic analysis based on information derived automatically from the source code of the program.     

实时系统最坏执行时间分析*

实时系统开发过程中必须强调时间的重要性和支持时间的可预报性。最坏执行时间分析与可调度性分析构成了实时系统时间方面操作可信的基础。最坏执行时间分析计算任务执行时间的上界,这些任务的上界用来分配正确的CPU时间给实时任务。最坏执行时间是可调度分析工具的输入,可调度分析决定了一组任务在一个给定的目标系统下是否可调度。对最坏执行时间分析方面的研究进行了综述,给出在这一领域所取得的进展。 还讨论了在最坏执行时间分析方面存在的问题,给出了将来的研究方向。     

信息物理系统实时任务WCET的研究

信息物理系统（CPS）是最近几年才出现的一个新的交叉领域的研究概念,它被普遍认为是计算机信息处理技术史上的下一次革命,将会改变人与现实物理世界之间的交互方式,具有广泛的应用前景。简要介绍了CPS的概念、一些新的特性。研究了CPS实时性方面的最坏执行时间（WCET）分析的组成部分、获取方法和计算算法,并比较了几种算法的优劣,列举了这一领域一些研究进展,讨论了WCET分析这一领域中存在的问题,给出了将来的研究方向。     

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.     

可平台迁移的最坏执行时间分析

当前的很多最坏执行时间分析工具都是针对特定的编程语言或特定的编译器的,因而缺乏平台间的迁移性,从而不能被广泛使用.介绍了一种基于Java字节码的可平台迁移的最坏执行时间分析方法.该分析方法包括两方面：一是对字节码（javabyte code）的高层分析,提取出程序数据流和控制流信息;二是对Java虚拟机的底层分析,获得虚拟机的时间模型.最后这两种分析结合得到程序的最坏执行时间.同时还探讨了将来的研究方向.     

嵌入式Java处理器的方法调用机制

Java语言和Java处理器在实时嵌入式系统开发中的应用受到广泛关注。传统Java虚拟机的方法调用机制采用动态装载迟解析的执行方式,使得最坏情况执行时间(WCET)难以预测。针对该问题,提出一种提前解析-微程序执行的改进方法。将传统方法调用中的符号引用转化为直接调用,以微程序的方式运行在硬件处理器上,使执行限制在可预知的时钟周期内。实验结果证明,改进方法调用机制在执行时间上满足线性关系,具备良好的WCET可预测性。     

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

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