Trace Reduction for Virtual Memory Simulation

Warning: This page is under construction, so not all of the components used for our experiments are available yet.  Please send email to Scott Kaplan <sfkaplan@cs.utexas.edu> if there is a piece of software or a reference trace that you want, but isn't yet available.


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 paper on this topic appeared in SIGMETRICS '99, and you can grab a copy from our 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!)


Reduced Reference Traces

Because we reduced each of the original reference traces with these utilities at a large number of different reduction memory sizes, we did not store the reduced traces. However, below, we provide our implementations of SAD and OLR, as well as the simulators and scripts used to perform our experiments. Each reduced trace can easily be reproduced from the original trace and the trace reduction utility.


Simulators and Scripts


Page last updated on May 21, 1999

Send feedback to Scott Kaplan <sfkaplan@cs.utexas.edu>