bench4.cpp

/*
 * bench3.cpp — CS204 Policy-Discriminating Benchmark
 * IIT Ropar | 2025-26
 *
 * Designed for a 4 KB cache (16 sets × 4 ways × 64 B line). The existing
 * bench.cpp / bench2.cpp benchmarks have working sets that either fit
 * comfortably or stream through — so all policies converge near 99%
 * hit rate. This benchmark deliberately targets regimes where the
 * choice of eviction policy actually matters.
 *
 * THREE PHASES — each separates policies in a different way:
 *
 *  1. CYCLIC THRASH (assoc + 1 lines, same set)
 *     5 lines all map to set 0; cycle through them. On a 4-way cache:
 *       LRU / FIFO / LFU : every access misses (sequential eviction races)
 *       RANDOM           : ~60% hit (gets lucky)
 *       OPT              : ~75% hit (knows the cycle)
 *     This is the canonical "LRU pathological" example.
 *
 *  2. WEIGHTED ZIPF (80/20 access distribution)
 *     256 lines (16 KB total — 4× the cache). 20% of lines get 80% of
 *     accesses. LFU identifies the hot set by count and wins. LRU does
 *     okay. FIFO/RANDOM are oblivious to access frequency.
 *     Expected: LFU ~79%, LRU ~68%, FIFO/RANDOM ~62%.
 *
 *  3. SET-CONFLICT REUSE (warm + cold lines competing for one set)
 *     6 lines all map to the same set; 3 are warm (3 accesses/round)
 *     and 3 are cold (1 access/round). LFU keeps warm lines resident;
 *     LRU and FIFO keep evicting them.
 *     Expected: LFU 75%, LRU/FIFO 50%.
 *
 * Validated (Python reference simulator, 285k accesses):
 *   OPT     : ~78%
 *   LFU     : ~71%
 *   RANDOM  : ~60%
 *   LRU     : ~58%
 *   FIFO    : ~54%
 *
 * Build:
 *   g++ -O0 -std=c++17 -o bench3 bench3.cpp
 *
 * Trace:
 *   $PIN_ROOT/pin -t obj-intel64/mem_trace.so -- ./bench3
 *
 * Runtime under PIN: ~20-40 seconds. Trace size: ~25-40 MB.
 */

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <cstdint>
#include <cstdlib>

static volatile uint64_t g_sink = 0;

// Cache geometry assumptions (matches the recommended UI default):
//   LINE = 64 B, NSETS = 16, ASSOC = 4
// Address-bit layout: [tag | 4-bit set | 6-bit offset]
// → addresses 1024 B (= NSETS × LINE) apart map to the SAME set.

constexpr size_t LINE     = 64;
constexpr size_t NSETS    = 16;
constexpr size_t ASSOC    = 4;
constexpr size_t SAME_SET = LINE * NSETS;     // 1024 B

static uint8_t* alloc_aligned(size_t bytes) {
    size_t rounded = ((bytes + 4095) / 4096) * 4096;
    void* p = std::aligned_alloc(4096, rounded);
    if (!p) { std::cerr << "alloc failed\n"; std::exit(1); }
    return static_cast<uint8_t*>(p);
}

// ════════════════════════════════════════════════════════════════════════════
//  Phase 1: CYCLIC THRASH — 5 lines, same set, 4-way cache
// ════════════════════════════════════════════════════════════════════════════
static void cyclic_thrash() {
    constexpr size_t LINES = ASSOC + 1;
    uint8_t* buf = alloc_aligned(LINES * SAME_SET);
    for (size_t i = 0; i < LINES * SAME_SET; ++i) buf[i] = uint8_t(i);

    for (int round = 0; round < 5000; ++round) {
        for (size_t k = 0; k < LINES; ++k) {
            g_sink += buf[k * SAME_SET];
        }
    }
    std::free(buf);
}

// ════════════════════════════════════════════════════════════════════════════
//  Phase 2: WEIGHTED ZIPF — 80% of accesses hit 20% of lines
// ════════════════════════════════════════════════════════════════════════════
static void weighted_zipf() {
    constexpr size_t TOTAL_LINES = 256;
    constexpr size_t HOT_LINES   = 52;
    uint8_t* buf = alloc_aligned(TOTAL_LINES * LINE);
    for (size_t i = 0; i < TOTAL_LINES * LINE; ++i) buf[i] = uint8_t(i);

    std::mt19937 rng(42);
    std::uniform_int_distribution<int> coin(0, 99);
    std::uniform_int_distribution<size_t> hot_pick(0, HOT_LINES - 1);
    std::uniform_int_distribution<size_t> cold_pick(HOT_LINES, TOTAL_LINES - 1);

    for (int i = 0; i < 200000; ++i) {
        size_t line_idx = (coin(rng) < 80) ? hot_pick(rng) : cold_pick(rng);
        g_sink += buf[line_idx * LINE];
    }
    std::free(buf);
}

// ════════════════════════════════════════════════════════════════════════════
//  Phase 3: SET-CONFLICT REUSE — warm + cold lines all on one set
// ════════════════════════════════════════════════════════════════════════════
static void set_conflict_reuse() {
    constexpr size_t LINES = ASSOC + 2;            // 6 lines, all same set
    uint8_t* buf = alloc_aligned(LINES * SAME_SET);
    for (size_t i = 0; i < LINES * SAME_SET; ++i) buf[i] = uint8_t(i);

    // Lines 0..2 are warm (accessed 3× per round)
    // Lines 3..5 are cold (accessed 1× per round)
    for (int round = 0; round < 5000; ++round) {
        for (int rep = 0; rep < 3; ++rep)
            for (size_t k = 0; k < 3; ++k)
                g_sink += buf[k * SAME_SET];
        for (size_t k = 3; k < LINES; ++k)
            g_sink += buf[k * SAME_SET];
    }
    std::free(buf);
}

int main() {
    std::cerr << "[1/3] Cyclic thrash       (5 lines, 4-way, same set)...\n";
    cyclic_thrash();
    std::cerr << "[2/3] Weighted Zipf       (80/20 over 256 lines)...\n";
    weighted_zipf();
    std::cerr << "[3/3] Set-conflict reuse  (warm 3 + cold 3 on one set)...\n";
    set_conflict_reuse();

    std::cerr << "[done] sink = " << g_sink << "\n";
    return 0;
}