GATE CS 2017 Set 1 Q51 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

The cache is $2$-way set associative with $256$ blocks. Thus, the number of sets is:

The set index for any memory block $B$ is given by $B \pmod{128}$. Mapping the blocks in the sequence to their respective sets:

• Set 0: Blocks $0, 128, 256$
• Set 1: Blocks $1, 129, 257$

Since the sets are independent, we can analyze the accesses to Set 0 and Set 1 separately. Because the access patterns are identical in structure, both sets will experience the same number of conflict misses.

Analysis for Set 0 (Capacity = 2 blocks, LRU):

The access sequence for Set 0 in one iteration is: $\{0, 128, 256, 128, 0, 128, 256, 128\}$.

Iteration 1:

1. Access $0$: Compulsory Miss (Cache: $[0]$)
2. Access $128$: Compulsory Miss (Cache: $[128, 0]$)
3. Access $256$: Compulsory Miss (Cache: $[256, 128]$, $0$ evicted)
4. Access $128$: Hit (Cache: $[128, 256]$)
5. Access $0$: Conflict Miss (Cache: $[0, 128]$, $256$ evicted)
6. Access $128$: Hit (Cache: $[128, 0]$)
7. Access $256$: Conflict Miss (Cache: $[256, 128]$, $0$ evicted)
8. Access $128$: Hit (Cache: $[128, 256]$)

In Iteration 1, Set 0 has 2 conflict misses. The state of Set 0 at the end of Iteration 1 is $[128, 256]$ (with $128$ as MRU and $256$ as LRU).

Iterations 2 to 10 (9 iterations):
Starting with state $[128, 256]$:

1. Access $0$: Conflict Miss (Cache: $[0, 128]$)
2. Access $128$: Hit (Cache: $[128, 0]$)
3. Access $256$: Conflict Miss (Cache: $[256, 128]$)
4. Access $128$: Hit (Cache: $[128, 256]$)
5. Access $0$: Conflict Miss (Cache: $[0, 128]$)
6. Access $128$: Hit (Cache: $[128, 0]$)
7. Access $256$: Conflict Miss (Cache: $[256, 128]$)
8. Access $128$: Hit (Cache: $[128, 256]$)

Each of the remaining 9 iterations results in exactly 4 conflict misses.

Total Conflict Misses:

• Conflict misses for Set 0 = $2 + (9 \times 4) = 38$
• Conflict misses for Set 1 = $38$ (by symmetry)

Total conflict misses experienced by the cache = $38 + 38 = 76$.