Cross‐profiling for Java processors

Performance evaluation of embedded software is essential in an early development phase so as to ensure that the software will run on the embedded device's limited computing resources. The prevailing approaches either require the deployment of the software on the embedded target, which can be tedious and may be impossible in an early development phase, or rely on simulation, which can be very slow. In this article, we introduce a customizable cross‐profiling framework for embedded Java processors, including processors featuring a method cache. The developer profiles the embedded software in the host environment, completely decoupled from the target system, on any standard Java virtual machine, but the generated profiles represent the execution time metric of the target system. Our cross‐profiling framework is based on bytecode instrumentation. We identify several pointcuts in the execution of bytecode that need to be instrumented in order to estimate the CPU cycle consumption on the target system. An evaluation using the JOP embedded Java processor as target confirms that our approach reconciles high profile accuracy with moderate overhead. Our cross‐profiling framework also enables the performance evaluation of new processor architectures before they are implemented. As a case study, we explore the performance impact of various processor design choices and optimizations, such as different cache sizes or pipeline organizations, and come up with an improved processor design that yields speedups of up to 40% on standard Java benchmarks. Copyright © 2009 John Wiley & Sons, Ltd.     

Scalable and precise refinement of cache timing analysis via path-sensitive verification

Hard real-time systems require absolute guarantees in their execution times. Worst case execution time (WCET) of a program has therefore become an important problem to address. However, performance enhancing features of a processor (e.g. cache) make WCET analysis a difficult problem. In this paper, we propose a novel analysis framework by combining abstract interpretation and program verification for different varieties of cache analysis ranging from single to multi-core platforms. Our framework can be instantiated with different program verification techniques, such as model checking and symbolic execution. Our modeling is used to develop a precise yet scalable timing analysis method on top of the Chronos WCET analysis tool. Experimental results demonstrate that we can obtain significant improvement in precision with reasonable analysis time overhead.     

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

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

用于WCET静态分析的MIPS处理器建模方法研究

为获得安全而紧致的WCET估计，需要考虑执行程序的目标处理器的体系结构特征．Cache、流水线等用于提高性能的技术已经广泛地应用于现代处理器中，如果在静态分析过程中不考虑它们带来的影响，必然会导致WCET过估计．以Petri网作为模型工具，以WCET分析为应用目标构造MIPS处理器的体系结构模型，该方法讨论了各种RISC处理器中常见的体系结构特征的抽象以及它们在Petri网模型中的表示方法．通过实验验证，指令序列在Petri网模型上的模拟执行时间与指令序列在DLXView模拟器上的测试结果具有一致性，表明构建处理器的体系结构Petri网模型是一种有效的指令序列执行时间的静态分析方法．     

一种面向实时系统的程序基本块指令预取技术

面向通用计算机系统的指令预取技术无法满足实时系统的应用需求,其中一个重要原因是：无效预取引起的指令Cache内容污染使得实时任务WCET评估值不够精确,导致系统可调度性下降,严重影响系统效率.以简化实时任务WCET分析、降低任务WCET评估值为目标,提出一种基于程序基本块的指令预取方法.该方法以基本块为粒度执行指令预取,避免了传统指令预取技术引入的无效预取;通过简化最坏情况下的指令访问命中/缺失情况判定,简化任务WCET分析过程并优化WCET评估值.实时基准测试程序评估结果表明：与常规无预取方法相比,该预取方法可使实时任务WCET评估值降低约20%,平均执行情况下的指令Cache访问性能提升约10%.     

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可预测的Java指令集硬件实现

为能以硬件方式直接执行CISC结构的Java字节码,设计并实现适用于32位嵌入式实时Java平台的JPOR-32指令集。分析Java虚拟机规范中各Java字节码的功能和实现原理,设定执行每条指令时信号和数据在Java处理器数据通路上的变化,采用微指令方式执行复杂指令,简单指令直接执行,从而使JPOR-32的指令集具有RISC特性。实验结果验证了指令集的正确性及其最坏情况执行时间(WCET)的可预测性。     

一种基于抽象解释的WCET自动分析工具

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

Data cache organization for accurate timing analysis

