Cache Simulation

Hands-on cache simulation exercises exploring mapping techniques, replacement policies, and hit/miss patterns.

Introduction

Cache memory is what makes modern computers fast. Without it, your CPU would spend 90% of its time waiting for slow main memory. But how does cache actually work? The best way to understand is to simulate it yourself — trace memory addresses through the cache, decide where each block goes, handle replacements, and calculate hit rates. These exercises will make cache behavior intuitive, so you can solve any cache problem in exams or interviews without hesitation.

Cache Simulation Setup

Cache Parameters for Our Simulations

- Cache size	64 bytes
- Block size	16 bytes (4 words of 4 bytes each)
- Number of blocks	64/16 = 4 cache lines
- Memory address	8 bits (256 bytes addressable)
- Word size	4 bytes

Address Breakdown

For an 8-bit address with 16-byte blocks:

Example

Address: [Tag | Index/Set | Block Offset] Direct Mapped (4 lines): Offset = log₂(16) = 4 bits Index = log₂(4) = 2 bits Tag = 8 - 2 - 4 = 2 bits Fully Associative (4 lines, 1 set): Offset = 4 bits Index = 0 bits (only one set) Tag = 8 - 0 - 4 = 4 bits 2-Way Set Associative (2 sets, 2 lines each): Offset = 4 bits Index = log₂(2) = 1 bit Tag = 8 - 1 - 4 = 3 bits

Simulation 1: Direct-Mapped Cache

Configuration

4 cache lines, direct mapped
Block size: 16 bytes
Address format: [2-bit Tag | 2-bit Index | 4-bit Offset]

Address Sequence

Let's trace these byte addresses: 0, 16, 32, 48, 0, 64, 0, 16

Step	Address (decimal)	Address (binary)	Tag	Index	Block	Hit/Miss	Action
1	0	00_00_0000	00	00	0	Miss	Load block 0 into line 0
2	16	00_01_0000	00	01	1	Miss	Load block 1 into line 1
3	32	00_10_0000	00	10	2	Miss	Load block 2 into line 2
4	48	00_11_0000	00	11	3	Miss	Load block 3 into line 3
5	0	00_00_0000	00	00	0	Hit	Found in line 0!
6	64	01_00_0000	01	00	4	Miss	Evict block 0, load block 4 into line 0
7	0	00_00_0000	00	00	0	Miss	Conflict! Evict block 4, reload block 0
8	16	00_01_0000	00	01	1	Hit	Still in line 1

Cache State After Each Access

After step 4

Line 0: [Valid=1, Tag=00, Data=Block 0 (bytes 0-15)]

Line 1: [Valid=1, Tag=00, Data=Block 1 (bytes 16-31)]

Line 2: [Valid=1, Tag=00, Data=Block 2 (bytes 32-47)]

Line 3: [Valid=1, Tag=00, Data=Block 3 (bytes 48-63)]

After step 6

Line 0: [Valid=1, Tag=01, Data=Block 4 (bytes 64-79)] ← CHANGED!

Line 1: [Valid=1, Tag=00, Data=Block 1 (bytes 16-31)]

Line 2: [Valid=1, Tag=00, Data=Block 2 (bytes 32-47)]

Line 3: [Valid=1, Tag=00, Data=Block 3 (bytes 48-63)]

Hit Rate = 2/8 = 25%

Steps 6 and 7 demonstrate a conflict miss — addresses 0 and 64 both map to line 0, causing repeated evictions (thrashing).

Simulation 2: Fully Associative Cache

Same sequence, but now any block can go in any line:

Step	Address	Tag	Hit/Miss	Cache State
1	0	0000	Miss	[B0, -, -, -]
2	16	0001	Miss	[B0, B1, -, -]
3	32	0010	Miss	[B0, B1, B2, -]
4	48	0011	Miss	[B0, B1, B2, B3]
5	0	0000	Hit	[B0, B1, B2, B3]
6	64	0100	Miss	Need to evict! LRU = B1 → [B0, B4, B2, B3]
7	0	0000	Hit	[B0, B4, B2, B3] — B0 still here!
8	16	0001	Miss	LRU = B2 → [B0, B4, B1, B3]

Hit Rate = 3/8 = 37.5% (better than direct-mapped!)

The key difference: At step 7, address 0 still hits because fully associative has no conflict misses. Block 0 was not evicted when block 4 arrived (LRU chose block 1 instead).

Simulation 3: 2-Way Set Associative

Two sets, two lines each. Address format: [3-bit Tag | 1-bit Set Index | 4-bit Offset]

