Loading page…
Master the fundamental concepts of memory hierarchy through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksA 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.
cLoading…
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.
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.
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.
Generalise the cache to N-way set-associative with LRU replacement. The index now selects a set of WAYS lines, and a block may live in any way of its set. The same trace that thrashes a direct-mapped cache can hit almost every time with two or four ways. Show which set and way each access uses, and what it evicts.
The first line is cache SIZE LINE WAYS (powers of two, in bytes; WAYS = 1 is direct-mapped). Then hex addresses (0x optional) separated by whitespace or newlines.
sets = SIZE / (LINE · WAYS), offset = low log2(LINE) bits, set = next log2(sets) bits, tag = the rest.cLoading…
After the trace, print each set as set S: T0 T1 ..., one tag per way in way order (0x…, or - if invalid). Then:
cLoading…
with P to one decimal. Addresses and tags print in lower-case hex without leading zeros.
Input:
cLoading…
Output:
cLoading…
WAYS entries {valid, tag, last_used}, with a global access counter for LRU.Hidden tests run a conflict-heavy trace on a 4-way cache and a fully associative cache (a single set) whose LRU victim changes as blocks are reused.