Part IV·Memory Hierarchy·Chapter 47 of 66

Part IVMemory Hierarchy

Project --- A Trace-Driven Cache Simulator in C++

August 3, 2026·26 min read·advanced

The case study of Chapter 46 surveyed cache hierarchies as they ship in silicon. This project chapter goes the other direction. The reader will build a configurable trace-driven cache simulator in C++ from scratch and use it to explore the design space the previous chapter described. The simulator takes a memory-access trace as input and reports the hit rate, miss rate, and average memory access time (AMAT) for the configured cache geometry. Configuration knobs include cache size, associativity, line size, replacement policy (LRU, tree-PLRU, RRIP, Hawkeye, Mockingjay), and inclusion policy (inclusive, exclusive, NINE). The simulator runs on traces extracted from SPEC CPU 2017 and produced by ChampSim’s trace exporter.

The project follows the same shape as the ALU project of Chapter 11 and the assembler project of Chapter 23. First, the Setup and Installation section walks the reader through getting a modern C++ toolchain on macOS, Linux, and Windows. Then the project skeleton and the build system. Then the address-decomposition class. Then the replacement-policy hierarchy with five policies. Then the inclusion variants. Then the trace replay loop. Finally, the reader runs a small set of SPEC trace snippets and produces a per-policy AMAT comparison. The chapter ends with worked examples and exercises.

The simulator is not a clock-cycle-accurate model. It tracks hits and misses at every level and computes AMAT analytically. Cycle-accurate memory simulation is taken up in Chapter 48 using ChampSim and gem5. The project here builds the conceptual scaffolding the lab will extend.

01.Setup and Installation

The project requires three tools: a C++20 compiler (clang or gcc), the CMake build system, and xz, which the simulator invokes to stream the compressed SPEC trace files without unpacking them to disk. The C++ standard library is the only third-party dependency. The simulator does not pull in Boost, abseil, or any other library, to keep the build reproducible on a fresh machine.

macOS (Homebrew)

macOS setup via Homebrew

Plain Text

# Modern compiler and build tooling
brew install llvm cmake xz

# Optional: a sanitizer-enabled debug build wants gdb on Apple
# silicon, where lldb is the default. Skip if you do not need it.
brew install gdb

Verify each tool after installation:

Verify macOS installations

Plain Text

clang++ --version    # Apple clang or Homebrew clang 18.x+
cmake --version      # CMake 3.28 or later
xz --version

The Apple-supplied clang++ from Xcode Command Line Tools also works for the project. The Homebrew LLVM is the canonical choice when the project needs newer C++20 or C++23 features that have not yet landed in the Apple-vendored toolchain.

Linux (Arch as canonical)

Arch Linux setup

Plain Text

# Compiler, build system, decompression
sudo pacman -S clang gcc cmake xz
# Optional: ninja, faster builds than make
sudo pacman -S ninja

For Debian or Ubuntu, replace pacman with apt:

Debian/Ubuntu alternative

Plain Text

sudo apt update
sudo apt install build-essential cmake clang \
    xz-utils ninja-build

For Fedora:

Fedora alternative

Plain Text

sudo dnf install gcc-c++ clang cmake xz ninja-build

Windows (ArchWSL)

The recommended path on Windows is ArchWSL, the Arch Linux distribution for WSL2. Once ArchWSL is installed, the setup is identical to the Arch Linux instructions above. The project source tree should live inside the WSL2 filesystem (~/projects/cachesim) rather than on a Windows-mounted drive, since CMake reconfiguration and incremental compilation benefit from native filesystem performance.

Windows setup via ArchWSL

Plain Text

# Inside the ArchWSL terminal:
sudo pacman -S clang gcc cmake xz ninja

02.Project Skeleton

The project tree is small. The simulator splits into headers in include/ and implementation files in src/. The trace files live in traces/. The CMake build script sits at the top level.

Project directory layout

Plain Text

cachesim/
├── CMakeLists.txt
├── include/
│   ├── Address.hpp
│   ├── Cache.hpp
│   ├── Hierarchy.hpp
│   ├── Replacement.hpp
│   ├── Stats.hpp
│   └── Trace.hpp
├── src/
│   ├── Address.cpp
│   ├── Cache.cpp
│   ├── Hierarchy.cpp
│   ├── Replacement.cpp
│   ├── Stats.cpp
│   ├── Trace.cpp
│   └── main.cpp
├── traces/
│   ├── 600.perlbench_s-210B.champsimtrace.xz
│   ├── 605.mcf_s-994B.champsimtrace.xz
│   └── ...
└── tests/
    ├── test_address.cpp
    ├── test_cache.cpp
    └── test_replacement.cpp

