Miss ratio curve (MRC) profiling techniques are widely used for memory, cache analysis, and design. As noted by the authors, uses include cache partitioning, page size selection, memory management, memory cache prediction, and so on. Thus, MRC profiling techniques are useful to analyze high-throughput storage workloads. This paper describes an average eviction time (AET)-based algorithm for modeling the cache behavior of programs in a multilevel cache. It also shows how to compose an individual program’s cache when the cache is shared in a multiprogrammed environment. The paper provides a good chronology of various breakthroughs in MRC modeling, and guides readers through the improvements to space and time complexity reduction and usage.

Although the paper includes a comprehensive list of relevant work, it principally compares its efficacy against two of the current best known techniques: spatially hashed approximate reuse distance sampling (SHARDS) [1] and counter stacks [2]. Counter stacks use probabilistic counters to generate MRCs by estimating reuse distances from the last access. SHARDS “uses hash-based spatial sampling and a splay tree to track the reuse distances of the sampled data,” reducing space usage significantly. To account for time varying behavior, an adaptive phase sampling technique is described that improves AET’s model accuracy.

In summary, the authors claim that AET is better than counter stacks in space overhead, achieves comparable performance to SHARDS, and is more useful than SHARDS when running in a multiprogrammed environment sharing a least recently used (LRU)-based cache. As we see more computing architectures adopt a memory-centric approach, such papers are timely and useful.