A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache-Aware Allocators <s> To narrow the widening gap between processor and memory performance, the authors propose improving the cache locality of pointer-manipulating programs and bolstering performance by careful placement of structure elements. It is concluded that considering past trends and future technology, it seems clear that the processor-memory performance gap will continue to increase and software will continue to grow larger and more complex. Although cache-conscious algorithms and data structures are the first and perhaps best place to attack this performance problem, the complexity of software design and an increasing tendency to build large software systems by assembling smaller components does not favor a focused, integrated approach. We propose another, more incremental approach of cache-conscious data layout, which uses techniques such as clustering, coloring, and compression to enhance data locality by placing structure elements more carefully in the cache. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache-Aware Allocators <s> Poor placement of data blocks in memory may negatively impact application performance because of an increase in the cache conflict miss rate [18]. For dynamically allocated structures this placement is typically determined by the memory allocator. Cache index-oblivious allocators may inadvertently place blocks on a restricted fraction of the available cache indexes, artificially and needlessly increasing the conflict miss rate. While some allocators are less vulnerable to this phenomena, no general-purpose malloc allocator is index-aware and methodologically addresses this concern. We demonstrate that many existing state-of-the-art allocators are index-oblivious, admitting performance pathologies for certain block sizes. We show that a simple adjustment within the allocator to control the spacing of blocks can provide better index coverage, which in turn reduces the superfluous conflict miss rate in various applications, improving performance with no observed negative consequences. The result is an index-aware allocator. Our technique is general and can easily be applied to most memory allocators and to various processor architectures. Furthermore, we can reduce inter-thread and inter-process conflict misses for processors where threads concurrently share the level-1 cache such as the Sun UltraSPARC-T2™ and Intel "Nehalem" by coloring the placement of blocks so that allocations for different threads and processes start on different cache indexes. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache-Aware Allocators <s> Shared cache partitioning is a well-known technique used in multicore real-time systems to isolate task workloads and improve system predictability. Presently, the state-of-the-art studies that evaluate shared cache partitioning on multicore processors lack two key issues. First, the cache partitioning mechanism is typically implemented either in a simulation environment or in a general-purpose OS, and so the impact of kernel activities, such as interrupt handlers and context switching, on the task partitions tend to be overlooked. Second, the evaluation is typically restricted to either a global or partitioned scheduler, thereby by falling to compare the performance of cache partitioning when tasks are scheduled by different schedulers. In this work, we design and implement a shared cache partitioning mechanism in a multicore component-based RTOS capable of assigning partitions to internal OS data structures, including task and system stacks and interrupt handlers data. We evaluate our shared cache partitioning mechanism running task sets under global (G-EDF) and partitioned (P-EDF) multicore real-time scheduling algorithms. Our results indicate that a lightweight RTOS does not impact real-time tasks, and shared cache partitioning has different behavior depending on the scheduler and the task's working set size. <s> BIB003
Chilimbi et al. proposed a memory allocator (named ccmaloc -cache-conscious malloc) that receives the requested bytes and a pointer to an existing data object that the program is likely to access contemporaneously with the element to be allocated BIB001 . The allocator attempts to allocate the requested data in the same cache block as the existing item, thus improving data locality, cache hit rates, and the average execution time. The authors also integrated the memory allocator with a data structure reorganizer. The reorganizer basically transforms a pointer structure layout into a linear memory layout and maps structure elements to reduce cache conflicts using page coloring. The main drawback of this approach is the need for copying data to a new linear memory region and the absence of a predictable memory allocation time. Cache-Index Friendly (CIF) also tries to improve the average execution time, instead of improving the predictability, by explicitly controlling the cache-index position of allocated memory blocks BIB002 . The central idea in CIF is to insert small spacer regions into the array of blocks within the allocator to better distribute block indices and disrupting the regular ordering of block addresses, returned by the allocator. The authors performed a set of experiments to show that CIF reduces intratask and intercore interferences. CIF, however, is not designed for real-time systems. Gracioli and Fröhlich overloaded the C++ new operator to enable colored memory allocation/deallocation in an RTOS BIB003 . The overload of the new operator is part of the ISO C++ standard and is supported by any standard C++ compiler. The OS keeps a set of heaps, where each heap only contains pages with the same color. The user passes the color as parameter to the new operator, identifying from which heap the memory should be allocated (for instance, data = new (COLOR_0) (sizeof(int *)), allocates memory from the heap with pages colored as 0). The developer can also choose an OS-centric allocation scheme, in which the OS uses the thread ID to automatically choose from which heap data should be allocated (ID % maximum number of colors). The RTOS has its own colored heap, not causing interference with the application's colors. The approach does not have a predictable timing analysis. The PALLOC allocator is primarily designed to assign disjoint sets of DRAM banks (private banks) to applications running on different cores . This way, tasks running in parallel do not collide on DRAM banks and do not suffer intercore conflicts at this level, as long as there is a sufficient number of banks to accommodate them. However, its implementation also allows enforcing a last-level cache partitioning based on the assignment of colored pages to tasks. PALLOC modifies the Linux buddy allocator so that specific page colors can be selected when allocating new memory pages. System designers can create multiple partitions and specify desired sets for each partition through the CGROUP interface. When a process in a CGROUP requires physical memory, PALLOC allocates only pages from the specified partition.