The CMakeLists.txt is small. The simulator binary is one C++ target and the unit-test binary is a second target.

Top-level CMakeLists.txt

Plain Text

cmake_minimum_required(VERSION 3.24)
project(cachesim CXX)

set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

# Release with debug info is the default; debug builds add -O0.
if(NOT CMAKE_BUILD_TYPE)
    set(CMAKE_BUILD_TYPE RelWithDebInfo)
endif()

add_compile_options(-Wall -Wextra -Wpedantic -Wshadow
                    -Wconversion -Wnon-virtual-dtor)

include_directories(include)

set(SIM_SOURCES
    src/Address.cpp
    src/Cache.cpp
    src/Hierarchy.cpp
    src/Replacement.cpp
    src/Stats.cpp
    src/Trace.cpp
)

add_executable(cachesim ${SIM_SOURCES} src/main.cpp)

enable_testing()
add_executable(unit_tests ${SIM_SOURCES}
    tests/test_address.cpp
    tests/test_cache.cpp
    tests/test_replacement.cpp
)
add_test(NAME unit_tests COMMAND unit_tests)

03.Address Decomposition

Every cache access begins by splitting the address into three fields. The offset selects a byte within a line. The index selects a set within the cache. The tag is the rest, used to confirm that a hit in the selected set really corresponds to the requested line. The split depends on the cache geometry: a 32 KiB cache with 64-byte lines and 8-way associativity has 64 sets, so the index is 6 bits and the offset is 6 bits. A 1 MiB cache with the same line and 8-way associativity has 2048 sets, so the index is 11 bits.

The Address class encapsulates this decomposition.

Address.hpp: address decomposition

#pragma once
#include <cstdint>

class Address {
public:
    Address(uint64_t pa, uint32_t line_bits, uint32_t set_bits)
        : pa_(pa),
          line_bits_(line_bits),
          set_bits_(set_bits) {}

    uint64_t offset() const {
        return pa_ & ((1ULL << line_bits_) - 1);
    }

    uint64_t index() const {
        return (pa_ >> line_bits_) & ((1ULL << set_bits_) - 1);
    }

    uint64_t tag() const {
        return pa_ >> (line_bits_ + set_bits_);
    }

    uint64_t line_base() const {
        return pa_ & ~((1ULL << line_bits_) - 1);
    }

private:
    uint64_t pa_;
    uint32_t line_bits_;
    uint32_t set_bits_;
};

The class is a value type. It carries the geometry parameters explicitly because the same physical address has different decompositions in different caches (the L1 and the L2 of a hierarchy have different index widths). The line_base() method returns the line-aligned address used as the key in tag lookups.

04.The Cache Class

A single Cache object models one level of the hierarchy (the L1, the L2, or the L3). The Cache owns its sets, each of which owns its ways. The interface is small. A read or write call returns a hit-or-miss result plus, on a miss, the evicted line’s base address (used by the Hierarchy class to handle write-back to the next level and, in inclusive mode, back-invalidation of the inner levels). The Cache reports an address rather than a bare tag because the tag alone does not identify a line outside the cache that produced it, and the Hierarchy does not know that cache’s index width.

Cache.hpp: cache geometry and state

#pragma once
#include <cstdint>
#include <vector>
#include <memory>
#include "Address.hpp"
#include "Replacement.hpp"
#include "Stats.hpp"

enum class AccessType { Read, Write };

struct AccessResult {
    bool hit;
    bool evicted_dirty;
    uint64_t evicted_pa;   // line base of the evicted line
    bool evicted_valid;
};

struct CacheLine {
    bool valid = false;
    bool dirty = false;
    uint64_t tag = 0;
};

class Cache {
public:
    Cache(uint64_t size_bytes,
          uint32_t associativity,
          uint32_t line_bytes,
          std::unique_ptr<Replacement> policy,
          const std::string& name);

    AccessResult access(uint64_t pa, AccessType type);

    // For inclusion enforcement: invalidate a line by tag.
    bool invalidate(uint64_t pa);

    Stats stats() const { return stats_; }
    uint32_t line_bytes() const { return line_bytes_; }

private:
    uint32_t line_bits_;
    uint32_t set_bits_;
    uint64_t num_sets_;
    uint32_t associativity_;
    uint32_t line_bytes_;
    std::vector<std::vector<CacheLine>> sets_;
    std::unique_ptr<Replacement> policy_;
    std::string name_;
    Stats stats_;
};

