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.     

Rapid Prototyping with Constraints-based Scheduling for Multimedia Applications

With the increased demand in multimedia applications, the need to provide better system support is greater than ever. Multimedia applications have an added dimension of time in their execution which results in stringent timing requirements. Existing systems incorporate such stringent timing requirements either at the system-level or the application-level. System-level supports are typically operating-system-dependent whereas application-level supports are achieved by building timing controls into the application itself. This lengthens the application development time and fails to take full advantage of operating system's capabilities. In this paper, we propose a framework that resides between the system-level and application-level support. The framework consists of two layers: an interface layer that incorporates high-level end-to-end timing constraints, and a system layer that implements a host-end scheduling mechanism to support high-level end-to-end timing specifications. Two applications have been developed using this framework. The results indicate that the framework is able to support rapid-prototyping of multimedia applications with stringent timing requirements.     

Giotto:与平台无关的嵌入式时序触发语言

Gitto语言是一种能适用于硬实时控制应用的高级编程语言。介绍了Giotto语言的编程方法,以自主航模的设计为例,说明了Giotto语言如何在实际设计中应用,由于Giotto设计过程中将时序程序与功能程序分离的特点,使Giotto程序与具体的运行平台无关,提高了程序的健壮性、稳定性及代码的复用性。     

Compilation techniques for a reconfigurable LIW architecture

Matching an application to an architecture in structure and size is a way of achieving higher computation speed. This paper presents a combination of a compiler and a reconfigurable long instruction word (RLIW) architecture as an approach to the matching problem. Configurations suitable for the execution of different parts of a program are determined by a compiler, and code is generated for both reconfiguring the hardware and performing the computation. The RLIW machine, consisting of multiple processing and global data memory modules, effectively utilizes the fine-grained parallelism detected in programs by a compiler. The long word instructions control the operation of processing and memory modules in the system. To reduce the data transfer between processing modules and data memory modules, we provide reconfigurable interconnections among the processing modules which permit direct communication. The compiler uses new techniques, including region scheduling, generation of code for reconfiguration of the system, and memory allocation techniques, to achieve improved performance. Algorithms for packing operations into long word instructions and techniques for effectively assigning memory modules to the operands required by an instruction are developed. Results of the experiments to evaluate the system indicate that speedups of 60–300% can be obtained for both scientific and nonscientific programs. The reconfigurable architecture is responsible for much of the speedup. Also, the results indicate that the major problem of memory bottleneck faced in designing parallel systems is successfully attacked.This paper represents work done while the author was at the University of Pittsburgh     

面向实时应用的深度学习研究综述

深度学习算法和GPU算力的不断进步,正促进着人工智能技术在包括计算机视觉、语音识别、自然语言处理等领域得到广泛应用.与此同时,深度学习已经开始应用于以自动驾驶为代表的安全攸关领域.但是,近两年接连发生了几起严重的交通事故表明,深度学习技术的成熟度还远未达到安全攸关应用的要求.因此,对可信人工智能系统的研究已经成为了一个热点方向.对现有的面向实时应用的深度学习领域的研究工作进行了综述,首先介绍了深度学习技术应用于实时嵌入式系统所面临的关键设计问题;然后,从深层神经网络的轻量化设计、GPU时间分析与任务调度、CPU+GPU SoC异构平台的资源管理、深层神经网络与网络加速器的协同设计等多个方面对现有的研究工作进行了分析和总结;最后展望了面向实时应用的深度学习领域进一步的研究方向.     

Data-Dependency Graph Transformations for Instruction Scheduling

This paper presents a set of efficient graph transformations for local instruction scheduling. These transformations to the data-dependency graph prune redundant and inferior schedules from the solution space of the problem. Optimally scheduling the transformed problems using an enumerative scheduler is faster and the number of problems solved to optimality within a bounded time is increased. Furthermore, heuristic scheduling of the transformed problems often yields improved schedules for hard problems. The basic node-based transformation runs in O(ne) time, where n is the number of nodes and e is the number of edges in the graph. A generalized subgraph-based transformation runs in O(n² e) time. The transformations are implemented within the Gnu Compiler Collection (GCC) and are evaluated experimentally using the SPEC CPU2000 floating-point benchmarks targeted to various processor models. The results show that the transformations are fast and improve the results of both heuristic and optimal scheduling.     

