Trace Reduction for LRU-Based Simulations
Yannis Smaragdakis · 1998
LRU buffer management is a policy under which an element buffer of size k always stores the k most recently used elements. Many variants of the policy are widely used in memory systems (e.g., virtual memory subsystems). We study a simple algorithmic problem (called the trace reduction problem): given a sequence of references to elements (a reference trace), compute the shortest sequence with identical LRU behavior for buffers of at least a certain size. Despite the straightforward statement of the problem, its solution is non-trivial. We offer an algorithm and discuss its practical applications. These are mostly in the area of trace-driven program simulation: for quite realistic buffer sizes, reference traces from real programs can be reduced by a factor of up to several orders of magnitude. This compares favorably with all previous trace reduction techniques in the literature. 1 Introduction An LRU stack of size k is a data structure storing the k most recently accessed elements of ...