Cache questions look like unrelated formulas, but nearly all reduce to four operations: find the block or word offset, count sets, find index bits, and give remaining bits to the tag. Attempt each question before reading its explanation, then check the method, not guesses. If formats are unfamiliar, review MCQ, MSQ and NAT first.
1. Map blocks
Use sets=lines/ways, then set=block mod sets. A 64-line 4-way cache has 16 sets. At 8-way it has 8, so index falls from 4 bits to 3, tag gains 1.
Q1. GATE 1999: mapping
The main memory of a computer has 2^m blocks, while the cache has 2^c blocks. If the cache uses a set-associative mapping scheme with 2 blocks per set, then block k of main memory maps to the set:
(a) (k mod m) of the cache
(b) (k mod c) of the cache
(c) (k mod 2^c) of the cache
(d) (k mod 2^(c - 1)) of the cache
Answer: (d). The cache has 2^c blocks and 2 blocks per set, so the number of sets is 2^c / 2 = 2^(c - 1). Substituting that count in block number mod number of sets gives k mod 2^(c - 1). The common trap is using the number of cache blocks instead of the number of cache sets.
Q2. GATE 2014: associativity
If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?
(a) Width of tag comparator
(b) Width of set index decoder
(c) Width of way selection multiplexor
(d) Width of processor to main memory data bus
Answer: (d). From C = S x E x B, fixed capacity C and block size B mean that doubling ways E halves sets S. This may alter index bits, tag bits, comparator width, and way selection. Cache associativity does not determine the external processor-to-main-memory data-bus width, so only that width is guaranteed to remain unaffected.
2. Find address fields
Convert to bytes, then find block size, lines, sets, and tag=address-set-offset.
Q3. ISRO 2017: offset
A two 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 physical address space is 4 GB. The number of bits in the TAG, SET fields are
(a) 20, 7
(b) 19, 8
(c) 20, 8
(d) 21, 9
Answer: (b). Word = 4B, so block = 8x4=32B=2^5: offset 5. Lines = 2^14/2^5=2^9; sets = 2^9/2=2^8: SET 8. Four GB gives 32 address bits; TAG = 32-8-5=19.
Q4. GATE 2007: fields
Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields arerespectively:
(a) 9,6,5
(b) 7, 7, 6
(c) 7, 5, 8
(d) 9, 5, 6
Answer: (d). WORD = log2(64)=6. Sets = 128/4=32=2^5, so LINE/SET = 5. TAG = 20-6-5=9.
For a broader foundation in units, address lines, memory types, and cache purpose, work through Basics of Memory MCQs: 12 Solved Questions with Explanations before returning to these set-associative calculations.
3. Hardware cost
Data capacity excludes metadata. Delay follows tag width; directory entries include status bits.
Q5. GATE 2006: latency
Consider two cache organizations: The first one is 32 KB 2-way set associative with 32-byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k-bit comparator has a latency of k/10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2. The value of h1 is:
(a) 2.4 ns
(b) 2.3 ns
(c) 1.8 ns
(d) 1.7 ns
Answer: (a). Lines = 32KB/32B=1024; sets = 1024/2=512, so index = 9, offset = 5, tag = 32-9-5=18. Hence h1=18/10+0.6=2.4ns.
Q6. GATE 2012: directory
A computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit.
The size of the cache tag directory is
(a) 160 Kbits
(b) 136 Kbits
(c) 40 Kbits
(d) 32 Kbits
Answer: (a). Lines = 256x1024/32=8192; sets = 8192/4=2048: index 11, offset 5, tag 32-11-5=16. Entry = 16+2+1+1=20 bits; directory = 8192x20=163840bits=160Kbits.
4. Derive tag growth
At fixed capacity and block size, K ways move log2K bits from index to tag.
Q7. GATE 2026: tag growth
The size of the physical address space of a processor is 2^32 bytes. The capacity of a cache memory unit is 2^23 bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a ๐พ-way set-associative cache, where ๐พ= 2^๐ฟ and ๐ฟโ{1,2,3}. Let the length of the TAG field be ๐ bits for the direct mapped cache, and ๐ bits for the set-associative cache. Which one of the following options is true?
(a) N=๐+๐ฟ
(b) N=๐-๐ฟ
(c) N=๐+K
(d) N=๐-K
Answer: (a). Offset = 7; direct-mapped lines = 2^23/2^7=2^16, so M=32-16-7=9. With K=2^L, set bits = 16-L; therefore N=32-(16-L)-7=9+L=M+L.
Q8. GATE 2018: symbolic tag
The size of the physical address space of a processor is 2^๐ bytes. The word length is 2^๐ bytes. The capacity of cache memory is 2^๐ bytes. The size of each cache block is 2^๐ words. For a ๐พ-way set-associative cache memory, the length (in number of bits) of the tag field is
(a) ๐ โ ๐ โ log2ย ๐พ
(b) ๐ โ ๐ + log2ย ๐พ
(c) ๐ โ ๐ โ ๐ โ ๐ โ log2ย ๐พ
(d) ๐ โ ๐ โ ๐ โ ๐ + log2ย ๐พ
Answer: (b). Block bytes = 2^(M+W). Index = N-M-W-log2K; offset = M+W. Thus tag = P-(N-M-W-log2K)-(M+W)=P-N+log2K.
5. Split address
Q9 finds widths. Q10 pads a hexadecimal address, then applies them.
Q9. GATE 2008: field widths
Consider a computer with a 4-ways set-associative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. The number of bits in the TAG, SET and WORD fields, respectively are:
(a) 7, 6, 7
(b) 8, 5, 7
(c) 8, 6, 6
(d) 9, 4, 7
Answer: (d). Address = 20 bits; WORD = log2(128)=7. Lines = 8192/128=64; sets = 64/4=16, so SET = 4, TAG = 20-7-4=9.
Q10. GATE 2008: hexadecimal tag
Consider a computer with a 4-ways set-associative mapped cache of the following characterยญistics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. While accessing the memory location 0C795H by the CPU, the contents of the TAG field of the corresponding cache line is
(a) 000011000
(b) 110001111
(c) 00011000
(d) 110010101
Answer: (a). 0C795H=0000 1100 0111 1001 0101. Slice 9/4/7: TAG 000011000 | SET 1111 | WORD 0010101; TAG = 000011000.
6. Trace conflicts and LRU
Discard offset bits, keep the low index bits, and replace only inside that set.
Q11. GATE 2020: same set
A computer system with a word length of 32 bits has a 16 MB byte- addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider the following four physical addresses represented in hexadecimal notation.
\(A1 = 0x42C8A4,ย ย ย ย \ \ \ \ \ \ \ ย ย ย ย A2 = 0x546888,ย ย \ \ \ \ \ \ \ ย ย ย ย ย ย ย A3 = 0x6A289C,ย ย ย ย \ \ \ \ \ \ \ ย ย ย ย ย A4 = 0x5E4880\)
Which one of the following is TRUE ?
(a) \(A1\)ย andย \(A4\) are mapped to different cache sets.
(b) \(A2\)ย andย \(A3\) are mapped to the same cache set.
(c) \(A3\)ย andย \(A4\) are mapped to the same cache set.
(d) \(A1\)ย andย \(A3\) are mapped to the same cache set.
Answer: (b). Offset = 8; sets = 64KB/(256Bx4)=64, so index = 6. Shift 8, keep 6 bits: A1->0x08, A2->0x28, A3->0x28, A4->0x08. A2 and A3 share set 40.
Q12. GATE 2004: LRU
Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is 8, 12, 0, 12, 8
(a) 2
(b) 3
(c) 4
(d) 5
Answer: (c). Four blocks at 2-way give 2 sets. All references are even, hence set 0. MRU to LRU: 8 miss [8]; 12 miss [12,8]; 0 miss, evict 8 [0,12]; 12 hit [12,0]; 8 miss, evict 0 [8,12]. Total = 4.
7. Check traps and practise
Diagnose misses: late word-to-byte conversion; not dividing by ways; confusing lines with sets; omitting status bits; slicing unpadded hex; running LRU outside one set.
Redo misses without notes. Then follow Computer Architecture in GATE Guidance by Sanchit Sir, or take timed GATE Test Series practice. The GATE CS Exam category is the hub.
