Cache Memory, Memory Hierarchy and Address Translation Practice Questions for GATE CS

Solve 274+ Cache Memory, Memory Hierarchy and Address Translation practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Cache Memory and Memory Hierarchy

Your Journey Through Cache Memory

Topic 1: Direct-Mapped Cache Addressing

Address decomposition: Tag, Index, Offset. Simple one-to-one mapping. Foundation for all cache concepts.

Topic 2: Set-Associative Cache

K-way associativity. Trade-off between direct-mapped and fully associative. More flexible placement.

Topic 3: Access Sequences and Conflict Misses

Sequential access patterns. Conflict vs capacity misses. Real exam traps.

Topic 4: Write Policies and Replacement

Write-through vs write-back. Write-allocate vs no-write-allocate. LRU and other replacement algorithms.

Topic 5: Cache Performance

Hit rate, miss rate, miss penalty. Effective memory access time (EMAT). Multi-level cache (L1, L2).

Topic 6: TLB and Virtual Memory Integration

Address translation. Cache and TLB interaction. Complete system view.

What you will master by the end:

Calculate tag, index, offset bits for any cache configuration
Analyze cache performance and hit rates
Understand conflict misses and replacement policies
Solve multi-level cache problems
Connect cache with virtual memory systems

What is a Direct-Mapped Cache?

The Core Idea

A direct-mapped cache is the simplest cache organization where each memory block maps to exactly one specific cache line.

Cache Line = B mod N

Where $B$ is block number and $N$ is number of lines

Why This Matters

Fast lookup: Hardware checks only one location
Simple design: Minimal comparison logic needed
Conflict problem: Two different memory blocks may compete for the same cache line

Visual Intuition

Main MemoryCache

Block 0→ Line 0

Block 1→ Line 1

Block 2→ Line 2

Block 3→ Line 3

Block 4→ Line 0 (conflict)

Block 5→ Line 1 (conflict)

Key takeaway: One memory block has one home in the cache. No choices, no flexibility.

Cache Memory, Memory Hierarchy and Address Translation: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Computer Organization and Architecture MCQ

A processor uses 32-bit addresses and has a 128 KB, 8-way set-associative cache. The block size is not specified but is known to be a power of two. What is the number of bits in the tag field?

A.
15
B.
16
C.
20
D.
18

Correct Answer:

Step-by-Step Solution

Key idea: When block size is not given, use the cancellation trick — block size terms cancel out in the calculation. The Cancellation Trick:

Tag = Address - lo g_{2} (Cache size) + lo g_{2} (K)

Step 1: Apply the formula. Tag =

32 - lo g_{2} (128 KB) + lo g_{2} (8)

Tag =

32 - lo g_{2} (2^{17}) + lo g_{2} (2^{3})

Tag =

32 - 17 + 3

Tag =

18

bits. Why this works: Index bits =

lo g_{2} (Sets) = lo g_{2} (\frac{Cache / B}{K}) = lo g_{2} (Cache) - lo g_{2} (B) - lo g_{2} (K)

Offset bits =

lo g_{2} (B)

Index + Offset =

lo g_{2} (Cache) - lo g_{2} (B) - lo g_{2} (K) + lo g_{2} (B) = lo g_{2} (Cache) - lo g_{2} (K)

Tag = Address - (Index + Offset) = Address -

lo g_{2} (Cache) + lo g_{2} (K)

Answer: 18 bits.

Question 2 · Computer Organization and Architecture MCQ

A processor uses 32-bit addresses and has a 32 KB, 4-way set-associative cache. The block size is not specified but is known to be a power of two. What is the number of bits in the tag field?

A.
17
B.
18
C.
19
D.
20

Correct Answer:

Step-by-Step Solution

Key idea: When block size is not given, use the cancellation trick — block size terms cancel out in the calculation. The Cancellation Trick:

Tag = Address - lo g_{2} (Cache size) + lo g_{2} (K)

Step 1: Apply the formula. Tag =

32 - lo g_{2} (32 KB) + lo g_{2} (4)

Tag =

32 - lo g_{2} (2^{15}) + lo g_{2} (2^{2})

Tag =

32 - 15 + 2

Tag =

19

