A Survey of Miss-Ratio Curve Construction Techniques <s> Histogram <s> Many techniques characterize the program working set by the notion of the program footprint, which is the volume of data accessed in a time window. A complete characterization requires measuring data access in all O(n^2) windows in an n-element trace. Two recent techniques have significantly reduced the measurement time, but the cost is still too high for real-size workloads. Instead of measuring all footprint sizes, this paper presents a technique for measuring the average footprint size. By confining the analysis to the average rather than the full range, the problem can be solved accurately by a linear-time algorithm. The paper presents the algorithm and evaluates it using the complete suites of 26 SPEC2000 and 29 SPEC2006 benchmarks. The new algorithm is compared against the previously fastest algorithm in both the speed of the measurement and the accuracy of shared-cache performance prediction. <s> BIB001 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Histogram <s> The in-memory cache system is a performance-critical layer in today's web server architecture. Memcached is one of the most effective, representative, and prevalent among such systems. An important problem is memory allocation. The default design does not make the best use of the memory. It fails to adapt when the demand changes, a problem known as slab calcification. ::: ::: This paper introduces locality-aware memory allocation (LAMA), which solves the problem by first analyzing the locality of the Memcached requests and then repartitioning the memory to minimize the miss ratio and the average response time. By evaluating LAMA using various industry and academic workloads, the paper shows that LAMA outperforms existing techniques in the steady-state performance, the speed of convergence, and the ability to adapt to request pattern changes and overcome slab calcification. The new solution is close to optimal, achieving over 98% of the theoretical potential. <s> BIB002 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Histogram <s> The reuse distance (LRU stack distance) is an essential metric for performance prediction and optimization of storage and CPU cache. Over the last four decades, there have been steady improvements in the algorithmic efficiency of reuse distance measurement. This progress is accelerating in recent years both in theory and practical implementation. ::: ::: In this paper, we present a kinetic model of LRU cache memory, based on the average eviction time (AET) of the cached data. The AET model enables fast measurement and low-cost sampling. It can produce the miss ratio curve (MRC) in linear time with extremely low space costs. On both CPU and storage benchmarks, AET reduces the time and space costs compare to former techniques. Furthermore, AET is a composable model that can characterize shared cache behavior through modeling individual programs. <s> BIB003 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Histogram <s> Modern processors use high-performance cache replacement policies that outperform traditional alternatives like least-recently used (LRU). Unfortunately, current cache models do not capture these high-performance policies as most use stack distances, which are inherently tied to LRU or its variants. Accurate predictions of cache performance enable many optimizations in multicore systems. For example, cache partitioning uses these predictions to divide capacity among applications in order to maximize performance, guarantee quality of service, or achieve other system objectives. Without an accurate model for high-performance replacement policies, these optimizations are unavailable to modern processors. We present a new probabilistic cache model designed for high-performance replacement policies. It uses absolute reuse distances instead of stack distances, and models replacement policies as abstract ranking functions. These innovations let us model arbitrary age-based replacement policies. Our model achieves median error of less than 1% across several high-performance policies on both synthetic and SPEC CPU2006 benchmarks. Finally, we present a case study showing how to use the model to improve shared cache performance. <s> BIB004
These methods bin the data recorded into a histogram, and build a miss-ratio curve from that histogram by integrating the probability density function or summing the total frequencies over a given range. Average Eviction Time BIB003 . Hu et. al. presents as series of kinetic equations related to average data eviction in the cache. Based on the reuse time histogram, they estimate the probability that reference x has reuse time greater than t, which is then related to a stack movement. From here we can solve for the average eviction time for a given cache size. The average eviction time for a cache now relates miss-rate to time, so we have the following equation: Where P(x) is the probability that a reference has reuse time greater than t. In order to gain constant space complexity, they perform sampling over random random intervals, keeping the amount of data in the reuse time histogram constant with respect to the number of requests. Footprint BIB001 . Xiang et. al. introduces the footprint function as a mapping from an execution window to the volume of references during that time. For a given number of references n there are n 2 number of execution windows. Therefore, the average footprint is measured for a set of references. This can be done by measuring the following: • Reuse Time Histogram • The rst use of every reference • The last use of every reference The miss-ratio curve under the footprint metric is constructed for a given cache size d as the fraction of reuse times that have an average footprint smaller than d. In HOTL, it was shown that the footprint metric is the cache locality theory equivalent of Denning's working set size. The footprint algorithm runs in O(N ) and O(M) where N is the total number of accesses and M is the total unique accesses. The algorithm was recently applied in LAMA (Locality Aware Memory Allocation) BIB002 , to guide memcached's slab reallocation problem. Hit-Evict Distribution BIB004 . Beckmann et. al. introduces two new histograms of information, hit and evict. The hit distribution is the frequency of hits for given reuse times. Likewise, the evict distribution is the frequency of evicts for given reuse times. The motivation behind this work is to reduce the dependence on the LRU stack property that many analytic models assume. In their work they create an age distribution based o of the reuse times. This age distribution when combined with the hit and evict distribution can give an accurate LRU model for cache miss rates.