The implementation file fleshes out the access logic. A read or write decomposes the address, scans the indexed set for a tag match, and either reports a hit (advancing the replacement policy’s state) or selects a victim and reports a miss.

Cache.cpp: the access method

#include "Cache.hpp"
#include <cassert>
#include <bit>

static uint32_t log2_exact(uint64_t n) {
    assert(std::has_single_bit(n));
    return std::countr_zero(n);
}

Cache::Cache(uint64_t size_bytes,
            uint32_t associativity,
            uint32_t line_bytes,
            std::unique_ptr<Replacement> policy,
            const std::string& name)
    : line_bits_(log2_exact(line_bytes)),
      set_bits_(log2_exact(size_bytes
                            / (associativity * line_bytes))),
      num_sets_(size_bytes / (associativity * line_bytes)),
      associativity_(associativity),
      line_bytes_(line_bytes),
      sets_(num_sets_, std::vector<CacheLine>(associativity)),
      policy_(std::move(policy)),
      name_(name) {}

AccessResult Cache::access(uint64_t pa, AccessType type) {
    Address a(pa, line_bits_, set_bits_);
    auto& set = sets_[a.index()];

    // Tag scan.
    for (uint32_t way = 0; way < associativity_; ++way) {
        if (set[way].valid && set[way].tag == a.tag()) {
            policy_->on_hit(a.index(), way);
            if (type == AccessType::Write) set[way].dirty = true;
            stats_.hits++;
            return {true, false, 0, false};
        }
    }

    // Miss: select a victim.
    stats_.misses++;
    uint32_t victim = policy_->select_victim(a.index());

    // Rebuild the victim's line-base address from its tag and
    // the set it sits in. Only this class knows the geometry.
    uint64_t victim_pa =
        (set[victim].tag << (line_bits_ + set_bits_))
        | (a.index() << line_bits_);

    AccessResult result{
        .hit = false,
        .evicted_dirty = set[victim].dirty,
        .evicted_pa = victim_pa,
        .evicted_valid = set[victim].valid,
    };

    // Install the new line.
    set[victim].valid = true;
    set[victim].dirty = (type == AccessType::Write);
    set[victim].tag = a.tag();
    policy_->on_insert(a.index(), victim);
    return result;
}

bool Cache::invalidate(uint64_t pa) {
    Address a(pa, line_bits_, set_bits_);
    auto& set = sets_[a.index()];
    for (uint32_t way = 0; way < associativity_; ++way) {
        if (set[way].valid && set[way].tag == a.tag()) {
            set[way].valid = false;
            set[way].dirty = false;
            return true;
        }
    }
    return false;
}

The access method is the heart of the simulator. It runs in constant time per access (assuming a tag scan over the associativity, which is a small constant). The replacement policy callbacks (on_hit, on_insert, select_victim) are virtual so the same Cache class can be combined with any policy.

05.Replacement Policies

The replacement policy is the most active research area in cache design. The simulator implements five policies through a common interface. The base class abstracts the three callbacks the Cache invokes: on_hit (move-to-MRU or update predictor state), on_insert (initialize the new line’s recency state), and select_victim (return the way index to evict on the next insert).

Replacement.hpp: the policy interface

#pragma once
#include <cstdint>
#include <vector>
class Replacement {
public:
    virtual ~Replacement() = default;
    virtual void on_hit(uint64_t set_idx, uint32_t way) = 0;
    virtual void on_insert(uint64_t set_idx, uint32_t way) = 0;
    virtual uint32_t select_victim(uint64_t set_idx) = 0;
};

LRU stack

The simplest exact policy. Each set holds a list of way indices ordered from MRU to LRU. On a hit, the way is moved to the front. On a miss, the back of the list is the victim, and after insertion the inserted way moves to the front.

Replacement.cpp: LRU policy

class LRU : public Replacement {
public:
    LRU(uint64_t num_sets, uint32_t associativity)
        : assoc_(associativity), order_(num_sets) {
        for (auto& list : order_) {
            list.resize(associativity);
            for (uint32_t i = 0; i < associativity; ++i)
                list[i] = i;
        }
    }
    void on_hit(uint64_t set_idx, uint32_t way) override {
        move_to_front(set_idx, way);
    }
    void on_insert(uint64_t set_idx, uint32_t way) override {
        move_to_front(set_idx, way);
    }
    uint32_t select_victim(uint64_t set_idx) override {
        return order_[set_idx].back();
    }
private:
    void move_to_front(uint64_t set_idx, uint32_t way) {
        auto& list = order_[set_idx];
        auto it = std::find(list.begin(), list.end(), way);
        if (it == list.end()) return;
        list.erase(it);
        list.insert(list.begin(), way);
    }
    uint32_t assoc_;
    std::vector<std::vector<uint32_t>> order_;
};