Step	Address	Tag	Set	Hit/Miss	Set 0 Contents	Set 1 Contents
1	0	000	0	Miss	[B0, -]	[-, -]
2	16	000	1	Miss	[B0, -]	[B1, -]
3	32	001	0	Miss	[B0, B2]	[B1, -]
4	48	001	1	Miss	[B0, B2]	[B1, B3]
5	0	000	0	Hit	[B0, B2]	[B1, B3]
6	64	010	0	Miss	[B4, B2]→LRU evicts B0? No—B0 was just used! Evict B2 → [B0, B4]	[B1, B3]
7	0	000	0	Hit	[B0, B4]	[B1, B3]
8	16	000	1	Hit	[B0, B4]	[B1, B3]

Hit Rate = 4/8 = 50% (best of the three!)

Simulation 4: Replacement Policy Comparison

Cache: Fully associative, 4 lines. Access sequence: A, B, C, D, E, A, B, C, D, E

FIFO (First In, First Out)

Step 1: A (miss)	[A, -, -, -]
Step 2: B (miss)	[A, B, -, -]
Step 3: C (miss)	[A, B, C, -]
Step 4: D (miss)	[A, B, C, D]
Step 5: E (miss)	[E, B, C, D] ← A evicted (oldest)
Step 6: A (miss)	[E, A, C, D] ← B evicted
Step 7: B (miss)	[E, A, B, D] ← C evicted
Step 8: C (miss)	[E, A, B, C] ← D evicted
Step 9: D (miss)	[D, A, B, C] ← E evicted
Step 10: E (miss)	[D, E, B, C] ← A evicted

Hit rate = 0/10 = 0% (pathological case — working set > cache size)

LRU (Least Recently Used)

Same sequence, same result for this case: Hit rate = 0% (working set of 5 blocks in 4-line cache means no reuse possible regardless of policy).

Key Insight

When the working set is larger than the cache, no replacement policy can help — you will always miss. This is a capacity miss.

Simulation 5: Loop Access Pattern

Consider code accessing an array in a loop:

Example

// Array of 128 bytes, cache has 64 bytes (4 blocks of 16) for (int i = 0; i < 3; i++) // 3 iterations for (int j = 0; j < 32; j++) // Access bytes 0-31 (2 blocks) sum += array[j];

First Iteration (i=0)

Access byte 0: Miss (load block 0: bytes 0-15)
Access bytes 1-15: All hits! (spatial locality within block)
Access byte 16: Miss (load block 1: bytes 16-31)
Access bytes 17-31: All hits!

Iteration 1: 2 misses, 30 hits

Second Iteration (i=1)

Access byte 0: Hit! (block 0 still in cache — temporal locality)
Access bytes 1-31: All hits!

Iteration 2: 0 misses, 32 hits

Third Iteration (i=2)

Same as iteration 2: 0 misses, 32 hits

Overall: 2 misses out of 96 accesses = 97.9% hit rate!

This demonstrates why loops have excellent cache performance — spatial locality (sequential access) fills blocks efficiently, and temporal locality (repeated iterations) provides hits on subsequent passes.

Performance Impact Calculator

Formula Application

- L1 cache hit time	1 ns
- L1 miss rate	5%
- L2 hit time	10 ns
- L2 miss rate	20%
- Main memory time	100 ns
Without any cache	100 ns per access
With cache hierarchy	2.5 ns per access
Speedup	100/2.5 = 40× faster!

This is why cache matters — a 40× speedup from a component that costs a fraction of the total chip area.

Exercises

Trace: Direct-mapped cache with 8 lines, 8-byte blocks. Address sequence: 0, 4, 8, 16, 32, 0, 64, 0. Calculate hit rate.
Compare: Run the same sequence through fully associative and 2-way set associative. Which has better hit rate?
Design: If your program accesses addresses 0, 64, 128, 192 repeatedly (all map to same line in direct-mapped), what cache organization eliminates these conflict misses?
Calculate: A cache has 95% hit rate with 2ns hit time. If miss penalty is 50ns, what AMAT would you need to achieve with a second-level cache to improve overall AMAT by 20%?

Key Takeaways

Direct-mapped caches are fast but suffer from conflict misses when multiple blocks map to the same line
Fully associative eliminates conflict misses but requires expensive comparison hardware (one comparator per line)
Set-associative is the practical middle ground — N-way associativity with N comparators per set
Spatial locality fills entire cache blocks efficiently — sequential array access has excellent hit rates
Temporal locality provides hits on repeated access — loops reuse cached data across iterations
When working set exceeds cache size, capacity misses are unavoidable regardless of replacement policy
The multiplicative effect of miss rates across levels means even small improvements in L1 hit rate have huge impact on AMAT

Introduction