Caches are essential to bridge the gap between the high latency main memory and the fast processor pipeline. Standard processor architectures implement two first-level caches to avoid a structural hazard in the pipeline: an instruction cache and a data cache. For tight worst-case execution times it is important to classify memory accesses as either cache hit or cache miss. The addresses of instruction fetches are known statically and static cache hit/miss classification is possible for the instruction cache. The access to data that is cached in the data cache is harder to predict statically. Several different data areas, such as stack, global data, and heap allocated data, share the same cache. Some addresses are known statically, other addresses are only known at runtime. With a standard cache organization all those different data areas must be considered by worst-case execution time analysis. In this paper we propose to split the data cache for the different data areas. Data cache analysis can be performed individually for the different areas. Access to an unknown address in the heap does not destroy the abstract cache state for other data areas. Furthermore, we propose to use a small, highly associative cache for the heap area. We designed and implemented a static analysis for this cache, and integrated it into a worst-case execution time analysis tool.     

Scheduling of hard real-time garbage collection

Automatic memory management or garbage collection greatly simplifies development of large systems. However, garbage collection is usually not used in real-time systems due to the unpredictable temporal behavior of current implementations of a garbage collector. In this paper we propose a real-time garbage collector that can be scheduled like a normal real-time thread with a deadline monotonic assigned priority. We provide an upper bound for the collector period so that the application threads will never run out of memory. Furthermore, we show that the restricted execution model of the Safety Critical Java standard simplifies root scanning and reduces copying of static data. Our proposal has been implemented and evaluated in the context of the Java processor JOP.     

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

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

An accurate worst case timing analysis for RISC processors

An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each program construct is a simple time bound. In our approach, associated with each program construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. The paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach     

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.     

一种实时Java处理器''''区域''''内存实现模型

Java实时规范（RTSJ）提出的‘区域’内存（Scoped Memory）既避免了垃圾回收对系统实时性的影响，又能充分利用内存空间，引起了众多研究人员的重视．本文讨论了‘区域’内存的实现及影响最坏情况下执行时间（WCET）的因素，并提出一种针对嵌入式实时Java处理器的‘区域’内存实现模型．该模型中非实时处理在字节码被执行之前完成，消除了运行时管理‘区域’内存对WCET的影响，在简化处理器实现的同时保证了运行时WCET的可预测性．     

Flow‐sensitive runtime estimation: an enhanced hot spot detection heuristics for embedded Java just‐in‐time compilers

Java just‐in‐time compilers often compile only hot methods because the compilation overhead is a part of the running time. This requires precise and efficient hot spot detection, which includes distinguishing hot methods from cold ones, detecting them as early as possible, and paying a small detection overhead. Hot spot detection is especially important in embedded applications because they show more of a start‐up phase behavior of a regular application where methods are not executed heavily, so the hot methods are not definite. Because a long‐running method is likely to be a hot method, we can detect a hot method by measuring its running time during interpretation. However, precise measurement of the running time during execution is too expensive, especially in embedded systems, so many counter‐based heuristics have been proposed to estimate it such as Oracle's HotSpot heuristic. One problem is that although the overhead of these heuristics is low, they do not estimate the running time precisely, which may lead to imprecise hot spot detection.This paper proposes a new hot spot detection heuristic called flow‐sensitive runtime estimation, which can estimate the running time more precisely than others with a relatively low overhead. It only counts important bytecode instructions dynamically, but it can obtain the precise count of all interpreted bytecode instructions with a simple arithmetic calculation. We also propose a static analysis technique to predict those hot methods which spends a huge execution time once invoked, so as to compile them at their first invocation. Our experimental results show that these techniques can improve the performance by as much as an average of 7.4% compared with the HotSpot heuristic for the benchmarks when they run once, which is often regarded as showing the start‐up phase behavior. Even for real embedded Java applications such as the digital TV Java Xlet applications, our techniques can improve the user response time by an average of 7.1%. Copyright © 2015 John Wiley & Sons, Ltd.     

Reducing the Upper Bound Delay by Optimizing Bank-to-Core Mapping

