Implement Set-Associative Cache (2-way, 4-way)

Associativity Reduces Conflict Misses

A set-associative cache groups N lines per index (ways). An address maps to one set but can occupy any way within it. Two-way and four-way designs are common in L1 and L2.

cCopy
Loading…

Trade-offs

• Direct-mapped: one line per set, cheapest hardware, worst conflicts
• 2-way: halves conflict misses for many access patterns
• Fully associative: one set, search all ways, expensive comparators

For example, streaming through two arrays whose addresses alias to the same direct-mapped index thrashes; a 2-way cache keeps both lines resident.

For this exercise, you will extend your simulator to 2-way and 4-way associativity with LRU or FIFO replacement per set. This task asks you to compare miss rates against the direct-mapped baseline on the same trace.

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.