cache_sim.cpp

//cache sim
#include <bits/stdc++.h>

using Addr  = uint64_t;
using Trace = std::vector<Addr>;

enum class Policy { FIFO, LRU, RANDOM, BELADY, SALRU };

const char* policy_name(Policy p) {
    switch (p) {
        case Policy::FIFO:   return "FIFO";
        case Policy::LRU:    return "LRU";
        case Policy::RANDOM: return "Random";
        case Policy::BELADY: return "Belady";
        case Policy::SALRU:  return "SA-LRU";
    }
    return "?";
}

// Cache
class Cache {
public:
    uint64_t hits   = 0;
    uint64_t misses = 0;

private:
    size_t assoc; // ways per set (e.g. 4)
    size_t num_sets; // total sets
    size_t block_size; // bytes per block (e.g. 64)
    Policy policy;

    // The entire cache is a 2D array of tags.
    std::vector<std::vector<uint64_t>> sets;

    // SA-LRU: store actual address for each cached tag
    // so we can check if it belongs to a stride pattern
    std::vector<std::unordered_map<uint64_t, Addr>> tag_to_addr;

    // SA-LRU: small window of recent addresses for stride detection
    std::deque<Addr> recent;

    // Belady: precomputed next-use table
    // future[set_idx][tag] = sorted queue of future ticks
    std::vector<std::unordered_map<uint64_t, std::deque<size_t>>> future;

    size_t   tick = 0;
    std::mt19937 rng{42};

public:
    Cache(size_t kb, size_t blk_b, size_t ways, Policy pol, const Trace* tr = nullptr)
        : assoc(ways), block_size(blk_b), policy(pol)
    {
        size_t total_lines = (kb * 1024) / blk_b;
        num_sets = total_lines / ways;
        sets.resize(num_sets);

        if (pol == Policy::SALRU)
            tag_to_addr.resize(num_sets);

        if (pol == Policy::BELADY && tr)
            build_future_table(*tr);
    }

    // access() — call for every address in the trace
    bool access(Addr addr) {
        uint64_t block   = addr / block_size;
        size_t   set_idx = block % num_sets;
        uint64_t tag     = block / num_sets;

        bool hit = false;
        switch (policy) {
            case Policy::FIFO:   hit = do_fifo  (set_idx, tag);        break;
            case Policy::LRU:    hit = do_lru   (set_idx, tag);        break;
            case Policy::RANDOM: hit = do_random(set_idx, tag);        break;
            case Policy::BELADY: hit = do_belady(set_idx, tag);        break;
            case Policy::SALRU:  hit = do_salru (set_idx, tag, addr);  break;
        }

        hit ? hits++ : misses++;
        tick++;
        recent.push_back(addr);
        if (recent.size() > 8) recent.pop_front();
        return hit;
    }

    double hit_rate()  const { return (hits+misses) ? double(hits)/(hits+misses) : 0; }
    double miss_rate() const { return 1.0 - hit_rate(); }

private:

    bool in_cache(size_t si, uint64_t tag) {
        auto& s = sets[si];
        return std::find(s.begin(), s.end(), tag) != s.end();
    }

    void evict_oldest(size_t si) {
        sets[si].erase(sets[si].begin());
    }

    // FIFO 
    bool do_fifo(size_t si, uint64_t tag) {
        if (in_cache(si, tag)) return true;
        if (sets[si].size() >= assoc) evict_oldest(si);
        sets[si].push_back(tag);
        return false;
    }

    //LRU
    bool do_lru(size_t si, uint64_t tag) {
        auto& s = sets[si];
        auto  it = std::find(s.begin(), s.end(), tag);
        if (it != s.end()) {
            s.erase(it);
            s.push_back(tag);   // move to MRU
            return true;
        }
        if (s.size() >= assoc) evict_oldest(si);
        s.push_back(tag);
        return false;
    }

    //RANDOM 
    bool do_random(size_t si, uint64_t tag) {
        if (in_cache(si, tag)) return true;
        if (sets[si].size() >= assoc) {
            std::uniform_int_distribution<size_t> dist(0, sets[si].size() - 1);
            size_t idx = dist(rng);
            sets[si].erase(sets[si].begin() + idx);
        }
        sets[si].push_back(tag);
        return false;
    }

