CPU & Computer ArchitectureMemory HierarchyHard

Implement Direct-Mapped Cache Simulator

Master the fundamental concepts of memory hierarchy through this focused micro-challenge.

~90 minutes Memory Hierarchy Ready to learn

Topic Overview

Cache Indexing

A direct-mapped cache splits physical addresses into tag, index, and offset. Each index maps to exactly one cache line; conflicts evict even if other lines sit idle.

c
Loading…

Hit and Miss

On access:

Compare stored tag at index with computed tag
Check valid bit
Hit: return data; miss: fetch line from memory, replace entry

For example, with 64-byte lines and 256 lines, index is 8 bits and two addresses that agree on those bits contend for the same slot.

For this exercise, you will simulate loads and stores, counting hits and misses. This task asks you to implement tag compare and line fill, the same mechanics perf indirectly observes when LLC miss rate spikes.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

Trace first: walk one failing input by hand before changing random lines
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Implementation Task

Your Task

Simulate a direct-mapped cache. Each address is split into tag / index / offset. The index picks exactly one line, and a stored tag decides hit or miss. The cache is write-back, write-allocate, so stores mark lines dirty and dirty lines are written back when evicted. Trace every access and classify each miss as a cold miss (empty line) or a conflict miss (another tag was there).

Input

c
Loading…

Address split

offset = the low log2(LINE) bits. index = the next log2(SIZE / LINE) bits. tag = the remaining high bits.

Behaviour

Hit: the line is valid and its tag matches. A W hit sets the dirty bit.
Miss: if the line was invalid, it's a cold miss. Otherwise it's a conflict miss, which evicts the old tag and writes it back first if dirty. Then fill the line with the new tag. It is dirty if and only if this access is a W.

Output

c
Loading…

(, writeback only if the evicted line was dirty.) dump prints line I: tag=0xT plus dirty for each valid line in index order, or cache empty. At the end:

c
Loading…

with P to one decimal (0.0 when there were no accesses). Addresses and tags print in lower-case hex without leading zeros.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

An array of lines {valid, dirty, tag}; compute the field widths from SIZE and LINE with shifts and masks.
Keep the statistics counters separate from the trace printing.

Hidden tests cover two arrays that map to the same lines (ping-pong conflicts), writes that dirty lines and later write back, a cache with a single line, and dump.