Notes

Outline

Evaluating Synthetic Trace Models Using Locality Surfaces By Elizabeth S. Sorenson J. Kelly Flanagan Brigham Young University

Trace-Driven Simulation Popular method for evaluating caches The larger the cache, the longer the trace needed Long traces require large storage One solution: Synthetic Traces

Synthetic Traces Small storage requirements Extract limited number of parameters from a real trace Can create an arbitrarily long trace Can create traces for future workloads and systems Tend to be inaccurate

Which Synthetic Trace Models Independent Reference Model Stack Model Partial Markov Model Distance Model Distance-Strings Model

Evaluation Methods Locality Surfaces Programs tend to use a small portion of memory most of the time Principle that caches are based on Cache simulation results (miss rate) Use configurations typical of level one caches Size: 32 Kbyte to 64 Kbyte 1-way associative to 8-way associative

Locality Surface Good way to visualize locality Incorporates both temporal and spatial locality Useful for qualitatively predicting cache performance

Example Locality Surface

Traces Used Twolf from SPECint2000 benchmark suite Collected using the BACH method Pentium III, Redhat Linux 6.2 Separate instruction fetches and data reads and writes

Twolf Instruction Fetches

Twolf Data Reads and Writes

Independent Reference Model Determine the frequency of any given memory address occurring in original trace Use the frequencies as probabilities Generate references based on these probabilities

IRM – Instruction Fetches

IRM – Data Reads & Writes

IRM – compare stride=0 axis

Stack Model Maintain an LRU stack of references seen Record frequency of accessing references x deep in stack Use these frequencies to generate references When generating a reference not in the stack, use a random reference

SM – Instruction Fetches

SM – Data Reads & Writes

SM – compare stride=0 axis

Partial Markov Model Assumes all references either random or sequential Determines probabilities of changing states vs. staying the same

PMM – Instruction Fetches

PMM – Data Reads & Writes

Distance Model Determine frequency of any stride occurring between successive entries in trace When generating references, generate a stride from the stored distribution and add it to previous reference

DM – Instruction Fetches

DM – Data Reads & Writes

DM – compare delay=1 axis

Distance-Strings Model Again uses frequencies of strides occurring, except uses strides between the start of bursts of sequential references Also uses the frequencies of the lengths of sequential bursts

DSM – Instruction Fetches

DSM – Data Reads & Writes

DSM – compare delay=1 axis

Instruction Fetches Cache Simulation Results

Data Reads & Writes Cache Simulation Results

Conclusions None of these models adequately replicate all aspects of locality IMR and SM do approximate the effective working set size to some degree IRM, SM, and DM mostly successful at the aspects of locality they intended to produce

Future Work This is only the first step in the process We will evaluate in a similar fashion some more recent models GOAL: a synthetic trace generation model based on the locality surface