Volta User Manual

Trevor Harmon

Table of Contents

1. Introduction
Worst-case Execution Time
Java Microprocessors
2. The Volta Tool Suite
System Requirements
ILP Solver Installation
Build and Test
Quick Start
3. Cascade
Control Flow Graphs
Control Flow Trees
Export Formats
Command Line Interface
Application Programming Interface
4. Clepsydra
Timing Strategy
Loop Bound Strategy
Analysis Strategy
Method Cache Strategy
Export Formats
Command Line Interface
Application Programming Interface
5. jEdit Plugins
Clepsydra Plugin
Cascade Plugin
6. Canteen
Using Canteen with the Clepsydra Plugin
7. Java Compiler for WCET Annotations
Annotation Data Format
Dump Annotations Utility
A. Known Limitations
B. Further Reading
C. GNU General Public License
Section 0
Section 1
Section 2
Section 3
Section 4
Section 5
Section 6
Section 7
Section 8
Section 9
Section 10
NO WARRANTY Section 11
Section 12
How to Apply These Terms to Your New Programs

List of Figures

1.1. Scheduling Equations
1.2. WCET Measurement
1.3. Static WCET Analysis
1.4. Cyclone FPGA
2.1. Lake Volta
3.1. Avrora CFG
3.2. Simple Java method
3.3. Cascade CFG
3.4. Control flow tree
3.5. SVG Diagram of Control Flow
4.1. Clepsydra
4.2. aiT
4.3. Clepsydra CFG
4.4. Timing strategy
4.5. Loop bound annotation
4.6. Back-annotation
4.7. SVG Diagram of Clepsydra
5.1. jEdit plugin
5.2. jEdit plugin options

Chapter 1. Introduction

With the increasing size and complexity of hard real-time systems, developers are beginning to move away from C. Despite its status as the most popular language in real-time computing, it is relatively low-level, error-prone, and difficult to scale to large systems.

A growing number of real-time developers and researchers are considering Java as an alternative. This much newer language offers direct benefits: Compilers for Java catch many errors that C compilers miss; the language definition specifically addresses safety and security issues; and the high-level nature of Java makes it more productive, maintainable, and portable than C.

For real-time systems, Java is an immature but viable platform. Commercial implementations of the Real-time Specification for Java (RTSJ) are available from aicas and Sun, and real-time garbage collectors, such as Metronome, are showing promise. Boeing is using real-time Java to guide drone aircraft, and the United States Navy will use it in next-generation battleships.

Worst-case Execution Time

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.

Real-time scheduling equations

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 chart illustrating why measurement provides unsafe WCET estimation

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.

A simple diagram of WCET analysis

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.

Java Microprocessors

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:

  • Predictability Running bytecode directly on the processor eliminates just-in-time compilation, making execution time far less variable. Java's stack addressing scheme also helps to reduce variability. In JOP, for example, bytecode is translated into microcode that executes in a four-state pipeline, mitigating the need for branch prediction and the uncertainty it would introduce. Cache analysis in Java microprocessors is simpler, as well. Jump instructions are guaranteed never to target beyond the address range of the declaring method; therefore, a method-based cache, such as the one employed by JOP, makes every non-invocation instruction a cache hit. These characteristics yield a much tighter bound when performing static WCET analysis.

  • Easier certification A subtler benefit of Java microprocessors is important when considering safety- and mission-critical real-time systems. Such systems must obtain certification, such as the DO-178B standard for avionics software, to ensure traceability through design, code, and test. In a traditional real-time Java application, multiple layers must be certified: the operating system, the virtual machine, and the application itself. When the application runs on a Java processor, however, the OS and VM layers disappear, removing tens of thousands of lines of code and making the certification process faster and cheaper.

  • The Java language Moving a real-time system to a Java processor brings advantages due to the nature of the source language: stronger type safety, easier portability, and so on.

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.

Photograph of the Cyclone FPGA

Chapter 2. The Volta Tool Suite

As a response to the increasing size and complexity of hard real-time software, a significant portion of the real-time community is likely to adopt the solutions offered by the Java platform. Specialized Java processors are particularly important in such environments, not just for easing the development process but also for providing safe guarantees that the system will perform as designed.