bits. Answer: 19 bits.

Question 3 · Computer Organization and Architecture MCQ

An urn contains 3 red and 2 black balls. A Polya Urn process is run for $n$ draws. For how many values of $n \in {1, 2, 3, 4, 5}$ is the probability of drawing a red ball on the $n$ -th draw strictly greater than $\frac{3}{5}$ ?

A.
0
B.
1
C.
3
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: The martingale property of the Polya Urn process.

Step 1: The martingale property states that the expected proportion of red balls remains constant throughout the process.

Step 2: Consequently, the probability of drawing a red ball at any specific step $n$ is exactly equal to the initial proportion of red balls.

Step 3: Initial proportion = $\frac{3}{3 + 2} = \frac{3}{5}$ .

Step 4: Since the probability is always exactly $\frac{3}{5}$ , it is never strictly greater than $\frac{3}{5}$ for any $n$ .

Answer: 0.

Question 4 · Computer Organization and Architecture MCQ

In a Polya Urn process starting with 2 red and 3 black balls, what is the expected number of red balls drawn in 10 draws?

A.
2
B.
4
C.
5
D.
6

Correct Answer:

Step-by-Step Solution

Key idea: Linearity of expectation and the constant probability of drawing red.

Step 1: The probability of drawing a red ball at any specific step $i$ is the initial proportion $p = \frac{r}{r + b}$ .

Step 2: Here, $p = \frac{2}{2 + 3} = \frac{2}{5}$ .

Step 3: Let $X_{i}$ be the indicator variable for drawing red on step $i$ . $E [X_{i}] = p = \frac{2}{5}$ .

Step 4: The total number of red balls drawn in $n = 10$ draws is $X = \sum_{i = 1}^{10} X_{i}$ .

Step 5: By linearity of expectation, $E [X] = \sum_{i = 1}^{10} E [X_{i}] = 10 \times \frac{2}{5} = 4$ .

Answer: 4.

Question 5 · Computer Organization and Architecture MCQ

An urn initially contains 2 red and 8 black balls. A Polya Urn process is run. For how many values of $n \in {10, 20, 50, 100, 1000}$ is the expected proportion of red balls in the urn exactly $\frac{1}{5}$ ?

A.
1
B.
3
C.
4
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: The martingale property of the Polya Urn process.

Step 1: The martingale property states that the expected proportion of red balls after $n$ draws is exactly equal to the initial proportion.

Step 2: Initial proportion = $\frac{2}{2 + 8} = \frac{2}{10} = \frac{1}{5}$ .

Step 3: Therefore, for ANY number of draws $n$ , the expected proportion is exactly $\frac{1}{5}$ .

Step 4: Since this holds for all $n$ , it holds for all 5 values in the set.

Answer: 5.

Question 6 · Computer Organization and Architecture MCQ

Consider the following cache tagging strategies:

VIVT (Virtual Index, Virtual Tag)
PIPT (Physical Index, Physical Tag)
VIPT (Virtual Index, Physical Tag)

How many of these strategies inherently avoid the synonyms problem without requiring the cache index size to be strictly less than or equal to the page size?

A.
0
B.
1
C.
2
D.
3

Correct Answer:

Step-by-Step Solution

Key idea: Synonyms occur when different virtual addresses map to the same physical address but different cache indices.

Step 1: VIVT uses virtual indices. Different VAs mapping to the same PA can have different indices, so it suffers from synonyms.

Step 2: PIPT uses physical indices. Since the PA is the same, the index is the same. It inherently avoids synonyms without any size constraints.

Step 3: VIPT uses virtual indices. It only avoids synonyms if the virtual index bits are a subset of the page offset bits (which are identical for the same PA). This requires the index size constraint.

Step 4: Only PIPT (1 strategy) inherently avoids synonyms without the constraint.

Answer: B

Question 7 · Computer Organization and Architecture MCQ

For a computer system with a 16-bit physical address, the address is divided into tag, index, and offset fields. If the block size is 16 bytes, what is the maximum possible number of index bits, assuming the tag field must be at least 1 bit?

A.
11
B.
12
C.
15
D.
16

Correct Answer:

Step-by-Step Solution

