Cache Memory Design Questions and Answers

Q: Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, 1K=210, 1M=220 .]

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.

Q: The size of the physical address space of a processor is 232 bytes. The capacity of a cache memory unit is 223 bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a K-way set-associative cache, where K = 2L and L ∈ {1, 2, 3}. Let the length of the TAG field be M bits for the direct mapped cache, and N bits for the set-associative cache.Which one of the following options is true?

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.

Q: For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block.Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte addressable), respectively?

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, 212 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.

Q: The size of the physical address space of a processor is \(2^{P}\) bytes. The word length is \(2^{W}\) bytes. The capacity of cache memory is \(2^{N}\) bytes. The size of each cache block is \(2^{M}\) words. For a \(K\)-way set-associative cache memory, the length (in number of bits) of the tag field is

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.

Q: The term ‘Locality of Reference’ is generally associated with :

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.

Q: A 4-way set-associative cache memory unit with a capacity of 16 kB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. The number of bits in the TAG field is :

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.

Q: A hierarchical memory system that uses cache memory has cache access time of 50 nano seconds, main memory access time of 300 nano seconds, 75% of memory requests are for read, hit ratio of 0.8 for read access and the write-through scheme is used. What will be the average access time of the system, both for read and write requests ?

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.

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, 1K=2¹⁰, 1M=2²⁰ .]

A.\(6 \times 2^{10}\)
B.\(8 \times 2^{10}\)
C.\(2^{12}\)
D.\(2^{14}\)

Exam Year(s)

GATE CS - 2025,

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.

Discuss in Forum

The size of the physical address space of a processor is 2³² bytes. The capacity of a cache memory unit is 2²³ bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a K-way set-associative cache, where K = 2^L and L ∈ {1, 2, 3}. Let the length of the TAG field be M bits for the direct mapped cache, and N bits for the set-associative cache.

Which one of the following options is true?

A.N = M + L
B.N = M - L
C.N = M + K
D.N = M - K

Exam Year(s)

GATE CS - 2026,

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.

Discuss in Forum

For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block.

Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte addressable), respectively?

A.64 KB and 4 KB
B.128 KB and 16 KB
C.64 KB and 8 KB
D.128 KB and 6 KB

Exam Year(s)

GATE CS - 2025,

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.

Discuss in Forum

The size of the physical address space of a processor is \(2^{P}\) bytes. The word length is \(2^{W}\) bytes. The capacity of cache memory is \(2^{N}\) bytes. The size of each cache block is \(2^{M}\) words. For a \(K\)-way set-associative cache memory, the length (in number of bits) of the tag field is

A.\(P - N - \log_{2} K\)
B.\(P - N + \log_{2} K\)
C.\(P - N - M - W - \log_{2} K\)
D.\(P - N - M - W + \log_{2} K\)

Exam Year(s)

GATE CS - 2018,

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.

Discuss in Forum

The term ‘Locality of Reference’ is generally associated with :

A.Secondary Memory
B.Registers
C.Main Memory
D.Cache Memory

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

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.

Discuss in Forum

A 4-way set-associative cache memory unit with a capacity of 16 kB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. The number of bits in the TAG field is :

A.5
B.15
C.20
D.25

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

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.

Discuss in Forum

A hierarchical memory system that uses cache memory has cache access time of 50 nano seconds, main memory access time of 300 nano seconds, 75% of memory requests are for read, hit ratio of 0.8 for read access and the write-through scheme is used. What will be the average access time of the system, both for read and write requests ?

A.157.5 nano sec.
B.110 nano sec.
C.75 nano sec.
D.82.5 nano sec.

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

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.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Cache Memory Design Questions and Answers || Cache Memory Design MCQ Questions and Answers || Cache Memory Design GK Questions and Answers || Cache Memory Design GK MCQ Questions || Cache Memory Design Multiple Choice Questions and Answers || Cache Memory Design GK || GK on Cache Memory Design || Computer Organization and Architecture Questions and Answers || Computer Organization and Architecture MCQ Questions and Answers || Computer Organization and Architecture GK Questions and Answers || GK on Computer Organization and Architecture

Cache Memory Design Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications