Energy optimal cache replacement algorithm

From SuperMe

Jump to: navigation, search

Contents

Energy-Optimal Cache Replacement Algorithm

Project Members

Project by: Tim Russell
Advisors: Dr. Yifeng Zhu and Jianhui Yue

Project Abstract

Project Description

As computers proliferate in our everyday world and computing resources in science, business, and academia become more demanding, the need for energy efficiency becomes ever more evident. Small-scale mobile devices can benefit from such efficiency by extending battery lifetimes and/or reducing footprint, and large-scale computational and storage centers benefit from reduced fiscal overhead and compliance with environment-friendly “green” policies. Two readily identifiable targets for energy-conscious computer research are memory and disk components, both of which account for large shares of a total computer's energy usage. And since the performance and behavior of memory and disks are intricately linked, advances in efficient use of one may (and probably will) result in tandem benefits for the other, giving even larger energy savings. We seek to improve the energy efficiency of memory through the development of an optimal energy-aware cache replacement algorithm.

Cache replacement algorithms are policies which a computer uses to manage a cache of information stored in memory. The use of this cache enhances performance, because a computer can access information in memory at speeds that are orders of magnitude faster than accessing the same data on disk. If the cache is full and information not in the cache is requested, the algorithm must choose which pages to evict to make room for the new ones. Until recently, the quality of replacement algorithms was almost exclusively measured by—and so researched was focused on—the “hit rate” of the cache, i.e. how often the requested data was found in the cache. Belady's well-known MIN algorithm was used as the theoretical optimum algorithm, since it provides the upper-bound for hit rate.

Current research into energy-aware computing, however, has quickly shown that commonly used replacement algorithms such as LRU, and even MIN, offer poor energy-conscious cache management (ref). Modern memory power management schemes allow memory which is not in use to revert to lower-power modes to conserve energy. Unfortunately, there is an energy and time cost involved in transitioning between these power states, and memory must be in the highest power state to give the maximum performance. Non-uniform cache misses with traditional algorithms can detract from memory and disk power management schemes, because intermittent memory accesses can reduce memory idle time and cause more power state transitions. Our goal is to develop a cache replacement algorithm which effectively keeps portions of memory active so that they will not transition to lower power modes if they will soon be accessed again, thereby circumventing the time and energy cost of the transitions. Additionally, by keeping some portions of memory more active, other portions of memory can be kept in low-power modes longer. Recent studies (ref) have shown that the power savings garnered by the latter are greater than the cost of keeping the former active, thereby achieving overall energy savings.

Background Information

Much research has been done in the areas of cache management and and page replacement algorithms. Effective replacement algorithms enhance computer performance by minimizing cache “miss” ratios. Performance gains are achieved, because if a given data request is fulfilled by the cache (a “hit”), the data can be retrieved from memory much faster than from disk. Under this metric, a good replacement algorithm is one that chooses as a victim the pages whose next reference is the greatest length of time in the future. Of course, to fully realize this goal, the algorithm would need knowledge of the future (i.e. would need to know the entire reference string to make the correct choice). This is exactly Belady's MIN algorithm. Algorithms which assume knowledge of the entire reference string are dubbed off-line, while those which assume only knowledge of past and current references are called on-line. It should be clear that off-line algorithms are not actually realizable (computer scientists haven't figured out how to predict the future), but Belady's algorithm provides a theoretical optimal page replacement algorithm, against which other algorithms can be measured.

Belady's algorithm (and many other traditional page replacement algorithms) assume a uniform cost (in time, energy, or any other commodity) for memory access. The MIN algorithm can easily be shown to give non-optimal energy usage with modern power management schemes which allow memory to power down during idle periods to save energy. Many new algorithms have been developed to account for this variable-cost access to memory. Variable cost can result from several factors, including: multi-mode power management schemes, hardware heterogeneity, and hierarchical storage cache systems. Large-scale data storage centers, in particular, exhibit the latter two qualities (ref), and because they tend to remain continuously active for long periods of time (the goal of the facility), energy savings could accumulate quickly. Interestingly, a recent study (ref) actually found that energy-aware cache management schemes not only brought about significant energy savings, but also increased performance and responsiveness. Hence, there does not necessarily need to be a trade-off between energy frugality and performance. Finally, since the effective use of cache allows disks to be idle for longer, allowing them to more aptly employ disk power management schemes, tandem energy savings increase the boon.

Tentative Schedule

Related Work

  1. Design and Implementation of Power-Aware Virtual Memory
  2. Cost-Aware Caching Algorithms for Distributed Storage Servers: Liang et al. Introduce two offline cost-aware replacement algorithms (MIN-d and MIN-cod) for non-uniform access caches and examine its performance relative to other well-known algorithms. An online algorithm, HD-cod (an implementation of MIN-cod) is given and analyzed.
  3. Power Aware Page Allocation
  4. Power-Aware Storage Cache Management: Zhu and Zhu introduce an offline energy-optimal cache replacement algorithm which utilizes dynamic programming and which focuses on maximizing energy savings by assisting disk power management schemes. Two online algorithms, PA-LRA and PB-LRU are then introduced and evaluated. Both algorithms are shown to out-perform well-known replacement algorithms in terms of of both responsiveness and disk energy conservation.
  5. Caching for Bursts (C-Burst): Let Hard Disks Sleep Well and Work Energetically A Linux-kernel implementation of a partitioned cache replacement algorithm.
  6. Non-Lecture A: Greedy Algorithms An overview of the development of greedy algorithms with some specific examples.
  7. Energy Efficient Buffer Cache Replacment Jianhui Yue's paper on his chip_2Q cache replacement algorithm.
  8. Optimal Replacement Is NP-Hard for Nonstandard Caches Brehob et. al investigate the hardness of optimal cache replacement algorithms for nonstandard caches (i.e. victim caches, assist caches, skew caches, and "smart" caches). The authors show that the caching problem for nonstandard caches is NP-hard, meaning that no poly-time algorithm exists for the problem, unless P=NP.
Retrieved from "http://arch.eece.maine.edu/superme/index.php/Energy_optimal_cache_replacement_algorithm"