    //BELADY
    bool do_belady(size_t si, uint64_t tag) {
        if (in_cache(si, tag)) return true;
        if (sets[si].size() >= assoc) {
            uint64_t victim     = sets[si][0];
            size_t   worst_next = 0;
            for (uint64_t t : sets[si]) {
                size_t nu = next_use(si, t);
                if (nu > worst_next) { worst_next = nu; victim = t; }
            }
            auto it = std::find(sets[si].begin(), sets[si].end(), victim);
            sets[si].erase(it);
        }
        sets[si].push_back(tag);
        return false;
    }

    size_t next_use(size_t si, uint64_t tag) {
        auto& q = future[si][tag];
        while (!q.empty() && q.front() <= tick) q.pop_front();
        return q.empty() ? SIZE_MAX : q.front();
    }

    void build_future_table(const Trace& tr) {
        future.resize(num_sets);
        for (size_t i = 0; i < tr.size(); i++) {
            uint64_t block = tr[i] / block_size;
            size_t   si    = block % num_sets;
            uint64_t tag   = block / num_sets;
            future[si][tag].push_back(i);
        }
    }

    // SA-LRU 
    bool do_salru(size_t si, uint64_t tag, Addr addr) {
        auto& s    = sets[si];
        auto& amap = tag_to_addr[si];

        // HIT
        auto it = std::find(s.begin(), s.end(), tag);
        if (it != s.end()) {
            s.erase(it);
            s.push_back(tag);
            return true;
        }

        // MISS
        if (s.size() >= assoc) {
            int64_t stride = detect_stride();
            if (stride != 0) {
                int protected_count = 0;
                int max_protect = (int)assoc / 2;
                for (int i = 0; i < (int)s.size() && protected_count < max_protect; i++) {
                    uint64_t ct    = s[i];
                    Addr     caddr = amap.count(ct) ? amap[ct] : 0;
                    int64_t  diff  = (int64_t)addr - (int64_t)caddr;
                    if (caddr != 0 && diff != 0 && diff % stride == 0) {
                        s.erase(s.begin() + i);
                        s.push_back(ct);    // protect: move to MRU
                        i--;
                        protected_count++;
                    }
                }
            }
            uint64_t victim = s.front();
            amap.erase(victim);
            s.erase(s.begin());
        }

        s.push_back(tag);
        amap[tag] = addr;
        return false;
    }

    int64_t detect_stride() {
        if (recent.size() < 4) return 0;
        size_t  n  = recent.size();
        int64_t d1 = (int64_t)recent[n-1] - (int64_t)recent[n-2];
        int64_t d2 = (int64_t)recent[n-2] - (int64_t)recent[n-3];
        int64_t d3 = (int64_t)recent[n-3] - (int64_t)recent[n-4];
        return (d1 == d2 && d2 == d3 && d1 != 0) ? d1 : 0;
    }
};

// Trace loader
Trace load_trace(const std::string& path, size_t maxn = 0) {
    Trace tr;
    std::ifstream f(path);
    if (!f.is_open()) { std::cerr << "Cannot open: " << path << "\n"; exit(1); }
    std::string line;
    while (std::getline(f, line)) {
        if (line.empty() || line[0] == '#') continue;
        char rw; Addr addr;
        std::istringstream ss(line);
        ss >> rw >> std::hex >> addr;
        if (!ss.fail()) tr.push_back(addr);
        if (maxn && tr.size() >= maxn) break;
    }
    return tr;
}

// Synthetic trace
Trace generate_synthetic(size_t n = 200000) {
    Trace tr; tr.reserve(n);
    std::mt19937 rng(42);
    std::uniform_int_distribution<Addr> rand_a(0, 0xFFFF);
    Addr base = 0x1000;
    while (tr.size() < n) {
        for (int i = 0; i < 16 && tr.size() < n; i++) tr.push_back(base + i*4);    // stride-4
        for (int i = 0; i < 8  && tr.size() < n; i++) tr.push_back(base + i*32);   // stride-32
        Addr hot[4] = {base, base+4, base+8, base+12};
        for (int r = 0; r < 4 && tr.size() < n; r++)
            for (Addr a : hot) tr.push_back(a);                                      // hot set
        for (int i = 0; i < 4  && tr.size() < n; i++) tr.push_back(rand_a(rng)*4); // random
        base += 256;
    }
    tr.resize(n); return tr;
}

