Volta User Manual

In spite of these advances, an essential element is missing. Even when a real-time Java implementation provides deterministic scheduling, priority inversion avoidance, and a real-time garbage collector, no guarantee on the timeliness of the system can be made without knowledge of the worst-case execution time (WCET) for each task. To understand why this knowledge is so important, consider the major real-time scheduling algorithms shown in Figure 1.1. All of these algorithms require knowledge of the WCET.

Figure 1.1.  Real-time scheduling algorithms require worst-case execution time (the C variables) to determine whether deadlines can be met.

While most real-time practitioners are aware of its significance, the job of calculating this WCET is often perfunctory or even neglected. A common tactic in industry is to perform a series of tests under varying conditions and attempt to extrapolate the actual WCET from the resulting measurements. While this approach works well for average response time, worst-case response time is not amenable to measurement. An unexpected set of input data could cause the system to react more slowly than was measured during testing, as illustrated in Figure 1.2.

Figure 1.2.  This histogram of execution time for a fictional real-time task illustrates the weakness of measurement when dealing with worst-case execution time.

A more dependable and systematic approach to finding the WCET involves a static analysis. Given the executable code for a task and the processor on which it will run, static analysis provides an upper bound on the time taken to execute the task. Figure 1.3 shows a high-level sketch of this process for a trivial example.

Figure 1.3.  This trivial example shows how static analysis places an upper bound on worst-case execution time.

In the non-trivial real world, static analysis is not so simple. The traditional real-time Java environment offers many sources of unpredictability that result in alarmingly pessimistic WCET values. For instance, just-in-time compilation, a common technique for improving average performance in Java virtual machines, causes the first few executions of a task to be slow while subsequent executions are fast. Static analysis must account for this variance, leading to very large estimations of WCET. Developers are faced with unsettling choices: Turning off just-in-time compilation would merely slow down every execution, while reducing the WCET to the expected (average) running time would be unsafe and defeat the very purpose of analysis.

Modern processors are another enemy of tight WCET analysis. Large pipelines, branch prediction, and sophisticated multi-level caching have greatly improved average throughput at the expense of worst-case throughput. In Figure 1.3, for example, setting flag to true might trigger a cache miss. The WCET analysis must therefore include the lengthy cache servicing time even if its occurrence is rare. Although prior work has focused on modeling the processor to place a tighter bound on this cache interference, the technique remains challenging, particularly for data caches.

In the last few years, a new approach for dealing with WCET analysis in Java has emerged. Rather than fight the increasingly unpredictable behavior of virtual machines and superscalar processors, an alternative strategy eliminates them entirely. The approach relies on specialized processors that understand Java bytecode as their native instruction set. Examples include the aJ-100, the Cjip, and the JOP (see Figure 1.4). These Java-specific processors offer several advantages for real-time systems:

These qualities make Java processors an attractive platform for hard real-time systems. Although moving to such a novel and unique architecture may seem drastic, developers of real-time systems have a tradition of adopting new platforms when special needs arise, as evidenced by the popularity of ARM and PowerPC architectures in embedded devices.

Figure 1.4.  The Java Optimized Processor runs on FPGA chips, such as the Altera Cyclone.

To install and use the Volta tools, the following components are required:

Note that even if Java 1.6 is installed, Ant may be using some other version. Use ant -diagnostics to verify the java.version property for which Ant is configured.

To obtain Volta, download a release from the project site's Download section. Unpack the distribution into a directory of your choice.

Access to the source code can also be obtained via the project's Subversion page. This method is recommended because Volta is still under development, and the Subversion repository usually offers more recent code with new features and bug fixes.

ant

ant test

ant clean

The Cascade, and Clepsydra, and Canteen tools in Volta provide “sandboxes” for quick testing and easy experimentation. To use them, locate the QuickTest.java file in a tool's directory, edit it as desired, then run the tool's quick-test target.

For example, to play in Cascade's sandbox, edit the cascade/test/src/QuickTest.java file, then execute the following commands, starting in the top-level Volta directory:

cd cascade
ant quick-test

You should then see some output relating to the QuickTest.java file. You should also find that various files have been generated, such as a DOT representation of the control flow.

Cascade is different: It operates at the source code level, making the control flow data much easier to read and understand. It relies on JODE, a powerful Java decompiler, to produce a source code representation for every node in the CFG. In most cases, the decompiled code matches the original Java source code exactly.

To illustrate this point, consider the code in Figure 3.2. When compiled to a Java class with debugging symbols enabled, Cascade can generate a CFG of this method, as shown in Figure 3.3.

public void test()
{
    int j = 0;

    for (int i = j; i < 10; i++)
    {
        j++;
    }
}

Figure 3.3.  Control flow graphs in Cascade reveal high-level source code information, making them easier to digest.

Note that even at this high level, none of the low-level information is lost. Cascade preserves the original bytecode instructions for each node and can optionally show them in the graph visualization. This characteristic is vital for WCET analyzers built on top of Cascade.