The cost of LRU is the move-to-front, which is linear in the associativity per access. For the eight-way to sixteen-way caches studied in this project the cost is acceptable. For real silicon, true LRU is rarely implemented above four-way associativity because the recency-state storage and update bandwidth scale poorly.

Tree-PLRU

Tree-PLRU represents the recency order as a binary tree of one-bit decision nodes, one tree per set. The associativity is the number of leaves. On a hit on leaf $k$ , every internal node on the path from the root to $k$ is updated to point away from $k$ . The victim is read off by walking from the root, taking the bit at each node, which yields a leaf opposite the most-recently-used branch at each level.

Replacement.cpp: tree-PLRU

class TreePLRU : public Replacement {
public:
    TreePLRU(uint64_t num_sets, uint32_t associativity)
        : assoc_(associativity),
          tree_(num_sets,
                std::vector<bool>(associativity - 1, false)) {}

    void on_hit(uint64_t set_idx, uint32_t way) override {
        update_path(set_idx, way);
    }
    void on_insert(uint64_t set_idx, uint32_t way) override {
        update_path(set_idx, way);
    }
    uint32_t select_victim(uint64_t set_idx) override {
        uint32_t node = 0;
        uint32_t way = 0;
        uint32_t level_size = 1;
        while (level_size < assoc_) {
            bool bit = tree_[set_idx][node];
            way = (way << 1) | (bit ? 1 : 0);
            node = 2 * node + 1 + (bit ? 1 : 0);
            level_size *= 2;
        }
        return way;
    }
private:
    void update_path(uint64_t set_idx, uint32_t way) {
        uint32_t node = 0;
        uint32_t level_size = assoc_;
        while (level_size > 1) {
            level_size /= 2;
            bool branch_bit = (way / level_size) & 1;
            tree_[set_idx][node] = !branch_bit;
            node = 2 * node + 1 + branch_bit;
        }
    }
    uint32_t assoc_;
    std::vector<std::vector<bool>> tree_;
};

Tree-PLRU costs $a - 1$ bits per set, one for each internal node of the tree, and both the update and the victim walk touch only $\log_2 a$ of those bits. The approximation is excellent on high-locality workloads and starts to diverge from true LRU on scan-heavy streams, the well-known limitation of approximate-LRU policies.

RRIP

The RRIP family represents each line’s predicted re-reference interval as a small integer (typically 2 bits, encoding values 0 through 3). On a hit, the value is set to 0 (near re-reference). On a miss, the new line is inserted with the "long" value 2, leaving 3 reserved for the distant prediction. BRRIP inserts at 3 most of the time and at 2 with a small probability. The victim is the line with the highest RRPV. On ties, the leftmost is chosen, and if no line has the maximum value, every RRPV in the set is incremented and the search repeats.

Replacement.cpp: SRRIP

class SRRIP : public Replacement {
public:
    SRRIP(uint64_t num_sets, uint32_t associativity)
        : assoc_(associativity),
          rrpv_(num_sets,
                std::vector<uint8_t>(associativity, 3)) {}

    void on_hit(uint64_t set_idx, uint32_t way) override {
        rrpv_[set_idx][way] = 0;
    }
    void on_insert(uint64_t set_idx, uint32_t way) override {
        rrpv_[set_idx][way] = 2; // "long" but not "max"
    }
    uint32_t select_victim(uint64_t set_idx) override {
        auto& vec = rrpv_[set_idx];
        while (true) {
            for (uint32_t w = 0; w < assoc_; ++w)
                if (vec[w] == 3) return w;
            for (uint32_t w = 0; w < assoc_; ++w)
                if (vec[w] < 3) vec[w]++;
        }
    }
private:
    uint32_t assoc_;
    std::vector<std::vector<uint8_t>> rrpv_;
};

The RRIP policy needs only two bits per line, which is much smaller than a true-LRU representation at high associativity. The performance is reliably ahead of LRU on scan-heavy workloads and is the family of policies that the modern ARM and Intel LLCs descend from, as noted in Chapter 46.

Hawkeye (sketch)

Hawkeye, by Jain and Lin, adds a predictor that classifies each PC’s allocation behavior as "OPT-friendly" or "OPT-averse." On insertion, a line tagged with an averse PC enters at high RRPV (short retention), while a friendly PC enters at low RRPV (long retention). The predictor is trained online by replaying recent history against the Belady-OPT algorithm and observing which insertions would have been kept by OPT.

