Code for Sampling-Based Adaptive Replacement (SBAR)
(Works on Linux.  Known to not work on Sun machines with Unix)


Download: 
To  execute the sample code for sbar, download the following files:

  1. mcache.h => The header file for the simulated cache
  2. mcache.c => The source file for the simulated cache
  3. cachesim.c => A cache simulator that contains the trace reader
  4. Makefile => A sample makefile
  5. art_00.atr.gz => A trace file containing the L2 access stream for art

Compile:
After saving these files in a directory, compile the code by typing "make". This should produce the executable cachesim.
Type ./cachesim -h for help.


Sample runs:

For testing cachesim, type "make test".  This should simulate five cache configurations:

1.   The baseline 1MB 16-way LRU-managed cache
./cachesim -mtdrepl LRU art_00.atr.gz
=======================
Count: 1000001
Miss:   770365 (77.04%)
=======================

2.   A 1 MB 16-way cache with RANDOM replacement
./cachesim -mtdrepl RND art_00.atr.gz
=======================
Count: 1000001
Miss:   485051 (48.51%)
=======================

3.   A 1 MB 16-way cache with LFU replacement
./cachesim -mtdrepl LFU art_00.atr.gz
=======================
Count: 1000001
Miss:   326694 (32.67%)
=======================

4.  A 1MB 16-way cache with SBAR (selecting between the default LRU policy and ATD's RND policy using 32 leader sets)
./cachesim -mtdrepl LRU -leaders 32 -atdrepl RND art_00.atr.gz
=======================
Count: 1000001
Miss:   468935 (46.89%)
SBAR used MTD policy: 24.5%
SBAR used ATD policy: 75.5%
=======================

5.  A 1MB 16-way cache with SBAR (selecting between the default LRU policy and ATD's LFU policy using 32 leader sets)
./cachesim -mtdrepl LRU -leaders 32 -atdrepl LFU art_00.atr.gz
=======================
Count: 1000001
Miss:   355329 (35.53%)
SBAR used MTD policy: 16.7%
SBAR used ATD policy: 83.3%
=======================

The example shows how the code can be used to select between LRU and RND (or LFU) using dynamic set sampling with 32 leader sets.  SBAR can outperform the component policies because it dynamically selects the policy best suited to paritcular phase of the program.

In general, the framework can be used to dynamically select between any two replacement policies.  For example, to select between LRU and any policy X, first implement the policy X in the code.  Then, use LRU for mtdrepl and X for atdrepl.  The code can also be extended to support more than two replacement policies.


Generating the trace file:
The trace for the art benchmark was obtained by using a single simpoint of 250M instructions.  To limit the trace size, the trace file only contains the first 1 Million L2 accesses. The first-level I and D caches is configured as 16kB, 2-way with 64B linesize. The trace.atr file contains line-address for the lines that missed the first level cache.  Each trace entry is stored in the trace file as eight consecutive bytes. The trace.atr file is compressed using gzip and the resulting trace.atr.gz file is used as the input to cachesim.


Disclaimer:
Standard open-source policies apply. 

Please feel free to email me if you have any questions, comments, suggestions, or feedback.

This document was generated by Moinuddin on September, 12 2006