Background on Worst-Case Execution Time (WCET) estimation
Knowing task worst-case execution times (WCET) is of prime importance for the timing analysis of hard real-time systems.
Timing analysis is in general made of two levels : WCET analysis and schedulability analysis. WCET analysis considers the time requirements of an isolated task. At this level, activities other than ones related to the considered task are ignored. Tasks are assumed to never block (blocking is dealt with by the schedulability analysis). At the upper level (i.e. the schedulability analysis level) multiple tasks execute on the processor and compete for resources, and thus may block while attempting to access the resources.The tightness of schedulability analysis relies on the accuracy of the WCET analysis.
A static WCET analysis tool should be able to work on the high-level to determine the structure of a program’s task, working either on a piece of source code or disassembled binary executable. But it should also work on a low-level basis, depending on the real hardware that the task will execute on, with all the specific features it holds. Making those two kinds of analysis, the tool should give an upper bound on the time required to execute a given task on a given hardware.
At the low-level, static WCET analysis is complicated due to the presence of architectural features that improve the performances of the processor : instruction/data caches, branch prediction and pipeline for example. Taking into account modern architectural features makes it possible to determine tight WCET bounds. On a given architecture, it is possible thanks to the modeling of modern architectural features.
We have designed an open-source static WCET analysis tool named Heptane. The first version of Heptane has been designed around 2000. Heptane implements IPET (Implicit Path Enumeration Technique) and includes cache analysis techniques for many cache architectures (several replacement policies, cache hierarchies, shared caches on multi-cores).
- supported instruction sets: MIPS, ARM
- runs on Linux and MacOS (no support for Windows)
- programming language used to program Heptane: C++
- open source software, GPL licence
- contents of the archive:
- source code of Heptane,
- source code of the compatible gcc toolchain to compile programs,
- source code of control flow graph management library,
- annotated benchmark programs
- development status: stable research prototype
- provided support: limited
Download link: heptane_svn.tgz (generated Dec, 16th, 2016)
Bug report/support/questions: send us (Isabelle Puaut, Damien Hardy, and Loïc Besnard) an e-mail.