A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <s> Cache memories have been extensively used to bridge the gap between high speed processors and relatively slow main memories. However, they are a source 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 the worst-case behavior of applications with respect to caches in order to determine safe and precise bounds on task worst-case execution times (WCETs) and cache-related preemption delays. An alternative approach to cope with caches in real-time systems is to statically lock their contents such that memory access times and cache-related preemption times are predictable. In this paper, we propose two low-complexity algorithms for selecting the contents of statically-locked caches. We evaluate their performances and compare them with those of a state of the art static cache analysis method. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <s> Caches have become increasingly important with the widening gap between main memory and processor speeds. However, they are a source of unpredictability due to their characteristics, resulting in programs behaving in a different way than expected.Cache locking mechanisms adapt caches to the needs of real-time systems. Locking the cache is a solution that trades performance for predictability: at a cost of generally lower performance, the time of accessing the memory becomes predictable.This paper combines compile-time cache analysis with data cache locking to estimate the worst-case memory performance (WCMP) in a safe, tight and fast way. In order to get predictable cache behavior, we first lock the cache for those parts of the code where the static analysis fails. To minimize the performance degradation, our method loads the cache, if necessary, with data likely to be accessed.Experimental results show that this scheme is fully predictable, without compromising the performance of the transformed program. When compared to an algorithm that assumes compulsory misses when the state of the cache is unknown, our approach eliminates all overestimation for the set of benchmarks, giving an exact WCMP of the transformed program without any significant decrease in performance. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <s> Caches are notorious for their unpredictability. It is difficult or even impossible to predict if a memory access results in a definite cache hit or miss. This unpredictability is highly undesired for real-time systems. The Worst-Case Execution Time (WCET) of a software running on an embedded processor is one of the most important metrics during real-time system design. The WCET depends to a large extent on the total amount of time spent for memory accesses. In the presence of caches, WCET analysis must always assume a memory access to be a cache miss if it can not be guaranteed that it is a hit. Hence, WCETs for cached systems are imprecise due to the overestimation caused by the caches. Modern caches can be controlled by software. The software can load parts of its code or of its data into the cache and lock the cache afterwards. Cache locking prevents the cache's contents from being flushed by deactivating the replacement. A locked cache is highly predictable and leads to very precise WCET estimates, because the uncertainty caused by the replacement strategy is eliminated completely. This paper presents techniques exploring the lockdown of instruction caches at compile-time to minimize WCETs. In contrast to the current state of the art in the area of cache locking, our techniques explicitly take the worst-case execution path into account during each step of the optimization procedure. This way, we can make sure that always those parts of the code are locked in the I-cache that lead to the highest WCET reduction. The results demonstrate that WCET reductions from 54% up to 73% can be achieved with an acceptable amount of CPU seconds required for the optimization and WCET analyses themselves. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <s> Modern processors often provide cache locking capability which can be applied statically and dynamically to manage cache in a predictable manner. The selection of instructions to be locked in the instruction cache (I-Cache) has dramatic influence on the performance of multi-task real-time embedded systems. This paper focuses on using cache locking techniques on a shared I-Cache in a real-time embedded system with multi-tasks to minimize its worst-case utilization (WCU) which is one of the most important criteria for designing realtime embedded systems. We analyze the static and dynamic strategies to perform I-Cache locking and propose different algorithms which utilize the foreknowing information of the real-time embedded applications. Experiments show that the proposed algorithms can reduce WCU further compared to previous techniques. Design suggestions on which strategy should be utilized under different situations are also induced from the experimental results. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <s> Cache is effective in bridging the gap between processor and memory speed. It is also a source of unpredictability because of its dynamic and adaptive behavior. Worst-case execution time (WCET) of an application is one of the most important criteria for real-time embedded system design. The unpredictability of instruction miss/hit behavior in the instruction cache (I-Cache) leads to an unnecessary over-estimation of the real-time application's WCET. A lot of modern processors provide cache locking capability. Static I-Cache locking locks function/instruction blocks of a program into the I-Cache before program execution. In this way, a more precise estimation of WCET can be achieved. The selection of functions/instructions to be locked in the I-Cache has dramatic influence on the performance of the real-time application. This paper focuses on the static I-Cache locking problem to minimize WCET for real-time embedded systems. We formulate the problem using an Execution Flow Tree (EFT) and a linear programming model. For a subset of the problems with certain properties, corresponding polynomial time optimal algorithms are proposed. We prove that the general problem is an NP-Hard problem. We also show that for a subset of the general problem with certain patterns, optimal solutions can be achieved in polynomial time. Experimental results show that our algorithms can reduce the WCET of applications further compared to current best known techniques. <s> BIB005 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <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> BIB006 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <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> BIB007 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware-Software Approaches <s> Cache locking is an effective technique to improve timing predictability in real-time systems. In static cache locking, the locked memory blocks remain unchanged throughout the program execution. Thus static locking may not be effective for large programs where multiple memory blocks are competing for few cache lines available for locking. In comparison, dynamic cache locking overcomes cache space limitation through time-multiplexing of locked memory blocks. Prior dynamic locking technique partitions the program into regions and takes independent locking decisions for each region. We propose a flexible loop-based dynamic cache locking approach. We not only select the memory blocks to be locked but also the locking points (e.g., loop level). We judiciously allow memory blocks from the same loop to be locked at different program points for WCET improvement. We design a constraint-based approach that incorporates a global view to decide on the number of locking slots at each loop entry point and then select the memory blocks to be locked for each loop. Experimental evaluation shows that our dynamic cache locking approach achieves substantial improvement of WCET compared to prior techniques. <s> BIB008
Campoy et al. [2001] were the first authors to use cache locking in the context of uniprocessor HRT systems. The authors proposed a genetic algorithm that selects which instruction blocks are loaded and locked in the cache in a preemptive, multitasking system. In such a system, the locking of a cache line from one task affects the other tasks. The genetic algorithm estimates the WCET of each task with data loaded and locked in the cache. The algorithm uses the estimated WCET to determine the response time for each task. Experimental results indicated that the proposed algorithm calculates the response time of tasks with negligible overestimation and without performance loss, considering a preemptive scheduler  . BIB001 addressed intratask and intracore interferences using static cache locking of instruction caches in uniprocessor multitasking HRT systems. The authors proposed two algorithms to select the instruction cache blocks that should be locked. In contrast to Campoy et al. [2001] , the two algorithms use memory access patterns of the instruction flow to determine which cache lines must be locked. The first algorithm aims at minimizing the CPU utilization of the task set, while the second aims at reducing the intracore interference using a fixed-priority scheduler. The authors compared the two algorithms with a static cache analysis for large instruction caches and caches with a large degree of associativity. Both algorithms have presented a better performance BIB001 . A dynamic locking strategy for instruction caches was proposed in  . A control-flow graph is extracted from task binary. Next, basic blocks are identified and regions of code that aggregate one or more basic blocks are created. The authors propose an heuristic algorithm (Region Merging and Inlining) to perform close-optimal aggregations of basic blocks to regions. Each region has a locked/unlocked state that is set appropriately by the allocation algorithm considering the following parameters: (a) mapping of region to cache lines, (b) execution frequency, and (c) performance gain derived from locking the considered region with respect to its loading/locking cost. The approach has been tested on an emulated MIPS R3000 platform. BIB002 combined compile-time cache analysis with data cache locking to improve the WCET estimation of uniprocessor HRT systems. An algorithm executed at compile time identifies code regions where a static analysis does not precisely predict their behavior. The algorithm uses a reuse vector to perform cache locality analysis and to select data to be loaded and locked in the cache. Static analysis is used in the other code regions. Also, the compile-time algorithm inserts beyond the lock instructions, unlock and load instructions and compute the WCET for k-way set-associative data caches. The authors implemented the algorithm in the SUIF2 compiler and obtained a more predictable cache behavior with minimal performance loss. BIB003 proposed a technique that also explore static locking of instruction caches at compile-time to minimize the WCET in uniprocessor SRT/HRT systems. Differently from the previous works, the technique uses the worst-case execution path in order to apply cache locking. An optimization algorithm receives a compiled and linked binary executable file as input. The target processor is ARM920T. Then, the algorithm calls a static WCET analysis tool (aiT), which extracts data that impact the WCET from the binary's function. From this data, the optimization algorithm selects the most relevant code (i.e., functions) that will be locked in the instruction cache. Experimental results reported a reduction between 54% and 73% in the WCET of some benchmarks running on the ARM920T processor. Exploiting information extracted at compile time, BIB004 propose and analyze three algorithms to perform allocation of instruction cache area through locking. The proposed algorithms consider both static locking and dynamic locking, with the goal of minimizing worst-case CPU utilization through cache allocation. The results are for a set of tasks in a multitask scenario, improving on what achieved for single-task systems in BIB005 . Based on the achieved results, practical guidelines are provided to select the locking methodology that best fits specific workload characteristics. Experimental results show that close-optimal solutions for the cache allocation problem can be found, improving the efficiency of the heuristic compared to what presented in BIB003 . BIB006 proposed a dynamic cache-locking strategy to load and lock the best cache lines into the instruction cache at each context switch. The proposed approach deals with both intratask and intracore interferences. The method is based on an Integer Linear Programming (ILP) method, is named Lock-MS (Maximize Schedulability), and targets uniprocessor HRT systems. The ILP-method analyzes a single task and the interference among tasks to load and lock the most relevant cache lines. At runtime, a dynamic cache-locking method preloads the cache contents at every context switch, minimizing the worst cost of a preemption. The authors compared Lock-MU with a static locking mechanism BIB001 and obtained better performance results. BIB008 acknowledge the limitations of region-based dynamic locking and propose a more flexible locking strategy. Specifically, this work focuses on instruction caches and aims at performing a partial locking of the cache to exploit the additional benefits of the unlocked cache lines. Moreover, instead of splitting the instruction blocks in regions that are (un)loaded in cache in a mutually exclusive manner, the article introduces the notion of loop-driven locking. The key idea is the following: given a series of nested loops, each line selected for locking at an inner loop can also be locked/unlocked at the entry/exit point of any of the outer loops. The evaluation performed on the Chronos WCET tool reveals benefits with respect to (a) the static partial locking strategy proposed in a previous work by the same authors and (b) region-based dynamic locking as proposed in  . BIB007 proposes a memory framework that uses profiling techniques to analyze the memory access pattern of tasks and obtain the most frequently accessed memory pages. Profiling is performed using memory observation tools, and it is execution-independent. Then, page coloring is used to rearrange task pages into the physical memory address space to optimize in-cache placement. Next, cache locking is used to provide isolation among tasks on the same core and on different cores, thus increasing predictability in HRT systems. The solution focuses on using existing hardware support on modern multicore platforms and is implementable using locking by-line, by-master and by-way. The framework was implemented and evaluated in the Linux kernel. Evaluation was conducted using locking support in ARM Cortex-A9, and a porting to Freescale P4080 was performed in a successive extension of the work .