A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware Index-Based Partitioning <s> SMART, a technique for providing predictable cache performance for real-time systems with priority-based preemptive scheduling, is presented. The technique is implemented in a R3000 cache design. The value density acceleration (VDA) cache allocation algorithm is also introduced, and shown to be suitable for run-time cache allocation. > <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware Index-Based Partitioning <s> The last line of defense in the cache hierarchy before going to off-chip memory is very critical in chip multiprocessors (CMPs) from both the performance and power perspectives. We investigate different organizations for this last line of defense (assumed to be L2 in this article) towards reducing off-chip memory accesses. We evaluate the trade-offs between private L2 and address-interleaved shared L2 designs, noting their individual benefits and drawbacks. The possible imbalance between the L2 demands across the CPUs favors a shared L2 organization, while the interference between these demands can favor a private L2 organization. We propose a new architecture, called Shared Processor-Based Split L2, that captures the benefits of these two organizations, while avoiding many of their drawbacks. Using several applications from the SPEC OMP suite and a commercial benchmark, Specjbb, on a complete system simulator, we demonstrate the benefits of this shared processor-based L2 organization. Our results show as much as 42.50% improvement in IPC over the private organization (with 11.52% on the average), and as much as 42.22% improvement over the shared interleaved organization (with 9.76% on the average). <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware Index-Based Partitioning <s> Cache hierarchies have been traditionally designed for usage by a single application, thread or core. As multi-threaded (MT) and multi-core (CMP) platform architectures emerge and their workloads range from single-threaded and multithreaded applications to complex virtual machines (VMs), a shared cache resource will be consumed by these different entities generating heterogeneous memory access streams exhibiting different locality properties and varying memory sensitivity. As a result, conventional cache management approaches that treat all memory accesses equally are bound to result in inefficient space utilization and poor performance even for applications with good locality properties. To address this problem, this paper presents a new cache management framework (CQoS) that (1) recognizes the heterogeneity in memory access streams, (2) introduces the notion of QoS to handle the varying degrees of locality and latency sensitivity and (3) assigns and enforces priorities to streams based on latency sensitivity, locality degree and application performance needs. To achieve this, we propose CQoS options for priority classification, priority assignment and priority enforcement. We briefly describe CQoS priority classification and assignment options -- ranging from user-driven and developer-driven to compiler-detected and flow-based approaches. Our focus in this paper is on CQoS mechanisms for priority enforcement -- these include (1) selective cache allocation, (2) static/dynamic set partitioning and (3) heterogeneous cache regions. We discuss the architectural design and implementation complexity of these CQoS options. To evaluate the performance trade-offs for these options, we have modeled these CQoS options in a cache simulator and evaluated their performance in CMP platforms running network-intensive server workloads. Our simulation results show the effectiveness of our proposed options and make the case for CQoS in future multi-threaded/multi-core platforms since it improves shared cache efficiency and increases overall system performance as a result. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware Index-Based Partitioning <s> The usage of cache memories in time-critical applications has been limited as caches introduce unpredictable execution behavior. Cache partitioning techniques have been developed to reduce the impact of unpredictability owing to context switch effects. However, partitioning reduces the cache size available for each task resulting in capacity related cache misses. This paper introduces a fully associative cache architecture for multi-tasking applications where effective partition sizes are increased by tag compression in the cache. The proposed scheme uses a few don't care cells in its least significant bits of the tag to aggregate multiple tag entries into a single entry. The experimental results indicate that the proposed scheme is context switch resilient when eight different real-time benchmarks use the cache concurrently. Further, this cache architecture requires less time and less energy to perform tag table search compared to contemporary fully associative caches of the same size. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware Index-Based Partitioning <s> The role of the operating system (OS) in managing shared resources such as CPU time, memory, peripherals, and even energy is well motivated and understood [23]. Unfortunately, one key resource — lower-level shared cache in chip multi-processors — is commonly managed purely in hardware by rudimentary replacement policies such as least-recently-used (LRU). The rigid nature of the hardware cache management policy poses a serious problem since there is no single best cache management policy across all sharing scenarios. For example, the cache management policy for a scenario where applications from a single organization are running under "best effort" performance expectation is likely to be different from the policy for a scenario where applications from competing business entities (say, at a third party data center) are running under a minimum service level expectation. When it comes to managing shared caches, there is an inherent tension between flexibility and performance. On one hand, managing the shared cache in the OS offers immense policy flexibility since it may be implemented in software. Unfortunately, it is prohibitively expensive in terms of performance for the OS to be involved in managing temporally fine-grain events such as cache allocation. On the other hand, sophisticated hardware-only cache management techniques to achieve fair sharing or throughput maximization have been proposed. But they offer no policy flexibility. This paper addresses this problem by designing architectural support for OS to efficiently manage shared caches with a wide variety of policies. Our scheme consists of a hardware cache quota management mechanism, an OS interface and a set of OS level quota orchestration policies. The hardware mechanism guarantees that OS-specified quotas are enforced in shared caches, thus eliminating the need for (and the performance penalty of) temporally fine-grained OS intervention. The OS retains policy flexibility since it can tune the quotas during regularly scheduled OS interventions. We demonstrate that our scheme can support a wide range of policies including policies that provide (a) passive performance differentiation, (b) reactive fairness by miss-rate equalization and (c) reactive performance differentiation. <s> BIB005 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware Index-Based Partitioning <s> As part of the trend towards Chip Multiprocessors (CMPs) for the next leap in computing performance, many architectures have explored sharing the last level of cache among different processors for better performance-cost ratio and improved resource allocation. Shared cache management is a crucial CMP design aspect for the performance of the system. This paper first presents a new classification of cache misses - CII: Compulsory, Inter-processor and Intra-processor misses - for CMPs with shared caches to provide a better understanding of the interactions between memory transactions of different processors at the level of shared cache in a CMP. We then propose a novel approach, called set pinning, for eliminating inter-processor misses and reducing intra-processor misses in a shared cache. Furthermore, we show that an adaptive set pinning scheme improves over the benefits obtained by the set pinning scheme by significantly reducing the number of off-chip accesses. Extensive analysis of these approaches with SPEComp 2001 benchmarks is performed using a full system simulator. Our experiments indicate that the set pinning scheme achieves an average improvement of 22.18% in the L2 miss rate while the adaptive set pinning scheme reduces the miss rates by an average of 47.94% as compared to the traditional shared cache scheme. They also improve the performance by 7.24% and 17.88% respectively. <s> BIB006 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hardware Index-Based Partitioning <s> Multi-core architectures consisting of multiple processing cores on a chip have become increasingly prevalent. Synthesizing hard real-time applications onto these platforms is quite challenging, as the contention among the cores for various shared resources leads to inherent timing unpredictability. This paper proposes the use of shared cache in a predictable manner through a combination of locking and partitioning mechanisms. We explore possible design choices and evaluate their effects on the worst-case application performance. Our study reveals certain design principles that strongly dictate the performance of a predictable memory hierarchy. <s> BIB007
Several hardware index-based cache partitioning have been proposed to improve the average-case performance of applications. However, some of these approaches could also be applied to SRT. In the following text, we discuss the main hardware indexbased partitioning approaches and classify each approach in either average-case or HRT. Average-case performance. The Shared Processor-Based Split L2 cache organization assigns cache sets according to the CPU ID BIB002 . The L2 cache controller (configurable by the OS) keeps a table that maps the CPU ID to its sets. Every CPU memory access looks first at its available sets but can subsequently look at other CPU sets before going to the main memory. Upon a miss, the requested memory block is allocated only into the available CPU sets. Set pinning is a similar approach, where cache sets are associated with owner cores BIB006 . However, in set pinning, memory accesses that would lead to intercore interference are redirected to a small-core owned private (POP) cache. Each core has its POP cache, storing memory blocks that would cause intercore cache misses. The objective is to reduce these cache misses and improve the average system performance. CQoS classifies the applications memory accesses in priorities and then assigns more set partitions to higher priority applications BIB003 ]. The CQoS framework also implements a selective cache allocation in which it counts the number of lines occupied in the cache at a given priority level and probabilistically allocates or rejects cache line allocation requests. BIB005 proposed a hardware implementation of a quota enforcement mechanism. The quota is enforced at a set level for different tasks/applications that access the shared cache. The mechanism requires the maintenance of an ownership information for each cache block, which is performed by adding a Tag-owner-ID along with each tag in the cache address bits. Hard real-time systems. Strategic Memory Allocation for Real-Time (SMART) was the first hardware-based implementation of a cache mechanism designed to provide predictability for uniprocessor real-time systems BIB001 . SMART divides the cache into M segments. Then, these M segments are mapped into N tasks. Shared data structures that require coherent cache accesses are placed in a specific partition, named shared partition. This shared partition can be formed by a set of segments BIB001 . Performance-critical tasks have private partitions. Private partitions are protected and all tasks can access the shared partition. In order to identify the number of segments assigned to a task, a cache location address has also a cache ID field. Moreover, a hardware flag identifies whether a task accesses a private or a shared partition. The cache ID, segment count field, and hardware flags are part of each task's context and are loaded on every context switch performed by the OS. The authors presented a SMART designed for the MIPS R3000 processor. BIB004 proposed a hardware-based cache partitioning for fully associative cache architectures. The cache-partitioning mechanism should provide a mean to search and isolate a cache line efficiently. Thus, a partition segment is created by aggregating multiple memory entries and associating them with a single tag entry BIB004 . Content addressable memory (CAM) cells together with ternary content addressable memory (TCAM) cells form each tag entry. The use of CAM and TCAM reduces miss ratio. BIB007 proposed a cache-partitioning mechanism able to perform three different partitioning strategies: "(1) no partition, where a cache block may be occupied by any task, scheduled on any core; (2) task-based partitioning, where each task is assigned a portion of the cache; or (3) core-based partition, where each core is assigned a portion of the cache, and each task scheduled on that core may occupy the whole portion while it is executing." Cache partitioning is then combined with a static cache-locking mechanism (a cache line cannot be removed from the cache) or a dynamic scheme (a cache line can be reloaded at runtime). The experimental evaluation performed in a dual-core processor (simulated) with 2-way set-associative L1 and L2 caches resulted in a set of guiding design principles for real-time systems: (1) the best cache-partitioning method that should be used with a static cache locking is core-based partition; (2) core-based partitioning is the best option independent of locking strategy; and (3) when comparing dynamic and static cache locking, the dynamic approach is better only when tasks have a considerable number of hot regions and when the size of the shared cache is not big.