程序最坏执行时间极值统计方法

程序的最坏执行时间WCET是实时系统时间操作方面的可信基础,现有的WCET静态分析方法都需要对系统某种程度上的额外知识和限定性假设,导致现有的WCET分析方法本质上为偏高估计,降低了资源的利用率和系统的性能。给出一种基于极值统计的程序最坏执行时间估计新方法,采用程序执行时间的测量值作为样本,利用Gumbel分布建立程序最坏执行时间统计模型,根据测量样本序列预测执行时间的最大值,与以往的方法相比,这种方法综合体现了各种硬件特性对程序执行时间的影响,估计结果更为精确,更适合处理硬件特性和软件复杂度较高情况下的程序最坏执行时间估计。实验结果表明利用Gumbel分布建立的WCET估计模型能够快速且有效地给出实时程序的最坏执行时间估计。     

一种精确程序最坏执行时间分析方法

Java语言的动态特性使程序的最坏执行时间分析较悲观和难以预测,提出一种精确最坏执行时间分析方法,在高层分析中,引入一种标记方法,对带有标记的Java类文件进行反编译提取控制流程,得到每一个基本块中的Java 字节码指令的最坏情况下的执行次数,在底层分析中,建立结合流水线和高级缓存影响的时间模型,得到每条指令所对应的执行时间,最后结合高层分析和底层分析的结果得到程序的最坏情况下的执行时间。实验表明,该方法可以使对实时Java 程序的最坏情况执行时间预测更加安全和精确。     

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

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

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

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

同步语言的时间可预测多线程代码生成方法

能够提供更强计算能力的多核处理器将在安全关键系统中得到广泛应用.但是,由于现代处理器所使用的流水线、乱序执行、动态分支预测、Cache等性能提高机制以及多核之间的资源共享,使得系统的最坏执行时间分析变得非常困难.为此,国际学术界提出时间可预测系统设计的思想,以降低系统的最坏执行时间分析难度.已有研究主要关注硬件层次及其编译方法的调整和优化,而较少关注软件层次,即时间可预测多线程代码的构造方法以及到多核硬件平台的映射.本文提出一种基于同步语言模型驱动的时间可预测多线程代码生成方法,并对代码生成器的语义保持进行证明;提出一种基于AADL(Architecture Analysis and Design Language)的时间可预测多核体系结构模型,作为本文研究的目标平台;最后,给出多线程代码到多核体系结构模型的映射方法,并给出系统性质的分析框架.     

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

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

一种快速程序最坏执行时间分析方法研究

给出一种带有路径冲突检测的程序最坏情况执行时间估计方法,这种方法首先检测程序中存在的分支约束,然后将程序中存在的分支约束信息转化为程序流程控制图（CFG图）中结点之间的语义冲突,并按照结点对的形式保存在相应的冲突数组里,在接下来的WCET计算阶段通过边搜索程序执行路径边检测冲突数组里保存的已有的冲突关系以便在搜索路径的同时排除非可行执行路径,最终在可行执行路径集中选择具有最大执行时间的执行路径。与以往的方法相比,在保持估计精度的前提下,本文的方法避免了穷举所有执行路径带来的复杂度,提高了搜索的效率。实验结果表明本文方法对于语句间语义依赖关系比较强的实时程序能够快速且有效地给出估计结果。     

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

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

一种消除时间隐通道的方法调用控制策略

采用消息过滤算法可以在支持对象模型的多级安全系统中实现强制访问控制。但是,这种算法会引入时问隐通道,可能致使机密信息泄露。本文提出并实现了一种可信的控制策略,在消息过滤算法中采用异步消息传递方式消除时间隐通道,并对系统中对象方法的执行进行调度,确保消除时间隐通道不会导致执行结果不正确。     

面向对象程序设计语言的绑定时间分析技术