// Stride analysis
void print_stride_analysis(const Trace& tr) {
    std::unordered_map<int64_t, int> cnt;
    size_t lim = std::min(tr.size(), size_t(50000));
    for (size_t i = 1; i < lim; i++) {
        int64_t s = (int64_t)tr[i] - (int64_t)tr[i-1];
        if (s != 0) cnt[s]++;
    }
    std::vector<std::pair<int64_t,int>> v(cnt.begin(), cnt.end());
    std::sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.second > b.second; });
    printf("\nTop 10 Strides:\n  %-14s %s\n", "Stride(bytes)", "Count");
    for (int i = 0; i < 10 && i < (int)v.size(); i++)
        printf("  %-14lld %d\n", (long long)v[i].first, v[i].second);
}

// Reuse distance analysis
void print_reuse_analysis(const Trace& tr) {
    std::unordered_map<Addr, size_t> last;
    double sum = 0; size_t count = 0;
    size_t lim = std::min(tr.size(), size_t(10000));
    for (size_t i = 0; i < lim; i++) {
        if (last.count(tr[i])) { sum += i - last[tr[i]]; count++; }
        last[tr[i]] = i;
    }
    printf("\nReuse Distance Analysis:\n");
    printf("  Unique addresses : %zu\n", last.size());
    printf("  Reuse events     : %zu\n", count);
    if (count) printf("  Avg reuse dist   : %.1f accesses\n", sum / count);
}

// ============================================================
// Run all 5 policies
// ============================================================
struct Result { Policy p; size_t kb; double hit; double miss; };

std::vector<Result> run_all(const Trace& tr, size_t kb, size_t blk, size_t ways) {
    std::vector<Result> out;
    for (Policy pol : { Policy::FIFO, Policy::LRU, Policy::RANDOM,
                        Policy::BELADY, Policy::SALRU }) {
        Cache c(kb, blk, ways, pol, pol == Policy::BELADY ? &tr : nullptr);
        for (Addr a : tr) c.access(a);
        Result r;
        r.p = pol; r.kb = kb; r.hit = c.hit_rate(); r.miss = c.miss_rate();
        out.push_back(r);
    }
    return out;
}

// Write CSVs
void write_csvs(const std::vector<Result>& fixed,
                const std::vector<std::vector<Result>>& sweep) {
    {
        std::ofstream f("results_fixed.csv");
        f << "policy,hit_rate,miss_rate\n";
        for (auto& r : fixed)
            f << policy_name(r.p) << ","
              << std::fixed << std::setprecision(4)
              << r.hit << "," << r.miss << "\n";
    }
    {
        std::ofstream f("results.csv");
        f << "policy,cache_kb,hit_rate,miss_rate\n";
        for (auto& run : sweep)
            for (auto& r : run)
                f << policy_name(r.p) << "," << r.kb << ","
                  << std::fixed << std::setprecision(4)
                  << r.hit << "," << r.miss << "\n";
    }
    printf("\nCSV files written: results_fixed.csv  results.csv\n");
}

