Table of Contents
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.)
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.
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.
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.
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;
.
.
.
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;
@LoopBound(max=10)
for (int i = j; i < 10; i++)
{
j++;
}
}
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.
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.
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.