A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> Prior to this work, all implementations of stack simulation [MGS70] required more than linear time to process an address trace. In particular these implementations are often slow for highly-associative memories and traces with poor locality, as can be found in simulations of tile systems. We describe a new implementation of stack simulation where the refrrenced block and its stack distance are found using a hash table rather than by traversing the stack. The key to this implementation is that designers are rarely interested in a continuum of memory sizes, but instead desire metrics for only a discrete set of alternatives (e.g., powers of two). Our experimental evaluation shows the run-time of the new implementation to be linear in address trace length and independent of trace locality. Kim, et al., [KHW91] present the results of this research in more detail. <s> BIB001 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this purpose. However, dynamically tracking MRC at run time is challenging in systems with virtual memory because not every memory reference passes through the operating system (OS).This paper proposes two methods to dynamically track MRC of applications at run time. The first method is using a hardware MRC monitor that can track MRC at fine time granularity. Our simulation results show that this monitor has negligible performance and energy overheads. The second method is an OS-only implementation that can track MRC at coarse time granularity. Our implementation results on Linux show that it adds only 7--10% overhead.We have also used the dynamic MRC to guide both memory allocation for multiprogramming systems and memory energy management. Our real system experiments on Linux with applications including Apache Web Server show that the MRC-directed memory allocation can speed up the applications' execution/response time by up to a factor of 5.86 and reduce the number of page faults by up to 63.1%. Our execution-driven simulation results with SPEC2000 benchmarks show that the MRC-directed memory energy management can improve the Energy * Delay metric by 27--58% over previously proposed static and dynamic schemes. <s> BIB002 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> This paper investigates the problem of partitioning a shared cache between multiple concurrently executing applications. The commonly used LRU policy implicitly partitions a shared cache on a demand basis, giving more cache resources to the application that has a high demand and fewer cache resources to the application that has a low demand. However, a higher demand for cache resources does not always correlate with a higher performance from additional cache resources. It is beneficial for performance to invest cache resources in the application that benefits more from the cache resources rather than in the application that has more demand for the cache resources. This paper proposes utility-based cache partitioning (UCP), a low-overhead, runtime mechanism that partitions a shared cache between multiple applications depending on the reduction in cache misses that each application is likely to obtain for a given amount of cache resources. The proposed mechanism monitors each application at runtime using a novel, cost-effective, hardware circuit that requires less than 2kB of storage. The information collected by the monitoring circuits is used by a partitioning algorithm to decide the amount of cache resources allocated to each application. Our evaluation, with 20 multiprogrammed workloads, shows that UCP improves performance of a dual-core system by up to 23% and on average 11% over LRU-based cache partitioning. <s> BIB003 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> Miss rate curves (MRCs) are useful in a number of contexts. In our research, online L2 cache MRCs enable us to dynamically identify optimal cache sizes when cache-partitioning a shared-cache multicore processor. Obtaining L2 MRCs has generally been assumed to be expensive when done in software and consequently, their usage for online optimizations has been limited. To address these problems and opportunities, we have developed a low-overhead software technique to obtain L2 MRCs online on current processors, exploiting features available in their performance monitoring units so that no changes to the application source code or binaries are required. Our technique, called RapidMRC, requires a single probing period of roughly 221 million processor cycles (147 ms), and subsequently 124 million cycles (83 ms) to process the data. We demonstrate its accuracy by comparing the obtained MRCs to the actual L2 MRCs of 30 applications taken from SPECcpu2006, SPECcpu2000, and SPECjbb2000. We show that RapidMRC can be applied to sizing cache partitions, helping to achieve performance improvements of up to 27%. <s> BIB004 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> Shared caches in chip multi-processors (CMPs) have important benefits such as accelerating inter-core communication, yet the inherent cache contention among multiple processes on such architectures can significantly degrade performance. To address this problem, cache partitioning has been studied based on the prediction of the cache miss rate curve (MRC) of the concurrently running programs. On-line MRC prediction, however, either requires special hardware support or incurs a high overhead when conducted purely in software. This paper presents a new MRC prediction scheme based on a fractal model and hence called Fractal MRC. It uses the easily available features in performance monitoring units of modern Intel processors and predicts the MRC of a running program with low overhead and high accuracy. No changes to applications and hardware are required. The prediction is validated against the measured results for 26 applications from SPEC CPU2006 benchmark suite. The highest prediction accuracy is 99.3%, the accuracy of 12 of the applications is over 80%, and the average is 76%. The cost of prediction is 2% slowdown on average. The new, efficient and accurate MRC prediction has enabled a dynamic technique to partition cache between pairs of applications at run time to match or exceed the best performance attainable with static cache partitioning. <s> BIB005 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> This short paper outlines a theory for deriving the traditional metrics of miss rate and reuse distance from a single measure called the footprint. It gives the correctness condition and discusses the uses of the new theory in on-line locality analysis and multicore cache management. <s> BIB006 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> Reuse distance is a well established approach to characterizing data cache locality based on the stack histogram model. This analysis so far has been restricted to offline use due to the high cost, often several orders of magnitude larger than the execution time of the analyzed code. This paper presents the first parallel algorithm to compute accurate reuse distances by analysis of memory address traces. The algorithm uses a tunable parameter that enables faster analysis when the maximum needed reuse distance is limited by a cache size upper bound. Experimental evaluation using the SPEC CPU 2006 benchmark suite shows that, using 64 processors and a cache bound of 8 MB, it is possible to perform reuse distance analysis with full accuracy within a factor of 13 to 50 times the original execution times of the benchmarks. <s> BIB007 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Access Counters <s> Existing techniques for identifying working set sizes based on miss ratio curves (MRCs) have large memory overheads which make them impractical for storage workloads. We present a novel data structure, the counter stack, which can produce approximate MRCs while using sublinear space. We show how counter stacks can be checkpointed to produce workload representations that are many orders of magnitude smaller than full traces, and we describe techniques for estimating MRCs of arbitrary workload combinations over arbitrary windows in time. Finally, we show how online analysis using counter stacks can provide valuable insight into live workloads. <s> BIB008
These methods either use: (1) a set of counters to represent stack distances at each cache size or (2) a set of counters to represent total accesses and unique accesses. Powers of 2 by BIB001 . First purposed by Kim et. al. in 1991, they use Mattson's algorithm with two key di erences: • Counters are used representing cache sizes of 2 k • Use a hash table to record previous stack location and stack distance for each reference Therefore on reference x, we lookup its position and stack distance i. Then increment the counter corresponding to cache size i, this means that x would hit in all caches size > i. Now we have to push x on the top of the stack and update stack distances for all references in the stack, the worst case on this is M. Therefore the running time is in the same asymptotic bound, O(N * M) as Mattson's, but in practice it runs faster since it is insensitive to a program's average stack distance. This algorithm has been applied to build miss-ratio curves in Zhou et. al. BIB002 . They present a hardware and software implementation for calculating page miss-ratio curves to guide memory management in a multi-program environment, a known NP-hard problem. At the hardware level, Tam et. al. BIB004 have used this algorithm to manage L2 cache partitioning. Here they create an access trace to L2 by recording the misses of L1, then they send the access trace log into the algorithm given by Kim. Their miss-ratio curve is then used to guide how much of the L2 cache should an application receive. CounterStacks BIB008 . This recent development by Wires et. al. uses probabilistic counters (HyperLogLogs) and Bloom lters (for set inclusion) in order to maintain a list of unique accesses over a period of time. Speci cally, they build a list for time t that contains the number of unique accesses. This allows us to keep track of how much a counter increased (stack distance) over a number of non-distinct accesses. An example is given in Table 2 . In order to derive the stack distance, we need to look at the intra-counter change, that is to nd the last reference, we must nd the newest counter. In Table 2 we nd the last reference to a is at position 1, hence the stack distance of a lies at position (1,4) = 3. CounterStacks uses O(N * lo (M)) to process a set of references, since we still need to nd the last reference to each element. But CounterStacks achieves a great reduction in space complexity, O(lo (M)) through its use of probabilistic counters which set a small bound on the overall error in stack distance calculation. UMONs BIB003 . Qureshi et. al. developed utility monitor circuits (UMONs) that approximate hit rate vs. number of sets in an LRU cache. They use access counters for a xed number of stack positions for each set. Since the cache obeys the LRU policy, we can get the hit rate for a given number of sets by reading the counters for n sets. This process is used in partitioning caches by set per application. If application A has a higher utility for a number of sets (i.e. its hit rate curve is not as steep) then it will be assigned that number of sets. Application B will be left with the remaining number of sets. Fractals BIB005 . L. He et. al. use a fractal equation to calculate the miss-rate of a given cache size from the time between two consecutive misses. This is known as the inter-miss gap described by Denning and related to LRU miss-rate by Ding in HOTL BIB006 . From the distribution of these inter-miss gaps we can get the LRU miss rate for a given cache size, by the following: Their collection inter-miss gaps used hardware counters to record a cache miss, the number of references n, and a new cache miss. n is then saved into a bu er. This model allows for online processing at the cost of a 2% slowdown. Unfortunately, their model ignores cold misses which leads to inaccuracy (the cold miss equation is not fractal). On average in the SPEC2006 benchmark they report 76% percent miss-ratio curve accuracy. PARDA BIB007 . Q. Niu et. al introduce the rst explicit parallel stack distance algorithm based on Mattson's stack processing. PARDA exploits the independences of the de ne-use chains in references. That is, since we only care about the reference to the last location, all previous references are independent. Therefore, we can create chunks that contain all references between the last use and the current use for a given access. The algorithm is outlined below: Table 3 : Example reuse time calculation for a set of requests These methods use counters to record reuse times for a particular set of references, these counters are then aggregated to form a reuse time distribution. Statcache  . Statcache by Berg et. al. uses random sampling to select some memory references. For each memory reference it does the following: (1) Set a (hardware) watchpoint on the address and record current number of memory accesses at that time n. The Statcache model assumes a cache with random replacement, because of this we can assume that the probability that a cache line is still in a cache after a cache miss is uniform. Since the model calculates the probability that a reference will cause a cache miss, by assuming miss-ratio does not change over time, we can x missrate and derive the probability that a number of references cause a miss from its reuse distance from their reuse time. Statstack  . The Stackstack model builds o of the Statcache work, this time modeling an LRU cache. They de ne the expected stack distance of a reference with reuse time t to be the average stack distance of all references with reuse time t. The miss-ratio curve is then constructed by computing the expected stack distance of each reuse time weighted by their frequency, this gives us a stack distance distribution. If one were to interpret the Statstack model's relationship between average stack distance vs. time, then we would arrive at the kinetic equation present in the average eviction model (AET). Stackstack performs in the same time bound as the AET model, O(N ) time and O(1) space due to their sampling techniques.