A correct Hawkeye implementation is substantially more code than SRRIP. The simulator ships a working version under Replacement.cpp (around 150 lines) that mirrors the ISCA 2016 paper’s description. The interface is identical to LRU and SRRIP. A user selecting Hawkeye on the command line gets the same callback signatures, with the policy doing its training internally.

Mockingjay (sketch)

Mockingjay, by Shah, Jain, and Lin (HPCA 2022), generalizes Hawkeye by replacing the binary classification with a quantitative time-to-next-reference estimate. Each allocation records the cycle at which it occurred, and the predictor estimates the distance to the next access. Insertions then use that estimate to set RRPV.

The implementation in this simulator (also under Replacement.cpp, around 180 lines) follows the HPCA 2022 paper’s algorithm. As with Hawkeye, the user selects it on the command line and the simulator instantiates the policy through the same interface.

06.The Hierarchy: Composing Caches

A real machine has more than one cache. The Hierarchy class chains the L1, L2, and L3 in sequence. On a miss at one level, the access cascades to the next. On a victim eviction at one level, the inclusion policy decides what happens at the levels above.

Hierarchy.hpp: hierarchy composition

#pragma once
#include "Cache.hpp"

enum class Inclusion { Inclusive, Exclusive, NINE };

class Hierarchy {
public:
    Hierarchy(std::vector<std::unique_ptr<Cache>>&& caches,
              Inclusion policy);

    void access(uint64_t pa, AccessType type);

    const std::vector<std::unique_ptr<Cache>>&
    caches() const { return caches_; }

private:
    std::vector<std::unique_ptr<Cache>> caches_;
    Inclusion policy_;

    void handle_eviction_inclusion(size_t level,
                                  uint64_t evicted_pa);
};

Hierarchy.cpp: cascading access and inclusion

#include "Hierarchy.hpp"

void Hierarchy::access(uint64_t pa, AccessType type) {
    for (size_t level = 0; level < caches_.size(); ++level) {
        AccessResult r = caches_[level]->access(pa, type);
        if (r.hit) {
            // Hit at this level. Done. Higher levels see no
            // further traffic for this access.
            return;
        }
        // Miss at this level. Handle eviction per inclusion
        // policy, then continue to the next level.
        if (r.evicted_valid && policy_ == Inclusion::Inclusive
            && level > 0) {
            // The line just evicted at this level, which is the
            // outer cache with respect to everything closer to
            // the core, must back-invalidate the same line at
            // levels 0 through level-1 (the inner caches).
            //
            // Note: in Inclusive mode, the OUTER cache evicting
            // a line forces the INNER cache to invalidate. The
            // direction is "outward eviction triggers inward
            // invalidation," not the other way.
            handle_eviction_inclusion(level, r.evicted_pa);
        }
        // Continue to next level on miss at this level.
    }
    // Miss all the way to DRAM. No further bookkeeping for the
    // simulator. AMAT is computed by the Stats class from the
    // hit/miss counts.
}

The inclusion handling deserves a closer look. In strictly inclusive mode, an outward eviction forces an inward invalidation. In exclusive mode, an outward eviction installs the line in the next-lower level, and an inner-level hit deallocates the line from the outer level. In NINE mode, the two levels are decoupled and an eviction at one does not affect the other.

For brevity the snippet above shows only the inclusive case. The full source (around 90 additional lines) handles the exclusive and NINE cases as well. The trade-offs between the three are documented in Chapter 39 and observed in real designs in Chapter 46.

07.Trace Replay and Statistics

The simulator reads traces from the ChampSim trace format, which is the de facto standard for cache and prefetcher research. Each trace record is exactly 64 bytes and encodes the instruction pointer, the type (load, store, branch, other), the target address, and a small set of dependency flags. The simulator ignores the non-memory records and replays the loads and stores in order.

Trace.hpp: trace record and reader

#pragma once
#include <cstdint>
#include <string>
#include <fstream>

struct TraceRecord {
    uint64_t ip;
    uint8_t  is_branch;
    uint8_t  branch_taken;
    uint8_t  destination_registers[2];
    uint8_t  source_registers[4];
    uint64_t destination_memory[2];
    uint64_t source_memory[4];
};

class TraceReader {
public:
    explicit TraceReader(const std::string& path);
    bool next(TraceRecord& rec);
private:
    std::ifstream file_;
};

The main loop is straightforward. For each record, every memory source address is a load and every memory destination address is a store. Each access goes through the Hierarchy. After the trace runs out, the simulator prints per-level statistics and the overall AMAT.

main.cpp: trace replay