Despite this improvement over conventional analysis tools, control flow graphs can still be difficult to follow, especially when the graphs are large. To counter this problem, Cascade can also visualize the control flow as a tree. These control flow trees naturally resemble the original source code, as it is also a tree structure. They avoid the somewhat arbitrary—and potentially confusing—node and edge placements that can be found in a graph visualization. (For instance, note the nonsensical placement of the terminating node within the for loop cycle in Figure 3.3.) Control flow trees are also conducive to certain types of analysis techniques, such as tree-based WCET analysis.

Figure 3.4 shows the plain-text representation of a control flow tree for Figure 3.2. Note that Cascade associates each element of the tree with its corresponding bytecode instructions. Note, too, that a pseudo-node for the goto instruction has been added, as well as the implied return statement. Though these elements do not appear in the original source code, they are necessary to preserve all of the instructions in the generated bytecode.

j = 0 [0: iconst_0 0, 1: istore_1 1] 
i = j [2: iload_1 1 [j,I], 3: istore_2 2] 
for (i < 10) [4: iload_2 2 [i,I], 5: bipush 10, 7: if_icmpge 19] 
    j++ [10: iinc 1 [j,I] 1] 
    i += 1 [13: iinc 2 [i,I] 1] 
    goto [16: goto 4] 
return [19: return]

For an even friendlier representation, Cascade can also produce control flow trees as Scalable Vector Graphics (SVG) diagrams, as shown in Figure 3.5

Figure 3.5.  Cascade can generate SVG diagrams of control flow trees for better legibility.

In addition, Cascade can export control flow graphs in DOT, GML, and GraphML formats. These external formats can be fed into other tools; thus, Cascade is not bound to Volta and can be used independently by any project requiring control flow analysis of Java.

Cascade can be invoked from the command line to perform control flow analysis of a single method. To do so, run Java from the command line and specify the edu.uci.eecs.doc.cascade.Cascade class followed by the appropriate arguments, as described below. (Alternatively, the quick-test target in the Ant build script provides an easy way of supplying these arguments without re-typing them.)

Cascade also provides an API for creating and accessing control flow data structures. For example, the edu.uci.eecs.doc.cascade.controlflow package provides abstractions of source code elements such as ForLoop and ReturnStatement.

Documentation of the Cascade API is available in the Volta distribution and at the Volta web site.

The timings in Figure 4.3 apply to the JOP processor and were generated using a tree-based method, but Clepsydra can be configured to work with any Java processor and with a variety of analysis techniques. To achieve this flexibility, Clepsydra relies on the Strategy pattern so that processor models and analysis algorithms can be swapped in and out cleanly, even at run-time. Specifically, it requires four strategies in order to calculate the WCET of a method: a timing strategy, a loop bound strategy, an analysis strategy, and a method cache strategy. Clepsydra provides default implementations of each strategy, but users are free to plug in custom strategies as needed.

