Trace Reduction for Virtual Memory Simulation

A reference trace is a sequential log of the memory locations used by an executing program.  These traces are used as input for trace driven simulation, which allows researchers to simulate the behavior and performance of a memory system without modifying a real kernel or real hardware.  While trace driven simulation has great benefits, the traces themselves can be painfully large.  Only a few seconds of program execution can generate traces of many megabytes.

Most existing reference trace methods have been developed for hardware cache simulations.  However, virtual memory research has become an increasingly important topic in recent years.  As such, we present here two new methods for trace reduction that are designed to reduce traces by discarding information useless to LRU and LRU-like page replacement policies, and thus most virtual memory simulations.  Safely Allowed Drop (SAD) and Optimal LRU Reduction (OLR) are these two new methods described in our paper, and provided below.  Note that we also offer the original and reduced traces, as well as the simulators, used in the experiments described in our research.

Our conference paper on this topic appeared in SIGMETRICS '99, and a journal version will appear in ACM TOMACS; you can grab copies of either from the page of papers.

Trace Reducers

Below is a simple tar-and-gzipped file that contains the source code for both SAD and OLR. Included is a README, as well as a sample trace file with which to test the code. Itís a reasonably small file, so donít be afraid to grab it and try it out!

Test suite

Each of these programs was linked with VMTrace, given an input (provided with each package here), and executed to provide us with the reference traces needed. Below are the reference traces that we gathered and used for these programs, as well as those gathered at The University of Washington using the Etch tool on the Windows NT platform. You do not need these programs to verify our simulations, but you're welcome to them nonetheless!

Original Reference Traces

These traces were gathered using VMTrace on a Linux/x86 machine on the test suite above.


This group of traces was gathered by researchers at the University of Washington by applying the Etch trace gathering tool to on a Windows NT machine to a set of programs for which we donít have the source. (Sorry!)

Send feedback to Scott Kaplan <>

Last modified: Tue Sep 16 10:24:25 EDT 2003