Trace reduction for virtual memory simulations

The unmanageably large size of reference traces has spurred the development of sophisticated trace reduction techniques. In this paper we present two new algorithms for trace re-duction — Safely Allowed Drop (SAD) and Optimal LRU Reduction (OLR). Both achieve high reduction factors and guarantee exact simulations for common replacement poli-cies and for memories larger than a user-defined threshold. In particular, simulation on OLR-reduced traces is accu-rate 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 pos-sible trace that has the same LRU behavior as the original for a memory of at least this size