#include "Cache.hpp"
#include "Hierarchy.hpp"
#include "Replacement.hpp"
#include "Trace.hpp"
#include <iostream>

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "usage: cachesim <trace> [config.txt]\n";
        return 1;
    }

    // Build the hierarchy. In production this is parsed from
    // a config file. Here we hard-code a typical desktop
    // hierarchy: 32 KiB / 8-way / LRU L1, 1 MiB / 8-way / RRIP
    // L2, 16 MiB / 16-way / Hawkeye L3, with inclusion = NINE.
    std::vector<std::unique_ptr<Cache>> caches;
    caches.emplace_back(std::make_unique<Cache>(
        32 * 1024, 8, 64,
        std::make_unique<LRU>(64, 8), "L1"));
    caches.emplace_back(std::make_unique<Cache>(
        1024 * 1024, 8, 64,
        std::make_unique<SRRIP>(2048, 8), "L2"));
    caches.emplace_back(std::make_unique<Cache>(
        16 * 1024 * 1024, 16, 64,
        std::make_unique<Hawkeye>(16384, 16), "L3"));

    Hierarchy h(std::move(caches), Inclusion::NINE);

    TraceReader reader(argv[1]);
    TraceRecord rec;
    uint64_t accesses = 0;
    while (reader.next(rec)) {
        for (auto a : rec.source_memory)
            if (a) { h.access(a, AccessType::Read); accesses++; }
        for (auto a : rec.destination_memory)
            if (a) { h.access(a, AccessType::Write); accesses++; }
    }

    // Report.
    std::cout << "Total accesses: " << accesses << "\n";
    for (const auto& c : h.caches()) {
        auto s = c->stats();
        std::cout << "  hits=" << s.hits
                  << "  misses=" << s.misses
                  << "  hit_rate=" << double(s.hits)
                                    / (s.hits + s.misses)
                  << "\n";
    }
    return 0;
}

The Stats class records the per-cache hit and miss counts. The AMAT is computed by the post-run summary as $\mathrm{AMAT} = \sum_{i} (1 - \mathrm{HR}_{< i})\, \mathrm{HR}_i\, t_i + (1 - \mathrm{HR}_{\le N})\, t_{\mathrm{DRAM}},$ where $\mathrm{HR}_i$ is the hit rate at level $i$ , $\mathrm{HR}_{< i}$ is the cumulative hit rate above level $i$ , and $t_i$ is the user-supplied access latency for that level. The latency table is part of the config file. The simulator ships a default that mirrors the Sapphire Rapids defaults from Chapter 46.

08.Running on SPEC Traces

The ChampSim trace repository hosts public SPEC CPU 2017 traces collected by the simulator’s maintainers. The traces are distributed as .champsimtrace.xz files, each of which decompresses to tens of gigabytes, since a billion 64-byte records is roughly 64 GB. The simulator reads the compressed file directly through a small xz-decompressor wrapper, so the on-disk footprint stays small.

Building and running on the perlbench trace

Plain Text

mkdir build && cd build
cmake -GNinja ..
ninja
# A typical run, the trace size determines wall time. The default
# trace is approximately 1 billion records.
./cachesim ../traces/600.perlbench_s-210B.champsimtrace.xz

A representative output (single-threaded, on a 2025-era laptop) runs in about 90 seconds for a 1-billion-record trace and prints a summary like:

Sample output

Plain Text

Total accesses: 423,118,201
  L1: hits=415,892,143 misses=7,226,058 hit_rate=0.9829
  L2: hits=6,891,022 misses=335,036 hit_rate=0.9536
  L3: hits=287,901 misses=47,135 hit_rate=0.8593
AMAT (L1=5 L2=15 L3=40 DRAM=180): 5.206 cycles

The AMAT computation uses the latencies given in the config or in the chapter’s default table. A reader can rerun the same trace with different replacement policies (LRU at L3, then RRIP, then Hawkeye, then Mockingjay) and observe the L3 hit rate shifting by a few percentage points between policies, with Mockingjay typically winning on the SPEC-2017-with-large-working- set traces (mcf, cactuBSSN, lbm) and LRU and RRIP being closer to each other on small-working-set traces (povray, wrf).

09.Worked Examples

Example: Validating the address decomposition

Write a unit test that constructs an Address for the value 0xDEAD_BEEF_CAFE_1234 with a 64-byte line size and a cache geometry of 32 KiB and 8-way associativity (so 64 sets, 6-bit index).

The expected fields:

offset() == 0x34
index() == (0xDEAD_BEEF_CAFE_1234 >> 6) & 0x3F = the low six bits of 0x37AB_6FBB_F2BF_848 = 0x08 = 8
tag() == 0xDEAD_BEEF_CAFE_1234 >> 12 = 0x000D_EADB_EEFC_AFE1
line_base() == 0xDEAD_BEEF_CAFE_1200

