Trace reduction for virtual memory simulations
Scott F. Kaplan, Yannis Smaragdakis, Paul R. Wilson · 1999
The unmanageably large size of reference traces has spurred the development of sophisticated trace reduction techniques. In this paper we presenttwonew algorithms for trace reduction --- Safely Allowed Drop (SAD) and Optimal LRU Reduction (OLR). Both achieve high reduction factors and guarantee exact simulations for common replacement policies and for memories larger than a user-defined threshold. In particular, simulation on OLR-reduced traces is accurate for the LRU replacement algorithm, while simulation on SAD-reduced traces is accurate for the LRU and OPT algorithms. OLR also satisfies an optimality property: for a given trace and memory size it produces the shortest possible trace that has the same LRU behavior as the original for a memory of at least this size. Our approach has multiple applications, especially in simulating virtual memory systems