WCET Determination: Introduction

   Hard real-time systems have specified deadlines for their tasks. It is the duty of the developer to guarantee that the tasks making up the system will always meet the deadlines specified. When it comes to processors with caches and complex pipelines, computing sharp upper limits on the worst-case execution time (WCET) is of critical importance.

   There is a tremendous gap between the cycle times of modern microprocessors and the access times of main memory. Caches are used to overcome this gap in virtually all performance-oriented processors (including high-performance microcontrollers and DSPs). Pipelines enable acceleration by overlapping the executions of different instructions. The consequence is that the execution behavior of the instructions cannot be analyzed separately since it depends on the execution history.

   Cache memories usually work without any hitches, but under some circumstances, however, minimal changes in the program code or program input may lead to dramatic changes in cache behavior. For (hard) real-time systems, this is undesirable and possibly even hazardous. The widely used classical methods of predicting execution times are not generally applicable:

• Software monitoring or the dual loop benchmark changes the code, in the process influencing the cache behavior.
• Hardware simulation, emulation, or direct measurement with logic analyzers can only determine the execution time for one particular input. This can generally not be used to infer the cache behavior for all possible inputs.
• Making the safe, yet for the most part unrealistic assumption that all memory references result in cache misses results in the execution time being overestimated by several hundred percent. Overestimates of the execution time in turn result in waste of hardware resources.

Next: Timing validation | Previous: WCET determination | Contents | Home