🧠 Memory Cache Simulator

A full-stack set-associative cache simulator that captures real memory traces from running programs using Intel Pin, simulates cache behavior across 5 replacement policies, and visualizes results through interactive Streamlit dashboards and Matplotlib heatmaps.

---

📋 Table of Contents

• Features
• Architecture
• Project Structure
• Prerequisites
• Getting Started
  • 1. Build the Pin Tool
  • 2. Compile a Benchmark
  • 3. Generate a Memory Trace
  • 4. Compile the Simulator
  • 5. Run the Simulation
• Cache Replacement Policies
• Benchmarks
• Visualization
  • Streamlit Dashboard
  • CLI Heatmap Plotter
• Sample Results
• Address Decomposition

---

✨ Features

• Real memory traces via Intel Pin dynamic binary instrumentation
• 5 replacement policies — LRU, FIFO, LFU, RANDOM, OPT (Bélády's optimal)
• Configurable cache geometry — cache size, number of sets, associativity, line size
• 4 purpose-built benchmarks — from simple matrix ops to policy-discriminating workloads
• Interactive Streamlit UI — parameter sweeps, multi-policy comparison, per-set heatmaps
• Publication-quality plots — standalone Matplotlib heatmap generator
• Region-of-Interest (ROI) tracing — trace only the code section you care about
• OPT (Bélády's) upper bound — theoretical best-case for comparison

---

🏗 Architecture

┌─────────────────┐    Intel Pin     ┌──────────────────┐
│   bench*.cpp    │ ──────────────→  │  mem_trace.cpp   │
│  (workloads)    │  instruments     │  (Pin tool)      │
└─────────────────┘                  └────────┬─────────┘
                                              │ writes
                                              ▼
                                     ┌──────────────────┐
                                     │   mem.trace      │
                                     │ R 0x... / W 0x.. │
                                     └────────┬─────────┘
                                              │ reads
                                              ▼
┌─────────────────┐                  ┌──────────────────┐
│   cache.h       │ ◄──────────────  │  cache_sim.cpp   │
│ (engine)        │  #include        │  (CLI frontend)  │
└─────────────────┘                  └────────┬─────────┘
                                              │ outputs
                                    ┌─────────┴──────────┐
                                    ▼                    ▼
                           ┌──────────────┐    ┌──────────────┐
                           │ *_heatmap.csv│    │  stats CSV   │
                           └──────┬───────┘    └──────────────┘
                                  │ reads
                    ┌─────────────┼────────────┐
                    ▼             ▼             ▼
           ┌──────────────┐ ┌──────────┐ ┌──────────────┐
           │plot_heatmap  │ │  app.py  │ │  cache_ui.py │
           │   .py        │ │(simple)  │ │  (advanced)  │
           └──────────────┘ └──────────┘ └──────────────┘

---

📁 Project Structure

Memory-Cache-Simulator/
│
├── cache.h              # Cache simulation engine (header-only, all 5 policies)
├── cache_sim.cpp        # CLI frontend — parses args, runs trace, outputs stats
├── mem_trace.cpp        # Intel Pin tool — instruments binaries for memory traces
│
├── bench.cpp            # Benchmark 1: Dijkstra + matrix multiply + scan-with-polluter
├── bench2.cpp           # Benchmark 2: Pointer chase, conflict thrash, big transpose
├── bench3.cpp           # Benchmark 3: Simple 4×4 matrix addition
├── bench4.cpp           # Benchmark 4: Policy-discriminating workloads (cyclic, Zipf)
│
├── cache_ui.py          # Full Streamlit dashboard (sweep engine, 4-tab comparison)
├── app.py               # Simple Streamlit dashboard (single-run view)
├── plot_heatmap.py      # Standalone CLI heatmap plotter (Matplotlib)
│
├── makefile             # Pin SDK build entry point
├── makefile.rules       # Pin build rules (builds mem_trace.so)
├── obj-intel64/         # Pin build artifacts (mem_trace.so)
│
├── *_heatmap.csv        # Per-set eviction/hit-rate data (one per policy)
├── heatmap.png          # Sample generated heatmap comparison
└── cds.txt              # Command cheat sheet

---

🔧 Prerequisites

Tool	Version	Purpose
Intel Pin	3.x+	Dynamic binary instrumentation
g++	C++17 support	Compiling simulator and benchmarks
Python 3	3.8+	Visualization scripts
Streamlit	latest	Interactive dashboard UI
Matplotlib	latest	Heatmap generation
pandas	latest	CSV data handling
NumPy	latest	Numerical computations

Install Python dependencies:

pip install streamlit matplotlib pandas numpy

---

🚀 Getting Started

1. Build the Pin Tool

cd /path/to/Memory-Cache-Simulator
make

This compiles mem_trace.cpp into obj-intel64/mem_trace.so using the Intel Pin SDK.

2. Compile a Benchmark

g++ -o bench bench4.cpp

Any of the bench*.cpp files can be used. bench4.cpp is recommended as it is specifically designed to differentiate between replacement policies.

3. Generate a Memory Trace

$PIN_ROOT/pin -t obj-intel64/mem_trace.so -- ./bench

This runs the benchmark under Pin and produces mem.trace with entries like:

R 0x7ffd5a3b2c40
W 0x7ffd5a3b2c48
R 0x55a4e8001060
...

Pin tool options:

Flag	Description	Default
-o <file>	Output trace file path	mem.trace
-max <N>	Stop after N accesses	unlimited
-rw <r|w|rw>	Record reads, writes, or both	rw
-flush <N>	Flush buffer every N accesses	100000
-main_only <0|1>	Only trace main executable (skip libc, etc.)	0
-size <0|1>	Append access size to each line	0
-roi <0|1>	Region-of-interest mode (trace between __trace_start() / __trace_stop())	0

4. Compile the Simulator

g++ -O2 -std=c++17 -o cache_sim cache_sim.cpp

5. Run the Simulation

./cache_sim --trace mem.trace \
            --size 32 \
            --sets 128 \
            --assoc 4 \
            --line 64 \
            --policy LRU

CLI options:

Flag	Description
--trace <file>	Path to memory trace file
--size <KB>	Total cache size in KB
--sets <N>	Number of sets (must be power of 2)
--assoc <N>	Set associativity (ways)
--line <bytes>	Cache line size in bytes (must be power of 2)
--policy <name>	LRU | FIFO | LFU | RANDOM | OPT
--csv <file>	Append summary results to CSV
--heatmap <file>	Export per-set heatmap data to CSV
--show-heatmap	Print ASCII heatmap to terminal

Constraint: sets × assoc × line_size / 1024 must equal size (KB).

---

🔄 Cache Replacement Policies

Policy	Strategy	Notes
LRU	Evict the least recently used line	Tracks last-access timestamp per line
FIFO	Evict the first inserted line	Insertion timestamp never updated on hit
LFU	Evict the least frequently used line	Frequency counter incremented on hit; ties broken by oldest insertion
RANDOM	Evict a random line	Uses std::rand() with seed 42 for reproducibility
OPT	Evict the line used furthest in the future	Bélády's algorithm — theoretical upper bound; requires two-pass trace scan

Implementation Highlights

• Pointer-to-member generic victim selection — a single victim_min() / victim_max() function handles LRU, FIFO, and OPT using C++ pointer-to-member syntax
• Two-pass OPT — first pass builds per-block future-use lists (reversed for O(1) pop_back()), second pass simulates
• All metadata co-located on each CacheLine — simplifies code at minor memory cost

---

🏋️ Benchmarks

bench.cpp — Dijkstra Bench

Three phases with different locality profiles:

1. Dijkstra's algorithm on a 200-node graph (160 KB adjacency matrix) — good temporal + spatial reuse
2. Matrix multiply (64×64, ikj loop order) — poor spatial locality on column accesses
3. Scan-with-polluter — hot working set (256 entries) polluted by a larger array (4096 entries)

bench2.cpp — Cache Stress

Four aggressive phases targeting 20–60% miss rates:

1. Pointer chase — 128 MB random linked list, zero spatial locality
2. Conflict thrash — 4 KB stride forcing all accesses to the same cache set
3. Big transpose — 8192×8192 byte matrix, terrible write locality
4. Reuse-distance ladder — arrays from 16 KB to 16 MB to reveal the cache capacity boundary

bench3.cpp — Simple Matrix Addition

A trivial 4×4 matrix addition for quick smoke testing.

bench4.cpp — Policy Discriminator ⭐

Specifically crafted for a 4 KB cache (16 sets × 4-way × 64 B) to differentiate policies:

1. Cyclic thrash — 5 lines competing for 4 ways (LRU pathological case)
2. Weighted Zipf — 80/20 distribution over 256 lines (LFU excels)
3. Set-conflict reuse — 3 warm + 3 cold lines in the same set (LFU retains warm lines)

---

📊 Visualization

Streamlit Dashboard

Full-featured UI (cache_ui.py) — supports parameter sweeps across all combinations of policies, sets, and associativity:

streamlit run cache_ui.py

Features:

• Multi-select policies, sets, and associativity for batch comparison
• 4 tabs: Compare | Hit Rate | Heatmaps | Summary
• Grouped bar charts, line plots (log₂ scale), stacked heatmaps
• Dark theme with custom styling

Simple UI (app.py) — single-run dashboard:

streamlit run app.py

CLI Heatmap Plotter

Generate publication-quality comparison heatmaps from CSV files:

# Export per-set data for each policy
for p in LRU FIFO LFU RANDOM OPT; do
  ./cache_sim --trace mem.trace --size 1 --sets 4 --assoc 4 --line 64 \
              --policy $p --heatmap ${p}_heatmap.csv
done

# Plot multi-policy comparison
python3 plot_heatmap.py \
    --input LRU_heatmap.csv FIFO_heatmap.csv LFU_heatmap.csv \
            RANDOM_heatmap.csv OPT_heatmap.csv \
    --out heatmap.png

Sample Heatmap Output

---

📈 Sample Results

Results from a 4-set, 4-way, 64 B line (1 KB cache) simulation on bench4:

Policy	Set 0 Hit%	Set 1 Hit%	Set 2 Hit%	Set 3 Hit%	Total Evictions
OPT	98.46	99.26	98.58	98.79	620,701
LRU	97.85	99.20	98.31	98.64	780,877
FIFO	96.71	98.50	98.02	98.04	1,183,265
RANDOM	96.98	98.37	97.82	97.82	1,184,855
LFU	95.12	98.56	96.70	89.82	2,308,696

Policy hierarchy on this trace: OPT > LRU > FIFO ≈ RANDOM > LFU

LFU's poor Set 3 performance (89.82%) is a classic frequency-count pathology — stale high-frequency entries block fresh ones from entering the cache.

---

🔍 Address Decomposition

The simulator decomposes 64-bit addresses as:

┌──────────────────────────────┬───────────────┬──────────────┐
│           TAG                │    INDEX      │    OFFSET    │
│   (64 - index - offset) bits │  log₂(sets)   │  log₂(line)  │
└──────────────────────────────┴───────────────┴──────────────┘

For example, with 128 sets and 64 B lines:

• Offset: 6 bits (log₂(64))
• Index: 7 bits (log₂(128))
• Tag: 51 bits (64 − 7 − 6)

---

📄 License

This project was developed as a course project for CS204 at IIT Ropar.