Nowadays, inter-task interferences are the main difficulty in analyzing the timing behavior of multicores. The timing predictable embedded multicore architecture MERASA, which allows safe worst-case execution time (WCET) estimations, has emerged as an attractive solution. In the architecture, WCET can be estimated by the upper bound delay (UBD) which can be bounded by the interference-aware bus arbiter (IABA) and the dynamic cache partitioning such as columnization or bankization. However, this architecture faces a dilemma between decreasing UBD and efficient shared cache utilization. To obtain tighter WCET estimation, we propose a novel approach that reduces UBD by optimizing bank-to-core mapping on the multicore system with IABA and the two-level partitioned cache. For this, we first present a new UBD computation model based on the analysis of inter-task interference delay, and then put forward the core-sequence optimization method of bank-to-core mapping and the optimizing algorithms with the minimum UBD. Experimental results demonstrate that our approach can reduce WCET from 4% to 37%.     

Static worst-case execution time analysis of the μ C/OS-II real-time kernel

Worst-case execution time (WCET) analysis is one of the major tasks in timing validation of hard real-time systems. In complex systems with real-time operating systems (RTOS), the timing properties of the system are decided by both the applications and RTOS. Traditionally, WCET analysis mainly deals with application programs, while it is crucial to know whether RTOS also behaves in a timely predictable manner. In this paper, static analysis techniques are used to predict the WCET of the system calls and the Disable Interrupt regions of the μC/OS-II real-time kernel, which presents a quantitative evaluation of the real-time performance of μC/OS-II. The precision of applying existing WCET analysis techniques on RTOS is evaluated, and the practical difficulties in using static methods in timing analysis of RTOS are also discussed.     

一种用于硬实时Java处理器的类转换器设计及实现

通过分析Class文件处理过程及其中影响实时性的操作，提出一种用于硬实时Java处理器的类转换器，它读取标准Class文件，处理并生成适合Java处理器直接执行的内存映像文件．由于装载、连接过程中大量操作（如符号引用的解析）都由类转换器提前处理完毕，使得Java处理器操作大为简化．同时，由于所有影响Java处理器实时性的操作也由类转换器提前处理，Java处理器最坏情况执行时间（Worst Case Execution Time）完全可预测．     

Lightweight Bytecode Verification

In this paper, we provide a theoretical foundation for and improvements to the existing bytecode verification technology, a critical component of the Java security model, for mobile code used with the Java “micro edition” (J2ME), which is intended for embedded computing devices. In Java, remotely loaded “bytecode” class files are required to be bytecode verified before execution, that is, to undergo a static type analysis that protects the platform's Java run-time system from so-called type confusion attacks such as pointer manipulation. The data flow analysis that performs the verification, however, is beyond the capacity of most embedded devices because of the memory requirements that the typical algorithm will need. We propose to take a proof-carrying code approach to data flow analysis in defining an alternative technique called “lightweight analysis” that uses the notion of a “certificate” to reanalyze a previously analyzed data flow problem, even on poorly resourced platforms. We formally prove that the technique provides the same guarantees as standard bytecode safety verification analysis, in particular that it is “tamper proof” in the sense that the guarantees provided by the analysis cannot be broken by crafting a “false” certificate or by altering the analyzed code. We show how the Java bytecode verifier fits into this framework for an important subset of the Java Virtual Machine; we also show how the resulting “lightweight bytecode verification” technique generalizes and simulates the J2ME verifier (to be expected as Sun's J2ME “K-Virtual machine” verifier was directly based on an early version of this work), as well as Leroy's “on-card bytecode verifier,” which is specifically targeted for Java Cards.     

Checking secure information flow in Java bytecode by code transformation and standard bytecode verification

A method is presented for checking secure information flow in Java bytecode, assuming a multilevel security policy that assigns security levels to the objects. The method exploits the type‐level abstract interpretation of standard bytecode verification to detect illegal information flows. We define an algorithm transforming the original code into another code in such a way that a typing error detected by the Verifier on the transformed code corresponds to a possible illicit information flow in the original code. We present a prototype tool that implements the method and we show an example of application. Copyright © 2004 John Wiley & Sons, Ltd.