A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Average-Case Performance <s> This paper proposes dynamic cache partitioning amongst simultaneously executing processes/threads. We present a general partitioning scheme that can be applied to set-associative caches. ::: ::: Since memory reference characteristics of processes/threads can change over time, our method collects the cache miss characteristics of processes/threads at run-time. Also, the workload is determined at run-time by the operating system scheduler. Our scheme combines the information, and partitions the cache amongst the executing processes/threads. Partition sizes are varied dynamically to reduce the total number of misses. ::: ::: The partitioning scheme has been evaluated using a processor simulator modeling a two-processor CMP system. The results show that the scheme can improve the total IPC significantly over the standard least recently used (LRU) replacement policy. In a certain case, partitioning doubles the total IPC over standard LRU. Our results show that smart cache management and scheduling is essential to achieve high performance with shared cache memory. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Average-Case Performance <s> CMPs enable simultaneous execution of multiple applications on the same platforms that share cache resources. Diversity in the cache access patterns of these simultaneously executing applications can potentially trigger inter-application interference, leading to cache pollution. Whereas a large cache can ameliorate this problem, the issues of larger power consumption with increasing cache size, amplified at sub-100nm technologies, makes this solution prohibitive. In this paper, in order to address the issues relating to power-aware performance of caches, we propose a caching structure that addresses the following: 1. Definition of application-specific cache partitions as an aggregation of caching units (molecules). The parameters of each molecule namely size, associativity and line size are chosen so that the power consumed by it and access time are optimal for the given technology. 2. Application-Specific resizing of cache partitions with variable and adaptive associativity per cache line, way size and variable line size. 3. A replacement policy that is transparent to the partition in terms of size, heterogeneity in associativity and line size. Through simulation studies we establish the superiority of molecular cache (caches built as aggregations of molecules) that offers a 29% power advantage over that of an equivalently performing traditional cache. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Average-Case Performance <s> This paper investigates the problem of partitioning a shared cache between multiple concurrently executing applications. The commonly used LRU policy implicitly partitions a shared cache on a demand basis, giving more cache resources to the application that has a high demand and fewer cache resources to the application that has a low demand. However, a higher demand for cache resources does not always correlate with a higher performance from additional cache resources. It is beneficial for performance to invest cache resources in the application that benefits more from the cache resources rather than in the application that has more demand for the cache resources. This paper proposes utility-based cache partitioning (UCP), a low-overhead, runtime mechanism that partitions a shared cache between multiple applications depending on the reduction in cache misses that each application is likely to obtain for a given amount of cache resources. The proposed mechanism monitors each application at runtime using a novel, cost-effective, hardware circuit that requires less than 2kB of storage. The information collected by the monitoring circuits is used by a partitioning algorithm to decide the amount of cache resources allocated to each application. Our evaluation, with 20 multiprogrammed workloads, shows that UCP improves performance of a dual-core system by up to 23% and on average 11% over LRU-based cache partitioning. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Average-Case Performance <s> Multi-core processors with shared caches are now commonplace. However, prior works on shared cache management primarily focused on multi-programmed workloads. These schemes consider how to partition the cache space given that simultaneously-running applications may have different cache behaviors. In this paper, we examine policies for managing shared caches for running single multi-threaded applications. First, we show that the shared-cache miss rate can be significantly reduced by reserving a certain amount of space for shared data. Therefore, we modify the replacement policy to dynamically partition each set between shared and private data. Second, we modify the insertion policy to prevent streaming data (data not reused before eviction) from promoting to the MRU position. Finally, we use a low-overhead sampling mechanism to dynamically select the optimal policy. Compared to LRU policy, our scheme reduces the miss rate on average by 8.7% on 8MB caches and 20.1% on 16MB caches respectively. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Average-Case Performance <s> Efficient management of shared on-chip resources such as the shared level 2 (L2) cache has become an important problem with the emergence of chip multiprocessors (CMPs). Partitioning the shared cache in chip multiprocessors (CMPs) among concurrently executing applications can provide important benefits such as throughput improvement, fairness guarantees, and quality of service (QoS) enhancements. We pose an interesting related question, which is, if partitioning the shared cache space among concurrently executing threads of the same application can enhance the application performance. We address this problem by identifying and speeding up the slowest thread, also termed as the critical path thread, during each execution interval since the overall performance of a multithreaded application is determined by the critical path thread. To do so, we propose a dynamic, runtime system based, cache partitioning scheme that partitions the shared cache space dynamically among the individual threads of a given application. In a nutshell, we wish to take some cache space away from the faster threads and give it to the critical path thread at each execution interval. We show that speeding up the critical path thread this way, results in overall performance enhancement of the application execution in the long term. Our experimental evaluation indicates that, the proposed dynamic cache partitioning scheme yields benefits up to 15% over a shared cache with no partitions, up to 23% over a statically partitioned cache (private cache) and up to 20% over a throughput-oriented scheme. <s> BIB005 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Average-Case Performance <s> In recent years, high performance computing systems have obtained more processing cores and share a last level cache (LLC). However, as their number grows, the core-to-way ratio in the LLC increases, presenting problems to existing cache partitioning techniques which require more ways than cores. Furthermore, effective energy management of the LLC becomes increasingly important due to its size. This paper proposes a Region Aware Cache Partitioning (RECAP), an LLC energy-saving scheme for high-performance, many-core processors. RECAP partitions the data within the cache into shared and private regions. Applications only access the ways containing the data that they require, realising dynamic energy savings. Any ways that are not within the shared or private regions can be turned off to save static energy. We evaluate our scheme using an 8-core CMP running multi-programmed workloads and show that it achieves 17% dynamic and 13% static energy savings in the shared LLC with a 15% performance gain. Across our multi-threaded applications, we achieve 17% dynamic and 41% static energy savings with no impact on performance. <s> BIB006
Ranganathan et al. [2000] proposed a cache architecture that allows dynamic reconfiguration of partitions. Specifically, the traditional structure of a set-associative cache is adapted to allow dynamic definition of partitions that can be assigned to given address ranges. The dynamic reconfiguration can be performed at runtime by software. In the proposed architecture, each cache partition can be the result of the aggregation of one or more cache ways, leading to a way-based partitioning scheme. Additional cache logic is required to differentiate between address spaces/partitions; to multiplex the tag comparators, and to generate different miss/hit signals for each addressed partition. However, the additional logic and wiring has been proven to minimally affect the cache access time, with a variable overhead that is proportional to the ratio # o f partitions cache size . Although the described scheme has not been designed for real-time applications, a straightforward extension could be designed for multicore systems, allowing to bind the address space of a task running on a given core to a given cache partition. This would eliminate the intercore interference for all those data that reside in an exclusively owned partition. However, intratask interference (self-evictions) could still be possible. BIB004 proposed a technique to partition each cache set into shared and private ways. The technique classifies all cache lines in shared or private. Let A be the shared cache associativity and Q be a quota for shared cache lines, partitioning is performed in such a way that the shared cache lines occupy Q way in each set while private lines occupy A-Q BIB004 . By assigning different partitions to shared and private data, they reduced the LLC miss rate and increased QoS. BIB005 proposed a dynamic software-based partitioning technique that partitions the shared cache among threads of an application. At the end of each 15ms interval, the dynamic cache-partitioning scheme uses hardware performance counters information, such as the number of cache hits and misses, the number of cycles, and retired instructions for each thread, to allocate different cache spaces based on individual thread performance. The objective is to speed up the critical path, that is, the thread that has the slowest performance and, consequently, improve the overall performance of the application. To perform cache partitioning, the authors use either a reconfigurable cache, which modifies the cache hardware structure during the execution, or modify the cache replacement algorithm, which partitions the cache gradually. According to BIB005 , "When a thread suffers a cache miss and the number of cache ways that belong to it is less than the thread's assigned cache partition ways, a cache line belonging to some other thread is chosen for replacement. If the number of cache ways belonging to the thread is greater than or equal to the assigned number of ways, a cache line belonging to the same thread is chosen for replacement." Consequently, the replacement policy gradually partitions the shared cache. Experimental results have shown a performance gain of up to 23% over a statically partitioned cache BIB005 . The work does not provide real-time guarantees. Similarly to BIB004 and BIB006 propose RECAP, an architecture for a set-associative cache that can be partitioned across cores at the granularity of a single cache way. Different cache ways are assigned to shared and private data, based on the observation that the majority of memory accesses for parallel applications is performed in shared memory, while more than 90% of cache data belong to private memory regions. Moreover, RECAP performs an automatic arrangement of the partitioned ways so that private data assigned to specific cores are allocated on ways that are positioned on the left side of the cache, while shared data are allocated on ways starting from the right end of the cache. The enforced data alignment allows to keep the unused ways in the center of the cache, thus allowing dynamic power saving by powering down unused ways. Partition arrangement for each core is performed in order to maximize utilization of the cache ways: a heuristic algorithm monitors the number of misses for each core and determines how many cache blocks need to be assigned in order to capture a given fraction of cache misses. Finally, the computed ways-to-cores assignment is enforced on the proposed cache architecture by programming a series of configuration registers. The results show a 15% average performance increase for large applications, with a reduction of power consumption, which is more than 80%. However, even though this approach is effective to limit intercore interference, its scope is beyond predictability, making it suitable for soft real-time rather than safetycritical applications for two reasons: (1) because intracore/intratask interference is not addressed due to the heuristic approach that is being used to perform ways-to-cores assignment at runtime. BIB002 propose the idea of "molecular caches": CPU caches that are organized as a series of molecules. In this architecture, molecules are small in size (8-32KB) and reflect the structure of a direct-mapped cache. Molecules are grouped into tiles that can be assigned statically or dynamically to cores. Thus, by definition, per-core partitions are defined at the granularity of tiles, which in turn represent an aggregation of cache ways. Moreover, in order to address intracore interference, individual regions can be defined internally to each tile and assigned to a specific application. In order to do this, each molecule of the same region inside a given partition exposes a configuration register that can be programmed with a unique identifier of a running application. In this way, all the molecules of a given region will be exclusively used by the matching application. The proposed scheme results effective in isolating cache misses from different running applications on the same or different cores, but the complexity of the resulting structure may not scale well with cache size. Since molecules (and thus regions) can be dynamically assigned to applications (or unassigned), a high degree of runtime reconfiguration is possible. As such, assignment decisions need to be made by a software module that runs periodically or in an adaptive manner. The metric used in the assignment controller is keeping the experienced number of caches misses as close as possible to a threshold that is statically defined for each application. Even though intertask interference is not addressed by such a partitioning scheme, molecular caches represent an effective solution to prevent inter-/intracore interference while providing the cache with a fine-grained partitioning mechanism. Moreover, the particular choice of associativity and size for the molecules leads to a circuit design that enables a reduction in energy dissipation. However, due to its complexity, a hardware implementation of molecular caches is not available to date. The applicability of such an architecture to real-time applications would be broad, assuming that the assignment controller employs a predictable allocation strategy. BIB003 propose a utility-based approach to dynamically partition the cache on a demand basis. The main insight is that differences in the working set size as well as memory addressing patter of applications affect the way they benefit from cache assignment. Specifically, applications that exhibit low spatial and temporal locality in their memory access pattern, combined with a large memory footprint size, benefit less from cache resources than applications with opposite characteristics. Thus, the former can be classified as low-utility applications, while the latter can be considered as high-utility applications from the cache assignment point of view. To account for cache utility, BIB003 propose adding a low-overhead circuit in the cache controller. The addition consists of a number of utility monitors (one per each core accessing the shared cache) and a single circuit that runs the partitioning algorithm relying on data collected at the utility monitors. The partitioning algorithm reads all the hit counters from the different utility monitors and computes a cache partitioning at the granularity of a way that minimizes the overall number of misses suffered by all the applications. Evaluation results show that such partitioning approach is able to provide fairness and performance speedup if compared to using LRU and static partitioning (e.g., an even split of the cache in two halves for two cores). The hardware overhead is relatively low when applied to LRU caches but can significantly increase for different cache replacement policies. However, the inherently heuristic approach employed in the partitioning algorithm is not directly suitable for HRT purposes because the amount of assigned cache strictly depends on the workload on other cores. This problem could be mitigated, allowing a minimal assignment of cache per each core or application. BIB001 present a dynamic cache-partitioning scheme. In this scheme, cache space is explicitly allocated among simultaneously executing processes with the goal of minimizing the overall cache misses. In order to attain this goal, the cache controller is augmented with a set of online counters. Next, each process' gain or loss under different cache allocations is considered. By using the described mechanism, the hardware dynamically adjusts the allocation to match process needs. Allocation is performed at the granularity of single cache ways. This technique mitigates the effects of cache pollution due to intercore interference in multicore systems. However, the inherently heuristic nature of this work makes it not directly suitable for real-time systems. In fact, the amount of cache dynamically allocated to a given task depends on the behavior of all the other active tasks in the system.