A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Existing Solutions and Contributions <s> To narrow the widening gap between processor and memory performance, the authors propose improving the cache locality of pointer-manipulating programs and bolstering performance by careful placement of structure elements. It is concluded that considering past trends and future technology, it seems clear that the processor-memory performance gap will continue to increase and software will continue to grow larger and more complex. Although cache-conscious algorithms and data structures are the first and perhaps best place to attack this performance problem, the complexity of software design and an increasing tendency to build large software systems by assembling smaller components does not favor a focused, integrated approach. We propose another, more incremental approach of cache-conscious data layout, which uses techniques such as clustering, coloring, and compression to enhance data locality by placing structure elements more carefully in the cache. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Existing Solutions and Contributions <s> In multitasking real-time systems it is required to compute the WCET of each task and also the effects of interferences between tasks in the worst case. This is very complex with variable latency hardware, such as instruction cache memories, or, to a lesser extent, the line buffers usually found in the fetch path of commercial processors. Some methods disable cache replacement so that it is easier to model the cache behavior. The difficulty in these cache-locking methods lies in obtaining a good selection of the memory lines to be locked into cache. In this paper, we propose an ILP-based method to select the best lines to be loaded and locked into the instruction cache at each context switch (dynamic locking), taking into account both intra-task and inter-task interferences, and we compare it with static locking. Our results show that, without cache, the spatial locality captured by a line buffer doubles the performance of the processor. When adding a lockable instruction cache, dynamic locking systems are schedulable with a cache size between 12.5% and 50% of the cache size required by static locking. Additionally, the computation time of our analysis method is not dependent on the number of possible paths in the task. This allows us to analyze large codes in a relatively short time (100KB with 10^6^5 paths in less than 3min). <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Existing Solutions and Contributions <s> Poor placement of data blocks in memory may negatively impact application performance because of an increase in the cache conflict miss rate [18]. For dynamically allocated structures this placement is typically determined by the memory allocator. Cache index-oblivious allocators may inadvertently place blocks on a restricted fraction of the available cache indexes, artificially and needlessly increasing the conflict miss rate. While some allocators are less vulnerable to this phenomena, no general-purpose malloc allocator is index-aware and methodologically addresses this concern. We demonstrate that many existing state-of-the-art allocators are index-oblivious, admitting performance pathologies for certain block sizes. We show that a simple adjustment within the allocator to control the spacing of blocks can provide better index coverage, which in turn reduces the superfluous conflict miss rate in various applications, improving performance with no observed negative consequences. The result is an index-aware allocator. Our technique is general and can easily be applied to most memory allocators and to various processor architectures. Furthermore, we can reduce inter-thread and inter-process conflict misses for processors where threads concurrently share the level-1 cache such as the Sun UltraSPARC-T2™ and Intel "Nehalem" by coloring the placement of blocks so that allocations for different threads and processes start on different cache indexes. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Existing Solutions and Contributions <s> General-purpose dynamic memory allocation algorithms strive for small memory fragmentation and good av\-er\-age-case response times. Hard real-time settings, in contrast, place different demands on dynamic memory allocators: worst-case response times are more important than av\-er\-age-case response times. Furthermore, predictable cache behavior is a prerequisite for timing analysis to derive tight bounds on a program's execution time. This paper proposes a novel algorithm that meets these demands. It guarantees constant response times, does not cause unpredictable cache pollution, and allocations are cache-set directed, i.e., allocated memory is guaranteed to be mapped to a given cache set. The latter two are necessary to enable a subsequent precise static cache analysis. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Existing Solutions and Contributions <s> Locking cache lines in hard real-time systems is a common means to ensure timing predictability of data references and to lower bounds on worst-case execution time, especially in a multi-tasking environment. Growing processing demand on multi-tasking real-time systems can be met by employing scalable multi-core architectures, like the recently introduced tile-based architectures. This paper studies the use of cache locking on massive multi-core architectures with private caches in the context of hard real-time systems. In shared cache architectures, a single resource is shared among {\em all} the tasks. However, in scalable cache architectures with private caches, conflicts exist only among the tasks scheduled on one core. This calls for a cache-aware allocation of tasks onto cores. Our work extends the cache-unaware First Fit Decreasing (FFD) algorithm with a Naive locked First Fit Decreasing (NFFD) policy. We further propose two cache-aware static scheduling schemes: (1) Greedy First Fit Decreasing (GFFD) and (2) Colored First Fit Decreasing (CoFFD). This work contributes an adaptation of these algorithms for conflict resolution of partially locked regions. Experiments indicate that NFFD is capable of scheduling high utilization task sets that FFD cannot schedule. Experiments also show that CoFFD consistently outperforms GFFD resulting in lower number of cores and lower system utilization. CoFFD reduces the number of core requirements from 30% to 60% compared to NFFD. With partial locking, the number of cores in some cases is reduced by almost 50% with an increase in system utilization of 10%. Overall, this work is unique in considering the challenges of future multi-core architectures for real-time systems and provides key insights into task partitioning with locked caches for architectures with private caches. <s> BIB005 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Existing Solutions and Contributions <s> Multi-core architectures are shaking the fundamental assumption that in real-time systems the WCET, used to analyze the schedulability of the complete system, is calculated on individual tasks. This is not even true in an approximate sense in a modern multi-core chip, due to interference caused by hardware resource sharing. In this work we propose (1) a complete framework to analyze and profile task memory access patterns and (2) a novel kernel-level cache management technique to enforce an efficient and deterministic cache allocation of the most frequently accessed memory areas. In this way, we provide a powerful tool to address one of the main sources of interference in a system where the last level of cache is shared among two or more CPUs. The technique has been implemented on commercial hardware and our evaluations show that it can be used to significantly improve the predictability of a given set of critical tasks. <s> BIB006 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Existing Solutions and Contributions <s> Many modern multi-core processors sport a large shared cache with the primary goal of enhancing the statistic performance of computing workloads. However, due to resulting cache interference among tasks, the uncontrolled use of such a shared cache can significantly hamper the predictability and analyzability of multi-core real-time systems. Software cache partitioning has been considered as an attractive approach to address this issue because it does not require any hardware support beyond that available on many modern processors. However, the state-of-the-art software cache partitioning techniques face two challenges: (1) the memory co-partitioning problem, which results in page swapping or waste of memory, and (2) the availability of a limited number of cache partitions, which causes degraded performance. These are major impediments to the practical adoption of software cache partitioning. In this paper, we propose a practical OS-level cache management scheme for multi-core real-time systems. Our scheme provides predictable cache performance, addresses the aforementioned problems of existing software cache partitioning, and efficiently allocates cache partitions to schedule a given task set. We have implemented and evaluated our scheme in Linux/RK running on the Intel Core i7 quad-core processor. Experimental results indicate that, compared to the traditional approaches, our scheme is up to 39% more memory space efficient and consumes up to 25% less cache partitions while maintaining cache predictability. Our scheme also yields a significant utilization benefit that increases with the number of tasks. <s> BIB007
Several works have been proposed to cope with the described cache memory hierarchy problems in the context of real-time embedded systems and to tighten the WCET estimation. In general, such works rely on enforcing timing isolation between subcomponents in the system: the execution time of one subcomponent should not depend on the behavior of other subcomponents. Such isolation can be implemented (a) at the level of a single task, where subcomponents are functions or basic blocks in the task's code; (b) at the level of a core, where subcomponents are tasks; or (c) at the multicore system level, where subcomponents are individual cores or software partitions running on each core. Two approaches are most commonly used to enforce a more deterministic behavior on CPU caches. The first approach to timing isolation is cache partitioning, which divides the cache in partitions and assigns specific partitions to tasks or cores  BIB006  BIB007 . Based on the structure of a set-associative cache, these approaches can be further categorized in (a) indexbased cache partitioning, when partitions are formed as an aggregation of associative sets in the cache (horizontal slicing); and (b) way-based cache partitioning, when each available cache way is exclusively assigned to a single partition. The second technique that has been investigated is cache locking. Cache locking relies on hardware features present in many embedded platforms. Specifically, it is possible to flag a given cache line or way as locked, thus preventing its content from being evicted until a successive unlock operation is performed BIB002 BIB005 BIB006 . Both cache partitioning and locking can be available to applications through the operating system (OS) memory allocator. The problem of developing OS-level memory allocators that can perform cache-aware allocations and feature a predictable execution time has been addressed in BIB001 , BIB003 , and BIB004 . The common denominator for all the aforementioned techniques is to improve the predictability of real-time systems deployed on top of cache-based architectures, in order to provide better isolation guarantees for real-time embedded applications. Even though the focus of this survey is real-time systems, we also include some related work for general purpose systems. We note that the optimization techniques for the latter systems are throughput oriented as opposed to worst-case oriented. In the process of improving the overall throughput, the timing requirement of each task is not guaranteed to be met. In contrast, real-time tasks care about meeting their timing requirements, and there is no gain in improving above such requirement. Still, some of these average-case optimization techniques can be adapted for SRT systems. To the best of our knowledge, no complete classification of these works has been attempted so far. Aiming at closing this gap, this article presents a survey of cache management mechanisms for real-time embedded systems, from the first studies of the field in 1990 up to the latest research published in 2015. The objective of the survey is to categorize each approach and to provide a detailed comparison in terms of similarities and differences. In summary, our contributions are: -We classify each related work into one of the following categories: index-based cache partitioning, way-based cache partitioning, cache locking, or OS memory allocators. We also mention which techniques exploits more than one mechanism to improve predictability. -For each category, we present an overview of the approach (index-based and waybased cache partitioning, cache locking, and memory allocators) and discuss the main characteristics of each work. In particular, we detail (a) whether the approach is implemented in hardware or software, and in the latter case, whether it requires compiler or OS support; (b) what type of isolation it provides, that is, whether it addresses intratask, intracore, or intercore interference; (c) the level of isolation, that is, how effective the approach is at preventing the addressed source of interference; and (d) any further limitation or key assumptions in the work that might limit its applicability, in particular in an industrial context. -We provide a discussion on open issues and future directions in the field. The remainder of this article is organized as follows: Section 2 provides background on current processor and memory organizations. It describes the problems raised by these organizations. The following four sections present our categorization of related works. Section 3 presents all related works categorized as index-based cache partitioning. Section 4 categorizes the related work in way-based cache partitioning and Section 5 as cache-locking mechanisms. Section 6 presents operating systems memory allocators that either use one of the three previous techniques or are designed to be predictable. In the end of these four sections, we present a table summarizing the main characteristics of each work. Section 7 identifies open problems and future directions in the field. Finally, Section 8 concludes the article.