Question 51

Cache configuration:

• Total cache blocks = 256.
• 2-way set-associative $\implies$ Number of sets = $256 / 2 = 128$ sets (indexed 0 to 127).
• Set index of block $B$ is $B \bmod 128$.

The sequence of accesses is:

Notice that:

• Blocks 0, 128, 256 all map to set $0$ ($0 \bmod 128 = 128 \bmod 128 = 256 \bmod 128 = 0$).
• Blocks 1, 129, 257 all map to set $1$ ($1 \bmod 128 = 129 \bmod 128 = 257 \bmod 128 = 1$).
  Because sets 0 and 1 are completely independent and exhibit identical access sequences, we can trace set 0 and double the result.

Trace set 0 for the 8 accesses (0, 128, 256, 128, 0, 128, 256, 128):

• Iteration 1:
  1. Access 0: Miss (Compulsory 1), Cache = [0]
  2. Access 128: Miss (Compulsory 2), Cache = [0, 128]
  3. Access 256: Miss (Compulsory 3), replaces 0, Cache = [128, 256]
  4. Access 128: Hit, Cache = [256, 128]
  5. Access 0: Miss (Conflict 1), replaces 256, Cache = [128, 0]
  6. Access 128: Hit, Cache = [0, 128]
  7. Access 256: Miss (Conflict 2), replaces 0, Cache = [128, 256]
  8. Access 128: Hit, Cache = [256, 128]
     Iteration 1 for Set 0 yields: 3 Compulsory misses, 2 Conflict misses, 3 Hits. Cache end state: [256, 128].

• Iterations 2 through 10 (each iteration starts with cache = [256, 128]):
  1. Access 0: Miss (Conflict), replaces 256, Cache = [128, 0]
  2. Access 128: Hit, Cache = [0, 128]
  3. Access 256: Miss (Conflict), replaces 0, Cache = [128, 256]
  4. Access 128: Hit, Cache = [256, 128]
  5. Access 0: Miss (Conflict), replaces 256, Cache = [128, 0]
  6. Access 128: Hit, Cache = [0, 128]
  7. Access 256: Miss (Conflict), replaces 0, Cache = [128, 256]
  8. Access 128: Hit, Cache = [256, 128]
     Each subsequent iteration experiences exactly 4 Conflict misses and 4 Hits!

Total conflict misses for Set 0 over 10 iterations:

By symmetry, Set 1 also experiences 38 conflict misses.
Total conflict misses across the entire cache: