Introduction
This page documents the research activity undertaken at Imperial College with respect to WCET analysis.
Tool Support
Tool support in WCET analysis is invaluable in assessing how techniques perform against each other. For this very reason, we aim to provide public accessibility to the tools developed at Imperial College London.
Running the Tools
All our tools ship either as executable jar files or Python scripts. They have been tested extensively on 32-bit versions (and in some cases on 64-bit versions) of Ubuntu. They should run without the slighest hint of trouble! We would be delighted (and at the same time disappointed) to hear about bugs using the email address below.
Our tools are littered with assertion checks. To safeguard against problems downstream, we recommend running the Java interpreter with assertions enabled (the -ea option).
A tool comes with a bunch of options, some of them, quite bizarrely, are non-optional options. To see the options available to a specific jar tool run:
java -ea -jar <tool>.jar -h
Equally for a Python tool run:
python <tool>.py -h
Python
Our analysis tools run with Python 2.7. They have not been tested for backward compatability, nor are they likely to work with Python 3.0 onwards.
lp_solve
Some of our tools use integer linear programming to compute WCET estimates. Our tools assume you have the lp_solve application in your PATH. See the lp_solve website for more details.
uDraw(Graph) Integration
All of our tools allow the data structures (CFGs, dominator trees, etc.) used to be visualised via uDraw(Graph). See the help output of a tool for more details.
WCET benchmarks for dynamic analysis
We have modified the widely-used WCET benchmarks supplied by Mälardalen University so that they are amenable to dynamic analyses. Each C file is associated with a corresponding test file (with suffix .test) which specifies precisely the expected inputs. The benchmarks and test files are available here.
Tools Currently Available
- Infeasible path elimination: download analysis tools
Important: to run these tools you need to install: an ARM cross compiler with binutils support (available through packages gcc-arm-linux-gnueabi and binutils-arm-linux-gnueabi on Ubuntu), Gem5 (we only support the ARM build), lp_solve, ECLiPSe and pyevolve.
This tool eliminates infeasible paths using a mixture of super block analysis, suppression of redundant flow facts through logical relations, dynamic analysis and bounded model checking.
To run a program on Gem5 with a single, random automatically-generated test vector, then do a WCET calculation with the information collected from Gem5 execution runs, do the following:
python src/ToolGem5.py -r root file.c -T 1
where root is the root function to which the analysis is restricted and file.c is the C file. We have modified the Mälardalen WCET benchmarks (see above) so that the name of the root function and the name of the C file correspond. For example, for a file called foo.c the root function is called foo.
To run a program on Gem5 with test vectors produced by a genetic algorithm, then do a WCET calculation with the information collected from Gem5 execution runs, do the following:
python src/ToolGem5.py -r root file.c --ga
You can also post-process previously generated Gem5 traces as follows:
python src/ToolGem5.py -r root file.c trace.gz
where trace.gz is the compressed Gem5 trace file.
- WCET analysis of GPU code: download analysis tools and download gpgpu-sim-3.20
Important: to run this tool you need install the version of GPGPU-sim which we ship. GPGPU-sim itself has several dependencies - see the documentation supplied for further information. We have tested this infrastucture using NVIDIA's CUDA compiler, v4.0.
This tool computes an estimate of the WCET of a GPU application running on NVIDIA hardware. Two values are computed: one is based on how long a warp is stalled according to measurements; the other builds an analytical model of warp execution on streaming multiprocessors and obtains values for parameters in this model from measurements.
- CFG generation: download jar
This tool generates Control Flow Graphs (CFGs). The tool accepts arguments to control the number of vertices, the maximum fan out of any vertex, how many loops to incorporate into the CFG, the loop-nesting depth, and whether to include break and continue edges in loops.
In principle it can produce a number of CFGs represeting an entire program. There is also support for recursion (direct and indirect). However, at the current time, subprogram generation is a little buggy.
- WCET computation: download jar
Important: to run this tool you need to have the 32-bit version of the Java lp_solve libraries in your LD_LIBRARY_PATH. See the lp_solve website for more details.
This tool produces a WCET estimate from a program by assigning unit cost to basic blocks in each CFG and assigning loop bounds according to the nesting-level of the header. Thus it does not solve WCET estimates for "real" programs as yet.
Contact
For more information email Adam Betts, the maintainer of this page.