A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache Analysis Methods <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> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache Analysis Methods <s> Multi-core chips have been increasingly adopted by microprocessor industry. For real-time systems to safely harness the potential of multi-core computing, designers must be able to accurately obtain the worst-case execution time (WCET) of applications running on multi-core platforms, which is very challenging due to the possible runtime inter-core interferences in using shared resources such as the shared L2 caches. As the first step toward time-predictable multi-core computing, this paper presents a novel approach to bounding the worst-case performance for threads running on multi-core processors with shared L2 instruction caches. The idea of our approach is to compute the worst-case instruction access interferences between different threads based on the program control flow information of each thread, which can be statically analyzed. Our experiments indicate that the proposed approach can reasonably estimate the worst- case shared L2 instruction cache misses by considering inter-thread instruction conflicts. Also, the WCET of applications running on multi-core processors estimated by our approach is much better than the estimation by simply assuming all L2 instruction accesses are misses. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache Analysis Methods <s> The increasing demand for new functionalities in current and future hard real-time embedded systems like automotive, avionics and space industries is driving an increase in the performance required in embedded processors. Multicore processors represent a good design solution for such systems due to their high performance, low cost and power consumption characteristics. However, hard real-time embedded systems require time analyzability and current multicore processors are less analyzable than single-core processors due to the interferences between different tasks when accessing shared hardware resources. In this paper we propose a multicore architecture with shared resources that allows the execution of applications with hard real-time and non hard real-time constraints at the same time, providing time analizability for the hard real-time tasks so that they can meet their deadlines. Moreover our architecture proposal provides high-performance for the non hard real-time tasks. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache Analysis Methods <s> The state-of-the-art techniques in multicore timing analysis are limited to analyze multicores with shared instruction caches only. This paper proposes a uniform framework to analyze the worst-case performance for both shared instruction caches and data caches in a multicore platform. Our approach is based on a new concept called address flow graph, which can be used to model both instruction and data accesses for timing analysis. Our experiments, as a proof-of-concept study, indicate that the proposed approach can accurately compute the worst-case performance for real-time threads running on a dual-core processor with a shared L2 cache (either to store instructions or data). Category: Embedded computing <s> BIB004
As we mentioned earlier, several well-developed cache analysis techniques have been proposed for single-core processors. These techniques analyze the interference due to intratask and intracore cache conflicts. The latter is known as cache-related preemption delay (CRPD). The CPRD focuses on cache reload overhead due to preemptions, while the intratask analysis focuses on the cache conflicts within the same task assuming nonpreemptive execution. Since the focus of this article is on techniques that manage the cache (spatial isolation rather than joint analysis), a detailed description of such analysis techniques is out of the articles's scope. Unfortunately, the single-core timing analysis techniques are not applicable for multicore processors with shared caches. In this case, intercore interference is caused by tasks that can run in parallel, and this requires analyzing all system's tasks. The analysis of nonshared caches has been already considered as a complex process and extending it to shared caches is even harder. In fact, the researchers in the community of WCET analysis seems to agree that "it will be extremely difficult, if not impossible, to develop analysis methods that can accurately capture the contention between multiple cores in a shared cache" BIB001 . Despite this challenge, few works have been proposed to address the problem of shared caches. However, these techniques are only applicable for simple architectures and statically scheduled tasks. The first work that studies the analysis of shared caches in multicore processors is proposed in BIB002 . This work assumes a system with two tasks simultaneously running on two cores with direct-mapped shared instruction cache. Later, a cache conflict graphs were used to capture the potential intercore conflicts BIB004 . The work in improves upon BIB002 by exploiting the lifetime information of tasks and bypassing the disjoint tasks (tasks that cannot overlap at runtime) from the analysis. This work assumes a task model where all tasks are synchronized. Clearly, for systems with dynamic scheduling, it will be extremely difficult to identify the disjoint tasks. Other research proposes to bypass the shared cache for single-usage cache lines to avoid intercore conflicts and, therefore, improve the timing analysis. For systems where tasks are allowed to migrate between cores, cache-related migration delay (CRMD) has been studied in . This work estimates the number of cache lines that can be reused from the L2 shared cache when a task migrates from one core to another. Due to the lack of analysis techniques for multicore platforms with a complex hierarchy of shared caches, an empirical study has been proposed in  to evaluate the impact of cache-related preemption and migration delays (CPMD). In contrast to timing analysis techniques where caches are used without restrictions, the approach of managed caches have the advantage to avoid complex analysis methods for estimating the cache behavior. Indeed, the time-predictable architecture in BIB003 proposes a statically partitioned L2 cache to avoid the intercore cache conflicts. In addition, manged caches can be used in situations where the static analysis cannot be used, for example, the case where the cache replacement policy is not documented. On the other hand, while managing the cache space provides a timing isolation between tasks, the reduced cache space may impact the task execution time. We are not a ware of any work that compares the managed shared caches with statically analyzed caches.