Introduction

Predicting the execution time of programs or code segments is a difficult task. Yet, in the context of hard real-time systems, it is essential to provide a schedule for tasks with known deadlines. Thus, tasks have to be analyzed to determine their best-case execution time (BET) and worst-case execution time (WET). The following problems have to be addressed to predict the execution time of a task or program:

• The number of loop iterations needs to be known prior to execution. It is often required that the maximum number of iterations is provided by the programmer [].
• The possible execution paths in the control flow have to be analyzed to predict both BET and WET.
• Architectural features have to be taken into account (e.g. pipeline stalls).

Cache memories have become a major factor to bridge the bottleneck between the time to access main memory and the faster clock rate of current processors. In the context of real-time systems, caches have been regarded as a source for unpredictability which conflicts with the goal of making the execution of tasks deterministic []. For a system with an instruction cache as a primary (on-chip) cache, the execution time of an instruction can vary greatly depending on whether the given instruction is in cache or not. In addition, context switches and interrupts may replace the instructions cached by one task with instructions from another task or an interrupt handler. As a result, it has been common practice to simply disable the cache for sections of code when predictability was required [].

This work shows that it is possible to predict some cache behavior with certain restrictions. Let a task be the portion of code executed between two scheduling points (context switches). When a task starts execution, the cache memory is assumed to be invalidated. During task execution, instructions are gradually brought into cache and often result in many hits and misses which can be predicted by Static Cache Simulation, a technique which analyzes control flow prior to execution time. Furthermore, a slight change in the architecture in conjunction with the simulator's analysis allows, without loss of predictability, significantly faster execution time than on system with a disabled instruction cache.

This paper is structured as follows: Section 2 reviews related work in the area. Section 3 introduces the method of Static Cache Simulation. Section 4 details a bit-encoding approach which can exploit caches for real-time systems. Section 5 provides a quantitative analysis of both Static Cache Simulation and the bit-encoding approach. Section 6 outlines future work and section 7 presents the conclusions of this study.