Overview of Real-Time Java Computing
---
paper_title: The worst-case execution-time problem—overview of methods and survey of tools

paper_content:

The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools1 and research prototypes.
---
paper_title: The real-time specification for Java

paper_content:

New languages, programming disciplines, operating systems, and software engineering techniques sometimes hold considerable potential for real-time software developers. A promising area of interest-but one fairly new to the real-time community-is object-oriented programming. Java, for example, draws heavily from object orientation and is highly suitable for extension to real-time and embedded systems. Recognizing this fit between Java and real-time software development, the Real-Time for Java Experts Group (RTJEG) began developing the real-time specification for Java (RTSJ) in March 1999 under the Java Community Process. This article explains RTSJ's features and the thinking behind the specification's design. The goal of the RTJEG, of which the authors are both members, was to provide a platform-a Java execution environment and application program interface (API)-that lets programmers correctly reason about the temporal behavior of executing software.
---
paper_title: Design and implementation of a comprehensive real-time java virtual machine

paper_content:

The emergence of standards for programming real-time systems in Java has encouraged many developers to consider its use for systems previously only built using C, Ada, or assembly language. However, the RTSJ standard in isolation leaves many important problems unaddressed, and suffers from some serious problems in usability and safety. As a result, the use of Java for real-time programming has continued to be viewed as risky and adoption has been slow. In this paper we provide a description of IBM's new real-time Java virtual machine product, which combines Metronome real-time garbage collection, ahead-of-time compilation, and a complete implementation of the RTSJ standard, running on top of a custom real-time multiprocessor Linux kernel. We will describe the implementation of each of these components, including how they interacted both positively and negatively, and the extensions to previous work required to move it from research prototype to a system implementing the complete semantics of the Java language. The system has been adopted for hard real-time development of naval weapons systems and soft real-time telecommunications servers. We present measurements showing that the system is able to provide sub-millisecond worst-case garbage collection latencies, 50 microsecond Linux scheduling accuracy, and eliminate non-determinism due to JIT compilation.
---
paper_title: A Real-time Java Virtual Machine for Avionics - An Experience Report

paper_content:

We report on our experience with the implementation of the Real-time Specification for Java (RTSJ) in the DARPA Program Composition for Embedded System (PCES) program. Within the scope of PCES, Purdue University and the Boeing Company collaborated on the development of Ovm, an open source implementation of the RTSJ virtual machine. Ovm was deployed on a ScanEagle Unmanned Aerial Vehicle and successfully flight tested during the PCES Capstone Demonstration.
---
paper_title: Java for Safety-Critical Applications

paper_content:

In recent years, various approaches to real-time execution of Java have proven their worth in numerous commercial and defense applications. The Real-time Specification for Java has extended the Java platform with a range of features needed for real-time computing. As the use of real-time Java has become more widespread, the demand for Java in real-time applications with safety requirements has led to an eort to define a new standard—JSR-302 Safety-Critical Java (SCJ). The goal of this standard is to facilitate the creation of safety-critical Java applications capable of certification under standards such as DO 178B level A or IEC61508 for SIL 4. JSR-302 is nearing completion and will soon be released for public review. This paper introduces some of the primary goals, challenges, and proposed solutions for safety-critical Java and its relationship with the Real-time Specification for Java.
---
paper_title: The real-time specification for Java

paper_content:

New languages, programming disciplines, operating systems, and software engineering techniques sometimes hold considerable potential for real-time software developers. A promising area of interest-but one fairly new to the real-time community-is object-oriented programming. Java, for example, draws heavily from object orientation and is highly suitable for extension to real-time and embedded systems. Recognizing this fit between Java and real-time software development, the Real-Time for Java Experts Group (RTJEG) began developing the real-time specification for Java (RTSJ) in March 1999 under the Java Community Process. This article explains RTSJ's features and the thinking behind the specification's design. The goal of the RTJEG, of which the authors are both members, was to provide a platform-a Java execution environment and application program interface (API)-that lets programmers correctly reason about the temporal behavior of executing software.
---
paper_title: Ravenscar-Java: a high integrity profile for real-time Java

paper_content:

For many, Java is the antithesis of a high integrity programming language. Its combination of object-oriented programming features, its automatic garbage collection, and its poor support for real-time multi-threading are all seen as particular impediments. The Real-Time Specification for Java has introduced many new features that help in the real-time domain. However, the expressive power of these features means that very complex programming models can be created, necessitating complexity in the supporting real-time virtual machine. Consequently, Java, with the real-time extensions as they stand, seems too complex for confident use in high integrity systems. This paper presents a Java profile for the development of software-intensive high integrity real-time systems. This restricted programming model removes language features with high overheads and complex semantics, on which it is hard to perform timing and functional analyses. The profile fits within the J2ME framework and is consistent with well-known guidelines for high integrity software development, such as those defined by the U.S. Nuclear Regulatory Commission.
---
paper_title: Efficient microarchitecture modeling and path analysis for real-time software

paper_content:

Real-time systems are characterized by the presence of timing constraints in which a task must be completed within a specific amount of time. This paper examines the problem of determining the bound on the worst case execution time (WCET) of a given program on a given processor There are two important issues in solving this problem: (i) program path analysis, which determines what sequence of instructions will be executed in the worst case, and (ii) microarchitecture modeling, which models the hardware system and determines the WCET of a known sequence of instructions. To obtain a tight estimate on the bound both these issues must be addressed accurately and efficiently. The latter is becoming difficult to model for modern processors due to the presence of pipelined instruction execution units and cached memory systems. Because of the complexity of the problem, all existing methods that we know of focus only on one of above issues. This limits the accuracy of the estimated bound and the size of the program that can be analyzed. We present a more effective solution that addresses both issues and uses an integer linear programming formulation to solve the problem. This solution is implemented in the program cinderella which currently targets the Intel i960KB processor and we present some experimental results of using this tool.
---
paper_title: Java virtual-machine support for portable worst-case execution-time analysis

paper_content:

The current trend towards the usage of Java in real-time, supported by two specifications (Real-Time Java and Real-Time Core extensions for the Java platform) requires adequate schedulability analysis, and consequently, worst case execution time (WCET) analysis techniques for the Java platform. This paper proposes a framework for providing portable WCET analysis for the Java platform. Portability means that the analysis is language and hardware independent. It is achieved by, separating the WCET analysis process in three stages and by analysing the Java byte code, not the high-level source code, thus enabling the analysis of programs written in other languages (such as Ada and compiled for the Java virtual machine). The three stages are: a Java virtual machine platform dependent (low-level) analysis, a software dependent (high-level) analysis and an on-line integration step.
---
paper_title: Portable worst-case execution time analysis using Java Byte Code

paper_content:

Addresses the problem of performing worst-case execution time (WCET) analysis of Java Byte Code (JBC), which may be generated from different compilers and from different source languages. The motivation for the framework presented is to provide WCET analysis which is portable and therefore more likely to be used in an industrial context. Two issues are addressed in this paper: how to extract data flow and control flow information from JBC programs, and how to provide a compiler-/language-independent mechanism to introduce WCET annotations in the source code. We show that an annotation mechanism based on calls to a static class with empty methods result in similar code when generated by Java or Ada compilers.
---
paper_title: Timing anomalies in dynamically scheduled microprocessors

paper_content:

Previous timing analysis methods have assumed that the worst-case instruction execution time necessarily corresponds to the worst-case behavior. We show that this assumption is wrong in dynamically scheduled processors. A cache miss, for example, can in some cases result in a shorter execution time than a cache hit. Many examples of such timing anomalies are provided. We first provide necessary conditions when timing anomalies can show up and identify what architectural features that may cause such anomalies. We also show that analyzing the effect of these anomalies with known techniques results in prohibitive computational complexities. Instead, we propose some simple code modification techniques to make it impossible for any anomalies to occur. These modifications make it possible to estimate WCET by known techniques. Our evaluation shows that the pessimism imposed by these techniques is fairly limited; it is less than 27% for the programs in our benchmark suite.
---
paper_title: Modeling Shared Cache and Bus in Multi-cores for Timing Analysis

paper_content:

Timing analysis of concurrent programs running on multi-core platforms is currently an important problem. The key to solving this problem is to accurately model the timing effects of shared resources in multi-cores, namely shared cache and bus. In this paper, we provide an integrated timing analysis framework that captures timing effects of both shared cache and shared bus. We also develop a cycle-accurate simulation infra-structure to evaluate the precision of our analysis. Experimental results from a large fragment of an in-orbit spacecraft software show that our analysis produces around 20% over-estimation over simulation results.
---
paper_title: The worst-case execution-time problem—overview of methods and survey of tools

paper_content:

The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools1 and research prototypes.
---
paper_title: Multicore Real-Time Scheduling to Reduce Inter-Thread Cache Interferences

paper_content:

The worst-case execution time (WCET) of each real-time task in multicore processors with shared caches can be significantly affected by inter-thread cache interferences. The worst-case inter-thread cache interferences are dependent on how tasks are scheduled to run on different cores. Therefore, there is a circular dependence between real-time task scheduling, the worst-case inter-thread cache interferences, and WCET in multicore processors, which is not the case for single-core processors. To address this challenging problem, we present an offline real-time scheduling approach for multicore processors by considering the worst-case inter-thread interferences on shared L2 caches. Our scheduling approach uses a greedy heuristic to generate safe schedules while minimizing the worst-case inter-thread shared L2 cache interferences and WCET. The experimental results demonstrate that the proposed approach can reduce the utilization of the resulting schedule by about 12% on average compared to the cyclic multicore scheduling approaches in our theoretical model. Our evaluation indicates that the enhanced scheduling approach is more likely to generate feasible and safe schedules with stricter timing constraints in multicore real-time systems.
---
paper_title: Addressing dynamic dispatching issues in WCET analysis for object-oriented hard real-time systems

