Consider a cache (M1) and memory (M2) hierarchy with following characteristics: M1: 16K word, 50 ns Access time; M2: 1M word, 400 ns Access time. Assume 8-word cache blocks and set size 256 words with set associative mapping. (i) Show and explain the mapping between M2 and M1. (ii) Calculate the eff

Cache M1 has 16K words and memory M2 has 1M words. Let a block have 8 words. A set has 256 words, so it holds $256/8 = 32$ blocks, and the cache is 32-way set associative.

(i) Mapping between M2 and M1

The sizes are

$$\text{M1 blocks} = \frac{16384}{8} = 2048, \qquad \text{M1 sets} = \frac{16384}{256} = 64$$

$$\text{M2 blocks} = \frac{2^{20}}{8} = 131072$$

M2 has 1M words, which is $2^{20}$, so the address has 20 bits. The word field has $\log_2 8 = 3$ bits. The set field has $\log_2 64 = 6$ bits. The tag is

$$20 - 6 - 3 = 11 \text{ bits}$$

The block number of M2, taken modulo 64, gives the set of M1. So blocks $0, 64, 128, \ldots$ of M2 go to set 0, blocks $1, 65, 129, \ldots$ go to set 1, and so on. Each set of M1 is shared by $131072/64 = 2048$ blocks of M2, which is $2^{11}$, the number of different tags. Within the set, the block can be placed in any of the 32 places. The 11-bit tag stored with the block tells which of the 2048 blocks is present. To find a word, the set field picks the set. Then the 32 tags in that set are compared with the tag of the address in parallel.

 M2 blocks (131072)         M1 sets (64), 32 blocks each
 block 0, 64, 128 ... ---->  Set 0  [ b ][ b ] ... [ b ]
 block 1, 65, 129 ... ---->  Set 1  [ b ][ b ] ... [ b ]
 ...                         ...
 block 63, 127 ...    ---->  Set 63 [ b ][ b ] ... [ b ]

(ii) Effective memory access time

With hit ratio $h = 0.95$, $t_1 = 50$ ns and $t_2 = 400$ ns, when the cache and memory are accessed in parallel on a miss,

$$t_{eff} = h,t_1 + (1-h),t_2 = 0.95 \times 50 + 0.05 \times 400 = 47.5 + 20 = 67.5 \text{ ns}$$

Therefore the effective access time is 67.5 ns. If the memory is accessed only after the cache misses, the miss time is $50 + 400$ ns, and the time becomes $50 + 0.05 \times 400 = 70$ ns. Either way, it is close to the cache speed and much better than 400 ns.