In anticipation of this trend, the Volta[1] project offers a suite of tools for worst-case execution time analysis in Java microprocessors. It is fully open-source (available under the GNU Public License) and implemented in Java. Still a work-in-progress, it is intended as a platform for research and experimentation in real-time (especially hard real-time) computing.

The Volta suite includes Cascade, a control flow analyzer; Clepsydra, a WCET analyzer; Canteen, a set of time-predictable collection classes; Cascade and Clepsydra plugins for the jEdit text editor; and a Java compiler modified to support WCET annotations.

Figure 2.1.  Lake Volta, the largest man-made lake in the world, as seen from space.

Photograph of Lake Volta

System Requirements

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.

ILP Solver Installation

If you plan to use the Clepsydra tool, you will also need to download and install an ILP solver. By default, Clepsydra is configured for the lp_solve solver. (Note that only version has been tested with Clepsydra; bugs have been encountered in more recent versions of lp_solve.)

To install lp_solve on Mac OS X, the easiest method is via Fink. Use Fink to install the lpsolve-java package. If Fink was installed to the default location (/sw), Clepsydra will then find lp_solve automatically.

Windows users will need to install lp_solve manually. First, download the development package and the Java bindings. Next, unpack the lpsolve55.dll and lpsolve55j.dll files and copy them to a directory. Finally, add this directory to your system's PATH environment variable. (If you don't add it to the path, you will get an error: Can't find dependent libraries.) Note that if the directory is \lp_solve, Clepsydra will find the files automatically. Otherwise, you must modify Clepsydra's build file and change the ilp.library.path property to point to the directory to which you copied the files.

Build and Test

Once Volta has been installed, you can build it from the console by typing:


To verify the installation, you can run a series of unit tests by typing:

ant test

To remove the generated files:

ant clean

Quick Start

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.

[1] Named after the lake in Ghana, not the physicist from Italy.

Chapter 3. Cascade

A major component in Volta is Cascade, a tool for generating control flow data structures for subsequent analysis by higher-level tools. It takes as input a Java class file and can produce a control flow graph, or CFG, for each method in the class.

Most control flow analyzers operate at the assembly language level. With no source code information, the output of such tools is difficult to comprehend, as shown in Figure 3.1.

Figure 3.1.  Traditional control flow analyzers are extremely low-level and produce graphs that are difficult to comprehend, such as this CFG created by the Avrora framework.

Diagram of an Avrora CFG

Control Flow Graphs

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.

Figure 3.2. A simple Java method.

public void test()
    int j = 0;

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

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

Diagram of a Cascade CFG

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.

Control Flow Trees

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.

Figure 3.4. The control flow tree of the Java code in Figure 3.2

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]

Export Formats

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.

Diagram of control flow

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.

Command Line Interface

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.)

edu.uci.eecs.doc.cascade.Cascade [-bytecode] {-classpath classpath} [-dot filename] [-gml filename] [-graphml filename] [-hideCacheMiss] {-method signature} [-print] [-recursive] [[-svg filename] | [-svgColorized filename]] [-text filename]


If specified, Cascade will add a list of bytecode instructions to each control flow node in all output formats.


A list of directories that will be searched when loading classes during control flow construction. Each path in the list must be separated by the system's path separator (e.g., : on UNIX-based systems).


If specified, Cascade will save a representation of the control flow graph in DOT format to the given file.


If specified, Cascade will save a representation of the control flow graph in GML format to the given file.


If specified, Cascade will save a representation of the control flow graph in GraphML format to the given file.


If specified, Cascade will not display cache miss blocks in the control flow graphs that it creates.


The method whose control flow graph or tree should be constructed. The method signature must be fully qualified. For example, the signature for indexOf is java.lang.String.indexOf(java.lang.String,int).


If specified, Cascade will print a plain-text representation of the control flow tree to the console.


If specified during control flow tree generation, Cascade will produce trees for the method, the methods that it invokes, the methods that they invoke, and so on.


If specified, Cascade will save a representation of the control flow tree in black-and-white SVG format to the given file.


If specified, Cascade will save a representation of the control flow tree in a color-coded SVG format to the given file.