A second address 0xDEAD_BEEF_CAFE_1238 should have the same tag and the same index (it sits 56 bytes into the same line, whose base is 0xDEAD_BEEF_CAFE_1200) but a different offset, 0x38. A third address 0xDEAD_BEEF_CAFE_2234 should have the same tag in a direct-mapped cache of this size but a different index there, since the 9-bit direct-mapped index separates the two into lines 0x48 and 0x88. In the 8-way 64-set cache the index is only six bits, so 0x48 & 0x3F and 0x88 & 0x3F are both 8, the two addresses land in the same set, and they collide there with different tags. Walk through which mapping behavior the direct-mapped versus the set-associative case produces.

Example: LRU on a small example

A 4-way set-associative cache, one set, starts empty. The following accesses arrive in order (lines A, B, C, D, A, E, B):

A: miss, install A. Order: A
B: miss, install B. Order: B, A
C: miss, install C. Order: C, B, A
D: miss, install D. Order: D, C, B, A
A: hit, move A to front. Order: A, D, C, B
E: miss, set is full, evict B (LRU). Order: E, A, D, C
B: miss, evict C. Order: B, E, A, D

The lists are written MRU first and LRU last, matching the convention the LRU class uses, so the victim is always the rightmost entry.

Total: 6 misses, 1 hit. Now repeat the same sequence on SRRIP. The starting RRPV for every line is 3 (cold cache). On each miss, install with RRPV 2 (long). On each hit, set RRPV to 0. On a victim search, find an RRPV-3 line. If none, age every line and re-search.

Walk through the same sequence on SRRIP and confirm the sequence is identical (since the cache is too small for the RRIP family to differ from LRU on this short trace). Repeat with a trace long enough that scan behavior matters and observe SRRIP outperforming LRU.

Example: The inclusion-policy contrast

Build a hierarchy with a 4-line L1 and an 8-line L2 (one set each, fully associative). Configure inclusive, exclusive, and NINE in three runs.

The access sequence is: A, B, C, D, E, F, G, H, A, B, C, D.

In inclusive mode, after the first eight accesses the L2 holds A through H. The next access to A is an L1 miss, L2 hit. Note that since L1 held A originally (assuming it was promoted on the first access), an L2 eviction of A in a strict-inclusive mode would force the L1 to invalidate too. Walk through the exact sequence of evictions for each policy and tabulate the final L1 and L2 contents.

In exclusive mode, every L2 line is one that was once in L1 but evicted from L1. After eight accesses, L1 holds the most recent four (E, F, G, H) and L2 holds the previous four (A, B, C, D). The reaccess to A finds A in L2 not L1, swaps it back into L1, and demotes the L1 victim to L2.

In NINE mode, the two caches are independent. After eight accesses, L1 holds the most recent four, L2 holds whatever it held without coordination with L1.

For each mode, count the total number of "from-DRAM" misses across the twelve-access sequence.

10.Exercises

Exercises

