A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Scratchpad Memories <s> We propose in this paper an algorithm for off-line selection of the contents of on-chip memories. The algorithm supports two types of on-chip memories, namely locked caches and scratchpad memories. The contents of on-chip memory, although selected off-line, is changed at run-time, for the sake of scalability with respect to task size. Experimental results show that the algorithm yields to good ratios of on-chip memory accesses on the worst-case execution path, with a tolerable reload overhead, for both types of on-chip memories. Furthermore, we highlight the circumstances under which one type of on-chip memory is more appropriate than the other depending of architectural parameters (cache block size) and application characteristics (basic block size). <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Scratchpad Memories <s> Scratchpads have been widely proposed as an alternative to caches for embedded systems. Advantages of scratchpads include reduced energy consumption in comparison to a cache and access latencies that are independent of the preceding memory access pattern. The latter property makes memory accesses time-predictable, which is useful for hard real-time tasks as the worst-case execution time (WCET) must be safely estimated in order to check that the system will meet timing requirements. However, data must be explicitly moved between scratchpad and external memory as a task executes in order to make best use of the limited scratchpad space. When dynamic data is moved, issues such as pointer aliasing and pointer invalidation become problematic. Previous work has proposed solutions that are not suitable for hard real-time tasks because memory accesses are not time-predictable. This paper proposes the scratchpad memory management unit (SMMU) as an enhancement to scratchpad technology. The SMMU implements an alternative solution to the pointer aliasing and pointer invalidation problems which (1) does not require whole-program pointer analysis and (2) makes every memory access operation time-predictable. This allows WCET analysis to be applied to hard-real time tasks which use a scratchpad and dynamic data, but results are also applicable in the wider context of minimizing energy consumption or average execution time. Experiments using C software show that the combination of an SMMU and scratchpad compares favorably with the best and worst case performance of a conventional data cache. <s> BIB002
Finally, it must be noted that scratchpad memories have been proposed as a more predictable alternative to caches, especially but not limited to real-time systems. The scratchpad memory is a special static RAM memory placed close to the processor (on-chip, similar to L1-cache). The address space of the scratchpad is mapped onto predefined memory address of the processor. Unlike caches, the scratchpads have to be explicitly managed. In other words, the memory blocks have to be moved in software from main memory and copied into the scratchpad before being used. Thus, scratchpads are highly predictable in the sense that they have one access latency compared to caches with two different latencies for cache hit and miss. However, the need for explicit program management means that legacy programs cannot be easily executed on scratchpad-based systems; for this reason, support for scratchpad memory in available commercial systems is limited. Since the focus of this survey is specifically on management mechanisms for cache-based systems, we do not cover scratchpad-based systems in details in the following sections; however, we provide a brief summary of work concerning scratchpad allocation below to allow a comparison with cache systems. In general, cache locking and scratchpad allocation have similar objectives: to control the set of memory blocks present in local memory at any time. However, as noted in BIB001 and BIB002 , there are significant differences between caches and scratchpad. First, scratchpads do not suffer from intratask interference, since the allocation of memory blocks is entirely under the control of the programmer/compiler; cache locking cannot prevent conflicts due to too many cache lines being allocated to the same associative set. However, since scratchpads are not transparent with respect to address translation, management schemes have to impose significant constraints on analyzable code; in particular, memory aliases must be statically resolved, since otherwise the management scheme risks loading the same data into two different positions in the scratchpad. A second important difference is related to the type of fragmentation. Cache-based systems suffer from internal fragmentation, since they cannot load data blocks smaller than the size of a cache line. Scratchpad-based systems suffer from external fragmentation because they are forced to load memory blocks of varying size into contiguous memory locations in the scratchpad. As shown in BIB001 , the relative performance of locked caches versus scratchpads is thus dependent on the size of the considered memory blocks. Due to the discussed differences, we argue that most techniques and results for cache-based systems cannot be directly applied to scratchpad-based systems and vice versa.