Cache Memory Design Questions and Answers

Answer: A

The tag storage is \(6 \times 2^{10}\) bits.

Split the 20-bit address for a direct-mapped cache:

\[ \begin{aligned} \text{offset} &= \log_{2}16 = 4\ \text{bits} \\ \text{lines} &= \frac{16\text{K}}{16} = 2^{10} \Rightarrow \text{index} = 10 \\ \text{tag} &= 20 - 10 - 4 = 6\ \text{bits} \end{aligned} \]

Each of the \(2^{10}\) lines stores one 6-bit tag, so the tags take \(6 \times 2^{10}\) bits in all.

\(8 \times 2^{10}\) would need an 8-bit tag, which happens if the index or offset is miscounted. \(2^{12}\) and \(2^{14}\) correspond to 4-bit and 16-bit tags per line, neither of which fits a 20-bit address split this way.

Answer: A

The relation is N = M + L.

The block offset needs 7 bits (128 = \(2^{7}\)), and the cache holds \(2^{23}/2^{7} = 2^{16}\) blocks.

\[ \begin{aligned} \text{Direct mapped: } M &= 32 - 16 - 7 = 9 \\ \text{sets} &= 2^{16}/2^{L} = 2^{16-L} \\ \text{Set-assoc.: } N &= 32 - (16-L) - 7 = 9 + L \end{aligned} \]

Each doubling of associativity halves the number of sets, removing one index bit and adding it to the tag, so the tag grows by L bits, not by K = \(2^{L}\). The tag never shrinks with higher associativity, which rules out both subtraction options.

Answer: A

The sizes are 64 KB of main memory and 4 KB of cache.

With one-byte blocks there is no offset field, so the address consists of the tag and the index only:

\[ \begin{aligned} \text{address bits} &= 4 + 12 = 16 \\ \text{main memory} &= 2^{16}\ \text{B} = 64\ \text{KB} \\ \text{cache} &= 2^{12} \times 1\ \text{B} = 4\ \text{KB} \end{aligned} \]

The cache has one block per index value, 2¹² blocks of one byte each, and the question says nothing else (tags or valid bits) is counted. 128 KB would need a 17-bit address, and caches of 8 KB, 16 KB or 6 KB do not match a 12-bit index with one-byte blocks.

Answer: B

The tag field has \(P - N + \log_{2} K\) bits.

The physical address has \(P\) bits. A block is \(2^{M}\) words of \(2^{W}\) bytes, so the block offset is \(M + W\) bits. The cache holds \(2^{N} / 2^{M+W}\) blocks, grouped \(K\) to a set:

\[ \begin{aligned} \text{sets} &= 2^{N - M - W} / K \\ \text{index} &= N - M - W - \log_{2} K \\ \text{tag} &= P - \text{index} - (M + W) \\ &= P - N + \log_{2} K \end{aligned} \]

Check: a direct-mapped cache (\(K = 1\)) gives a tag of \(P - N\) bits, and higher associativity means fewer sets and so a longer tag. \(P - N - \log_{2} K\) gets that direction wrong, and the options with \(- M - W\) subtract the block offset twice.

Answer: D

Locality of reference is associated with Cache Memory.

Programs tend to reuse recently used data and instructions (temporal locality) and to use items near those recently used (spatial locality), as in loops and arrays. A cache works because of this: by keeping recently used blocks in a small fast memory, it satisfies most references without going to main memory.

The principle applies to the whole memory hierarchy, including virtual memory, but it is the concept on which cache design rests and with which it is generally associated. Registers, main memory and secondary storage are not chosen because of locality in the same way.

Answer: C

The TAG field has 20 bits.

\[ \begin{aligned} \text{block} &= 8 \times 4 = 32 \text{ bytes} \Rightarrow 5 \text{ offset bits} \\ \text{blocks} &= 16\text{ KB} / 32 = 512 \\ \text{sets} &= 512 / 4 = 128 \Rightarrow 7 \text{ index bits} \\ \text{address} &= 4\text{ GB} = 2^{32} \Rightarrow 32 \text{ bits} \\ \text{tag} &= 32 - 7 - 5 = 20 \end{aligned} \]

The physical address splits into tag, set index and byte offset. 5 is only the width of the offset, and 15 and 25 do not come from a correct split of the 32-bit address.

Answer: A

The average access time is 157.5 nano sec.

Reads: a hit takes the cache time, 50 ns; on a miss the cache is checked and then main memory is read, 50 + 300 = 350 ns. Writes: with write-through, every write goes to main memory, 300 ns.

\[ \begin{aligned} t_{read} &= 0.8(50) + 0.2(350) = 110 \\ t &= 0.75(110) + 0.25(300) \\ &= 82.5 + 75 = 157.5\ \text{ns} \end{aligned} \]

110 ns is the read time alone and 82.5 ns is the read share only, both ignoring the writes; 75 ns is just the write share.