基于时间约束集的集束型设备群调度方法

随着300mm晶圆的加工技术问世,工业界开始采用一种全新的晶圆制造设备——集束型设备群(Multi-cluster tools).对于单个集束型设备(Single-cluster tools)调度研究已比较成熟,并提出了多种调度方法,然而对于集束型设备群调度研究尚处在一个起步阶段. 本文对带有驻留约束且具有多种晶圆类型的集束型设备群的调度问题进行了研究,在引入时间约束集概念的基础上建立了调度模型, 同时,提出了一种逐级回溯的调度方法,并对调度算法进行了仿真实验分析. 仿真结果表明本文提出的算法是有效且可行的.     

LET模型的时间语义编程语言

嵌入式实时系统的正确性不仅取决于计算结果的正确性,更取决于产生结果时间的正确性.然而软件不确定的并发执行带来系统时间行为不可预测问题,使得验证复杂度升高,成本增加,为此实时系统领域提出了许多实时编程语言来提高系统的时间可预测性.LET(logical execution time)模型结合了同步模型ZET(zero e...     

改进的指令总线功耗优化策略

针对编译器系统设计和编译中的低功耗优化,基于可重定向编译器,实现在编译器后端对VLIW指令总线进行功耗优化的策略.通过对编译生成的二进制目标码进行横向再调度来减少指令总线上的高低电位切换次数,达到降低系统功耗的目的.对编译后端的软件流水和超块调度两种性能优化策略进行对比实验,表明其优化效果在30%以上,并且代码的指令级并行性(Instruction Level Parallelism,ILP)与优化效果存在明显的相关性.最后,通过ILP对该策略提出改进,以指令级并行信息指导功耗优化,在功耗优化效果损失不大的前提下,可节省多达20%的算法开销.     

Extending the SCR Method for Real-Time Systems

Wepropose timed SCR specifications, which are a generalizationof SCR specifications, intended to specify quantitative timingproperties of real-time systems. We extend the tabular notationof the SCR method to deal with sporadic and periodic timing constraints.We present a formal semantics for timed SCR specifications bytranslating them into timed transition systems. A shutdown systemin Korean nuclear power plants is used as a case study to illustratetimed SCR specifications.     

Voltage-Clock Scaling for Low Energy Consumption in Fixed-Priority Real-Time Systems

Power and energy constraints are becoming increasingly prevalent in real-time embedded systems. Voltage-scaling is a promising technique to reduce energy and power consumption: clock speed tends to decrease linearly with supply voltage while power consumption goes down quadratically. We therefore have a tradeoff between the energy consumption of a task and the speed with which it can be completed. The timing constraints associated with real-time tasks can be used to resolve this tradeoff. In this paper, we present two algorithms for voltage-scaling. Assuming that a processor can operate in one of two modes: high voltage and low voltage, we show how to schedule the voltage settings so that deadlines are met while reducing the total energy consumed. We show that significant reductions can be made in energy consumption.     

硬实时系统在强分区约束下的双层分区调度

文中研究了硬实时系统在强分区约束下的双层分区的调度问题,合理建立了强分区约束下的双层分区调度模型,给出了最坏情况下的分区任务集可调度的判定条件.同时,在此基础上,提出了与分区利用率匹配的分区设计方法,导出了该方法下的系统可调度利用率的最小上限.仿真实验表明,在严格实时的条件下,文中提出的方法相对于现有方法更具优越性,并提高了分区可调度利用率的最小上限.     

即时编译器中的轻量级指令调度算法

介绍了一种为即时编译器和时空受限系统设计的轻量级线性复杂指令调度算法。该算法进行指令调度时,不基于传统的DAG图或表达式树,而是基于一种独创的数据结构扩展关联矩阵,其时间复杂性在最坏情况下也能与全部指令长度构成严格的线性关系,仅占用不到1 KB的内存空间。该算法已被Intel为Xscale设计的高性能J2ME虚拟机XORP采用为即时编辑器中的缺省指令调度算法。     

基于对象的分布式实时系统调度模型研究

为了解决分布式实时系统有关分配和调度等问题，给出并用形式化方法描述了一种基于对象分布式实时系统调度的通用模型。该模型包括表示时限的绝对时间约束，表示周期属性的周期约束，表示各种前趋关系和同步要求的相对时间约束以及保证资源使用一致性的一致性约束，此外该模型克服了以往模型不能在应用系统的逻辑和功能部件上描述系统实时的约束的不足，允许从方法和活动上描述所需的约束，降低了单一约束描述的繁杂程度，为了能够使用现有调度算法进行任务调度，讨论了约束转换的问题，给出了高层约束到底层约束的转换规则和相应的转换算法。     

基于平滑调度的弱硬实时系统约束规范

约束规范是弱硬实时系统研究的基础。从弱硬实时系统的定义出发,提出了一个新的约束规范,它能够有效实现平滑调度。给出并证明了弱硬实时系统约束规范严格性比较的一个重要定理。业已证明,该约束规范具有良好的性能和较好的适用范围。     

Scheduling of Time-Triggered Real-Time Systems

Thispaper introduces a new class of applications for constraint programming.This new type of application originates out of a special classof real-time systems, enjoying increasing popularity in areassuch as automotive electronics and aerospace industry. Real-timesystems of this kind are time triggered in the sense that theiroverall behavior is globally controlled by a recurring clocktick. Being able to compute an appropriate pre-runtime scheduleautomatically is the major challenge for such an architecture.What makes this specific off-line scheduling problem somewhatuntypical is that a potentially indefinite, periodic processinghas to be mapped onto a single time window. In this article wewill show how this problem can be solved by constraint programmingand we will describe which techniques from traditional schedulingand real-time computing led to success and which failed whenconfronted with a large-scale application of this type. The techniquesthat proved to be the most successful were special global constraintsand an elaborate search heuristics from Operations Research.Also for finding a valid schedule mere serialization is shownto be sufficient. The actual implementation was done in the concurrentconstraint programming language Oz.     

光纤通道交换机在强实时约束下的分组调度

以光纤通道交换网络强实时约束下的性能研究为背景,采用实时通信中的周期性任务模型,提出了负载匹配的加权轮循分组调度,导出了在该方法下网络消息集严格实时的充要条件,以最差情形下强实时的网络可达负载率为性能衡量指标推证了采用该算法的优越性并通过仿真进行了验证.     

Schedulability-Driven Communication Synthesis for Time Triggered Embedded Systems

We present an approach to static priority preemptive process scheduling for the synthesis of hard real-time distributed embedded systems where communication plays an important role. The communication model is based on a time-triggered protocol. We have developed an analysis for the communication delays with four different message scheduling policies over a time-triggered communication channel. Optimization strategies for the synthesis of communication are developed, and the four approaches to message scheduling are compared using extensive experiments.     

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.     

Threaded Prefetching: A New Instruction Memory Hierarchy for Real-Time Systems

Cache memories have been extensively used to bridge the speed gap between high speed processors and relatively slow main memory. However, they are not widely used in real-time systems due to their unpredictable performance. This paper proposes an instruction prefetching scheme called threaded prefetching as an alternative to instruction caching in real-time systems. In the proposed threaded prefetching, an instruction block pointer called a thread is assigned to each instruction memory block and is made to point to the next block on the worst case execution path that is determined by a compile-time analysis. Also, the thread is not updated throughout the entire program execution to guarantee predictability. This paper also compares the worst case performances of various previous instruction prefetching schemes with that of the proposed threaded prefetching. By analyzing several benchmark programs, we show that the worst case performance of the proposed scheme is significantly better than those of previous instruction prefetching schemes. The results also show that when the block size is large enough the worst case performance of the proposed threaded prefetching scheme is almost as good as that of an instruction cache with 100 % hit ratio.