A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> The MIPS R6000 microprocessor relies on a new type of translation lookaside buffer — called a TLB slice — which is less than one-tenth the size of a conventional TLB and as fast as one multiplexer delay, yet has a high enough hit rate to be practical. The fast translation makes it possible to use a physical cache without adding a translation stage to the processor's pipeline. The small size makes it possible to include address translation on-chip, even in a technology with a limited number of devices. The key idea behind the TLB slice is to have both a virtual tag and a physical tag on a physically-indexed cache. Because of the virtual tag, the TLB slice needs to hold only enough physical page number bits — typically 4 to 8 — to complete the physical cache index, in contrast with a conventional TLB, which needs to hold both a virtual page number and a physical page number. The virtual page number is unnecessary because the TLB slice needs to provide only a hint for the translated physical address rather than a guarantee. The full physical page number is unnecessary because the cache hit logic is based on the virtual tag. Furthermore, if the cache is multi-level and references to the TLB slice are “shielded” by hits in a virtually indexed primary cache, the slice can get by with very few entries, once again lowering its cost and increasing its speed. With this mechanism, the simplicity of a physical cache can been combined with the speed of a virtual cache. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> When a computer system supports both paged virtual memory and large real-indexed caches, cache performance depends in part on the main memory page placement. To date, most operating systems place pages by selecting an arbitrary page frame from a pool of page frames that have been made available by the page replacement algorithm. We give a simple model that shows that this naive (arbitrary) page placement leads to up to 30% unnecessary cache conflicts. We develop several page placement algorithms, called careful-mapping algorithms , that try to select a page frame (from the pool of available page frames) that is likely to reduce cache contention. Using trace-driven simulation, we find that careful mapping results in 10–20% fewer (dynamic) cache misses than naive mapping (for a direct-mapped real-indexed multimegabyte cache). Thus, our results suggest that careful mapping by the operating system can get about half the cache miss reduction that a cache size (or associativity) doubling can. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> Cache memories have become an essential part of modern processors to bridge the increasing gap between fast processors and slower main memory. Until recently, cache memories were thought to impose unpredictable execution time behavior for hard real-time systems. But recent results show that the speedup of caches can be exploited without a significant sacrifice of predictability. These results were obtained under the assumption that real-time tasks be scheduled non-preemptively.This paper introduces a method to maintain predictability of execution time within preemptive, cached real-time systems and discusses the impact on compilation support for such a system. Preemptive systems with caches are made predictable via software-based cache partitioning. With this approach, the cache is divided into distinct portions associated with a real-time task, such that a task may only use its portion. The compiler has to support instruction and data partitioning for each task. Instruction partitioning involves non-linear control-flow transformations, while data partitioning involves code transformations of data references. The impact on execution time of these transformations is also discussed. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> This paper presents a new technique, compiler-directed page coloring, that eliminates conflict misses in multiprocessor applications. It enables applications to make better use of the increased aggregate cache size available in a multiprocessor. This technique uses the compiler's knowledge of the access patterns of the parallelized applications to direct the operating system's virtual memory page mapping strategy. We demonstrate that this technique can lead to significant performance improvements over two commonly used page mapping strategies for machines with either direct-mapped or two-way set-associative caches. We also show that it is complementary to latency-hiding techniques such as prefetching.We implemented compiler-directed page coloring in the SUIF parallelizing compiler and on two commercial operating systems. We applied the technique to the SPEC95fp benchmark suite, a representative set of numeric programs. We used the SimOS machine simulator to analyze the applications and isolate their performance bottlenecks. We also validated these results on a real machine, an eight-processor 350MHz Digital AlphaServer. Compiler-directed page coloring leads to significant performance improvements for several applications. Overall, our technique improves the SPEC95fp rating for eight processors by 8% over Digital UNIX's page mapping policy and by 20% over a page coloring, a standard page mapping policy. The SUIF compiler achieves a SPEC95fp ratio of 57.4, the highest ratio to date. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> As the gap between memory and processor speeds continues to widen, cache efficiency is an increasingly important component of processor performance. Compiler techniques have been used to improve instruction and data cache performance for virtually indexed caches by mapping code and data with temporal locality to different cache blocks. In this paper we examine the performance of compiler and hardware approaches for reordering pages in physically addressed caches to eliminate cache misses. The software approach provides a color mapping at compile-time for code and data pages, which can then be used by the operating system to guide its allocation of physical pages. The hardware approach works by adding a page remap field to the TLB, which is used to allow a page to be remapped to a different color in the physically indexed cache while keeping the same physical page in memory. The results show that software page placement provided a 28% speedup and hardware page placement provided a 21% speedup on average for a superscalar processor. For a 4 processor single-chip multiprocessor, the miss rate was reduced from 8.7% down to 7.2% on average. <s> BIB005 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> Cache partitioning and sharing is critical to the effective utilization of multicore processors. However, almost all existing studies have been evaluated by simulation that often has several limitations, such as excessive simulation time, absence of OS activities and proneness to simulation inaccuracy. To address these issues, we have taken an efficient software approach to supporting both static and dynamic cache partitioning in OS through memory address mapping. We have comprehensively evaluated several representative cache partitioning schemes with different optimization objectives, including performance, fairness, and quality of service (QoS). Our software approach makes it possible to run the SPEC CPU2006 benchmark suite to completion. Besides confirming important conclusions from previous work, we are able to gain several insights from whole-program executions, which are infeasible from simulation. For example, giving up some cache space in one program to help another one may improve the performance of both programs for certain workloads due to reduced contention for memory bandwidth. Our evaluation of previously proposed fairness metrics is also significantly different from a simulation-based study. The contributions of this study are threefold. (1) To the best of our knowledge, this is a highly comprehensive execution- and measurement-based study on multicore cache partitioning. This paper not only confirms important conclusions from simulation-based studies, but also provides new insights into dynamic behaviors and interaction effects. (2) Our approach provides a unique and efficient option for evaluating multicore cache partitioning. The implemented software layer can be used as a tool in multicore performance evaluation and hardware design. (3) The proposed schemes can be further refined for OS kernels to improve performance. <s> BIB006 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> Cache partitioning techniques have been proposed in the past as a solution for the cache interference problem. Due to qualitative differences with general purpose platforms, real-time embedded systems need to minimize task real-time utilization (function of execution time and period) instead of only minimizing the number of cache misses. In this work, the partitioning problem is presented as an optimization problem whose solution sets the size of each cache partition and assigns tasks to partitions such that system worst-case utilization is minimized thus increasing real-time schedulability. Since the problem is NP-Hard, a genetic algorithm is presented to find a near optimal solution. A case study and experiments show that in a typical real-time embedded system, the proposed algorithm is able to reduce the worst-case utilization by 15% (on average) if compared to the case when the system uses a shared cache or a proportional cache partitioned environment. <s> BIB007 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <s> The major obstacle to use multicores for real-time applications is that we may not predict and provide any guarantee on real-time properties of embedded software on such platforms; the way of handling the on-chip shared resources such as L2 cache may have a significant impact on the timing predictability. In this paper, we propose to use cache space isolation techniques to avoid cache contention for hard real-time tasks running on multicores with shared caches. We present a scheduling strategy for real-time tasks with both timing and cache space constraints, which allows each task to use a fixed number of cache partitions, and makes sure that at any time a cache partition is occupied by at most one running task. In this way, the cache spaces of tasks are isolated at run-time. As technical contributions, we have developed a sufficient schedulability test for non-preemptive fixed-priority scheduling for multicores with shared L2 cache, encoded as a linear programming problem. To improve the scalability of the test, we then present our second schedulability test of quadratic complexity, which is an over approximation of the first test. To evaluate the performance and scalability of our techniques, we use randomly generated task sets. Our experiments show that the first test which employs an LP solver can easily handle task sets with thousands of tasks in minutes using a desktop computer. It is also shown that the second test is comparable with the first one in terms of precision, but scales much better due to its low complexity, and is therefore a good candidate for efficient schedulability tests in the design loop for embedded systems or as an on-line test for admission control. <s> BIB008 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Software Index-Based Partitioning <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> BIB009
The most common software-based cache-partitioning technique is page coloring   BIB008 . Page coloring explores the virtual to physical page address translations presented in virtual memory systems at OS level, when caches are physically indexed. Page addresses are mapped to predefined cache regions, avoiding the overlap of cache spaces. Figure 3 illustrates the physical addresses from the cache and OS point of views for the PL-310 (a.k.a. L2C-310) L2-cache controller adopted in ARM Cortex-A9 MPCore chips. By controlling the colored bits of the set-associative cache number, the OS can change the mapping of 4KB pages in the physical memory and the cache location. The PL-310 cache controller can be synthesized with a 1MB shared 16-way set-associative L2-cache with 32-bytes per line. There are 2 11 sets in the cache (1MB/16 ways × 1 way/32B). Thus, the first 5 bits in the cache address access a byte in a cache line, the next 11 bits access a set, and the remaining 16 bits define a line from one of the 16 ways (Tag in Figure 3 ). The idea of page coloring is to assign color 0 to page 0, color 1 to page 1, and so on, starting again from color 0 after reaching the maximum color number. In the same PL-310 chip, there are 128 cache lines in each 4KB page. Each of these lines has a different cache set index. Since 4 bits are available to page coloring (cache size/number of ways/page size), page 16 maps to the same color as page 0. It is possible to partition the cache by assigning different colors to tasks/cores. Below, we classify works that use software index-based partitioning in those proposed for improving the average-case performance and those proposed for proving real-time guarantees. In the latter case, we also classify the work regarding its implementation (OS or compiler-based) and identify whether it targets the SRT or HRT system. Average-case performance. The first implementation of a page-coloring mechanism targeting performance was carried out using the MIPS OS BIB001 ]. Then, page coloring was used to reduce cache misses in single applications by assigning different colors to applications and consequently, distributing the memory accesses through the entire cache BIB002  BIB005 . More recently, several shared cache-partitioning mechanisms based on page coloring for general-purpose systems have been proposed  BIB006 BIB008 .  used information collected by the hardware performance counters to estimate the size of each shared L2 cache partition. Experimental results have shown that cache partitioning can recover up to 70% of degraded instruction per cycles due to cache contention. BIB006 implemented a page-coloring mechanism in the Linux kernel for x86 processors. The authors changed the Linux memory management to support multiple lists. Each list is filled up with pages that have the same color. To search for a page when a process gets a page fault, the kernel uses a round-robin method to scan the lists with allocated colors. Two cache-partitioning policies were supported: static and dynamic. The static policy defines the memory colors assigned to each process at the beginning of its execution. In the dynamic policy, a page recoloring is enforced whenever a process desires to increase its cache resource. Page recoloring is carried out by rebuilding the virtual to physical memory mapping. Page recoloring involves data copy from an old page to a new page that has a new color. Although page recoloring achieved good QoS for general-purpose applications, the process of copying pages in a real-time application may result in deadline misses. proposed a hot-page coloring approach. Hot pages are identified by checking the page table entry access bit. Whenever a page is accessed, its access bit is automatically changed by the MMU. The estimation of the frequency of access to a page is done by checking and clearing the access bit periodically. This approach also supports page recoloring for dynamic execution environments. BIB004 implemented page-coloring support in the SUIF parallelizing compiler. The objective was to improve performance of general-purpose multicore systems. The proposed technique, named compiler-directed page coloring (CDPC), predicts access patterns of a compiler-parallelized application, such as array access patterns. Information from the compiler is used to perform cache partitioning using a page-coloring mechanism, tailored by each application. Basically, the OS generates preferred color for each virtual page. Additionally to the compiler information, the OS also receives machine-specific parameters, such as the number of cores, cache configuration, and page size. Then, the OS tries to honor all received information as much as possible. Although this work has not been proposed to directly deal with real-time systems, it could be adapted to be used in SRT systems. Real-time approaches. Several works proposed software-based cache partitioning to increase predictability of real-time systems  BIB003  BIB008 BIB009  . We classify these works in two categories: (1) those that are implemented at the OS level and (2) those that are implemented at the compiler level. We discuss both categories below. Hard real-time OS index-based partitioning. OS-controlled cache partitioning for real-time systems was first proposed by  . Wolfe proposed a mechanism similar to page coloring to provide predictable execution times for low-priority tasks in a preemptive uniprocessor system BIB003 . In fact, his approach alters the address decomposition into tag, index, and offset as in the page-coloring partitioning BIB003 . The technique requires that the task set is static and that all programs are compiled by the same compiler prior to the system start.  used page coloring to provide predictability for uniprocessor real-time systems. BIB007 considered the cache-partitioning problem "as an optimization problem whose objective is to minimize the worst-case system utilization under the constraint that the sum of all cache partitions cannot exceed the total cache size." The authors proposed a genetic algorithm to solve the optimization problem. The cache-partitioning mechanism is based on page coloring. Experimental evaluation has shown an improvement on the schedulability of single-core systems. BIB008 proposed a cache-aware multicore real-time scheduling algorithm, named FP CA , that divides the shared cache space into partitions. The used cachepartitioning mechanism is page coloring. Tasks are scheduled in a way that at any time, any two running tasks' cache spaces (e.g., a set of partitions) are nonoverlapped. A task can execute only if it gets an idle core and enough cache partitions. The authors proposed two schedulability tests, one based on a linear problem (LP) and another one as an over-approximation of the LP test. Tasks are not preemptive and the algorithm is blocking, that is, it does not schedule lower-priority ready jobs to execute in advance of higher priority even though there are enough available resources. BIB009 stated that cache partitioning based on page coloring suffers from two problems (1) the memory copartitioning and (2) the limited number of partitions. Then, the authors proposed a cache management scheme in which they assign to each core a set of private partitions to avoid intercore cache space interference. However, tasks within each core can share cache partitions. Although this can result in intracore interference, it solves the aforementioned problems. In other words, each task can now have a larger number of partitions, which could improve its execution performance. In addition, memory partitions can be utilized by all tasks. They bound the penalties due to the sharing of cache partitions by accounting for them as cache-related preemption delays when performing the schedulability analysis.