WCET vision
From JopWiki
[edit] The Vision
The goals of this project are,
- To minimize the need for annotations when doing WCET for Java programs, by using advanced program analysis, e.g. constant propagation.
- To help the programmer identify those places in a program where annotations cannot be avoided.
- To define powerfull and non trivial annotations that carry knowledge that cannot be inferred by any form of static analysis.
- To aid the programmer in creating and maintaining unavoidable annotations.
We want to implement a plugin for Eclipse that integrates only those WCET annotations that cannot be avoided into the workflow of the programmer in a non-intrusive manner.
[edit] Latest News
As argued below constant propagation can be used to illiminate trvial annotations, and least these should be illiminated, but it cannot be used to illiminate more advanced annotations (like in the example below with the bubble sort algorithm).
I'm currently exploring the use of other types of static program analysis that expands(calculates) the entire set of potential execution paths through a given program. The task is then from this set to find the longest path.
Now this is in general not possible as the set of possible execution paths is too big, but this maybe can be alliviated by combining constant propagation with other types of limitations to cut off parts of the set of possible execution paths.
The first goal is to automatically give a WCET of the bubble sort algorithm (included below) without the need for annotations, but maybe with the need to rewrite the program a bit.
So far just experimenting.....
Bubble sort contains a triangular loop - not the simplest example to begin with. Martin 08:03, 6 September 2007 (CDT)
[edit] Minimizing the need for annotations
The current state-of-the-art implementations for WCET analysis of Java programs rely on the programmer inserting annotations into the source code to help the WCET analysis tool give a tight upper bound. Consider the following example,
void method(int x)
{
int[] arr;
if (x < 10)
{
arr = new int[x];
for (int i = 0; i < arr.length; i++)
{
arr[i] = i;
}
}
else
{
throw new Exception("Illegal input");
}
}
In this example there is no need to use annotations to calculate a tight WCET. The reason is that constant propagation can be used to infer the upper limit to all values used. Thus in simple examples as above we can get rid of the need for annotations.
Now consider the following example,
void sort(int[] numbers) {
int top = 0;
while (top < numbers.length - 1) {
if (numbers[top] <= numbers[top + 1]) {
top++;
} else {
int temp = numbers[top];
numbers[top] = numbers[top + 1];
numbers[top + 1] = temp;
if (top > 0) {
top--;
}
}
}
}
This is an implementation of the Bubble sort algorithm for sorting numbers. Even if we can use constant propagation to infer the upper bound to the length of the array being sorted, there is still no way of infering the maximum loop bound of the while-loop. Thus annotations are unavoidable, but should only be required where it is absolutely needed.
[edit] Giving the right annotations
From other diciplines of computer science we know that the execution time of the Bubble sort algorithm is O(n2), but it is impossible to create a tool that can calculate this bound just by looking at the code. Instead we should allow the programmer to insert annotations stating the loop bound of the while loop as a function of known inferable values, in this case the loop bound will be array.length2.
In general it should not be needed to insert annotations that contain information that can be infered by analysing the source code.
[edit] Creating an WCET Eclipse plug-in
We want to create a plug-in for Eclipse that support the following,
- In the back ground the plug-in will perform various types of static analysis of the Java program being edited. This could be e.g. constant propagation analysis to aid in determining trivial upper bounds of loops and other programming constructs.
- Information being gathered from the background analysis should be visible to the programmer without degrading the readability of the source code.
- The plug-in should notify the programmer of problematic programming constructs that make static analysis impossible or of little value. This way the programmers attention will be directed toward creating programs that are analyzable.
- The plug-in should notify the programmer of places where annotations cannot be avoided, at those spots the plug-in should support the creation of correct and useful high level annotations.
- The plug-in should help manage the annotations and keeping them properly attached and correct as the user edits the code.
- Finally the plug-in should make visible to the programmer the correct result of the WCET analysis. This result should be updated incrementally and in real time as the source code is being edited.
This is the vision.
[edit] Papers
List of papers relevant to this work, with a short note about the content of the paper.
[edit] A Review Of Worst-Case Execution-Time Analysis
A good review of WCET work upto 1999. Focused on the hardware specfific issues (low-level analysis), not so much the high-level analysis (data flow analysis).
[edit] Addressing Dynamic Dispatching Issues in WCET Analysis for Object-Oriented Hard Real-Time Systems
Try to give a proper estimate on the WCET of method calls at polymorphic call sites.
Using annotations the programmer must restrict the possible type of the this at polymorphic call sites.
[edit] Deriving Java Virtual Machine Timing Models for Portable Worst-Case Execution Time Analysis
If a proper data flow analysis is completed (possibly with the help of annotations), the tasks still remains to calculate the absolute WCET using knowledge about the WCET of each individual byte code. This paper gives various ways of creating a Virtual Machine Timing Model which is a mapping of byte codes to WCET for each byte code. Together with the high level analysis this gives the final WCET.
[edit] Interactive Back-annotation of Worst-case Execution Time Analysis for Java Microprocessors
A description of a very clever tool that - still using annotations - adorns the source code in the editor with WCET of each line in the source code. Integrated the WCET analysis into the editing cycle of the programmer. Is implemented in JEdit.
[edit] Faster WCET flow analysis by program slicing
Relates to more advanced analysis of WCET by exploring the entire state space of the program in a clever way. Haven't read it entirely yet, but initially it looks very interesting.
