Q: Finding the worst-case execution time includes deciding if the program will halt at all, which is known to be an unsolvable problem, so how can Bound-T work?
A: The problem is unsolvable in general, but solvable for a large class of restricted programs. For example, it is trivial if the program has no conditional statements, loops or recursion. If the program has conditional statements, but no loops or recursion, an upper bound on the worst-case time is always solvable. Bound-T analyses programs with conditional statements and loops but without recursion. For amany loops, the loop-counter variable is so evident that Bound-T can determine an upper bound on the number of iterations, and thus an upper bound on the worst-case execution time. For other loops, Bound-T expects the user to state a bound on the iterations, either through an assertion file, or interactively when Bound-T asks for it.
Bound-T is most effective if the target program is designed and coded following specific guidelines that make the program analysable.
Note, by the way, that the question whether a given program always meets a given deadline, is decidable in general, since there are only finitely many possible executions before the deadline. If all these executions terminate before the deadline, the answer is yes, otherwise no. However, Bound-T does not use this approach, since it is obviously prone to combinatorial explosion.
Q: How will cache memories affect the result of WCET calculations? The worst time may be overestimated or may be correct, but the average execution time will be considerably less.
A: Yes, cache memories do have this complicating effect. On the other hand, in real-time systems tasks are often pre-empted and switched, which means that they share the cache and there may be many more cache misses than in sequential programs, and so the worst-case time is closer to reality.
Moreover, the processors used in embedded applications are often quite small, and do not have much cache. Instead, in real-time systems frequently used data or code is often statically allocated and locked into fast memories rather than dynamically loaded into a cache. Since the really critical data or code is often small, this reduces cost and improves timing predictability.
Bound-T currently makes no attempt to model caches, but there is academic research in this area, which in the future could give us practical methods to take caches into account. Instruction caches can already be modelled with moderate effort, but data cache is harder.
Q: What if the worst case is so rare that it is not relevant in real-world? Values like the average execution time, or the time with 95% probability, could have more value?
A: The answer depends on whether the system is a critical hard real-time system, where missing a single deadline can lead to system failure, perhaps even killing people, or a non-critical or soft real-time system, in which deadline misses decrease performance and may make customers unhappy, but are not catastrophic.
For hard real-time systems, which are the main target of Bound-T, obviously the absolute worst-case time is the relevant value. Exceptions can only be made for execution paths that occur when there already is a failure in the system. Such exceptional paths can be excluded from Bound-T analysis by assertions (which must, of course, be documented and explained). There is also a branch of WCET research that aims to compute a WCET bound with a very low risk of being exceeded, such as 10^-8 (G. Bernat, University of York), which may be sufficient for critical systems if the risk of other failures such as hardware errors is of the same order of magnitude.
For a soft real-time system, if the worst case reported by Bound-T seems unlikely, the same method can be used to eliminate unlikely cases one by one. The claim that the average performance will be satisfactory can then be supported by listing the eliminated cases and their estimated frequencies and execution times. However, testing is still the best way to determine average performance, especially in distributed systems with much queuing and scheduling.
Q: What about the best (shortest) execution time?
A: A lower bound on the best-case time could be found in the same way as Bound-T bounds the worst-case time, and this is planned as a future extension of Bound-T.
Q: Is Bound-T a complete tool for real-time software development, or do I need to buy some other tools?
A: Bound-T should be seen as an addition to a typical software development toolkit. Of course you still need an editor, compiler, linker, and perhaps a debugger. Bound-T has some functional overlap with profiling tools, which show the actual execution time of a test execution, and how this time is distributed across program units.
For concurrent real-time systems, with multiple threads of execution, a good complement to Bound-T is a schedulability analyser. This is a program that is given the set of threads and the execution frequency and worst-case execution time of each thread, and tells you whether the threads can be scheduled so that all deadlines are met. Schedulability analysers are often based on the Rate Monotonic Analysis (RMA) and are available from other vendors, but all need worst-case execution times as input.
Q: Is Bound-T compatible with my target processor <insert processor name>?
A: Because Bound-T analyses the machine instructions of the target program, there is a different version of Bound-T for each supported target processor.
At present (July 2002), Bound-T supports the Intel 8051 8-bit microcontroller series, the 32-bit ADSP-21020 digital signal processor, and the SPARC V7 processor (in the ERC32 implementation).
Bound-T is designed to be easily adaptable to new target processors, and additional processors will be supported to satisfy customer needs and market demands. Let us know your needs!
Q: Is Bound-T compatible with my programming language?
A: Bound-T is generally independent of the programming language in which the target program is written, because Bound-T analyses the binary object code (the executable program) and not the source code. Any dependency is more likely to concern the particular compiler or real-time kernel than the language (see below).
Q: Is Bound-T compatible with my compiler and linker?
A: Bound-T is generally independent of the compiler and linker used for the target program, as long as the standard calling sequence (ABI, Application Binary Interface) of the target is followed, and as long as the executable is in a standard format (e.g. COFF or ELF).
Bound-T will be optimised to support the particular code-generation style and code idioms of popular compilers, to increase the automation and convenience of the analysis. For each supported target processor, Bound-T aims to support the major (most common) compilers, linkers and executable formats.
For the Intel-8051 series, Bound-T currently supports the Keil compiler (Keil/Intel AOMF format) and the IAR compiler (UBROF format). Support for the Small Device C Compiler (SDCC) is being implemented.
For the ADSP-21020 series, Bound-T currently supports the ADI g21k compiler, which is based on the the GNU C compiler, and the ADI linker which generates executables in COFF.
For the SPARC V7 / ERC32, Bound-T currently supports both C and Ada programming using the GNU compilers in the Open Ravenscar Kernel which generate ELF32 binaries. Other version of the GNU compilers can also be used, for example the GAP compilers (GNAT Academic Program).
Note that the GNU program objcopy can translate a target program between different binary formats.
Q: Is Bound-T compatible with my real-time kernel?
A: When Bound-T is used to analyse a program that is linked with a real-time kernel, kernel calls can be handled in two ways.
The first way is to let Bound-T analyse the kernel routines in the same way as the application routines. This might succeed automatically, but this is perhaps unlikely since kernel code tends to be rather peculiar and to violate normal rules on calling sequences, stack usage etc. If the automatic analysis fails, the user may have to assert iteration bounds for loops in the kernel routines, which may be quite hard to do, if kernel source-code is not available, or if the kernel is complicated and dynamic.
The second way is to assert worst-case times for each kernel call, using documentation from the kernel supplier. This is the recommended way, since it does not require inside information on the kernel, and does not ask Bound-T to analyse peculiar kernel-level code.
For a kernel that is closely integrated with a specific programming language, such as a run-time system for Ada, a special version of Bound-T may be needed if the kernel calls do not follow the normal calling sequences.
Q: I develop programs for several target processors, with several compilers and kernels. Do I have to pay for each version of Bound-T that I would need?
A: There will be a basic price for the first version of Bound-T, and a reduced price for each additional version of a different target processor or for other special adaptations (compiler, kernel, programming language).