Question

Assume there are three small caches, each consisting of four one-word blocks. One cache is fully associative, a second is two-way set-associative, and the third is direct mapped. Find the number of misses for each cache organization given the following sequence of block addresses: 2, 4, 2, 7, 0, and 8. Assume a LRU (least recently used) scheme is used to choose which block to replace.

Answer 1

LRU (least recently used) technique is used to choose which block to replace.

one woy Set associative (diveet mapped) Block - Tag Data Given Block Address 2, 4, 2, 70, 8 wp-O Two way set associative set Tag Data Tag Data Fully - Associative Tag Data Tag Data Tag Data Tag Data 0 Direct mapped (block address) modulo (no of blocks is cache) Block address cache block 2 mod y = 4 mod y = 0 7 mod y = 3 o mod y = 0 & mod 4 - 0 oo wo N

Address of memory Block Associativity in cache Hit or contents of cache blocks Miss after reference 0 1 2 Mem [2] Mem [2] Miss Hermany) Miss Memory [4] Miss Hemory 3 Miss Memexy ft) Miss Memory [o] Miss Memory [8] 2. Two way associative cache Mem [1] (block address) modulo (no of sets in cache) Block address cacheset Address of memory block o modulo 2 - 0 4 modulo 2 = 0. 7 modulo 2 - 1 o modulo 2 = 0 8 modulo 2 = 0 contents of cache block after reference seto set D set set Mem[2] Menu Mem [2] Mem[2] miss du Nro. Miss Miss hit miss miss miss Mem[7] Mem[o] Memrs]

after Block © Fully associative cache- Address of Hitl contents of cache block memory block Miss reference Block 0 Block 1 Block Miss Mem [2] Miss Mem[u] hit MEM[2 ] Mem[2] Miss Mem [1] Deep Miss Mem[o du drooo Miss Mem[8] Memory [] – indicates invalid block/ address