为了实现面向对象语言的部分求值,提出了一种绑定时间分析技术.该技术通过针对引用类型变量和指针变量的上下文敏感分析,能够比较精确地分析面向对象语言中诸如对象元素、数组元素等复杂数据结构元素的绑定时间,进而扩大了部分求值的作用范围.这种方法采用两层BTA环境来保存静态变量和局部变量的BTA状态,设置一种专用句柄来表示不同程序点创建的对象,进而采用这种句柄的集合表示引用类型变量的BTA状态.在为面向对象语言程序标注绑定时间信息的过程中,采用一个正向分析和一个反向分析过程,借助于BTA环境来跟踪和设定各种变量、对象和引用变量的绑定时间.该技术已经用于实现Java程序的绑定时间分析,能够有效地分析大多数单线程的Java程序,为实现高性能Java程序部分求值提供了必要的手段.     

Transforming flow information during code optimization for timing analysis

The steadily growing embedded-systems market comprises many application domains in which real-time constraints must be satisfied. To guarantee that these constraints are met, the analysis of the worst-case execution time (WCET) of software components is mandatory. In general WCET analysis needs additional control-flow information, which may be provided manually by the user or calculated automatically by program analysis. For flexibility and simplicity reasons it is desirable to specify the flow information at the same level at which the program is developed, i.e., at the source level. In contrast, to obtain precise WCET bounds the WCET analysis has to be performed at machine-code level. Mapping and transforming the flow information from the source-level down to the machine code, where flow information is used in the WCET analysis, is challenging, even more so if the compiler generates highly optimized code. In this article we present a method for transforming flow information from source code to machine code. To obtain a mapping that is safe and accurate, flow information is transformed in parallel to code transformations performed by an optimizing compiler. This mapping is not only useful for transforming manual code annotations but also if platform-independent flow information is automatically calculated at the source level. We show that our method can be applied to every type of semantics-preserving code transformation. The precision of this flow-information transformation allows its users to calculate tight WCET bounds.     

Pipelined processors and worst case execution times

The calculation of worst case execution time (WCET) is a fundamental requirement of almost all scheduling approaches for hard real-time systems. Due to their unpredictability, hardware enhancements such as cache and pipelining are often ignored in attempts to find WCET of programs. This results in estimations that are excessively pessimistic. In this article a simple instruction pipeline is modeled so that more accurate estimations are obtained. The model presented can be used with any schedulability analysis that allows sections of nonpreemptable code to be included. Our results indicate the WCET overestimates at basic block level can be reduced from over 20% to less than 2%, and that the overestimates for typical structured real-time programs can be reduced by 17%–40%.     

T-CREST: Time-predictable multi-core architecture for embedded systems

Real-time systems need time-predictable platforms to allow static analysis of the worst-case execution time (WCET). Standard multi-core processors are optimized for the average case and are hardly analyzable. Within the T-CREST project we propose novel solutions for time-predictable multi-core architectures that are optimized for the WCET instead of the average-case execution time. The resulting time-predictable resources (processors, interconnect, memory arbiter, and memory controller) and tools (compiler, WCET analysis) are designed to ease WCET analysis and to optimize WCET performance. Compared to other processors the WCET performance is outstanding.The T-CREST platform is evaluated with two industrial use cases. An application from the avionic domain demonstrates that tasks executing on different cores do not interfere with respect to their WCET. A signal processing application from the railway domain shows that the WCET can be reduced for computation-intensive tasks when distributing the tasks on several cores and using the network-on-chip for communication. With three cores the WCET is improved by a factor of 1.8 and with 15 cores by a factor of 5.7.The T-CREST project is the result of a collaborative research and development project executed by eight partners from academia and industry. The European Commission funded T-CREST.     

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估计的Cache分析研究综述

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

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.     

WCET analysis of modern processors using multi-criteria optimisation

The Worst-Case Execution Time (WCET) is an important execution metric for real-time systems, and an accurate estimate for this increases the reliability of subsequent schedulability analysis. Performance enhancing features on modern processors, such as pipelines and caches, however, make it difficult to accurately predict the WCET. One technique for finding the WCET is to use test data generated using search algorithms. Existing work on search-based approaches has been successfully used in both industry and academia based on a single criterion function, the WCET, but only for simple processors. This paper investigates how effective this strategy is for more complex processors and to what extent other criteria help guide the search, e.g. the number of cache misses. Not unexpectedly the work shows no single choice of criteria work best across all problems. Based on the findings recommendations are proposed on which criteria are useful in particular situations.