If specified, Cascade will save a representation of the control flow tree in plain text format to the given file.

Application Programming Interface

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.

Chapter 4. Clepsydra

Clepsydra[2], another tool in the Volta suite, performs static worst-case execution time analysis. Clepsydra takes as input the high-level control flow information for a Java method and produces as output the WCET for every statement in the method, as well as the method as a whole.

Figure 4.1.  Modern design of a water clock by Bernard Gitton. (Photograph by Wikipedia user Luna04.)

Photograph of a clepsydra

Traditionally, WCET analyzers have operated at a very low level, producing timing data only in relation to executable machine instructions. The user must digest assembly opcodes, hexadecimal addresses, and other implementation details in order to make sense of the analysis. The abstractions provided by the higher-level source code language are lost, as shown in Figure 4.2.

Figure 4.2.  Even if the code was written in a high-level language, AbsInt's aiT tool requires the developer to understand assembly opcodes.

Screenshot of the aiT tool

In contrast, Clepsydra preserves these high-level abstractions. It displays WCET timing graphs that strongly resemble the original source code, as shown in Figure 4.3. The cycle count shown for each node is the number of cycles the node consumes in the worst case.

Figure 4.3.  Control flow graphs in Clepsydra reveal high-level source code information, making them easier to understand.

Diagram of a Clepsydra CFG


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.

Timing Strategy

A complete WCET analysis requires knowledge of the target processor. Clepsydra encapsulates this knowledge within its InstructionTimingStrategy interface, which provides cycle counts for individual bytecode instructions. As processors change, and new ones are created, Clepsydra requires only an updated timing strategy to support the new architecture.

To add support for a processor, the user must implement this interface then supply a reference to it, either as a class name on the command line or via one of Clepsydra's APIs, such as getBackAnnotations.

For the JOP processor, Clepsydra provides a ready-made implementation of the InstructionTimingStrategy interface, a snippet of which is shown in Figure 4.4. The complete source code is available in the Volta distribution and can be used as a template for other implementations of this interface.

Figure 4.4. Clepsydra relies on the Strategy pattern to make processor timing definitions easily swappable. This listing shows a portion of the JOP timing strategy.

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; 

Loop Bound Strategy

WCET analysis also requires knowledge of loop bounds, but there is no single “right way” to determine the maximum iterations of a loop. Recognizing that no single algorithm is best, Clepsydra factors out loop bound determination via the LoopBoundStrategy interface. Developers can plug in a default implementation supplied by Clepsydra, or they can implement their own without having to understand the details of Clepsydra's design.

The default implementation provided in Clepsydra is annotation-based. Called AnnotationLoopBoundStrategy, it assumes that the developer has annotated every loop construct with its maximum number of iterations. An example of such annotations can be seen in Figure 4.5. Here, the developer has indicated that the for loop iterates no more than ten times.

Figure 4.5. A simple Java method with a loop bound annotation.

public void test()
    int j = 0;

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

Note that Figure 4.5 is not, in fact, legal. Although Java supports the annotation syntax of the line immediately before the for loop, its location is illegal. Currently, Java allows annotations only on declarations, not on statements. If this restriction were removed, WCET annotations would have “for free” syntax checking, type safety, and tool support. Future versions of the Java specification may indeed remove this restriction, as described at the JSR-308 Statements web site.

In the meantime, AnnotationLoopBoundStrategy assumes that the code under analysis has been generated by a Java compiler capable of understanding statement annotations like the one in Figure 4.5. A prototype of such a compiler is available in the Volta distribution and described in Chapter 7.

Analysis Strategy

As with loop bound algorithms, WCET analysis techniques offer different strengths and weaknesses. Some techniques run fast but do not find a tight bound (e.g., tree-based approaches); others can be made tighter but require exponential running time (e.g., integer linear programming). No single approach is ideal, and for this reason Clepsydra makes analysis techniques pluggable via the AnalysisStrategy interface. Users can switch between them as needed, even at run-time, allowing the same Clepsydra framework to be used as existing techniques are refined and new ones are created.

Clepsydra provides ready-to-use implementations of both the tree and implicit path enumeration (IPET) techniques. For the former, the TreeAnalysisStrategy implements a simple recursive algorithm that computes the WCET of a control flow tree. The class also provides a mechanism for computing the WCET of individual control flow nodes, which is important for back-annotation.

The provided IPET implementation, IPETAnalysisStrategy, is more complicated. Part of this complexity is due to the graph-based nature of the technique; in addition, Clepsydra incorporates external C-based libraries to solve the ILP problem (due to the lack of open-source solvers in Java). Currently, two libraries are supported via the Adapter pattern: GLPK and lp_solve, accessed via the GLPKAdapter and LPSolveAdapter classes. These classes assume that their respective C libraries have already been installed.

Users may add support for additional ILP libraries by providing an implementation of the ILPSolver interface. For example, a commercial ILP solver, which is usually faster than the open-source libraries, can be integrated seamlessly into Clepsydra by writing a thin adapter for it.

Of course, Clepsydra is not restricted to the two built-in analysis strategies. Users can extend them or write new ones from scratch, then plug them in.

Method Cache Strategy

The JOP processor introduced an innovative method cache [Schoeberl2006]. Clepsydra is designed to take this cache into account when it encounters method invocations. For instance, the analysis can determine whether an invocation (or return) will be a guaranteed cache hit, at least in certain situations, thereby reducing the pessimism of the WCET result.

Because the method cache can have different configurations (single block, dual block, or variable block), Clepsydra factors out its cache analysis as a strategy. Simply called the MethodCacheStrategy, it includes functions for determining the cache hit ratio of an invocation and whether a method return is a guaranteed hit.

Clepsydra provides two simple implementations of this interface, SingleMethodCacheStrategy and DualMethodCacheStrategy. They are intended for cache configurations in which methods are stored in single blocks. (A more complex cache configuration, known as the variable block cache, is not currently supported.) Users can plug in different caching strategies depending on the cache configuration of the target processor.


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.

Clepsydra flow chart

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.

Export Formats

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.

Diagram of control flow with WCET

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.

Command Line Interface

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.)

edu.uci.eecs.doc.cascade.Clepsydra [-bytecode] {-classpath classpath} [-dot filename] [-gml filename] [-graphml filename] {[-tree] | [-ipet]} {-loopbounds classname} {-method signature} {-methodcache classname} [-print] [-recursive] [[-svg filename] | [-svgColorized filename]] [-text filename] {-timings classname}


If specified, Clepsydra will add a list of bytecode instructions to each control flow node in all output formats.


A list of directories that will be searched when loading classes during WCET analysis. Each path in the list must be separated by the system's path separator (e.g., : on UNIX-based systems).


If specified, Clepsydra will save a representation of the control flow graph in DOT format to the given file. Each node in the graph will also show its WCET, computed using the tree strategy.


If specified, Clepsydra will save a representation of the control flow graph in GML format to the given file.


If specified, Clepsydra will save a representation of the control flow graph in GraphML format to the given file.


Computes the WCET using the IPET strategy and prints the result. At least one of -tree or -ipet must be specified.


The name of a class that implements the LoopBoundStrategy interface.


The method to be analyzed for WCET. The method signature must be fully qualified. For example, the signature for indexOf is java.lang.String.indexOf(java.lang.String,int).


The name of a class that implements the MethodCacheStrategy interface.


If specified, Clepsydra will print a plain-text representation of the control flow tree to the console. Each node in the tree will also show its WCET, computed using the tree strategy.


When producing output, also include details of methods that are invoked (directly or indirectly) by the given method.


If specified, Clepsydra will save a representation of the control flow tree in SVG format to the given file. Each node in the tree will also show its WCET, computed using the tree strategy.


If specified, Clepsydra will save a representation of the control flow tree in a color-coded SVG format to the given file.


If specified, Cascade will save a representation of the control flow tree in plain text format to the given file. Each node in the tree will also show its WCET, computed using the tree strategy.


The name of a class that implements the InstructionTimingStrategy interface.


Computes the WCET using the tree strategy and prints the result. At least one of -tree or -ipet must be specified.

Application Programming Interface

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.

[2] A clepsydra is a clock that measures time by the escape of water.

Chapter 5. jEdit Plugins

Tools like Eclipse, NetBeans, and Visual Studio provide various mechanisms, known as plugins, for customizing the appearance and behavior of the editing environment. Plugins can therefore be designed to insert Clepsydra's WCET back-annotations directly into the editor window. They can also generate continuously updated control flow visualizations produced by Cascade. As the developer edits the source code, the plugin can run its analysis in the background and then automatically update the environment to match the changes. Watch the Volta screencast for a “live” demonstration of this feature.

Clepsydra Plugin

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.

Screenshot of the jEdit plugin


The jEdit plugin includes an Ant script that simplifies the installation process. First, make sure that the script's jedit.jars.dir property points to the location of jEdit's plugin JAR directory. (The default value should work fine.) Next, run ant install. This will build the plugin JAR and install it to the plugin directory. If you have previously installed the plugin, you will then need to either restart jEdit or use Activator to reload the plugin.

Also note that Clepsydra requires various third-party libraries, so the installation command copies them to the jEdit directory, as well. The list of dependent libraries is stored in the plugin.edu.uci.eecs.doc.clepsydra.plugins.jedit.Plugin.jars property of Clepsydra.props; it must be updated if Clepsydra's dependencies ever change.


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


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.

Screenshot of the jEdit plugin options dialog box


When the plugin has been installed, configured, and enabled, the back-annotation process will begin whenever a file is saved.

Choosing the PluginsClepsydra menu item will show or hide the back-annotations for the current buffer.

Cascade 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.

Chapter 6. Canteen

Libraries are vital to the software development process. By providing reusable code, they save developers time that would otherwise be spent creating sorting algorithms and other general-purpose functions. However, most libraries are designed to have good average-case performance, and little thought is given to their worst-case performance. As a result, the execution time of their operations may be difficult to predict, making them unsuitable for real-time systems.

For hard real-time systems, where guaranteed predictability is not just important but crucial, a new approach to software libraries is necessary. Such libraries should conform to safety-critical specifications that demand complete WCET analyzability and other forms of static verification. Achieving this goal demands certain restrictions: 1) The maximum bound of every loop in the library must be known; 2) exceptions are prohibited; and 3) dynamic memory allocations (after initialization) are prohibited.

As a demonstration of how to create an analyzable library, Volta includes Canteen, a set of predictable collection classes. It provides hard real-time versions of an array, linked list, set, and map, each of which conforms to its equivalent standard Java interface, including support for generics.


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.

Using Canteen with the Clepsydra Plugin

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.

Chapter 7. Java Compiler for WCET Annotations

Volta is certainly not the first set of tools for WCET analysis for Java. Several such prototypes have been created, and more are under development. Unfortunately, each relies on a competing and incompatible convention for annotations, resulting in portability problems and duplication of effort. For example, the Skånerost tool uses annotations that look like /*$ loop-bound 10 */, while the annotations in JOP's WCA tool look like //@WCA loop=10. Each tool requires custom parsers for these annotations, and source code written for one tool cannot be analyzed by the other without a rewrite.

Java's own annotation mechanism could solve these problems. The standard annotations in Java would provide a common platform for WCET analysis, improving portability and reducing the effort necessary to create analysis tools. However, Java annotations cannot be placed on critical source code statements such as loops, rendering the mechanism useless for WCET annotations.

The JSR-308 committee is currently investigating the possibility of removing this restriction, as discussed in the JSR-308 Statements document. In the meantime, the Volta tool suite includes a modified version of the standard Java compiler that allows annotations on loops. It parses the annotations for correctness and creates a representation of them in the Java class output. Tools such as Clepsydra can obtain the annotation parameters by loading the class attributes using BCEL or a similar tool.

To use this customized Java compiler, simply build and run it as you would the standard javac compiler. Instructions are available at the OpenJDK web site.

Annotation Data Format

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.

Dump Annotations Utility

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.

Appendix A. Known Limitations

The Volta suite is still in a prototype stage and has many known issues and limitations. It currently lacks support for:

  • Recursion

  • Polymorphism

  • Exception handling

  • switch, break, and continue statements

  • Inner and anonymous classes