public int getCycles(short opcode, boolean cacheHit) 
{ 
  int methodLoadTime = getMethodLoadTime(cacheHit); 

  switch (opcode) { 
    case SIPUSH: 
      return 3; 

    case LDC: 
      return 7 + readWaitStates; 

    case LDC2_W: 
      cycles = 17; 
      if (readWaitStates > 2) 
        cycles += readWaitStates - 2; 
      if (readWaitStates > 1) 
        cycles += readWaitStates - 1; 
      return cycles; 
    . 
    . 
    . 

public void test()
{
    int j = 0;

    @LoopBound(max=10)
    for (int i = j; i < 10; i++)
    {
        j++;
    }
}

The most novel feature in Clepsydra is its ability to annotate every statement in the source code with its worst-case execution time. By conducting the analysis at this high level, developers of real-time systems no longer must switch periodically between source language and assembly language. They can remain focused on the original code rather than the sometimes cryptic output of a WCET analysis tool.

Figure 4.6 provides an overview of how Clepsydra accomplishes this process, known as back-annotation. Analysis begins when the developer supplies a Java source file, which is immediately fed into a WCET annotation-aware Java compiler. The bytecode output of this compiler is then reconstructed into source form by the JODE decompiler. Next, Cascade translates the internal structures of the decompiler into a control flow tree. Finally, Clepsydra performs the actual analysis and produces worst-case timing values for every statement and compound structure in the decompiled source code. The dotted line in the figure represents a simple mapping between the Clepsydra output and the source code.

Figure 4.6.  An overview of the back-annotation process in Clepsydra.

The easiest way to use Clepsydra's back-annotation feature is via the getBackAnnotations method. It returns a map between lines of source code and the WCET for that line. Note that this method always uses the TreeAnalysisStrategy and cannot be configured to use other analysis strategies.

Like Cascade, Clepsydra can produce control flow trees in SVG format for highly readable analysis results that mimic the original source code, as shown in Figure 4.7.

Figure 4.7.  Clepsydra can generate SVG diagrams of control flow trees, where each node is “badged” with its worst-case cycle time.

In addition, Clepsydra can export control flow graphs in DOT, GML, and GraphML formats. Currently, however, only the DOT format includes WCET information; the other output formats are identical to Cascade's.

Clepsydra can be invoked from the command line to perform WCET analysis of a single method. To do so, run Java from the command line and specify the edu.uci.eecs.doc.clepsydra.Clepsydra class followed by the appropriate arguments, as described below. (Alternatively, the quick-test target in the Ant build script provides an easy way of supplying these arguments without re-typing them.)

Clepsydra also provides an API for performing a WCET analysis and obtaining the results. For example, the edu.uci.eecs.doc.clepsydra.ipet package provides an interface to ILP solvers. This interface contains, among other features, a method that saves the solver's output to MPS format.

(While the MPS format is much more common, the special format used by lp_solve is more readable by human eyes. To convert from the MPS format lp_solve format: lp_solve -fmps infile -wlp outfile. Use /dev/stdout as the outfile to dump the format to the console.)

Further documentation of the Clepsydra API is available in the Volta distribution and at the Volta web site.

Clepsydra includes a prototype of such a plugin for the jEdit editor. Figure 5.1 shows a screenshot of the jEdit plugin in action. The red text attached to each statement indicates the number of cycles that the statement consumes in the worst case. (The cycle counts in this example are based on JOP, but other Java-specific processors would produce similar results.) Note that these back-annotations were inserted automatically by the plugin following a WCET analysis of the code. The plugin re-runs the analysis and generates new back-annotations whenever the developer saves changes to disk.

Figure 5.1.  This screenshot shows a Clepsydra plugin for the jEdit text editor. The red text, which was inserted automatically by the plugin, indicates worst-case cycle consumption.

Configuration

After installation, Clepsydra must be configured by choosing Plugins → Plugin Options… from the jEdit menu, which will bring up a dialog box like the one in Figure 5.2. The options are:

Enabled

Globally enables or disables the plugin.

Class path

A list of paths to search when loading classes during the WCET analysis. Each path must be separated by the system path separator (e.g., :).

Source path

A list of paths to search when compiling the source code. Each path must be separated by the system path separator (e.g., :).

Compiler executable

The path to a compiler capable of understanding WCET statement annotations, such as the one described in Chapter 7.

Instruction timing class

The strategy to use for modeling the processor.

Loop bound class

The strategy to use for determining loop bounds.

Run-time JAR file

The location of a JAR containing Java's run-time classes (e.g., java.lang.Object).

Text color

The color to use for back-annotations.

Space between source code and WCET display

The size of the margin, in pixels, between the end of the line and its back-annotation.

Figure 5.2.  The Plugin Options dialog box in jEdit allows configuration of the Clepsydra plugin.

Cascade also includes a prototype jEdit plugin. Instead of adding back-annotations to the text area, it displays a control flow tree in a separate pane. The visualization is updated whenever the buffer is saved. Installation and usage is nearly identical to the Clepsydra plugin. The configuration options are slightly different but self-explanatory.

Canteen conforms to the same interfaces as the java.util package, so their usage is largely self-explanatory. There are, however, some special restrictions required by Canteen for hard real-time predictability.

First, creating elements the usual way (i.e., by calling Java's new operator) will not work. Instead, each collection must be initialized with a set of pre-allocated elements. When a new element is to be added to the collection, the user must pull one of these elements from the collection by calling newElement or newEntry, then pass it to the collection's add or put method.

Second, some methods are unimplemented. The unimplemented methods are documented as such in the Canteen source code.

For an example of how to use the classes in keeping these restrictions, refer to Canteen's QuickTest.java file.

In order to use Canteen's collection classes with the Clepsydra plugin for jEdit, some special configuration options are required. The Class Path option should include a path to the Canteen classes. Also, the Instruction Timing Class should be edu.uci.eecs.doc.canteen.analysis.InstructionTimingStrategy, and the Loop Bound Class should be edu.uci.eecs.doc.canteen.analysis.LoopBoundStrategy.

You should also make sure that jEdit has not loaded any third-party libraries, such as BCEL, that may conflict with the same libraries installed by the Clepsydra plugin for jEdit. Unsetting the CLASSPATH variable before launching jEdit should prevent this problem.

The modified compiler writes annotation data to class files as method attributes called RuntimeVisibleStatementAnnotations and RuntimeInvisibleStatementAnnotations. The format of these attributes is identical to the existing RuntimeVisibleAnnotations and RuntimeInvisibleAnnotations attributes (described in the Java 5 update to the Java Virtual Machine Specification) except that an additional field has been added following u2 type_index:

u4 pc;

This field holds the bytecode offset of the start of the loop.

To help debug the modified Java compiler, and also provide an example of how tools can access these annotations, the Volta project includes a utility called Dump Annotations. As its name implies, it will dump statement annotations to the console. It displays annotation data in the same struct-like format as the Java Virtual Machine Specification, making the output easy to read.

To use Dump Annotations, first build the modified Java compiler, specify the location of this modified javac in the build file, then run ant dump. You should see the results of a simple test case.