paper_content:

There is a trend towards using object-oriented programming languages to develop hard real-time applications. However some object-oriented features, such as dynamic dispatching and dynamic loading, are prohibited from being used in hard realtime systems because they are either unpredictable and/or un-analysable. Arguably, these restrictions could make applications very limited and unrealistic since they could eliminate the major advantages of object-oriented programming. This paper demonstrates how we can address the dynamic dispatching issues in Worst-Case Execution Timing (WCET) analysis with minimum annotations. The major contributions include: discussing the major issues involved in using and restricting dynamic binding features; weakening the restriction of using dynamic dispatching; presenting how to estimate tighter and safer WCET value in object-oriented hard real-time systems. Our approach shows that allowing the use of dynamic dispatching can not only provide a more flexible way to develop object-oriented hard real-time applications, but also does not necessarily result in unpredictable timing analysis.
---
paper_title: Performance analysis of embedded software using implicit path enumeration

paper_content:

Embedded computer systems are characterized by the presence of a processor running application specific dedicated software. A large number of these systems must satisfy real-time constraints. This paper examines the problem of determining the extreme (best and worst) case bounds on the running time of a given program on a given processor. This has several applications in the design of embedded systems with real-time constraints. An important aspect of this problem is determining which paths in the program are exercised in the extreme cases. The state of the art solution here relies on an explicit enumeration of program paths. This runs out of steam rather quickly since the number of feasible program paths is typically exponential in the size of the program. We present a solution for this problem that does not require an explicit enumeration of program paths, i.e., the paths are considered implicitly. This solution is implemented in the program cinderella1 which currently targets a popular embedded processor --- the Intel i960. The preliminary results of using this tool are also presented here.
---
paper_title: A Model Checking Based Approach to Bounding Worst-Case Execution Time for Multicore Processors

paper_content:

As multicore processors are increasingly adopted in industry, it has become a great challenge to accurately bound the worst-case execution time (WCET) for real-time systems running on multicore chips. This is particularly true because of the inter-thread interferences in accessing shared resources on multicores, such as shared L2 caches, which can significantly affect the performance but are very difficult to be estimated statically. This article proposes an approach to analyzing WCET for multicore processors with shared L2 instruction caches by using a model checking based method. We model each concurrent real-time thread, including the inter-thread cache interferences with a PROMELA process, and derive the WCET by using a binary search algorithm. To reduce the state explosion problem, we propose several techniques for reducing the memory consumption by exploiting domain-specific information. Our experiments indicate that compared to the static analysis technique based on extended ILP (integer linear programming), our approach improves the tightness of WCET estimation by more than 31.1p for the benchmarks we studied. However, due to the inherent complexity of multicore timing analysis and the state explosion problem, the model checking based approach currently can only work with small real-time kernels for dual-core processors.
---
paper_title: Combining Abstract Interpretation with Model Checking for Timing Analysis of Multicore Software

paper_content:

It is predicted that multicores will be increasingly used in future embedded real-time systems for high performance and low energy consumption. The major obstacle is that we may not predict and provide any guarantee on real-time properties of software on such platforms. The shared memory bus is among the most critical resources, which severely degrade the timing predictability of multicore software due to the access contention between cores. In this paper, we study a multicore architecture where each core has a local L1 cache and all cores use a shared bus to access the off-chip memory. We use Abstract Interpretation (AI) to analyze the local cache behavior of a program running on a dedicated core. Based on the cache analysis, we construct a Timed Automaton (TA) to model when the programs access the memory bus. Then we model the shared bus also using timed automata. The TA models for the bus and programs will be explored using the UPPAAL model checker to find the WECTs for the respective programs. Based on the presented techniques, we have developed a tool for multicore timing analysis, which allows automatic generation of the TA models from binary code and WCET estimation for any given TA model of the shared bus. Extensive experiments have been conducted, showing that the combined approach can significantly tighten the estimations. As examples, we have studied the TDMA and FCFS buses, of which the WCET bounds can be tightened by up to 240% and 82% respectively, compared with the worst-case bounds estimated based on worst-case bus access delay.
---
paper_title: WCET Analysis for Multi-Core Processors with Shared L2 Instruction Caches

paper_content:

Multi-core chips have been increasingly adopted by microprocessor industry. For real-time systems to safely harness the potential of multi-core computing, designers must be able to accurately obtain the worst-case execution time (WCET) of applications running on multi-core platforms, which is very challenging due to the possible runtime inter-core interferences in using shared resources such as the shared L2 caches. As the first step toward time-predictable multi-core computing, this paper presents a novel approach to bounding the worst-case performance for threads running on multi-core processors with shared L2 instruction caches. The idea of our approach is to compute the worst-case instruction access interferences between different threads based on the program control flow information of each thread, which can be statically analyzed. Our experiments indicate that the proposed approach can reasonably estimate the worst- case shared L2 instruction cache misses by considering inter-thread instruction conflicts. Also, the WCET of applications running on multi-core processors estimated by our approach is much better than the estimation by simply assuming all L2 instruction accesses are misses.
---
paper_title: A multithreaded Java microcontroller for thread-oriented real-time event-handling

paper_content:

We propose a multithreaded Java microcontroller (called Komodo microcontroller) with a new hardware event handling mechanism that allows handling of simultaneous overlapping events with hard real-time requirements. Real-time Java threads are used as interrupt service threads (ISTs) instead of interrupt service routines (ISRs). Our proposed Komodo microcontroller supports multiple ISTs with zero-cycle context switching overhead. We evaluate the basic architectural attributes using real-time event parameters of an autonomous guided vehicle. When calculating the maximum vehicle speed without violating the real-time constraints, ISTs dominate ISRs by a speed increase of 28%.
---
paper_title: Modeling out-of-order processors for software timing analysis

paper_content:

Estimating the worst case execution time (WCET) of a program on a given processor is important for the schedulability analysis of real-time systems. WCET analysis techniques typically model the timing effects of microarchitectural features in modern processors (such as the pipeline, caches, branch prediction, etc.) to obtain safe but tight estimates. In this paper, we model out-of-order processor pipelines for WCET analysis. This analysis is, in general, difficult even for a basic block (a sequence of instructions with single-entry and single-exit points) if some of the instructions have variable latencies. This is because the WCET of a basic block on out-of-order pipelines cannot be obtained by assuming maximum latencies of the individual instructions. Our timing estimation technique for a basic block is inspired by an existing performance analysis technique for tasks with data dependencies and resource contentions in real-time distributed systems. We extend our analysis by modeling the interaction among consecutive basic blocks as well as the effect of instruction cache. Finally, we employ integer linear programming (ILP) to compute the WCET of an entire program. The accuracy of our analysis is demonstrated via tight estimates obtained for several benchmarks.
---
paper_title: Worst-Case Execution Time Based Optimization of Real-Time Java Programs

paper_content:

Standard compilers optimize execution time for the average case. However, in hard real-time systems the worst-case execution time (WCET) is of primary importance. Therefore, a compiler for real-time systems shall include optimizations that aim to minimize the WCET. One effective compiler optimization is method in lining. It is especially important for languages, like Java, where small setter and getter methods are considered good programming style. In this paper we present and explore WCET driven in lining of Java methods. We use the WCET analysis tool for the Java processor JOP to guide to optimization along the worst-case path. The tool JCopter is integrated with the WCET analysis tool and is used to explore different in lining strategies. On real-time benchmarks the optimization results in a reduction of the WCET by a few percent up to a factor of about 2.
---
paper_title: WCET analysis of reusable portable code

paper_content:

Traditional worst-case execution-time analysis (WCET analysis) computes upper bounds for the execution times of code. This analysis uses knowledge about the execution contest of the code and about the target architecture. In contrast, the WCET analysis for reusable and portable code has to abstract from parameters that are unknown until the code is finally used. The analysis is done in two steps. The first step computes abstract WCET information to support the reuse and portability of the WCET information. The second step uses the abstract WCET information to compute concrete WCET bounds when the application context and the timing parameters of the target system are known. The paper describes each of the two analysis steps. It demonstrates how WCET information can be made portable and reusable.
---
paper_title: WCET analysis of instruction caches with prefetching

paper_content:

Instruction prefetching is an effective technique to reduce the instruction cache miss latency for improving the average-case performance. For real-time systems, however, the use of instruction prefetching will only besuitable if a reasonably tight worst-case performance of programs using instruction prefetching can be predicted. This paper presents an approach to modeling and computing the worst-case instruction cache performance with prefetching. Our experimental results indicate that instruction prefetching can benefit both the average-case and worst-case performance; however, the degree of the worst-case performance improvement due to instruction prefetching is less than that of the average-case performance, thus leading to increased time variation for real-time computing. Also, we find that the prefetching distance can significantly impact the worst-case performance analysis with instruction prefetching. Particularly, when the prefetching distance is equal to the L1 miss penalty, the worst-case execution time with instruction prefetching is minimized (i.e., optimal).
---
paper_title: Toward a Unified Standard for Worst-Case Execution Time Annotations in Real-Time Java

paper_content:

As real-time systems become more prevalent, there is a need to guarantee that these increasingly complex systems perform as designed. One technique involves a static analysis to place an upper bound on worst-case execution time (WCET). This temporal analysis cannot be made automatic and normally requires source annotations to assist a WCET analysis tool. At the same time, there is a growing interest in using Java for real-time systems. Several WCET analysis prototypes for Java have been created, and more are under development. Each relies on a competing and incompatible convention for annotations, resulting in portability problems and duplication of effort. We propose that Java's own annotation mechanism should be used to address such issues. These built-in annotations provide a common platform for WCET analysis, improving portability and reducing the effort necessary to create these vital tools. We examine the features that make Java's annotation standard attractive for WCET analysis, then discuss its current failings and make recommendations for future improvements.
---
paper_title: XRTJ: An Extensible Distributed High-Integrity Real-Time Java Environment