// Main
int main(int argc, char* argv[]) {
    bool        synthetic  = false;
    std::string trace_path = "";
    size_t      max_acc    = 200000;

    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "--synthetic")) synthetic = true;
        else if (!strcmp(argv[i], "--max") && i+1 < argc) max_acc = atoi(argv[++i]);
        else trace_path = argv[i];
    }

    Trace trace;
    if (synthetic || trace_path.empty()) {
        printf("Using synthetic trace (%zu accesses)\n", max_acc);
        trace = generate_synthetic(max_acc);
    } else {
        printf("Loading trace: %s\n", trace_path.c_str());
        trace = load_trace(trace_path, max_acc);
    }
    printf("Trace size: %zu accesses\n", trace.size());

    print_stride_analysis(trace);
    print_reuse_analysis(trace);

    const size_t KB = 4, BLK = 64, WAYS = 4;
    printf("\n=== Policy Comparison (%zuKB, %zuB block, %zu-way) ===\n", KB, BLK, WAYS);

    auto fixed = run_all(trace, KB, BLK, WAYS);
    double belady_hr = 0;
    for (auto& r : fixed) if (r.p == Policy::BELADY) belady_hr = r.hit;
    for (auto& r : fixed)
        printf("  %-8s  hit=%6.2f%%  miss=%6.2f%%  (vs Belady: %+.2f%%)\n",
               policy_name(r.p), r.hit*100, r.miss*100, (r.hit - belady_hr)*100);

    double lru_hr = 0, salru_hr = 0;
    for (auto& r : fixed) {
        if (r.p == Policy::LRU)   lru_hr   = r.hit;
        if (r.p == Policy::SALRU) salru_hr = r.hit;
    }
    printf("\nSA-LRU improvement over LRU: %+.2f%%\n", (salru_hr - lru_hr)*100);

    printf("\n=== Cache Size Sweep ===\n  %-8s", "KB");
    for (auto& r : fixed) printf("  %-9s", policy_name(r.p));
    printf("\n");

    std::vector<size_t> sizes = {1, 2, 4, 8, 16};
    std::vector<std::vector<Result>> all_runs;
    for (size_t sz : sizes) {
        auto res = run_all(trace, sz, BLK, WAYS);
        all_runs.push_back(res);
        printf("  %-8zu", sz);
        for (auto& r : res) printf("  %7.2f%%  ", r.hit*100);
        printf("\n");
    }

    write_csvs(fixed, all_runs);
    // ============================================================
    // EXTRA FEATURE: Multi-Level Cache Hierarchy Demonstration
    // ============================================================
    printf("\n=== L1, L2, L3 Cache Hierarchy Analysis ===\n");
    printf("Simulating real-world filtering effect...\n");

    // Standard architecture sizes
    // L1: 32KB, 8-way | L2: 256KB, 8-way | L3: 2048KB (2MB), 16-way
    Cache L1(32, 64, 8, Policy::LRU);
    Cache L2(256, 64, 8, Policy::LRU); 
    Cache L3(2048, 64, 16, Policy::SALRU); // Using your proposed policy at the Last Level!

    uint64_t l1_accesses = 0, l2_accesses = 0, l3_accesses = 0;

    for (Addr a : trace) {
        l1_accesses++;
        if (!L1.access(a)) { // If L1 Misses
            l2_accesses++;
            if (!L2.access(a)) { // If L2 Misses
                l3_accesses++;
                L3.access(a); // Go to L3
            }
        }
    }

    // Calculate Local Miss Rates
    double l1_local_mr = L1.miss_rate() * 100.0;
    double l2_local_mr = (l2_accesses > 0) ? (double(L2.misses) / l2_accesses) * 100.0 : 0;
    double l3_local_mr = (l3_accesses > 0) ? (double(L3.misses) / l3_accesses) * 100.0 : 0;

    // Calculate Global Miss Rates (Misses / Total Memory Accesses)
    double l1_global_mr = (double(L1.misses) / l1_accesses) * 100.0;
    double l2_global_mr = (double(L2.misses) / l1_accesses) * 100.0;
    double l3_global_mr = (double(L3.misses) / l1_accesses) * 100.0;

    printf("\nLevel | Accesses | Hits   | Misses | Local Miss Rate | Global Miss Rate\n");
    printf("------|----------|--------|--------|-----------------|-----------------\n");
    printf("  L1  | %-8llu | %-6llu | %-6llu | %6.2f%%         | %6.2f%%\n", 
           (unsigned long long)l1_accesses, (unsigned long long)L1.hits, (unsigned long long)L1.misses, l1_local_mr, l1_global_mr);
    printf("  L2  | %-8llu | %-6llu | %-6llu | %6.2f%%         | %6.2f%%\n", 
           (unsigned long long)l2_accesses, (unsigned long long)L2.hits, (unsigned long long)L2.misses, l2_local_mr, l2_global_mr);
    printf("  L3  | %-8llu | %-6llu | %-6llu | %6.2f%%         | %6.2f%%\n", 
           (unsigned long long)l3_accesses, (unsigned long long)L3.hits, (unsigned long long)L3.misses, l3_local_mr, l3_global_mr);
           
    printf("\nTotal accesses forced to Main Memory (L3 Misses): %llu\n", (unsigned long long)L3.misses);
    return 0;
}