A Survey of Miss-Ratio Curve Construction Techniques <s> INTRODUCTION <s> Probably the most basic reason behind the absence of a general treatment of resource allocation in modern computer systems is an adequate model for program behavior. In this paper a new model is developed, the “working set model”, which enables us to decide which information is in use by a running program and which is not. Such knowledge is vital for dynamic management of paged memories. The working set of pages associated with a process, defined to be the collection of its most recently used pages, is a useful allocation concept. A proposal for an easy-to-implement allocation policy is set forth; this policy is unique, inasmuch as it blends into one decision function the heretofore independent activities of process-scheduling and memory-management. <s> BIB001 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> INTRODUCTION <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> BIB002 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> INTRODUCTION <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
From the working set theory proposed by Denning in 1968 BIB001 to recent advancements in cache locality theory BIB002 BIB003 modeling data locality has been essential to cache design and OS resource allocation choices. In the past decade there has been a large emphasis on using these models to construct plots relating miss rate to cache size, called miss-ratio curves (MRCs) or equivalently hit-ratio curves (HRCs). Miss ratio curves have proven to be extremely useful in estimating how much data is being used by a particular workload, known as the working set size. Knowing the working set size of a workload helps estimate the utility of adding more memory or increasing the cache size. An example miss-ratio curve is shown in Figure 1 . The knee-point in this particular MRC is just over cache size 3000 for this workload. Notice how that an increase cache size to 4000 yields no signi cant decrease in miss-rate. Given the recent theoretic and implementation advancements in miss-ratio curve construction, we nd a survey on these methods to be useful update to the community and present some identi ed open lines of research yet to be fully explored in this domain.