Cache Architecture: Simulator Design

This repository contains two key projects that explore the core principles of cache architecture, both implemented in C/C++:

• Cache Simulator: A fully functional cache simulator built from scratch in C that models cache behavior using valgrind memory traces.
• Replacement Policy Analysis: Implementation and analysis of the Least Recently Used (LRU) replacement policy in a C++ cache simulator.

Project Overview

The "Memory Wall" problem highlights how CPU speeds have far outpaced main memory speeds. Caches bridge this gap by storing frequently used data in small, fast memory blocks. This project explores two core design questions:

1. How do we design a cache?
   By building a flexible simulator (csim.c) that can model different cache configurations (Set size, Associativity, Block size) and measure performance.

2. How do we optimize a cache?
   By implementing an intelligent LRU policy to replace naive eviction strategies, proving its effectiveness through simulation results.

Core Features

1. Configurable Cache Simulator

• Developed in C from scratch.
• Parses valgrind-generated memory traces.
• Supports any (S, E, B) configuration (Sets, Associativity, Block size).
• Reports hit, miss, and eviction statistics.
• Enables detailed analysis of cache performance.

2. LRU Replacement Policy

• Implemented in C++ within an existing cache simulator.
• Replaces a naive “always evict Way 0” policy.
• Uses timestamp/counter-based tracking to evict the Least Recently Used block.
• Demonstrates significantly reduced miss rates, especially for workloads with temporal locality.

Architecture and Design

Part 1: Cache Simulator from Scratch

The simulator (csim.c) models real cache hardware behavior and processes memory traces generated by valgrind. Each line of the trace represents a memory operation (e.g., L 0x1a2b3c, 4).

Core Workflow

1. Parse Access: Read each trace instruction.
2. Address Calculation: Extract tag and set index from the 64-bit address.
3. Set Selection: Locate the correct cache set (2D array of structs).
4. Hit Check: Match tags in valid lines.
5. Miss Handling:
   • If an empty line exists → fill it.
   • If all lines are occupied → evict using LRU.

Part 2: LRU Policy Implementation

The existing simulator (cachesim.cpp) was modified to integrate the LRU policy.

Before (Naive Policy)

• The cache always evicted Way 0, regardless of usage.
• Inefficient, as frequently accessed blocks could be evicted prematurely.

After (LRU Policy)

• Each cache line tracks a timestamp counter.
• On every access, the accessed line resets its counter to 0 (most recently used).
• On every access, others increment by 1 (aging).
• On eviction, the line with the largest counter (oldest) is replaced.

This effectively applies the Principle of Temporal Locality, optimizing cache efficiency.

Module Structure

Path	Description
Policy_Exploration/	Contains files for the LRU policy implementation.
├── cachesim.cpp	C++ simulator source (LRU logic implemented in cache_flush).
├── cachesim.h	Header file with LRU data structures and declarations.
├── Makefile	Build script for the simulator.
└── benchmarks/	Contains benchmark assembly files (exa.s, sort.s).
Simulator_Design/	Contains files for the cache simulator from scratch.
├── csim.c	Main C source for the simulator.
├── cachelab.h	Header with cache struct definitions and utilities.
├── Makefile	Build script for the simulator.
└── traces/	Contains memory traces (dave.trace, yi.trace, etc.).

Simulation and Results

Testing

• csim.c (Lab 09):
  Validated against a reference simulator using provided trace files.
• cachesim.cpp (Lab 08):
  Benchmarked using exa.s and sort.s under multiple cache configurations (1-way, 2-way, 4-way).

Findings

• Key Finding 1: LRU drastically reduces miss rates, especially in workloads with high temporal locality (e.g., sort.s).
• Key Finding 2: LRU performs best with higher associativity (4-way), as it gains more flexibility in replacement decisions.

Tools Used

• Languages: C, C++
• Toolchain: GCC, G++, Make
• Profiler: Valgrind (for trace generation)
• Environment: Linux / UNIX-based systems

Future Improvements

• Implement More Policies: Add and compare LFU, Random, and Pseudo-LRU strategies.
• Simulate Write Policies: Include Write-Back vs. Write-Through and Write-Allocate vs. No-Write-Allocate mechanisms.
• Multi-Level Caches: Extend csim.c to simulate a multi-level (L1 + L2) cache hierarchy.

License

This project is licensed under the MIT License

Summary

This project serves as a practical exploration of cache architecture in computer systems — from designing a simulator to evaluating real-world replacement policies. It bridges theory with implementation, showcasing how software simulation can be used to analyze and optimize hardware-level performance.

Regards

Awais Asghar