Amir H. Hashemi, David Kaeli, Brad Calder · 1997
As the gap between memory and processor performance continues to widen, it becomes increasingly important to exploit cache memory eflectively. Both hardware and aoftware approaches can be explored to optimize cache performance. Hardware designers focus on cache organization issues, including replacement policy, associativity, line size and the resulting cache access time. Software writers use various optimization techniques, including software prefetching, data scheduling and code reordering. Our focus is on improving memory usage through code reordering compiler techniques.In this paper we present a link-time procedure mapping algorithm which can significantly improve the eflectiveness of the instruction cache. Our algorithm produces an improved program layout by performing a color mapping of procedures to cache lines, taking into consideration the procedure size, cache size, cache line size, and call graph. We use cache line coloring to guide the procedure mapping, indicating which cache lines to avoid when placing a procedure in the program layout. Our algorithm reduces on average the instruction cache miss rate by 40% over the original mapping and by 17% over the mapping algorithm of Pettis and Hansen [12].
Cited by 110
Mostafa Javedankherad, Zolfa Zeinalpour‐Yazdi, Farid Ashtiani · 2018
Data traffic is increasing in recent years and small cell densification is a promising solution for handling the consequences of this growth. However, it faces with backhual' constraint which limits its efficiency. Caching the popular files near to the small base stations (SBSs) is an effective technique which decreases usage of backhual links. In this paper, we model the network by a graph and propose a new popular files' placement based on graph coloring for which different powerful solutions and algorithms have been presented in the literature. In this respect, we propose an algorithm to fill the caches of SBSs with the popular files and show the efficiency of our proposed algorithm through simulations.
Cited by 3
Mostafa Javedankherad, Zolfa Zeinalpour‐Yazdi, Farid Ashtiani · IEEE Systems Journal · 2020
Small cell densification is one of the effective ideas addressing the demand for higher capacity in cellular networks. The major problem in such networks is the limited capacity of wireless backhaul links. Caching the popular files in the memories of small cell base stations (SBSs) is an effective solution to this problem. One of the main challenges in caching is choosing the files to be stored in the memory of SBSs, especially when some SBSs have overlapped coverage. In this article, we propose a new caching scheme by exploiting the concept of graph coloring. To this end, we model the network scenario by a graph. This graph is divided into four subgraphs, i.e., placement, access, SBS, and delivery graphs. Through some modifications to the SBS graph, we convert it to a graph that can be colored. Then, we propose a graph coloring-based scheme to cache the popular files. We also derive a lower-bound for the hit rate improvement of our scheme compared to the conventional scheme which caches the most popular files anywhere. We evaluate the performance of our proposed scheme through simulations. Our results show that by employing the proposed scheme in a typical network, the load on the backhaul links is reduced significantly in average compared to the conventional scheme and some previously proposed schemes.
Cited by 5Open access
Xiao Zhang, Sandhya Dwarkadas, Kai Shen · 2009
Modern multi-core processors present new resource management challenges due to the subtle interactions of simultaneously executing processes sharing on-chip resources (particularly the L2 cache). Recent research demonstrates that the operating system may use the page coloring mechanism to control cache partitioning, and consequently to achieve fair and efficient cache utilization. However, page coloring places additional constraints on memory space allocation, which may conflict with application memory needs. Further, adaptive adjustments of cache partitioning policies in a multi-programmed execution environment may incur substantial overhead for page recoloring (or copying). This paper proposes a hot-page coloring approach enforcing coloring on only a small set of frequently accessed (or hot) pages for each process. The cost of identifying hot pages online is reduced by leveraging the knowledge of spatial locality during a page table scan of access bits. Our results demonstrate that hot page identification and selective coloring can significantly alleviate the coloring-induced adverse effects in practice. However, we also reach the somewhat negative conclusion that without additional hardware support, adaptive page coloring is only beneficial when recoloring is performed infrequently (meaning long scheduling time quanta in multi-programmed executions).
Cited by 279
Hakan Aydın, David Kaeli · ACM SIGARCH Computer Architecture News · 2000
Memory hierarchy performance has always been an important issue in computer architecture design. The likelihood of a bottleneck in the memory hierarchy is increasing, as improvements in microprocessor performance continue to outpace those made in the memory system. As a result, effective utilization of cache memories is essential in today's architectures.The nature of procedural software poses visibility problems when attempting to perform program optimization. One approach to increasing visibility in procedural design is to perform procedure inlining. The main downside of using inlining is that inlined procedures can place excess pressure on the instruction cache.To address this issue we attempt to perform code reordering. By combining reordering with aggressive inlining, a larger executable image produced through inlining can be effectively remapped onto the cache address space, while not noticeably increasing the instruction cache miss rate.In this paper, we evaluate our ability to perform aggressive inlining by employing cache line coloring. We have implemented three variations of our coloring algorithm in the Alto toolset and compare them against Alto's aggressive basic block reordering algorithms. Alto allows us to generate optimized executables, that can be run on hardware to generate results. We find that by using our algorithms, we can achieve up a 21% reduction is execution runtime over the base Compaq optimizing compiler, and a 6.4% reduction when compared to Alto's interprocedural basic block reordering algorithm.
Cited by 9Open access
2015
Real-time systems require tight bounds on the Worst Case Execution Time (WCET) of a task. Modern multicore CPUs provide multiple levels of storing data (caching) and differ-ent paths to access memory (banks) that improve the performance but also introduce unpre-dictability in task execution time. To obtain predictable task execution times, developers have to consider the WCET, which may void the benefits of modern CPUs and may lead to low utilization of resources. On multicore platforms, caches present a source of unpredictability as standard heap al-located regions do not provide guarantees on the cache set that will hold a particular page translation. This unpredictability can lead to cache misses and consequently inter-task inter-ference resulting in loose bounds on the WCET. Memory access latency varies significantly depending on where the data is located in Non-Uniform Memory Access (NUMA) systems and how banks are interleaved. Data allocations without locality awareness may experience high memory latency so that execution times become highly unpredictable, resulting in loose bounds on the WCET of tasks and overly conservative scheduling with low utilization of modern CPUs.
Cited by 0
Jung-Hoon Kim, Jeehong Kim, Deuk-Hyeon Ahn et al. · Lecture notes in computer science · 2011
Cited by 2
Amir Hooshang Hashemi, David R. Kaeli, Brad Calder · 2007
Efficient exploitation of the available cache memory space can have a significant improvement in program performance. By carefully restructuring a program such that temporally local sequences of instructions are mapped to different portions of the cache, fewer cache conflicts will result. In this paper we present a link-time procedure mapping algorithm which views the cache as a colored address space, each color representing a different cache line. The idea of coloring is borrowed from the register allocation problem. We consider the size of the cache and the size of a cache line in this work, when coloring procedures to indicate the current mapping of the procedure in the cache space. This algorithm takes as input a weighted program call graph, with nodes representing procedures and edge weights representing call frequencies. This graph is used as input to our color-based mapping algorithm to provide an improved program layout. The results in this paper are presented for reducing the ...
Cited by 0
Freenix Track, Shuji Yamamura, Akira Hirai et al. · 2002
Rights to individual papers remain with the author or the author's employer. Permission is granted for noncommercial reproduction of the work for educational or research purposes. This copyright notice must be included in the reproduced paper. USENIX acknowledges all trademarks herein.
Cited by 0
Zhaodong Kang, Jin Xu, Wenqi Wang et al. · IEEE Transactions on Knowledge and Data Engineering · 2021
Multi-set membership queries are fundamental operations in data science. In this paper, we propose a new data structure for multi-set membership queries, named coloring embedder, which is fast, accurate, and memory efficient. The idea of coloring embedder is to first map elements to a high-dimensional space, which nearly eliminates hashing collisions, and then use a dimensional reduction representation, similar to coloring a graph, to save memory. Theoretical proofs and experimental results show that the coloring embedder is effective in solving the problem of multi-set membership queries. We also find that web cache sharing is one of the typical application scenarios of the multi-set membership queries and current methods based on Bloom filters always send redundant queries. We apply coloring embedder to web cache sharing by arranging our data structure on the on-chip and off-chip memory and designing query, insertion and deletion operations for this scenario. The experimental results show that compared with the present method, our method can reduce the queries sent by proxies while reaching equal hit rate with the same size of on-chip memory. The source code of coloring embedder has been released on Github.
Cited by 4
Axel Ferréol, L. Corbin, Nikolaï Kosmatov · Lecture notes in computer science · 2025
Abstract Hypervisors allow sharing of computing resources between applications—possibly of various levels of criticality—that makes them increasingly relevant for modern embedded systems. In this context, memory isolation properties (including low-level cache isolation) are essential to guarantee. This paper presents a case study on formal verification of the cache coloring mechanism implemented in the Bao hypervisor. It proposes an original technique for coloring memory pages and assigning to each virtual machine only pages of certain colors, aimed to provide strong isolation guarantees. The implementation presents several challenges for formal verification, such as bit-level operations, complex arithmetic operations, multiple levels of nested loops, and linked lists. We identify two subtle bugs in the existing implementation breaking the expected guarantees, and propose bug fixes. We provide formal specification for the key functions of the mechanism and verify their (fixed) version in the verification platform with a few lemmas proved in the proof assistant. We present our specification choices, verification approach and obtained results. Finally, we outline possible optimizations of the current implementation.
Cited by 2Open access
Ludan Zhang, Yi Liu, Rui Wang et al. · 2012
As multi-core/many-core becomes the trend of processor architecture, conflict in shared cache has become more and more serious that restricts performance improvement of parallel program. Recent research has employed page coloring mechanism to realizing cache partitioning on real system for the purpose of decline shared cache conflict. However, page coloring-based cache partitioning has some side-effects, one is page coloring restricts memory space an application can allocate from which may lead to memory pressure, another is changing cache partition dynamically need massive page copying which will incur large overhead and may go against with application's performance. To make page coloring based cache partition more practical, we proposed a malloc allocator based dynamic cache partitioning mechanism with page coloring. Memory allocated by our malloc allocator can be partitioned among different applications according to the cache partitioning policy. Our partition policy is based on a type recognition approach. Cache partition can be adjusted at run-time by changing the color of the pages allocated by the malloc allocator. Only coloring the dynamic allocated pages can remission memory pressure and reduce page copying overhead lead by re-coloring compared to all-page coloring. To further alleviate the overhead, we introduced minimum distance page copying strategy and lazy flush strategy. These policies yield performance improvements for co-running applications as high as 14.28% through cache partitioning and reduce the overhead of re-coloring by 55% on average when partitioning frequency is high. Our results demonstrate that only partitioning the dynamically allocated memory can reach the purpose of reducing cache conflict miss and the minimum distance page copying strategy is more beneficial to application with larger data-set and shorter data reuse distance.
Cited by 4
Sparsh Mittal · arXiv (Cornell University) · 2013
In recent years, researchers have explored use of non-volatile devices such as STT-RAM (spin torque transfer RAM) for designing on-chip caches, since they provide high density and consume low leakage power. A common limitation of all non-volatile devices is their limited write endurance. Further, since existing cache management policies are write-variation unaware, excessive writes to a few blocks may lead to a quick failure of the whole cache. We propose an architectural technique for wear-leveling of non-volatile last level caches (LLCs). Our technique uses cache-coloring approach which adds a software-controlled mapping layer between groups of physical pages and cache sets. Periodically the mapping is altered to ensure that write-traffic can be spread uniformly to different sets of the cache to achieve wear-leveling. Simulations performed with an x86-64 simulator and SPEC2006 benchmarks show that our technique reduces the worst-case writes to cache blocks and thus improves the cache lifetime by 4.07X.
Cited by 10Open access
Sparsh Mittal · arXiv (Cornell University) · 2013
There has been a significant increase in leakage energy dissipation of CMOS\ncircuits with each technology generation. Further, due to their large size,\nlast level caches (LLCs) spend a large fraction of their energy in the form of\nleakage energy and hence, addressing this has become extremely important to\nmeet the challenges of chip power budget. For addressing this, several\ntechniques have been proposed. However, most of these techniques require\noffline profiling and hence cannot be used for real-life systems which usually\nrun multitasking programs, with possible pre-emptions. In this paper, we\npropose a dynamic profiling based technique for saving cache leakage energy in\nmultitasking systems. Our technique uses a small coloring-based profiling\ncache, to estimate performance and energy consumption of multiple cache\nconfigurations and then selects the best (least-energy) configuration among\nthem. Our technique uses non-intrusive profiling and saves energy despite\nintra-task and inter-task variations; thus, it is suitable for multitasking\nsystems. Simulations performed using workloads from SPEC2006 suite show the\nsuperiority of our technique over an existing cache energy saving technique.\nWith a 2MB baseline cache, the average saving in memory sub-system energy is\n22.8%.\n
Cited by 1Open access
Fabien Bouquillon, Clément Ballabriga, Giuseppe Lipari et al. · LillOA (Université de Lille (University Of Lille)) · 2019
National audience
Cited by 0Open access
Fangyuan Liu, Zhexin Xu · 2025
Multi-UAV networks play a pivotal role in collaborative task execution within complex environments, yet achieving efficient data sharing remains a critical challenge. This paper introduces a UAV cache file cooperative response algorithm based on greedy graph coloring (GGC-CR) to optimize power consumption and response efficiency in UAV networks. The proposed algorithm generates task lists, constructs conflict graphs, and employs greedy graph coloring to allocate response tasks, minimizing both transmission power consumption and response cycles. Simulation results demonstrate that GGC-CR consistently outperforms benchmark algorithms across varying node densities and cache capacities, significantly improving resource utilization and addressing the critical challenge of efficient data sharing in UAV networks.
Cited by 0
Sparsh Mittal · arXiv (Cornell University) · 2013
In recent years, researchers have explored use of non-volatile devices such\nas STT-RAM (spin torque transfer RAM) for designing on-chip caches, since they\nprovide high density and consume low leakage power. A common limitation of all\nnon-volatile devices is their limited write endurance. Further, since existing\ncache management policies are write-variation unaware, excessive writes to a\nfew blocks may lead to a quick failure of the whole cache. We propose an\narchitectural technique for wear-leveling of non-volatile last level caches\n(LLCs). Our technique uses cache-coloring approach which adds a\nsoftware-controlled mapping layer between groups of physical pages and cache\nsets. Periodically the mapping is altered to ensure that write-traffic can be\nspread uniformly to different sets of the cache to achieve wear-leveling.\nSimulations performed with an x86-64 simulator and SPEC2006 benchmarks show\nthat our technique reduces the worst-case writes to cache blocks and thus\nimproves the cache lifetime by 4.07X.\n
Cited by 7Open access
Xiaolin Wang, Xiang Wen, Yechen Li et al. · 2012
Cache sharing among multiple computing units on chip is common in today's multi-core processors, and a lot of research has focused on the effective management of shared cache. A software management method called page coloring is commonly used to divide the cache among different applications competing for the same cache entries. Both static and dynamic cache partition mechanism have been implemented in operating system or user-space level. However, few efforts have been made under virtualization environments. Our previous work has provided a static cache partition method based on page coloring in Xen, following that, a dynamic cache partition mechanism called Colored Page Migration (CoPaM) is presented in this paper.
Cited by 8
Jian Cui, Si Yuan Li, Feng Pan · Advanced materials research · 2013
Memory allocation and management of real-time task and sub real-time task have been becoming the hot problem that people concern all the time. Page coloring technology is a kind of practical method which can realize isolation of cache space. This article aimed at the problem of cache resource competition caused by shared memory on multi-core real-time system, to solve the collision of cache visit, put forward the scheme of cache space isolation based on page coloring technology and the realization method. The problem that data collide with the visit on cache can be finally avoided, by dividing the shared cache space.
Cited by 0
Rui Min, Yiming Hu · IEEE Transactions on Computers · 2001
Modern CPUs often use large physically indexed caches that are direct-mapped or have low associativities. Such caches do not interact well with virtual memory systems. An improperly placed physical page will end up in a wrong place in the cache, causing excessive conflicts with other cached pages. Page coloring has been proposed to reduce the conflict misses by carefully placing pages in the physical memory. While page coloring works well for some applications, many factors limit its performance. Page coloring limits the freedom of the page placement system and may increase swapping traffic. In this paper, we propose a novel and simple architecture, called color-indexed, physically tagged caches, which can significantly reduce the conflict misses. With some simple modifications to the TLB (translation look-aside buffer), the new architecture decouples the addresses of the cache from the addresses of the main memory. Since the cache addresses do not depend on the the physical memory addresses anymore, the system can freely place data in any cache page to minimize the conflict misses, without affecting the paging system. Extensive trace-driven simulation results show that our design performs much better than traditional page coloring techniques. The new scheme enables a direct-mapped cache to achieve hit ratios very close to or better than those of a two-way set associative cache. Moreover, the architecture does not increase cache access latency, which is a drawback of set associative caches. The hardware overhead is minimal. We show that our scheme can reduce the cache size by 50 percent without sacrificing performance. A two-way set associative cache that uses this strategy can perform very close to a fully associative cache.
Cited by 16