 # Cache Set Associativity

#1

Consider a write-back, n-way set associative cache with the following specifications
Set Size: 4
Block Size: 8 Bytes (Not including tag & valid bits)
Ceil(log2 ( n!)) bits per set are required to implement the LRU replacement policy
2 status bits (1 valid bit, 1 dirty bit)
64 sets

How many bits are stored per set?
(i)292
(ii)297
(iii)300
(iv)312

#2

Block size= 8Bytes = 2^3 Bytes
So Block Offset = 3bits

No of sets = 64 = 2^6
So No of bits required for set no = 6 bits

So tag bits = Physical Address - Block Offset - Set no = 16 - 3 - 6 = 7

Now Size of Set = No of blocks in each set * Block Size = 4 * 8 = 32 Bytes = 32 * 8 = 256 Bits

Additionaly we have to add the tag bits and valid bits for each set.

Bits stored per set = (Size of set in bits) + (Total Tag Size in bits) + (Total valid bit size in bits)

= 256 + (4*7) + (4*2)

=256 + 28 + 8

= 292 bits

292 + LRU bits required
= 292 + Ceil [ log2 (4!) ]
= 292 + Ceil [ log2 (24) ]
= 292 + 5
= 297
So option (ii) is correct.