Key idea: This is an observation and boundary question, recognisable because it asks for a "maximum possible" value under a specific constraint (tag $\geq$ 1 bit).

Step 1: Identify total address bits = 16.

Step 2: Calculate offset bits. Block size = 16 bytes = $2^{4}$ bytes, so offset = 4 bits.

Step 3: Apply the address decomposition formula: $Address = Tag + Index + Offset$ .

Step 4: Substitute knowns: $16 = Tag + Index + 4$ . This simplifies to $Tag + Index = 12$ .

Step 5: To maximize the index, we must minimize the tag. The constraint states tag $\geq$ 1 bit. So, minimum tag = 1.

Step 6: Maximum index = $12 - 1 = 11$ bits.

Answer: 11 bits.

Question 8 · Computer Organization and Architecture MCQ

In a direct-mapped cache system, the specific cache line to which a main memory block is mapped is uniquely determined by which part of the memory address?

A.
Tag field
B.
Index field
C.
Offset field
D.
Valid bit

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct formula question, recognisable because it asks for the specific address field responsible for the cache line mapping.

Step 1: Recall the address decomposition for a direct-mapped cache. The physical address is split into Tag, Index, and Offset.

Step 2: The Index field directly selects the cache line. The mapping formula is $Cache Line = Block Number mod Number of Lines$ , which is exactly what the Index bits represent.

Step 3: The Tag identifies the block, the Offset identifies the byte, and the Valid bit is metadata, not part of the address mapping.

Answer: The Index field.

Question 9 · Computer Organization and Architecture MCQ

A system uses a 20-bit physical address and a direct-mapped cache with a block size of 32 bytes. If the cache is designed to have at least 4 lines, what is the maximum possible number of bits in the tag field?

A.
12
B.
13
C.
15
D.
18

Correct Answer:

Step-by-Step Solution

Key idea: This is an observation and boundary question, recognisable because it asks for a "maximum possible" value under a specific constraint (at least 4 lines).

Step 1: Identify total address bits = 20.

Step 2: Calculate offset bits. Block size = 32 bytes = $2^{5}$ bytes, so offset = 5 bits.

Step 3: Apply the address decomposition formula: $Address = Tag + Index + Offset$ .

Step 4: Substitute knowns: $20 = Tag + Index + 5$ . This simplifies to $Tag + Index = 15$ .

Step 5: To maximize the tag, we must minimize the index. The constraint states "at least 4 lines". Since $4 = 2^{2}$ , the minimum index bits = 2.

Step 6: Maximum tag = $15 - 2 = 13$ bits.

Answer: 13 bits.

Question 10 · Computer Organization and Architecture MCQ

A direct-mapped cache has a capacity of 64 KB and a block size of 32 bytes. The physical address is 32 bits. How many bits are required in total to store all the tag values for the entire cache?

A.
$16 im es 2^{11}$
B.
$15 im es 2^{11}$
C.
$16 im es 2^{10}$
D.
$17 im es 2^{11}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a casework question, recognisable because it requires calculating multiple fields (lines, index, offset, tag) and then combining them to find a total storage metric (total tag memory).

Step 1: Calculate total cache lines. Cache size = 64 KB = $2^{16}$ bytes. Block size = 32 bytes = $2^{5}$ bytes. Lines = $2^{16} / 2^{5} = 2^{11} = 2048$ .

Step 2: Calculate index bits. $lo g_{2} (2^{11}) = 11$ bits.

Step 3: Calculate offset bits. $lo g_{2} (2^{5}) = 5$ bits.

Step 4: Calculate tag bits. $Tag = 32 - 11 - 5 = 16$ bits.

Step 5: Calculate total tag memory. Total bits = Tag bits $\times$ Number of lines = $16 \times 2^{11}$ .

Answer: $16 \times 2^{11}$ bits.

Try a question

Login to view the complete practice questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Cache Memory, Memory Hierarchy and Address Translation Practice Questions for GATE CS

Chapter Roadmap: Cache Memory and Memory Hierarchy

Your Journey Through Cache Memory

What you will master by the end:

What is a Direct-Mapped Cache?

The Core Idea

Why This Matters

Visual Intuition

Cache Memory, Memory Hierarchy and Address Translation: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit