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.     

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.     

Supporting Timing Analysis by Automatic Bounding of Loop Iterations

Static timing analyzers, which are used to analyze real-time systems, need to know the minimum and maximum number of iterations associated with each loop in a real-time program so accurate timing predictions can be obtained. This paper describes three complementary methods to support timing analysis by bounding the number of loop iterations. First, an algorithm is presented that determines the minimum and maximum number of iterations of loops with multiple exits. Even when the number of iterations cannot be exactly determined, it is desirable to know the lower and upper iteration bounds. Second, when the number of iterations is dependent on unknown values of variables, the user is asked to provide bounds for these variables. These bounds are used to determine the minimum and maximum number of iterations. Specifying the values of variables is less error prone than specifying the number of loop iterations directly. Finally, a method is given to tightly predict the execution time of inner loops whose number of iterations is dependent on counter variables of outer level loops. This is accomplished by formulating the total number of iterations of a loop in terms of summations and solving the resulting equation. These three methods have been successfully integrated in an existing timing analyzer that predicts the performance for optimized code on a machine that exploits caching and pipelining. The result is tighter timing analysis predictions and less work for the user.     

Modeling Control Speculation for Timing Analysis

The schedulability analysis of real-time embedded systems requires worst case execution time (WCET) analysis for the individual tasks. Bounding WCET involves not only language-level program path analysis, but also modeling the performance impact of complex micro-architectural features present in modern processors. In this paper, we statically analyze the execution time of embedded software on processors with speculative execution. The speculation of conditional branch outcomes (branch prediction) significantly improves a program's execution time. Thus, accurate modeling of control speculation is important for calculating tight WCET estimates. We present a parameterized framework to model the different branch prediction schemes. We further consider the complex interaction between speculative execution and instruction cache performance, that is, the fact that speculatively executed blocks can generate additional cache hits/misses. We extend our modeling to capture this effect of branch prediction on cache performance. Starting with the control flow graph of a program, our technique uses integer linear programming to estimate the program's WCET. The accuracy of our method is demonstrated by tight estimates obtained on realistic benchmarks.     

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

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

An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution

Previously published methods for estimation of the worst-case execution time on high-performance processors with complex pipelines and multi-level memory hierarchies result in overestimations owing to insufficient path and/or timing analysis. This does not only give rise to poor utilization of processing resources but also reduces the schedulability in real-time systems. This paper presents a method that integrates path and timing analysis to accurately predict the worst-case execution time for real-time programs on high-performance processors. The unique feature of the method is that it extends cycle-level architectural simulation techniques to enable symbolic execution with unknown input data values; it uses alternative instruction semantics to handle unknown operands. We show that the method can exclude many infeasible (or non-executable) program paths and can calculate path information, such as bounds on number of loop iterations, without the need for manual annotations of programs. Moreover, the method is shown to accurately analyze timing properties of complex features in high-performance processors using multiple-issue pipelines and instruction and data caches. The combined path and timing analysis capability is shown to derive exact estimates of the worst-case execution time for six out of seven programs in our benchmark suite.     

共享多端口数据Cache结构：SMPDCA

随着半导体工艺技术的飞速发展,单芯片多处理器（Single-Chip Multiprocessor,SCMP)结构将是一条提高处理器性能的有效途径。该文在分析SCMP结构的特点的基础上,提出了SCMP的一种结构实现：共享多端口数据Cache结构（Shared Multi-Ported Data Cache Architecture,SMPDCA).SMPDCA结构具有三个突出的优点：最小的通信延迟、没有Cache一致性维护开销和数据Cache命中率提高。模拟结果表明,与数据Cache私有的结构相比,SMPDCA结构的煅出优点使得应用程序的性能得到了明显的提高,特别是对于改善处理器之间的通信与交互比较多的应用程序的性能具有最为明显的效果。     

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.     

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

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

Selective-Splitting and Cache-Maintenance Algorithms for Associative-Client Caches

We propose a number of selective-splitting and cache-maintenance algorithms to reduce the computational complexity of associative-client caches and network load. Our selective-splitting algorithms selectively split query-intersected semantic regions based on the relative region access-latency or relative region size in a semantic data caching and replacement model. Our cache-maintenance algorithms are set up for studying a variety of design issues in synchronizing associative-client caches. We analyzed the performance of our proposed algorithms in a network environment. Results from our study show that the selective-splitting algorithms reduce the number of splitting operations by 80% in most cases, and the avoidance-based maintenance algorithms outperform the detection-based maintenance algorithms not only in reducing the network traffic but also in rendering consistent performance under various experimental variances.     

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.     

基于取指执行时序范畴的多核共享Cache干扰分析

在多核结构中,获得并行应用线程的安全、精确的最坏情况执行时间(worst case execution time, WCET)的最大挑战之一在于共享资源的竞争冲突检测.在共享Cache的多核处理器中,线程在共享Cache中的指令可能被其他并行线程的指令替换,从而导致了线程间在共享Cache上的干扰,因此多核结构下线程WCET需要考虑并行线程间在共享Cache上的干扰.在现有的简单地址映射干扰分析基础上,考虑了指令取指执行时序因素对干扰的影响,提出了非干扰状态的充分不必要条件,根据指令的取指执行时序范畴判断线程在共享Cache上的干扰状态.通过排除非干扰状态,可以进一步精确多核结构中线程的WCET估值.理论分析证明了该方法的有效性.实验结果表明,与当前现有的考虑执行周期和基于逻辑访问先后顺序的方法相比,基于时序方法下的WCET估值分别可以提高12%和7%的精确度.     

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

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

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

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

Efficient and Precise Cache Behavior Prediction for Real-Time Systems

Abstract interpretation is a technique for the static detection of dynamic properties of programs. It is semantics based, that is, it computes approximative properties of the semantics of programs. On this basis, it supports correctness proofs of analyses. It replaces commonly used ad hoc techniques by systematic, provable ones, and it allows for the automatic generation of analyzers from specifications by existing tools. In this work, abstract interpretation is applied to the problem of predicting the cache behavior of programs. Abstract semantics of machine programs are defined which determine the contents of caches. For interprocedural analysis, existing methods are examined and a new approach that is especially tailored for the cache analysis is presented. This allows for a static classification of the cache behavior of memory references of programs. The calculated information can be used to improve worst case execution time estimations. It is possible to analyze instruction, data, and combined instruction/data caches for common (re)placement and write strategies. Experimental results are presented that demonstrate the applicability of the analyses.     

PPT计时程序的实现和分析

随着计算机的发展,各种办公化软件也应运而生,而PPT作为办公化软件的一种,具有非常众多的使用者,倍受大家所青睐。文中以Powerpoint2003为制作媒介,介绍利用PPT制作一个可以在1秒钟进行变换的计时程序的制作过程。     

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

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

基于多级一致性协议的多核处理器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.