Build and test. Build the cachesim binary with the default L1/L2/L3 hierarchy. Run the test suite (ninja test) and confirm all unit tests pass. Report the wall-clock build time on your machine and the pass count of the test suite.
Address-decomposition unit tests. Extend tests/test_address.cpp with at least ten new test cases covering corner conditions: address 0, address all ones, line-aligned addresses, addresses one byte before and one byte after a line boundary, and several random samples. Verify each by hand and confirm the unit test catches a bug if you intentionally swap the index and offset shift constants.
Implement exact LRU as a linked list. Tree-PLRU is an approximation of LRU. Implement an alternative exact-LRU policy as a linked-list-of-way-indices, and compare its memory footprint and access cost to the recency-list LRU already in the simulator. Run both on mcf and verify the hit/miss counts agree to the bit.
Add LFU. The simulator ships LRU, tree-PLRU, SRRIP, Hawkeye, and Mockingjay. Implement Least-Frequently-Used (LFU) as a sixth policy: count the number of hits each way has received, evict the way with the lowest count. Compare LFU to the other five on a povray trace and a mcf trace.
Adaptive RRIP. The shipped SRRIP uses a fixed "long" insertion RRPV. DRRIP (Dynamic RRIP) uses a set-dueling approach to choose between SRRIP and BRRIP (probabilistic-distant insertion) per workload. Implement DRRIP and observe its win over SRRIP on the SPEC traces.
Per-set hit-rate distribution. Add per-set statistics to the Stats class. After a run, print the hit rate of each set. Plot the distribution. On a typical SPEC trace, the distribution is highly non-uniform: some sets are hammered, others almost untouched. The non-uniformity is a known phenomenon (set-imbalance) and the cause of conflict misses on small-N-set caches.
Skewed associativity. Implement a skewed-associative cache (Seznec 1993): the index function uses different bits for different ways, breaking the correlation between addresses and sets. Test on mcf and report the change in miss rate. The skewed configuration typically improves the hit rate on hash-collisions-prone workloads.
Compressed line storage. Modern cache designs sometimes store compressed lines to fit more effective lines per set. Build a simulator extension that models 2:1 compression of zero-dominated lines (lines whose content is mostly zero bytes). The trace format does not carry line content, so you will need to simulate "compressible" with a probabilistic flag.
Inclusion-policy stress test. The simulator handles inclusive, exclusive, and NINE through the Hierarchy class. Construct a 6-access trace that produces materially different L1 and L2 outcomes in the three modes. Run it. Tabulate the final state of each cache for each inclusion policy.
AMAT sensitivity analysis. Run a single trace through the simulator while sweeping the L1 size from 16 KiB to 256 KiB in factor-of-two steps. Plot the resulting AMAT. Identify the knee of the curve.
Replacement-policy sweep on SPEC. Run all five built-in replacement policies on five SPEC traces (perlbench, mcf, cactuBSSN, povray, lbm). Tabulate the L3 hit rate for every (trace, policy) pair. Compute the geometric mean per policy. Compare to the published ISCA 2016 Hawkeye and HPCA 2022 Mockingjay results.
Validate against a known result. Pick one of the SPEC traces and one replacement policy. Compare your simulator’s L3 hit rate to the value reported in the Mockingjay paper (HPCA 2022, Table 2) for the same trace. Account for differences in hierarchy parameters, then attempt to reproduce the paper’s number to within one percentage point. If you cannot, identify the configuration choice that explains the gap.
Pre-write the next chapter’s lab. Chapter 48 steps up to ChampSim, DRAMsim3, and gem5 for cycle-accurate simulation. Before that, study the ChampSim trace format your simulator already consumes. Extract the format’s exact byte layout from ChampSim’s source. Write a short note describing what cycle-level information the trace carries and what it does not.

Book mode

	clang++ --version # Apple clang or Homebrew clang 18.x+
	cmake --version # CMake 3.28 or later
	xz --version

	# Compiler, build system, decompression
	sudo pacman -S clang gcc cmake xz

	# Optional: ninja, faster builds than make
	sudo pacman -S ninja

	sudo apt update
	sudo apt install build-essential cmake clang \
	xz-utils ninja-build

	# Inside the ArchWSL terminal:
	sudo pacman -S clang gcc cmake xz ninja

	cachesim/
	├── CMakeLists.txt
	├── include/
	│ ├── Address.hpp
	│ ├── Cache.hpp
	│ ├── Hierarchy.hpp
	│ ├── Replacement.hpp
	│ ├── Stats.hpp
	│ └── Trace.hpp
	├── src/
	│ ├── Address.cpp
	│ ├── Cache.cpp
	│ ├── Hierarchy.cpp
	│ ├── Replacement.cpp
	│ ├── Stats.cpp
	│ ├── Trace.cpp
	│ └── main.cpp
	├── traces/
	│ ├── 600.perlbench_s-210B.champsimtrace.xz
	│ ├── 605.mcf_s-994B.champsimtrace.xz
	│ └── ...
	└── tests/
	├── test_address.cpp
	├── test_cache.cpp
	└── test_replacement.cpp

	#pragma once
	#include <cstdint>
	#include <vector>

	class Replacement {
	public:
	virtual ~Replacement() = default;
	virtual void on_hit(uint64_t set_idx, uint32_t way) = 0;
	virtual void on_insert(uint64_t set_idx, uint32_t way) = 0;
	virtual uint32_t select_victim(uint64_t set_idx) = 0;
	};

	mkdir build && cd build
	cmake -GNinja ..
	ninja

	# A typical run, the trace size determines wall time. The default
	# trace is approximately 1 billion records.
	./cachesim ../traces/600.perlbench_s-210B.champsimtrace.xz

	Total accesses: 423,118,201
	L1: hits=415,892,143 misses=7,226,058 hit_rate=0.9829
	L2: hits=6,891,022 misses=335,036 hit_rate=0.9536
	L3: hits=287,901 misses=47,135 hit_rate=0.8593
	AMAT (L1=5 L2=15 L3=40 DRAM=180): 5.206 cycles