Cache contents selection for statically-locked instruction caches: an algorithm comparison

Cache memories have been extensively used to bridge the gap between high speed processors and relatively slower main memories. However, they are sources of predictability problems because of their dynamic and adaptive behavior, and thus need special attention to be used in hard real-time systems. A lot of progress has been achieved in the last ten years to statically predict worst-case execution times (WCETs) of tasks on architectures with caches. However, cache-aware WCET analysis techniques are not always applicable or may be too pessimistic. An alternative approach allowing to use caches in real-time systems is to lock their contents (i.e. disable cache replacement) such that memory access times and cache-related preemption times are predictable. In this paper, we compare the performance of two algorithms for static locking of instruction caches: one using a genetic algorithm for cache contents selection (A.M. Campoy et al., 2001) and a pragmatical algorithm, called her-after reference-based algorithm (I. Puaut and D. Decotigny), which uses the string of memory references issued by a task on its worst-case execution path as an input of the cache contents selection algorithm. Experimental results show that (i) both algorithms behave identically with respect to the system worst-case utilization; (ii) the genetic algorithm behaves slightly better than the reference-based algorithm with respect to the average slack of tasks; (iii) the execution time of the cache-contents selection procedure is much better when using the reference-based algorithm than with the genetic algorithm.