In addition, a number of bugs exist in the supported features. For example, tree-based WCET calculation produces invalid results in the presence of return statements that are not the last statement in the method. A list of known bugs can be found in the Volta Bugs Tracker.

Appendix B. Further Reading

Interactive Worst-case Execution Time Analysis of Hard Real-time Systems. Ph.D. dissertation. 2009. Trevor Harmon.

Toward Libraries for Real-Time Java. May 2008. The Eleventh IEEE International Symposium on Object Oriented Real-Time Distributed Computing (ISORC 2008). . Trevor Harmon, Martin Schoeberl, Raimund Kirner, and Raymond Klefstad.

A Modular Worst-case Execution Time Analysis Tool for Java Processors. April 2008. The Fourteenth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2008). . Trevor Harmon, Raimund Kirner, Martin Schoeberl, and Raymond Klefstad.

Interactive Back-annotation of Worst-case Execution Time Analysis for Java Microprocessors. August 2007. The Thirteenth IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007). . Trevor Harmon and Raymond Klefstad.

Toward a Unified Standard for Worst-Case Execution Time Annotations in Real-Time Java. March 2007. The Fifteenth International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS 2007). . Trevor Harmon and Raymond Klefstad.

A Survey of Worst-Case Execution Time Analysis for Real-Time Java. March 2007. The Ninth International Workshop on Java and Components for Parallelism, Distribution and Concurrency (JAVAPDC 2007). . Trevor Harmon and Raymond Klefstad.

[Schoeberl2006] WCET Analysis for a Java Processor. October 2006. The Fourth International Workshop on Java Technologies for Real-time and Embedded Systems (JTRES 2006). . Martin Schoeberl and Rasmus Pedersen.

Appendix C. GNU General Public License

Version 2, June 1991

Free Software Foundation, Inc. 
  51 Franklin Street, Fifth Floor
  BostonMA 02110-1301

Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.

Version 2, June 1991


The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software - to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too.

When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.

To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it.

For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights.

We protect your rights with two steps:

  1. copyright the software, and

  2. offer you this license which gives you legal permission to copy, distribute and/or modify the software.

Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations.

Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all.

The precise terms and conditions for copying, distribution and modification follow.


Section 0

This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The “Program”, below, refers to any such program or work, and a “work based on the Program” means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term “modification”.) Each licensee is addressed as “you”.

Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does.

Section 1

You may copy and distribute verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program.

You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee.

Section 2

You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions:

  1. You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change.

  2. You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License.

  3. If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: If the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.)

These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it.

Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program.

In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License.

Section 3

You may copy and distribute the Program (or a work based on it, under Section 2 in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following:

  1. Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,

  2. Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,

  3. Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.)

The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable.

If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code.

Section 4

You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.

Section 5

You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it.

Section 6

Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License.

Section 7

If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program.

If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances.

It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice.

This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License.

Section 8

If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License.

Section 9

The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns.

Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and “any later version”, you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation.

Section 10

If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally.

NO WARRANTY Section 11


Section 12



How to Apply These Terms to Your New Programs

If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms.

To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the “copyright” line and a pointer to where the full notice is found.

<one line to give the program's name and a brief idea of what it does.> Copyright (C) <year> <name of author>

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

Also add information on how to contact you by electronic and paper mail.

If the program is interactive, make it output a short notice like this when it starts in an interactive mode:

Gnomovision version 69, Copyright (C) year name of author Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type “show w”. This is free software, and you are welcome to redistribute it under certain conditions; type “show c” for details.

The hypothetical commands “show w” and “show c” should show the appropriate parts of the General Public License. Of course, the commands you use may be called something other than “show w” and “show c”; they could even be mouse-clicks or menu items--whatever suits your program.

You should also get your employer (if you work as a programmer) or your school, if any, to sign a “copyright disclaimer” for the program, if necessary. Here is a sample; alter the names:

Yoyodyne, Inc., hereby disclaims all copyright interest in the program “Gnomovision” (which makes passes at compilers) written by James Hacker.

<signature of Ty Coon>, 1 April 1989 Ty Coon, President of Vice

This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Library General Public License instead of this License.