Cache Simulator

A comprehensive CPU cache simulator written in Python that models various cache architectures and replacement policies. This simulator accurately replicates cache behavior for different memory hierarchies, supporting direct-mapped, set-associative, and fully-associative caches.

Features

Cache Types

• Direct-mapped cache: One-way associative cache where each memory block maps to exactly one cache line
• N-way set-associative cache: Configurable associativity (e.g., 2-way, 4-way)
• Fully-associative cache: Any memory block can be stored in any cache line

Replacement Policies

• LRU (Least Recently Used): Evicts the cache line that hasn't been accessed for the longest time
• LFU (Least Frequently Used): Evicts the cache line with the lowest access frequency
• RR (Round Robin): Cycles through cache lines in a fixed order

Additional Capabilities

• Multi-level cache hierarchies: Simulate L1, L2, and L3 caches
• Boundary-crossing memory operations: Automatically splits memory operations that cross cache line boundaries
• Configurable cache parameters: Size, line size, associativity via JSON configuration
• Performance metrics: Tracks hits, misses, and main memory accesses
• Flexible address width: Supports various memory address bit lengths (not limited to 64-bit)

Installation

This project uses only Python's standard library, so no external dependencies are required.

# Clone the repository
git clone https://github.com/yourusername/python-cache.git
cd python-cache

# Ensure Python 3.6+ is installed
python3 --version

Usage

Basic Command Format

python3 main.py <path-to-config-file> <path-to-trace-file>

Configuration File Format

Create a JSON file defining your cache hierarchy:

{
  "caches": [
    {
      "name": "L1",
      "size": 32768,
      "line_size": 64,
      "kind": "4way",
      "replacement_policy": "lru"
    },
    {
      "name": "L2",
      "size": 262144,
      "line_size": 64,
      "kind": "8way",
      "replacement_policy": "lru"
    }
  ]
}

Parameters:

• name: Identifier for the cache level
• size: Total cache size in bytes
• line_size: Size of each cache line in bytes
• kind: Cache type - "direct", "Nway" (e.g., "2way", "4way"), or "full" for fully-associative
• replacement_policy: "lru", "lfu", or "rr" (not needed for direct-mapped caches)

Trace File Format

Memory trace files should contain one operation per line:

<operation> <address> <size> <bytes>

Example:

R 0x00007f8b4c000000 8 128
W 0x00007f8b4c000008 4 64

Example Commands

# Simulate a direct-mapped cache
python3 main.py my_tests/input/simple_direct_test_12_bit.json trace_file.out

# Simulate a 2-way set-associative cache with LFU policy
python3 main.py my_tests/input/_2_way_lfu.json trace_file.out

# Simulate a multi-level cache hierarchy (L1/L2/L3)
python3 main.py my_tests/input/l1l2l3_direct_test.json trace_file.out

Project Structure

.
├── cache_simulator.py      # Main simulator controller managing cache hierarchy
├── cache.py                # Cache implementations (DirectCache, LRUCache, LFUCache, RRCache)
├── linkedlist.py           # Doubly-linked list for LRU tracking
├── common.py               # Utility functions (debugging output)
├── main.py                 # Entry point and I/O handling
├── my_tests/               # Test cases and trace files
│   ├── input/             # Cache configuration files
│   ├── output/            # Expected simulation results
│   └── trace_files/       # Memory access trace files
└── README.md

How It Works

Cache Addressing

The simulator divides memory addresses into three components:

• Tag: Identifies which memory block is stored
• Index: Selects which cache set to use
• Offset: Specifies the byte within the cache line

For a 64-bit address with 64-byte cache lines and 256 cache sets:

| Tag (51 bits) | Index (8 bits) | Offset (6 bits) |

Memory Operation Handling

1. Address parsing: Extracts tag, index, and offset from the memory address
2. Boundary detection: Identifies operations crossing cache line boundaries
3. Cache lookup: Searches through the cache hierarchy (L1 → L2 → L3)
4. Hit/Miss handling:
   • Hit: Updates replacement policy tracking (LRU/LFU counter)
   • Miss: Applies replacement policy if the set is full, loads data from the next level
5. Performance tracking: Records hits, misses, and main memory accesses

Replacement Policy Implementation

• LRU: Uses a doubly-linked list to track access order in O(1) time
• LFU: Maintains frequency counters for each cache line
• RR: Uses modulo arithmetic to cycle through victim positions

Output

The simulator outputs JSON with performance metrics:

{
  "main_memory_accesses": 42,
  "caches": [
    {
      "name": "L1",
      "hits": 1523,
      "misses": 187
    },
    {
      "name": "L2",
      "hits": 145,
      "misses": 42
    }
  ]
}

Testing

The my_tests/ directory contains comprehensive test cases covering:

• Direct-mapped caches
• Set-associative caches (2-way, 4-way)
• Fully-associative caches
• All replacement policies (LRU, LFU, RR)
• Multi-level cache hierarchies
• Boundary-crossing scenarios
• Edge cases (empty caches, full caches)

Run tests by comparing simulator output with expected output files:

python3 main.py my_tests/input/full_lru.json trace.out > result.json
diff result.json my_tests/output/full_lru.json

Design Decisions

Data Structures

1. Sets for tag lookup: O(1) hit/miss detection
2. Arrays for tag storage: Contiguous memory representation of cache lines
3. Linked lists for LRU: Efficient access order tracking without index management
4. Dictionaries for LFU: Fast tag-to-index lookup for frequency updates

Optimization Techniques

• Pre-allocated victim counters track next free space in cache sets (avoids linear search)
• Tag sets enable O(1) membership testing instead of O(n) array traversal
• Memory operations are split at L1 boundaries to maximize lower-level cache efficiency

Requirements

• Python 3.6 or higher
• No external dependencies (uses standard library only)