paper_content:

Despite Java’s initial promise of providing a reliable and cost-effective platform-independent environment, the language appears to be unfavourable in the area of high-integrity systems and real-time systems. To encourage the use of Java in the development of distributed high-integrity real-time systems, the language environment must provide not only a well-defined specification or subset, but also a complete environment with appropriate analysis tools. We propose an extensible distributed high-integrity real-time Java environment, called XRTJ, that supports three attributes, i.e., predictable programming model, dependable static analysis environment, and reliable distributed run-time environment. The goal of this paper is to present an overview of our on-going project and report on its current status. We also raise some important issues in the area of distributed high-integrity systems, and present how we can deal with them by defining two distributed run-time models where safe and timely operations will be supported.
---
paper_title: Static Timing Analysis of Shared Caches for Multicore Processors

paper_content:

The state-of-the-art techniques in multicore timing analysis are limited to analyze multicores with shared instruction caches only. This paper proposes a uniform framework to analyze the worst-case performance for both shared instruction caches and data caches in a multicore platform. Our approach is based on a new concept called address flow graph, which can be used to model both instruction and data accesses for timing analysis. Our experiments, as a proof-of-concept study, indicate that the proposed approach can accurately compute the worst-case performance for real-time threads running on a dual-core processor with a shared L2 cache (either to store instructions or data). Category: Embedded computing
---
paper_title: Bounding worst-case instruction cache performance

paper_content:

The use of caches poses a difficult tradeoff for architects of real-time systems. While caches provide significant performance advantages, they have also been viewed as inherently unpredictable, since the behavior of a cache reference depends upon the history of the previous references. The use of caches is only suitable for real-time systems if a reasonably tight bound on the performance of programs using cache memory can be predicted. This paper describes an approach for bounding the worst-case instruction cache performance of large code segments. First, a new method called static cache simulation is used to analyze a program's control flow to statically categorize the caching behavior of each instruction. A timing analyzer, which uses the categorization information, then estimates the worst-case instruction cache performance for each loop and function in the program. >
---
paper_title: Bus-Aware Multicore WCET Analysis through TDMA Offset Bounds

paper_content:

In the domain of real-time systems, the analysis of the timing behavior of programs is crucial for guaranteeing the schedulability and thus the safeness of a system. Static analyses of the WCET (Worst-Case Execution Time) have proven to be a key element for timing analysis, as they provide safe upper bounds on a program's execution time. For single-core systems, industrial-strength WCET analyzers are already available, but up to now, only first proposals have been made to analyze the WCET in multicore systems, where the different cores may interfere during the access to shared resources. An important example for this are shared buses which connect the cores to a shared main memory. The time to gain access to the shared bus may vary significantly, depending on the used bus arbitration protocol and the access timings. In this paper, we propose a new technique for analyzing the duration of accesses to shared buses. We implemented a prototype tool which uses the new analysis and tested it on a set of real world benchmarks. Results demonstrate that our analysis achieves the same precision as the best existing approach while drastically outperforming it in matters of analysis time.
---
paper_title: Cache Behavior Prediction by Abstract Interpretation

paper_content:

Abstract Interpretation is a technique for the static analysis of dynamic properties of programs. It is semantics based, that is, it computes approximative properties of the semantics of programs. On this basis, it allows for correctness proofs of analyzes. It thus replaces commonly used ad hoc techniques by systematic, provable ones, and it allows the automatic generation of analyzers from specifications as in the Program Analyzer Generator, PAG.
---
paper_title: Cache modeling for real-time software: beyond direct mapped instruction caches

paper_content:

We present a method for determining a tight bound on the worst case execution time of a program when running on a given hardware system with cache memory. Caches are used to improve the average memory performance, however, their presence complicates the worst case timing analysis. Any pessimistic predictions on cache hits/misses will result in loose estimation. In our previous research in this area, we built an integer-linear-programming solution for this problem which included analysis of direct mapped instruction caches. In this paper we describe the complex extensions of this technique to deal with set associative instruction caches, data caches and unified caches. We believe that this research now provides a comprehensive solution to the problem of worst case performance analysis of software running on processors with caches. These techniques have been implemented in a design tool cinderella. Some experimental results are presented that demonstrate the practical applicability of this analysis.
---
paper_title: Scope-Aware Data Cache Analysis for WCET Estimation

paper_content:

Caches are widely used in modern computer systems to bridge the increasing gap between processor speed and memory access time. On the other hand, presence of caches, especially data caches, complicates the static worst case execution time (WCET) analysis. Access pattern analysis (e.g., cache miss equations) are applicable to only a specific class of programs, where all array accesses must have predictable access patterns. Abstract interpretation-based methods (must/persistence analysis) determines possible cache conflicts based on coarse-grained memory access information from address analysis, which usually leads to significantly pessimistic estimation. In this paper, we first present a refined persistence analysis method which fixes the potential underestimation problem in the original persistence analysis. Based on our new persistence analysis, we propose a framework to combine access pattern analysis and abstract interpretation for accurate data cache analysis. We capture the dynamic behavior of a memory access by computing its temporal scope (the loop iterations where a given memory block is accessed for a given data reference) during address analysis. Temporal scopes as well as loop hierarchy structure (the static scopes) are integrated and utilized to achieve a more precise abstract cache state modeling. Experimental results shows that our proposed analysis obtains up to 74% reduction in the WCET estimates compared to existing data cache analysis.
---
paper_title: Timing Analysis of Concurrent Programs Running on Shared Cache Multi-Cores

paper_content:

Memory accesses form an important source of timing unpredictability. Timing analysis of real-time embedded software thus requires bounding the time for memory accesses. Multiprocessing, a popular approach for performance enhancement, opens up the opportunity for concurrent execution. However due to contention for any shared memory by different processing cores, memory access behavior becomes more unpredictable, and hence harder to analyze. In this paper, we develop a timing analysis method for concurrent software running on multi-cores with a shared instruction cache. Communication across tasks is by message passing where the message mailboxes are accessed via interrupt service routines. We do not handle data cache, shared memory synchronization and code sharing across tasks. Our method progressively improves the lifetime estimates of tasks that execute concurrently on multiple cores, in order to estimate potential conflicts in the shared cache. Possible conflicts arising from overlapping task lifetimes are accounted for in the hit-miss classification of accesses to the shared cache, to provide safe execution time bounds. We show that our method produces lower worst-case response time (WCRT) estimates than existing shared-cache analysis on a real-world embedded application.
---
paper_title: WCET Analysis of Multi-Level Set-Associative Data Caches

paper_content:

Nowadays, the presence of cache hierarchies tends to be a common trend in processor architectures, even in hardware for real-time embedded systems. Caches are used to fill the gap between the processor and the main memory, reducing access times based on spatial and temporal locality properties of tasks. Cache hierarchies are going even further however at the price of increased complexity. In this paper, we present a safe static data cache analysis method for hierarchies of non-inclusive caches. Using this method, we show that considering the cache hierarchy in the context of data caches allows tighter estimates of the worst case execution time than when considering only the first cache level. We also present considerations about the update policy for data caches.
---
paper_title: Low-level analysis of a portable Java byte code WCET analysis framework

paper_content:

To support portability, worst-case execution time (WCET) analysis of Java byte code is performed at two levels - machine-independent program flow analysis at a higher level and machine-dependent timing analysis of individual program constructs at a lower level. This paper contributes a WCET analysis that computes worst-case execution frequencies of Java byte codes within the software being analysed and accounts for platform-dependent information, i.e. the processor's pipeline. The main part of the approach is platform-independent; only a limited analysis is needed on a per-platform basis.
---
paper_title: Deriving Java Virtual Machine Timing Models for Portable Worst-Case Execution Time Analysis

paper_content:

Performing worst-case execution time (WCET) analysis on the highly portable real-time Java architectures without resulting in the under utilisation of the overall system has several challenges. Current WCET approaches are tied to either a particular language or target architecture. It should also be stressed that most WCET analysis approaches are usually only considered in relation to procedural programming languages. In this paper, we propose a comprehensive portable WCET analysis approach, and demonstrate how Java virtual machine timing models can be derived effectively on real-time and embedded Java-based systems.
---
paper_title: Scoped types and aspects for real-time Java memory management

paper_content:

Real-time systems are notoriously difficult to design and implement, and, as many real-time problems are safety-critical, their solutions must be reliable as well as efficient and correct. While higher-level programming models (such as the Real-Time Specification for Java) permit real-time programmers to use language features that most programmers take for granted (objects, type checking, dynamic dispatch, and memory safety) the compromises required for real-time execution, especially concerning memory allocation, can create as many problems as they solve. This paper presents Scoped Types and Aspects for Real-Time Systems (STARS) a novel programming model for real-time systems. Scoped Types give programmers a clear model of their programs' memory use, and, being statically checkable, prevent the run-time memory errors that bedevil the RTSJ. Adopting the integrated Scoped Types and Aspects approach can significantly improve both the quality and performance of a real-time Java systems, resulting in simpler systems that are reliable, efficient, and correct.
---
paper_title: Real-time Java scoped memory: design patterns and semantics

paper_content:

One of the most powerful features of the real-time specification for Java (RTSJ) is the new memory management model based on scoped memory areas. This model allows programmers to ensure timely reclamation of memory and predictable performance, at the cost of an unfamiliar programming model. We report on experience using and implementing scoped memory areas. Our contribution is twofold: (i) we give an informal introduction to the semantics of the scope management rules of the RTSJ, (ii) we present a number of design patterns for effectively using the scoped memory area API
---
paper_title: The real-time specification for Java

paper_content:

New languages, programming disciplines, operating systems, and software engineering techniques sometimes hold considerable potential for real-time software developers. A promising area of interest-but one fairly new to the real-time community-is object-oriented programming. Java, for example, draws heavily from object orientation and is highly suitable for extension to real-time and embedded systems. Recognizing this fit between Java and real-time software development, the Real-Time for Java Experts Group (RTJEG) began developing the real-time specification for Java (RTSJ) in March 1999 under the Java Community Process. This article explains RTSJ's features and the thinking behind the specification's design. The goal of the RTJEG, of which the authors are both members, was to provide a platform-a Java execution environment and application program interface (API)-that lets programmers correctly reason about the temporal behavior of executing software.
---
paper_title: An Implementation of Scoped Memory for Real-Time Java

paper_content:

This paper presents our experience implementing the memory management extensions in the Real-Time Specification for Java. These extensions are designed to given real-time programmers the control they need to obtain predictable memory system behavior while preserving Java's safe memory model.We describe our implementation of certain dynamic checks required by the Real-Time Java extensions. In particular, we describe how to perform these checks in a way that avoids harmful interactions between the garbage collector and the memory management system. We also found that extensive debugging support was necessary during the development of Real-Time Java programs. We therefore used a static analysis and a dynamic debugging package during the development of our benchmark applications.
---
paper_title: A real-time garbage collector with low overhead and consistent utilization

paper_content:

Now that the use of garbage collection in languages like Java is becoming widely accepted due to the safety and software engineering benefits it provides, there is significant interest in applying garbage collection to hard real-time systems. Past approaches have generally suffered from one of two major flaws: either they were not provably real-time, or they imposed large space overheads to meet the real-time bounds. We present a mostly non-moving, dynamically defragmenting collector that overcomes both of these limitations: by avoiding copying in most cases, space requirements are kept low; and by fully incrementalizing the collector we are able to meet real-time bounds. We implemented our algorithm in the Jikes RVM and show that at real-time resolution we are able to obtain mutator utilization rates of 45% with only 1.6--2.5 times the actual space required by the application, a factor of 4 improvement in utilization over the best previously published results. Defragmentation causes no more than 4% of the traced data to be copied.
---
paper_title: On scheduling garbage collector in dynamic real-time systems with statistical timing assurances

paper_content:

We consider garbage collection (GC) in dynamic real-time systems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain assurances on mutator timing behavior, while ensuring that memory is never exhausted. We present a scheduling algorithm called GCUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, variable execution time demands, the unimodal arbitrary arrival model that allows a strong adversary, and resource overloads. We establish several properties of GCUA including probabilistically-satisfied utility lower bounds for each mutator activity, a lower bound on the system-wide total accrued utility, bounded sensitivity for the assurances to variations in mutator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and confirm the algorithm's effectiveness and superiority.
---
paper_title: Hard real-time garbage collection in the Jamaica virtual machine

paper_content:

Java's automatic memory management is the main reason that prevents Java from being used in hard real-time environments. We present the garbage collection mechanism that is used by the Jamaica Virtual Machine, an implementation of the Java Virtual Machine Specification. This mechanism differs significantly from existing implementations in the way threads are implemented, root references are found and in the object layout that is used. The implementation provides hard real-time guarantees while it allows unrestricted use of the Java language. Even dynamic allocation of normal garbage collected Java objects is possible with hard real-time guarantees.
---
paper_title: A correct and useful incremental copying garbage collector

paper_content:

Designing a garbage collector with real-time properties is a particularlydifficult task, involving the construction of both an incremental run-timealgorithm as well as methods enabling a priori reasoning about schedulability in two dimensions (time and memory usage in conjunction). In order to comply with such ambitious goals with any amount of formal rigor, a comprehensive understanding of the actual algorithm used is of course a fundamental requirement. In this paper we present a formal model of an incremental copying garbage collector, where each atomic increment is modeled as a transition between states of a heap process. Soundness of the algorithm is shown by proving that the garbage collecting heap process is weakly bisimilar to a non-collecting heap with infinite storage space. In addition, we show that our collector is both terminating and useful, in the sense that it actually recovers the unreachable parts of any given heap in a finite number of steps.
---
paper_title: Time-triggered garbage collection: robust and adaptive real-time GC scheduling for embedded systems

paper_content:

The advent of Java and similar languages on the real-time system scene necessitates the development of efficient strategies for scheduling the work of a garbage collector in a non-intrusive way. We propose a scheduling strategy, time-triggered garbage collection, based on assigning the collector a deadline for when it must complete its current cycle.We show that a time-triggered GC with fixed deadline can have equal or better real-time performance than an allocation-triggered GC, which is the standard approach to real-time GC. Also, by using a deadline-based approach, the GC scheduling and, consequently, real-time performance, is independent of a complex and error-prone GC work metric.Time-triggered GC allows a more high-level view on GC scheduling; we look at the GC cycle level rather than at the individual work increments. This makes it possible to schedule GC as any other thread. It is also suitable for making the GC auto-tuning by dynamically adjusting its deadline as necessary.We have implemented our approach in a run-time system for Java and present experimental data to support the practical feasibility of the approach.
---
paper_title: Scheduling Garbage Collection in Embedded Systems

paper_content:

The complexity of systems for automatic control and other safety-critical applications grows rapidly. Computer software represents an increasing part of the complexity. As larger systems are developed, we need to find scalable techniques to manage the complexity in order to guarantee high product quality. Memory management is a key quality factor for these systems. Automatic memory management, or garbage collection, is a technique that significantly reduces the complex problem of correct memory management. The risk of software errors decreases and development time is reduced. Garbage collection techniques suitable for interactive and soft real-time systems exist, but few approaches are suitable for systems with hard real-time requirements, such as control systems (embedded systems). One part of the problem is solved by incremental garbage collection algorithms, which have been presented before. We focus on the scheduling problem which forms the second part of the problem, i.e. how the work of a garbage collector should be scheduled in order to disturb the application program as little as possible. It is studied how a priori scheduling analysis of systems with automatic memory management can be made. The field of garbage collection research is thus joined with the field of scheduling analysis in order to produce a practical synthesis of the two fields. A scheduling strategy is presented that employs the properties of control systems to ensure that no garbage collection work is performed during the execution of critical processes. The hard real-time part of the system is thus never disturbed by garbage collection work. Existing incremental garbage collection algorithms are adapted to the presented strategy. Necessary modifications of the algorithms and the real-time kernel are discussed. A standard scheduling analysis technique, rate monotonic analysis, is extended in order to make a priori analysis of the schedulability of the garbage collector possible. The scheduling algorithm has been implemented in an industrially relevant real-time environment in order to show that the strategy is feasible in practice. The experimental evaluation shows that predictable behaviour and sub-millisecond worst-case delays can be achieved on standard hardware even by a non-optimized prototype garbage collector. (Less)
---
paper_title: List processing in real time on a serial computer

paper_content:

A real-time list processing system is one in which the time required by the elementary list operations (e.g. CONS, CAR, CDR, RPLACA, RPLACD, EQ, and ATOM in LISP) is bounded by a (small) constant. Classical implementations of list processing systems lack this property because allocating a list cell from the heap may cause a garbage collection, which process requires time proportional to the heap size to finish. A real-time list processing system is presented which continuously reclaims garbage, including directed cycles, while linearizing and compacting the accessible cells into contiguous locations to avoid fragmenting the free storage pool. The program is small and requires no time-sharing interrupts, making it suitable for microcode. Finally, the system requires the same average time, and not more than twice the space, of a classical implementation, and those space requirements can be reduced to approximately classical proportions by compact list representation. Arrays of different sizes, a program stack, and hash linking are simple extensions to our system, and reference counting is found to be inferior for many applications.
---
paper_title: Performance of a hardware-assisted real-time garbage collector

paper_content:

Hardware-assisted real-time garbage collection offers high throughput and small worst-case bounds on the times required to allocate dynamic objects and to access the memory contained within previously allocated objects. Whether the proposed technology is cost effective depends on various choices between configuration alternatives. This paper reports the performance of several different configurations of the hardware-assisted real-time garbage collection system subjected to several different workloads. Reported measurements demonstrate that hardware-assisted real-time garbage collection is a viable alternative to traditional explicit memory management techniques, even for low-level languages like C++.
---
paper_title: A study of concurrent real-time garbage collectors

paper_content:

Concurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the microseconds level. Concurrent collectors also offer much better scalability over incremental collectors. The main problem with concurrent real-time collectors is their complexity. The first concurrent real-time garbage collector that can support fine synchronization, STOPLESS, has recently been presented by Pizlo et al. In this paper, we propose two additional (and different) algorithms for concurrent real-time garbage collection: CLOVER and CHICKEN. Both collectors obtain reduced complexity over the first collector STOPLESS, but need to trade a benefit for it. We study the algorithmic strengths and weaknesses of CLOVER and CHICKEN and compare them to STOPLESS. Finally, we have implemented all three collectors on the Bartok compiler and runtime for C# and we present measurements to compare their efficiency and responsiveness.
---
paper_title: On bounding time and space for multiprocessor garbage collection

paper_content:

This paper presents the first multiprocessor garbage collection algorithm with provable bounds on time and space. The algorithm is a real-time shared-memory copying collector. We prove that the algorithm requires at most 2(R(l + 2/k) + N + 5PD) memory locations, where P is the number of processors, R is the maximum reachable space during a computation (number of locations accessible from the root set), N is the maximum number of reachable objects, D is the maximum depth of any data object, and k is a parameter specifying how many locations are copied each time a location is allocated. Furthermore we show that client threads are never stopped for more than time proportional to k non-blocking machine instructions. The bounds are guaranteed even with arbitrary length arrays. The collector only requires write-barriers (reads are unaffected by the collector), makes few assumptions about the threads that are generating the garbage, and allows them to run mostly asynchronously.
---
paper_title: Sapphire: copying GC without stopping the world

paper_content:

Many concurrent garbage collection (GC) algorithms have been devised, but few have been implemented and evaluated, particularly for the Java programming language. Sapphire is an algorithm we have devised for concurrent copying GC. Sapphire stresses minimizing the amount of time any given application thread may need to block to support the collector. In particular, Sapphire is intended to work well in the presence of a large number of application threads, on small- to medium-scale shared memory multiprocessors. A specific problem that Sapphire addresses is not stopping all threads while thread stacks are adjusted to account for copied objects (in GC parlance, the “flip” to the new copies). Sapphire extends previous algorithms, and is most closely related to replicating copying collection, a GC technique in which application threads observe and update primarily the old copies of objects [13]. The key innovations of Sapphire are: (1) the ability to “flip” one thread at a time (changing the thread's view from the old copies of objects to the new copies), as opposed to needing to stop all threads and flip them at the same time; and (2) avoiding a read barrier.
---
paper_title: Minimizing memory requirement of real-time systems with concurrent garbage collector

paper_content:

Garbage collection is a key feature in modern programming languages like Java™. But it also brings some obstacles to real-time issues. Previous work had been put on solving the real-time problems of the garbage collector. Among it there are concurrent collectors that can provide truly real-time guarantees but they rely on a relatively large amount of redundant system memory. This paper concentrates on minimizing the system memory requirement with a new concurrent garbage collector which is based on a deferrable server together with a particular parameter configuration scheme proposed by this paper. The parameter configuration scheme is addressed using two different approaches, that is, the utilization based analysis and exact analysis of the selection of parameters. In this way, the worst-case response time of a garbage collector is minimized, and so is the worst-case system memory requirement, with the schedulability of tasks with hard time constraint not jeopardized. Furthermore, the simulation results demonstrate that, based on the new algorithm, the actual maximum system memory requirement for a given task set also becomes less than that of any previous concurrent collector.
---
paper_title: Stopless: a real-time garbage collector for multiprocessors

paper_content:

We present Stopless: a concurrent real-time garbage collector suitable for modern multiprocessors running parallel multithreaded applications. Creating a garbage-collected environment that supports real-time on modern platforms is notoriously hard,especially if real-time implies lock-freedom. Known real-time collectors either restrict the real-time guarantees to uniprocessors only, rely on special hardware, or just give up supporting atomic operations (which are crucial for lock-free software). Stopless is the first collector that provides real-time responsiveness while preserving lock-freedom, supporting atomic operations, controlling fragmentation by compaction, and supporting modern parallel platforms. Stopless is adequate for modern languages such as C# or Java. It was implemented on top of the Bartok compiler and runtime for C# and measurements demonstrate high responsiveness (a factor of a 100 better than previously published systems), virtually no pause times, good mutator utilization, and acceptable overheads.
---
paper_title: A parallel, real-time garbage collector

paper_content:

We describe a parallel, real-time garbage collector and present experimental results that demonstrate good scalability and good real-time bounds. The collector is designed for shared-memory multiprocessors and is based on an earlier collector algorithm [2], which provided fixed bounds on the time any thread must pause for collection. However, since our earlier algorithm was designed for simple analysis, it had some impractical features. This paper presents the extensions necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. An implementation based on the modified algorithm is evaluated on a set of 15 SML benchmarks on a Sun Enterprise 10000, a 64-way UltraSparc-II multiprocessor. To the best of our knowledge, this is the first implementation of a parallel, real-time garbage collector. The average collector speedup is 7.5 at 8 processors and 17.7 at 32 processors. Maximum pause times range from 3 ms to 5 ms. In contrast, a non-incremental collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. Compared to a non-parallel, stop-copy collector, parallelism has a 39% overhead, while real-time behavior adds an additional 12% overhead. Since the collector takes about 15% of total execution time, these features have an overall time costs of 6% and 2%.
---
paper_title: Compilation Techniques for Real-Time Java Programs

paper_content:

In this paper, we introduce the IBMreg WebSpherereg real time product, which incorporates a virtual machine that is fully Javatrade compliant as well as compliant with the Real-Time Specification for Java (RTSJ). We describe IBM's real-time Java enhancements, particularly in the area of our Testarossa (TR) ahead-of-time (AOT) compiler, our TR just-in-time (JIT) compiler, and our Metronome (Bacon, et al., 2003) deterministic garbage collector (GC). The main focus of this paper is on the various techniques employed by the TR compilers to optimize and regulate the performance of code running in a real-time Java environment through a simple Java source code example. Through the example, we highlight the additional checks required to provide a conformant RTSJ implementation as well as the performance issues with ahead-of-time code generation and the overheads required to support Metronome. We show how these checks are implemented in a production JVM, and then report the cost of the real-time changes in practice for the example as well as the SPECjvm98 benchmark suite, SPECjbb2000, and SPECjbb2005
---
paper_title: Does "Just in Time" = "Better Late than Never"?

paper_content:

The World-Wide Web is emerging as a medium for distributing platform-independent, intermediate-form programs. Most Java vendors have recently announced plans to construct "just-in-time" systems, which translate the intermediate text into native code on demand. In this paper, we present experiments that show the benefits of just-in-time systems as compared with the traditional (compile prior to execution) systems. We introduce a new method--the continuous compiler-- that can outperform just-in-time systems by overlapping compilation with program interpretation and native execution. Based on those results, we then present a smart just-in-time system that blends interpretation with native-code execution, thereby obtaining improved performance.
---
paper_title: Time-Predictable Java Dynamic Compilation on Multicore Processors

paper_content:

Java has been increasingly used in programming for real-time systems. However, some of Java’s features such as automatic memory management and dynamic compilation are harmful to time predictability. If these problems are not solved properly then it can fundamentally limit the usage of Java for real-time systems, especially for hard real-time systems that require very high time predictability. In this paper, we propose to exploit multicore computing in order to reduce the timing unpredictability that is caused by dynamic compilation and adaptive optimization. Our goal is to retain high performance comparable to that of traditional dynamic compilation, while at the same time, obtain better time predictability for Java virtual machine (JVM). We have studied pre-compilation techniques to utilize another core more efficiently, preoptimization on another core (PoAC) scheme to replace the adaptive optimization system (AOS) in Jikes JVM and the counter based optimization (CBO). Our evaluation reveals that the proposed approaches are able to attain high performance while greatly reducing the variation of the execution time for Java applications. Category: Embedded computing
---
paper_title: Continuous program optimization: A case study

paper_content:

Much of the software in everyday operation is not making optimal use of the hardware on which it actually runs. Among the reasons for this discrepancy are hardware/software mismatches, modularization overheads introduced by software engineering considerations, and the inability of systems to adapt to users' behaviors.A solution to these problems is to delay code generation until load time. This is the earliest point at which a piece of software can be fine-tuned to the actual capabilities of the hardware on which it is about to be executed, and also the earliest point at wich modularization overheads can be overcome by global optimization.A still better match between software and hardware can be achieved by replacing the already executing software at regular intervals by new versions constructed on-the-fly using a background code re-optimizer. This not only enables the use of live profiling data to guide optimization decisions, but also facilitates adaptation to changing usage patterns and the late addition of dynamic link libraries.This paper presents a system that provides code generation at load-time and continuous program optimization at run-time. First, the architecture of the system is presented. Then, two optimization techniques are discussed that were developed specifically in the context of continuous optimization. The first of these optimizations continually adjusts the storage layouts of dynamic data structures to maximize data cache locality, while the second performs profile-driven instruction re-scheduling to increase instruction-level parallelism. These two optimizations have very different cost/benefit ratios, presented in a series of benchmarks. The paper concludes with an outlook to future research directions and an enumeration of some remaining research problems.The empirical results presented in this paper make a case in favor of continuous optimization, but indicate that it needs to be applied judiciously. In many situations, the costs of dynamic optimizations outweigh their benefit, so that no break-even point is ever reached. In favorable circumstances, on the other hand, speed-ups of over 120p have been observed. It appears as if the main beneficiaries of continuous optimization are shared libraries, which at different times can be optimized in the context of the currently dominant client application.
---
paper_title: A framework for reducing the cost of instrumented code

paper_content:

Instrumenting code to collect profiling information can cause substantial execution overhead. This overhead makes instrumentation difficult to perform at runtime, often preventing many known offline feedback-directed optimizations from being used in online systems. This paper presents a general framework for performing instrumentation sampling to reduce the overhead of previously expensive instrumentation. The framework is simple and effective, using code-duplication and counter-based sampling to allow switching between instrumented and non-instrumented code. Our framework does not rely on any hardware or operating system support, yet provides a high frequency sample rate that is tunable, allowing the tradeoff between overhead and accuracy to be adjusted easily at runtime. Experimental results are presented to validate that our technique can collect accurate profiles (93-98% overlap with a perfect profile) with low overhead (averaging 6% total overhead with a naive implementation). A Jalape~ no-specific optimization is also presented that reduces overhead further, resulting in an average total overhead of 3%.
---
paper_title: The superblock: An effective technique for VLIW and superscalar compilation

paper_content:

A compiler for VLIW and superscalar processors must expose sufficient instruction-level parallelism (ILP) to effectively utilize the parallel hardware. However, ILP within basic blocks is extremely limited for control-intensive programs. We have developed a set of techniques for exploiting ILP across basic block boundaries. These techniques are based on a novel structure called thesuperblock. The superblock enables the optimizer and scheduler to extract more ILP along the important execution paths by systematically removing constraints due to the unimportant paths. Superblock optimization and scheduling have been implemented in the IMPACT-I compiler. This implementation gives us a unique opportunity to fully understand the issues involved in incorporating these techniques into a real compiler. Superblock optimizations and scheduling are shown to be useful while taking into account a variety of architectural features.
---
paper_title: Design and Analysis of Profile-Based Optimization in Compaq's Compilation Tools for Alpha

paper_content:

This paper describes and evaluates the profile-based optimizations in the Compaq C compiler tool chain for Alpha. The optimizations include superblock formation, inlining, commando loop optimization, register allocation, code layout, and switch statement optimization. The optimizations either are extensions of classical optimizations or are restructuring transformations that enable classical optimizations. Profile-based optimization is highly effective, achieving a 17% speedup over aggressive classical optimization on the SPECInt95 benchmarks. Inlining contributes the most performance and code layout, superblock formation, and loop restructuring are also important.
---
paper_title: The essence of compiling with traces

paper_content:

The technique of trace-based just-in-time compilation was introduced by Bala et al. and was further developed by Gal et al. It currently enjoys success in Mozilla Firefox's JavaScript engine. A trace-based JIT compiler leverages run-time profiling to optimize frequently-executed paths while enabling the optimized code to ``bail out'' to the original code when the path has been invalidated. This optimization strategy differs from those of other JIT compilers and opens the question of which trace optimizations are sound. In this paper we present a framework for reasoning about the soundness of trace optimizations, and we show that some traditional optimization techniques are sound when used in a trace compiler while others are unsound. The converse is also true: some trace optimizations are sound when used in a traditional compiler while others are unsound. So, traditional and trace optimizations form incomparable sets. Our setting is an imperative calculus for which tracing is explicitly spelled out in the semantics. We define optimization soundness via a notion of bisimulation, and we show that sound optimizations lead to confluence and determinacy of stores.
---
paper_title: ADAPTIVE SYSTEMS FOR THE DYNAMIC RUN-TIME OPTIMIZATIONOF PROGRAMS

paper_content:

Abstract : This thesis investigates adaptive compiler systems that perform, during program execution, code optimizations based on the dynamic behavior of the program as opposed to current approaches that employ a fixed code generation strategy, i.e., one in which a predetermined set of code optimizations are applied at compile-time to an entire program. The main problems associated with such adaptive systems are studied in general: which optimizations to apply to what parts of the program and when. Two different optimization strategies result: an ideal scheme which is not practical to implement, and a more basic scheme that is. The design of a practical system is discussed for the FORTRAN IV language. The system was implemented and tested with programs having different behavioral characteristics.
---
paper_title: The potential of trace-level parallelism in java programs

paper_content:

The exploitation of parallelism among traces, i.e. hot paths of execution in programs, is a novel approach to the automatic parallelization of Java programs and it has many advantages. However, to date, the extent to which parallelism exists among traces in programs has not been made clear. The goal of this study is to measure the amount of trace-level parallelism in several Java programs. We extend the Jupiter Java Virtual Machine with a simulator that models an abstract parallel system. We use this simulator to measure trace-level parallelism. We further use it to examine the effects of the number of processors, trace window size, and communication type and cost on performance. Our results indicate that enough trace-level parallelism exists for a modest number of processors. Thus, we conclude that trace-based parallelization is a potentially viable approach to improve the performance of Java programs.
---
paper_title: HYBRID JAVA COMPILATION OF JUST-IN-TIME AND AHEAD-OF TIME FOR EMBEDDED SYSTEMS

paper_content:

Many embedded Java software platforms execute two types of Java classes: those installed statically on the client device and those downloaded dynamically from service providers at runtime. For higher performance, it would be desirable to compile static Java classes by ahead-of-time compiler (AOTC) and to handle dynamically downloaded classes by just-in-time compiler (JITC), providing a hybrid compilation environment. This paper proposes a hybrid Java compilation approach and performs an initial case study with a hybrid environment, which is constructed simply by merging an existing AOTC and a JITC for the same Java virtual machine. Both compilers are developed independently for their own performance advantages with a generally accepted approach of compilation, but we merged them as efficiently as possible. Contrary to our expectations, the hybrid environment does not deliver a performance, in-between of full-JITC's and full-AOTC's. In fact, its performance is even lower than full-JITC's for many benchmark...
---
paper_title: Debugging optimized code with dynamic deoptimization

paper_content:

SELF's debugging system provides complete source-level debugging ( expected behavior ) with globally optimized code. It shields the debugger from optimizations performed by the compiler by dynamically deoptimizing code on demand. Deoptimization only affects the procedure activations that are actively being debugged; all other code runs at full speed. Deoptimization requires the compiler to supply debugging information at discrete interrupt points ; the compiler can still perform extensive optimizations between interrupt points without affecting debuggability. At the same time, the inability to interrupt between interrupt points is invisible to the user. Our debugging system also handles programming changes during debugging. Again, the system provides expected behavior: it is possible to change a running program and immediately observe the effects of the change. Dynamic deoptimization transforms old compiled code (which may contain inlined copies of the old version of the changed procedure) into new versions reflecting the current source-level state. To the best of our knowledge, SELF is the first practical system providing full expected behavior with globally optimized code.
---
paper_title: Dynamic hot data stream prefetching for general-purpose programs

paper_content:

Prefetching data ahead of use has the potential to tolerate the grow ing processor-memory performance gap by overlapping long latency memory accesses with useful computation. While sophisti cated prefetching techniques have been automated for limited domains, such as scientific codes that access dense arrays in loop nests, a similar level of success has eluded general-purpose pro grams, especially pointer-chasing codes written in languages such as C and C++. We address this problem by describing, implementing and evaluating a dynamic prefetching scheme. Our technique runs on stock hardware, is completely automatic, and works for general-purpose programs, including pointer-chasing codes written in weakly-typed languages, such as C and C++. It operates in three phases. First, the profiling phase gathers a temporal data reference profile from a running program with low-overhead. Next, the profiling is turned off and a fast analysis algorithm extracts hot data streams, which are data reference sequences that frequently repeat in the same order, from the temporal profile. Then, the system dynamically injects code at appropriate program points to detect and prefetch these hot data streams. Finally, the process enters the hibernation phase where no profiling or analysis is performed, and the program continues to execute with the added prefetch instructions. At the end of the hibernation phase, the program is de-optimized to remove the inserted checks and prefetch instructions, and control returns to the profiling phase. For long-running programs, this profile, analyze and optimize, hibernate, cycle will repeat multiple times. Our initial results from applying dynamic prefetching are promising, indicating overall execution time improvements of 5.19% for several memory-performance-limited SPECint2000 benchmarks running their largest (ref) inputs.
---
paper_title: Coupling on-line and off-line profile information to improve program performance

paper_content:

In this paper we describe a novel execution environment for Java programs that substantially improves execution performance by incorporating both on-line and off-line profile information to guide dynamic optimization. By using both types of profile collection techniques, we are able to exploit the strengths of each constituent approach: profile accuracy and low overhead. Such coupling also reduces the negative impact of these approaches when each is used in isolation. On-line profiling introduces overhead for dynamic instrumentation, measurement, and decision making. Off-line profile information can be inaccurate when program inputs for execution and optimization differ from those used for profiling. To combat these drawbacks and to achieve the benefits from both online and off-line profiling, we developed a dynamic compilation system (based on JikesRVM) that makes use of both. As a result, we are able improve Java program performance by 9% on average, for the programs studied.
---
paper_title: Adaptive optimization of the Sun Java™ real-time system garbage collector

paper_content:

Garbage collection (GC) is one of the largest sources of unpredictability in Java™ applications, and a real-time virtual machine must use garbage collection algorithms that minimize delays to real-time threads and at the same time maximize the overall application's throughput. In order to achieve the optimal tradeoff between these conflicting objectives, the GC cycle (which needs to take place periodically in order to free the memory no longer used by the application) needs to be triggered at the optimal time: if it is triggered too soon then the application's throughput will decrease unnecessarily, while if it is triggered too late then the application can run out of free memory and block real-time threads unnecessarily. Starting with Sun Java RTS 2.0, a new real-time garbage collector (RTGC) is available. One of the key RTGC parameters is the StartupMemoryThreshold, which determines how low the free memory in the system can fall before a garbage collection is triggered. This paper presents a framework for dynamically adapting the StartupMemoryThreshold for achieving the optimal balance between the application's throughput and pause time, which was integrated into the beta release of Java RTS 2.2. An experimental evaluation of this framework using the SPECjbb2005 benchmark confirmed its effectiveness. This framework can be used in conjunction with any concurrent or a time-based incremental garbage collector.
---
paper_title: A region-based compilation technique for a Java just-in-time compiler

paper_content:

Method inlining and data flow analysis are two major optimization components for effective program transformations, however they often suffer from the existence of rarely or never executed code contained in the target method. One major problem lies in the assumption that the compilation unit is partitioned at method boundaries. This paper describes the design and implementation of a region-based compilation technique in our dynamic compilation system, in which the compiled regions are selected as code portions without rarely executed code. The key part of this technique is the region selection, partial inlining, and region exit handling. For region selection, we employ both static heuristics and dynamic profiles to identify rare sections of code. The region selection process and method inlining decision are interwoven, so that method inlining exposes other targets for region selection, while the region selection in the inline target conserves the inlining budget, leading to more method inlining. Thus the inlining process can be performed for parts of a method, not for the entire body of the method. When the program attempts to exit from a region boundary, we trigger recompilation and then rely on on-stack replacement to continue the execution from the corresponding entry point in the recompiled code. We have implemented these techniques in our Java JIT compiler, and conducted a comprehensive evaluation. The experimental results show that the approach of region-based compilation achieves approximately 5% performance improvement on average, while reducing the compilation overhead by 20 to 30%, in comparison to the traditional function-based compilation techniques.
---
paper_title: Design and implementation of a comprehensive real-time java virtual machine

paper_content:

The emergence of standards for programming real-time systems in Java has encouraged many developers to consider its use for systems previously only built using C, Ada, or assembly language. However, the RTSJ standard in isolation leaves many important problems unaddressed, and suffers from some serious problems in usability and safety. As a result, the use of Java for real-time programming has continued to be viewed as risky and adoption has been slow. In this paper we provide a description of IBM's new real-time Java virtual machine product, which combines Metronome real-time garbage collection, ahead-of-time compilation, and a complete implementation of the RTSJ standard, running on top of a custom real-time multiprocessor Linux kernel. We will describe the implementation of each of these components, including how they interacted both positively and negatively, and the extensions to previous work required to move it from research prototype to a system implementing the complete semantics of the Java language. The system has been adopted for hard real-time development of naval weapons systems and soft real-time telecommunications servers. We present measurements showing that the system is able to provide sub-millisecond worst-case garbage collection latencies, 50 microsecond Linux scheduling accuracy, and eliminate non-determinism due to JIT compilation.
---
paper_title: Continuous program optimization

paper_content:

In the wake of dramatic improvements in processor speed, it is often overlooked that much of the software in everyday operation is not making optimal use of the hardware on which it actually runs. Among the reasons for this discrepancy are hardware/software mismatches, performance problems induced by software engineering considerations, and the inability of systems to adapt to the user's behavior. ::: The obvious solution to the problem is to delay code generation until load-time. This is the earliest point at which a piece of software can be fine-tuned to the actual capabilities of the hardware on which it is about to be executed. An even better match can be achieved by replacing the already executing software at regular intervals by new versions constructed on-the-fly using a background code re-optimizer. The code produced using such dynamic re-optimizers is often of a higher quality than can be achieved using static “off-line” compilation because live profiling data can be used to guide optimization decisions and hence the software can adapt to changing usage patterns and the late addition of dynamic link libraries. ::: This dissertation presents an extensible architecture that provides code generation at load-time and continuous program optimization at run-time. It discusses important aspects such as when to optimize a given piece of software and how to optimize it. This dissertation also presents two new optimization techniques developed explicitly in the context of continuous optimization: object layout adaptation and trace scheduling. The former technique continuously improves the storage layout of dynamically allocated data structures to improve data cache locality. The latter increases the instruction level parallelism by continually adapting the instruction schedule to predominantly executed program paths. Using these new techniques, we have measured speed-ups of up to 96% over statically optimized programs under favorable circumstances.
---
paper_title: Profile guided code positioning

paper_content:

This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy. ::: After initial investigation in the literature, we decided to implement two prototypes for the Hewlett-Packard Precision Architecture (PA-RISC). The first, built on top of the linker, positions code based on whole procedures. This prototype has the ability to move procedures into an order that is determined by a “closest is best” strategy. ::: The second prototype, built on top of an existing optimizer package, positions code based on basic blocks within procedures. Groups of basic blocks that would be better as straight-line sequences are identified as chains. These chains are then ordered according to branch heuristics. Code that is never executed during the data collection runs can be physically separated from the primary code of a procedure by a technique we devised called procedure splitting. ::: The algorithms we implemented are described through examples in this paper. The performance improvements from our work are also summarized in various tables and charts.
---
paper_title: On-Line Trace Based Automatic Parallelization of Java Programs on Multicore Platforms

paper_content:

We propose two new approaches that automatically parallelize Java programs at runtime. These approaches, which rely on run-time trace information collected during program execution, dynamically recompile Java byte code that can be executed in parallel. One approach utilizes trace information to improve traditional loop parallelization, and the other parallelizes traces instead of loop iterations. We also describe a cost/benefit model that makes intelligent parallelization decisions, as well as a parallel execution environment to execute parallelized programs. These techniques are based on Jikes RVM. Our approach is evaluated by parallelizing sequential Java programs, and its performance is compared to that of the manually parallelized code. According to the experimental results, our approach has low overheads and achieves competitive speedups compared to the manually parallelizing code. Moreover, trace parallelization can exploit parallelism beyond loop iterations.
---
paper_title: Using profile information to assist classic code optimizations

paper_content:

This paper describes the design and implementation of an optimizing compiler that automatically generates profile information to assist classic code optimizations. This compiler contains two new components, an execution profiler and a profile-based code optimizer, which are not commonly found in traditional optimizing compilers. The execution profiler inserts probes into the input program, executes the input program for several inputs, accumulates profile information and supplies this information to the optimizer. The profile-based code optimizer uses the profile information to expose new optimization opportunities that are not visible to traditional global optimization methods. Experimental results show that the profile-based code optimizer significantly improves the performance of production C programs that have already been optimized by a high-quality global code optimizer.
---
paper_title: The Jalapeño virtual machine

paper_content:

Jalapeno is a virtual machine for JavaTM servers written in the Java language. To be able to address the requirements of servers (performance and scalability in particular), Jalapeno was designed "from scratch" to be as self-sufficient as possible. Jalapeno's unique object model and memory layout allows a hardware null-pointer check as well as fast access to array elements, fields, and methods. Run-time services conventionally provided in native code are implemented primarily in Java. Java threads are multiplexed by virtual processors (implemented as operating system threads). A family of concurrent object allocators and parallel type-accurate garbage collectors is supported. Jalapeno's interoperable compilers enable quasi-preemptive thread switching and precise location of object references. Jalapeno's dynamic optimizing compiler is designed to obtain high quality code for methods that are observed to be frequently executed or computationally intensive.
---
paper_title: Exploiting Multi-core Processors to Improve Time Predictability for Real-Time Java Computing

paper_content:

As a successful programming language, Java has extended its application from general-purpose systems to embedded, real-time systems. However, some of Java's excellent features, like automatic memory management and dynamic compilation, bring indeterminism to the execution time of real-time Java programs. In this paper, we propose several multi-core approaches to remove or at least reduce the unpredictability inside of Java Virtual Machine (JVM). Our goal is to retain high performance competitive to dynamic compilation and, at the same time, obtain better time predictability for JVM. Also, we study pre-compilation techniques to utilize second core more efficiently. Furthermore, we develop Pre-optimization on Another Core (PoAC) scheme to replace the Adaptive Optimization System (AOS) in Jikes JVM, which is very sensitive to execution time variation and impacts time predictability greatly. The experimental results indicate that our approaches are able to reach high performance while greatly reduce execution time variation of Java applications.
---
paper_title: Design, implementation and evaluation of adaptive recompilation with on-stack replacement

paper_content:

Modern virtual machines often maintain multiple compiled versions of a method. An on-stack replacement (OSR) mechanism enables a virtual machine to transfer execution between compiled versions, even while a method runs. Relying on this mechanism, the system can exploit powerful techniques to reduce compile time and code space, dynamically de-optimize code, and invalidate speculative optimizations. The paper presents a new, simple, mostly compiler-independent mechanism to transfer execution into compiled code. Additionally, we present enhancements to an analytic model for recompilation to exploit OSR for more aggressive optimization. We have implemented these techniques in Jikes RVM and present a comprehensive evaluation, including a study of fully automatic, online, profile-driven deferred compilation.
---
paper_title: Calpa: a tool for automating selective dynamic compilation

paper_content:

Selective dynamic compilation systems, typically driven by annotations that identify run-time constants, can achieve significant program speedups. However, manually inserting annotations is a tedious and time-consuming process that requires careful inspection of a program's static characteristics and run-time behavior and much trial and error in order to select the most beneficial annotations. Calpa is a system that generates annotations automatically for the DyC dynamic compiler. Calpa combines execution frequency and value profile information with a model of dynamic compilation cost and dynamically generated code benefit to choose run-time constants and other dynamic compilation strategies. For the programs tested so far, Calpa generates annotations of the same or better quality as those found by a human, but in a fraction of the time. The result was equal or-better program speedups from dynamic compilation, but without the need for programmer intervention.
---
paper_title: Bursty Tracing: A Framework for Low-Overhead Temporal Profiling

paper_content:

With processor speed increasing much more rapidly than memory access speed, memory system optimizations have the potential to significantly improve program performance. Unfortunately, cache-level optimizations often require detailed temporal information about a program’s references to be effective. Traditional techniques for obtaining this information are too expensive to be practical in an on-line setting. We address this problem by describing and evaluating a framework for low-overhead temporal profiling. Our framework extends the Arnold-Ryder framework that uses instrumentation and counter-based sampling to collect frequency profiles with low overhead. Our framework samples bursts (sub-sequences) of the trace of all runtime events to construct a temporal program profile. Our bursty tracing profiler is built using Vulcan, an executable-editing tool for x86, and we evaluate it on optimized x86 binaries. Like the Arnold-Ryder framework, we have the advantages of not requiring operating system or hardware support and being deterministic. Unlike them, we are not limited to capturing temporal relationships on intraprocedural acyclic paths since our trace bursts can span procedure boundaries. In addition, our framework does not require access to program source or recompilation. A direct implementation of our extensions to the Arnold-Ryder framework results in profiling overhead of 6-35%. We describe techniques that reduce this overhead to 3-18%, making it suitable for use in an on-line setting.
---
paper_title: Reconciling responsiveness with performance in pure object-oriented languages

paper_content:

Dynamically dispatched calls often limit the performance of object-oriented programs, since opject-oriented programming encourages factoring code into small, reusable units, thereby increasing the frequency of these expensive operations. Frequent calls not only slow down execution with the dispatch overhead per se, but more importantly they hinder optimization by limiting the range and effectiveness of standard global optimizations. In particular, dynamically dispatched calles prevent standard interprocedual optimizations that depend on the availability of a static call graph. The SELF implementation described here offers tow novel approaches to optimization. Type feedback speculatively inlines dynamically dispatched calls based on profile information that predicts likely receiver classes. Adaptive optimization reconciles optimizing compilation with interactive performance by incrementally optimizing only the frequently executed parts of a program. When combined, these two techniques result in a system that can execute programs significantly faster than previous systems while retaining much of the interactiveness of an interpreted system.
---
paper_title: Partial method compilation using dynamic profile information

paper_content:

The traditional tradeoff when performing dynamic compilation is that of fast compilation time versus fast code performance. Most dynamic compilation systems for Java perform selective compilation and/or optimization at a method granularity. This is the not the optimal granularity level. However, compiling at a sub-method granularity is thought to be too complicated to be practical. This paper describes a straightforward technique for performing compilation and optimizations at a finer, sub-method granularity. We utilize dynamic profile data to determine intra-method code regions that are rarely or never executed, and compile and optimize the code without those regions. If a branch that was predicted to be rare is actually taken at run time, we fall back to the interpreter or dynamically compile another version of the code. By avoiding compiling and optimizing code that is rarely executed, we are able to decrease compile time significantly, with little to no degradation in performance. Futhermore, ignoring rarely-executed code can open up more optimization opportunities on the common paths. We present two optimizations---partial dead code elimination and rare-path-sensitive pointer and escape analysis---that take advantage of rare path information. Using these optimizations, our technique is able to improve performance beyond the compile time improvements
---
paper_title: A trace-based Java JIT compiler retrofitted from a method-based compiler

paper_content:

This paper describes our trace-based JIT compiler (trace-JIT) for Java developed from a production-quality method-based JIT compiler (method-JIT). We first describe the design and implementation of our trace-JIT with emphasis on how we retrofitted a method-JIT as a trace-based compiler. Then we show that the trace-JIT often produces better quality code than the method-JIT by extending the compilation scope. Forming longer traces that span multiple methods turns out to be more powerful than method inlining in extending the compilation scope. It reduces method-invocation overhead and also offers more compiler optimization opportunities. However, the trace-JIT incurs additional runtime overhead compared to the method-JIT that may be offset by gains from the improved code quality. Overall, our trace-JIT achieved performance roughly comparable to the baseline method-JIT. We also discuss the issues in trace-based compilation from the viewpoint of compiler optimizations. Our results show the potentials of trace-based compilation as an alternative or complementary approach to compiling languages with mature method-based compilers.
---
paper_title: Real-time event-handling and scheduling on a multithreaded Java microcontroller

paper_content:

Abstract Our aim is to investigate the suitability of hardware multithreading for real-time event handling in combination with appropriate real-time scheduling techniques. We designed and evaluated a multithreaded microcontroller based on a Java processor core. Java threads are used as Interrupt Service Threads (ISTs) instead of the Interrupt Service Routines (ISRs) of conventional processors. Our proposed Komodo microcontroller supports multiple ISTs with zero-cycle context switching overhead. A so-called priority manager implements several real-time scheduling algorithms in hardware. We show the feasibility of a hardware real-time scheduler integrated deeply into the processor pipeline with a VHDL design and its synthesis. Evaluations with a software simulator and real-time applications as benchmarks show that hardware multithreading reaches a 1.2–1.4 performance increase for hard real-time applications (multithreading without latency utilization) and a 2.0–2.6 speedup by latency utilization for programs without hard real-time requirements. With respect to real-time scheduling on a multithreaded microcontroller, the Least Laxity First (LLF) scheme outperforms the Fixed Priority Preemptive (FPP), Earliest Deadline First (EDF), and Guaranteed Percentage (GP) schemes, but suffers from the highest implementation costs.
---
paper_title: WCET analysis for a Java processor

paper_content:

In this paper we propose a solution for a worst-case execution time (WCET) analyzable Java system: a combination of a time predictable Java processor and a tool that performs WCET analysis of Java bytecode. We present a Java processor, called JOP, designed for time-predictable execution of real-time tasks. JOP is an implementation of the Java virtual machine (JVM) in hardware. The execution time of bytecodes, the instructions of the JVM, is known cycle accurate for JOP. Therefore, JOP simplifies the low-level WCET analysis. A method cache, that fills whole Java methods into the cache, is analyzable with respect to the WCET. The WCET analysis tool is based on integer linear programming. The tool performs the low-level analysis at the bytecode level and integrates the method cache analysis for a two block cache.
---
paper_title: Towards a Java Multiprocessor

paper_content:

This paper describes the first steps towards a Java multiprocessor system on a single chip for embedded systems. The chip multiprocessing (CMP) system consists of a homogeneous set of processing elements and a shared memory. Each processor core is based on the Java Optimized Processor (JOP). A major challenge in CMP is the shared memory access of multiple CPUs. The proposed memory arbiter resolves possible emerging conflicts of parallel accesses to the shared memory using a fixed priority scheme. Furthermore, the paper describes the boot-up of the CMP. We verify the proposed CMP architecture by the implementation of the prototype called JopCMP. JopCMP consists of multiple JOPs and a shared memory. Finally yet importantly, the first implementation of the CMP composed of two/three JOPs in an FPGA enables us to present a comparison of the performance between a single-core JOP and the CMP version by running real applications.
---
paper_title: An effective instruction optimization method for embedded real-time Java processor

paper_content:

A method to optimize instructions in embedded real-time Java processors is proposed. It can reduce the CPI (cycles per instruction) and simplify the implementation of complex instructions, as well as make the WCET (worst case execution time) of the optimized instructions more predictable. Because this method optimizes instruction itself it can be used together with other architectural optimization methods such as pipeline or out-of-order execution etc.
---
paper_title: A multithreaded Java microcontroller for thread-oriented real-time event-handling

paper_content:

We propose a multithreaded Java microcontroller (called Komodo microcontroller) with a new hardware event handling mechanism that allows handling of simultaneous overlapping events with hard real-time requirements. Real-time Java threads are used as interrupt service threads (ISTs) instead of interrupt service routines (ISRs). Our proposed Komodo microcontroller supports multiple ISTs with zero-cycle context switching overhead. We evaluate the basic architectural attributes using real-time event parameters of an autonomous guided vehicle. When calculating the maximum vehicle speed without violating the real-time constraints, ISTs dominate ISRs by a speed increase of 28%.
---
paper_title: Secure, Real-Time and Multi-Threaded General-Purpose Embedded Java Microarchitecture

paper_content:

This paper presents a novel implementation of an embedded Java microarchitecture for secure, real-time, and multi-threaded applications. A general-purpose platform is established through the support of modern features of object-oriented languages, such as exception handling, automatic garbage collection and interface types. New techniques have been implemented for specific real-time issues, such as an integrated stack and thread management for fast context switching, concurrent garbage collection for real-time threads and autonomous control flows through preemptive round-robin scheduling.
---
paper_title: A Java processor architecture for embedded real-time systems

paper_content:

Architectural advancements in modern processor designs increase average performance with features such as pipelines, caches, branch prediction, and out-of-order execution. However, these features complicate worst-case execution time analysis and lead to very conservative estimates. JOP (Java Optimized Processor) tackles this problem from the architectural perspective - by introducing a processor architecture in which simpler and more accurate WCET analysis is more important than average case performance. This paper presents a Java processor designed for time-predictable execution of real-time tasks. JOP is the implementation of the Java virtual machine in hardware. JOP is intended for applications in embedded real-time systems and the primary implementation technology is in a field programmable gate array. This paper demonstrates that a hardware implementation of the Java virtual machine results in a small design for resource-constrained devices.
---
paper_title: Real-time Java processor optimized for RTSJ

paper_content:

Due to the preeminent work of the real-time specification for Java(RTSJ), Java is increasingly expected to become the leading programming language in real-time systems. To provide a Java platform suitable for real-time applications, a real-time Java processor can execute Java bytecode directly is proposed in this paper. This processor provides efficient support in hardware for mechanisms specified in the RTSJ and offers a simpler programming model through ameliorating the scoped memory of the RTSJ. The most important characteristic of the processor is that its WCET(worst case execution time) of the bytecode execution is predictable. It is vital for the real-time systems.
---
paper_title: Interactive Back-annotation of Worst-case Execution Time Analysis for Java Microprocessors

paper_content:

As real-time systems become more prevalent, there is a need to guarantee that these increasingly complex systems perform as designed. One technique involves a static analysis to place an upper bound on worst-case execution time (WCET). Tools for conducting this analysis typically require the developer to digest assembly opcodes, hexadecimal addresses, and other low-level details in order to make sense of the results. Java-specific processors offer a way out of this complexity. Such processors make Java software more predictable, and as a consequence, timing analysis of a real-time system becomes less computationally intensive. WCET analysis tools based on these processors can thus offer more powerful features at higher levels of abstraction. As proof of this concept, we present a tool for static WCET analysis of Java processors. Our performance measurements show that this tool makes WCET analysis interactive, offering continuous feedback to the developer in the form of back-annotations.
---

Title: Overview of Real-Time Java Computing

Section 1: INTRODUCTION
Description 1: Provide an overview of the significance of real-time systems and the increasing role of Java in real-time software development, including challenges such as worst-case execution time (WCET) analysis and the unpredictability of Java in a real-time context.

Section 2: REAL-TIME THREADS AND SCHEDULING
Description 2: Discuss the definitions of real-time threads and scheduling requirements according to the Real-Time Specification for Java (RTSJ) and Ravenscar-Java specifications, and the behavior of real-time applications.

Section 3: TIME PREDICTABILITY OF JAVA CODE
Description 3: Explain the necessity of knowing the WCET of Java programs and methods for WCET analysis at both the Java byte code (JBC) level and platform-dependent level.

Section 4: REAL-TIME JAVA MEMORY MANAGEMENT
Description 4: Examine Java's automatic memory management, challenges posed by garbage collection (GC) in real-time systems, and strategies for achieving time-predictable garbage collection.

Section 5: COMPILATION FOR REAL-TIME JAVA
Description 5: Analyze the impact of different compilation methods like interpretation, Just-In-Time (JIT) compilation, and Ahead-Of-Time (AOT) compilation on the time predictability of real-time Java applications.

Section 6: JAVA PROCESSORS FOR REAL-TIME COMPUTING
Description 6: Explore hardware solutions such as Java processors that aim to provide deterministic execution times for Java applications in real-time systems.

Section 7: CONCLUSIONS
Description 7: Summarize the current state of real-time Java computing, highlight the surveyed topics, and suggest directions for future research.