This is an implementation of M. Kharbutli and Y. Solihin's Counter-Based Cache Replacement and Bypassing Algorithms in SimpleScalar. This implementation is based on SimpleScalar-3v0d and should work on a vanilla installation (can be obtained from the SimpleScalar site). Only the AIP and LvP algorithms were implemented - bypassing is not included. In addition, it calculates the histogram of the LRU stack positions of cache hits (ie. how many hits each LRU position gets), as well as the histogram of the LRU stack position of AIP/LvP-evicted cache lines (as opposed to LRU-evicted cache lines; AIP and LvP operate on top existing replacement algorithms).

Files

Only 4 files need to be modified:
cache.c cache.h sim-cache.c sim-outorder.c

Installation

To install the modifications, replace the original files with the ones above and compile with gcc-3.3 or gcc-3.4 (you'll probably want to edit the Makefile to say CC=gcc-3.3 or CC=gcc-3.4 rather than CC=gcc). Additionally, don't forget to first select your configuration (ie. whether you want to build for Alpha or PISA; make config-alpha or make config-pisa, respectively). On Linux, don't forget to install libc6-dev as well.

Usage

By default, SimpleScalar accepts the following configuration input format for caches: 
<name>:<nsets>:<bsize>:<assoc>:<repl>
where 
    <name>   - name of the cache being defined
    <nsets>  - number of sets in the cache
    <bsize>  - block size of the cache
    <assoc>  - associativity of the cache
    <repl>   - block replacement strategy, 'l'-LRU, 'f'-FIFO, 'r'-random

    Examples:   -cache:dl1 dl1:4096:32:1:l
                -dtlb dtlb:128:4096:32:r
The modifications made by this implementation extend this format to accept an additional value that indicates the counter-based cache replacement policy (if any): 
<name>:<nsets>:<bsize>:<assoc>:<repl>[:<cbrPolicy>]
where 
    <cbrPolicy>   - counter-based replacement policy, 'a'-AIP, 'l'-LvP
and all other options are as before.

Output

The modifications made generate some additional output illustrated by this example of a unified L2 cache (taken from a Spec2000 Alpha gcc.166 skip-2-billion-run-3-billion sim-outorder run with AIP enabled): 
ul2.accesses              191962869 # total number of accesses
ul2.hits                  126909709 # total number of hits
ul2.misses                 65053160 # total number of misses
ul2.replacements           65044968 # total number of replacements
ul2.writebacks             32243798 # total number of writebacks
ul2.evictions_std          16232772 # total number of eviction victims chosen by the standard cache replacement policy (LRU)
ul2.evictions_cbr          48820388 # total number of eviction victims chosen by the CBR cache replacement policy (AIP)
ul2.invalidations                 0 # total number of invalidations
ul2.miss_rate                0.3389 # miss rate (i.e., misses/ref)
ul2.repl_rate                0.3388 # replacement rate (i.e., repls/ref)
ul2.wb_rate                  0.1680 # writeback rate (i.e., wrbks/ref)
ul2.inv_rate                 0.0000 # invalidation rate (i.e., invs/ref)
ul2.stack_dist[0]          62777033 # amount of cache hits at MRU/stack distance 0
ul2.stack_dist[1]          24656950 # amount of cache hits at MRU/stack distance 1
ul2.stack_dist[2]           2673971 # amount of cache hits at MRU/stack distance 2
ul2.stack_dist[3]           1200676 # amount of cache hits at MRU/stack distance 3
ul2.stack_dist[4]           3805901 # amount of cache hits at MRU/stack distance 4
ul2.stack_dist[5]           1229185 # amount of cache hits at MRU/stack distance 5
ul2.stack_dist[6]           4358315 # amount of cache hits at MRU/stack distance 6
ul2.stack_dist[7]          26207678 # amount of cache hits at MRU/stack distance 7
ul2.cbr_repl_stack_dist[0]      8638303 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 0
ul2.cbr_repl_stack_dist[1]     24113637 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 1
ul2.cbr_repl_stack_dist[2]      7918323 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 2
ul2.cbr_repl_stack_dist[3]      2407428 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 3
ul2.cbr_repl_stack_dist[4]      1964173 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 4
ul2.cbr_repl_stack_dist[5]      1365139 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 5
ul2.cbr_repl_stack_dist[6]      1113260 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 6
ul2.cbr_repl_stack_dist[7]      1300125 # amount of blocks evicted by CBR policy AIP at MRU/stack distance 7