chapter

Cache Memory, Memory Hierarchy and Address Translation Short Notes for GATE CS

Cache Memory, Memory Hierarchy and Address Translation short notes for GATE CS: 6 study cards covering concepts, formulas, shortcuts and exam traps, plus solv

cache memory memory hierarchy and address translation short notes

Quick Reference: Direct-Mapped Cache

.smart-card { font-family: system-ui, -apple-system, sans-serif; color: var(--color-text); background: var(--color-bg); padding: 1.5rem; border-radius: 12px; line-height: 1.6; } .formula-grid { display: grid; grid-template-columns: 1fr 1fr; gap: 1rem; margin-bottom: 1.5rem; } .formula-box { background: rgba(100, 150, 200, 0.05); padding: 1rem; border-radius: 8px; text-align: center; } .formula-label { font-size: 0.8rem; color: var(--color-muted); margin-bottom: 0.5rem; text-transform: uppercase; letter-spacing: 0.5px; } .key-points { background: rgba(100, 150, 200, 0.1); padding: 1rem; border-radius: 8px; margin-bottom: 1.5rem; } .checklist { list-style: none; padding: 0; margin: 0; } .checklist li { padding-left: 1.8rem; position: relative; margin-bottom: 0.6rem; font-size: 0.95rem; } .checklist li::before { content: ''; position: absolute; left: 0; top: 0.2rem; width: 16px; height: 16px; border: 2px solid var(--color-primary); border-radius: 50%; } Essential Formulas Lines \frac{Cache}{Block} Index lo g_{2} (Lines) Offset lo g_{2} (Block) Tag Addr - I - O Key Points: Direct-mapped: one block \to one line "Total tag storage" \neq "tag bits" Cache size \leq main memory size Problem-Solving Checklist Identify given information Determine addressing mode (byte/word) Calculate number of lines Find index and offset bits Calculate tag bits by subtraction Verify: Tag + Index + Offset = Address

Quick Reference: Set-Associative Cache

.sc13 { font-family: system-ui, sans-serif; color: var(--color-text); background: var(--color-bg); padding: 1.5rem; border-radius: 12px; } .sc13 h2 { margin-top: 0; font-size: 1.4rem; } .sc13-grid { display: grid; grid-template-columns: 1fr 1fr; gap: 0.8rem; margin-bottom: 1.5rem; } .sc13-box { background: color-mix(in srgb, var(--color-primary) 5%, transparent); padding: 0.8rem; border-radius: 8px; text-align: center; } .sc13-label { font-size: 0.75rem; color: var(--color-muted); text-transform: uppercase; } .sc13-checklist { list-style: none; padding: 0; margin: 0; } .sc13-checklist li { padding-left: 2rem; position: relative; margin-bottom: 0.6rem; font-size: 0.95rem; } .sc13-checklist li::before { content: ''; position: absolute; left: 0; top: 0.2rem; width: 16px; height: 16px; border: 2px solid var(--color-primary); border-radius: 50%; } .sc13-checklist li.checked::before { background: var(--color-primary); } .sc13-checklist li { animation: sc13-check 0.5s forwards; opacity: 0; } @keyframes sc13-check { to { opacity: 1; } } .sc13-checklist li:nth-child(1) { animation-delay: 0.1s; } .sc13-checklist li:nth-child(2) { animation-delay: 0.2s; } .sc13-checklist li:nth-child(3) { animation-delay: 0.3s; } .sc13-checklist li:nth-child(4) { animation-delay: 0.4s; } .sc13-checklist li:nth-child(5) { animation-delay: 0.5s; } Quick Reference Lines C / B Sets Lines / K Index lo g_{2} (Sets) Tag A - I - O Problem-Solving Checklist Identify given info Determine forward/reverse Calculate lines & sets Find index & offset Calculate tag or K

Conflict Misses — Quick Checklist

Six-step checklist Word address? \to multiply by word size in bytes. Find B (block size) and L (number of lines). Line = (address \div B) mod L for each address. Group addresses by line. Simulate or use shortcut: 1 address/line \to 1 miss then hits; k addresses/line \to every access misses. Sum hits and misses across all rounds. Remember: conflict miss = two different blocks, one line, alternating access. That is the whole game.

3 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

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?

Question 2

Level 1: Warm-up

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?

Question 3

Level 1: Warm-up

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} ?

Question 4

Level 1: Warm-up

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?

Question 5

Level 1: Warm-up

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} ?

Question 6

Level 1: Warm-up

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?

Question 7

Level 1: Warm-up

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?

Question 8

Level 1: Warm-up

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?

Question 9

Level 1: Warm-up

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?

Question 10

Level 1: Warm-up

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?

Free preview ends here

Login to view the complete short notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Cache Memory, Memory Hierarchy and Address Translation Short Notes for GATE CS

Cache Memory, Memory Hierarchy and Address Translation short notes for GATE CS: 6 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Quick Reference: Direct-Mapped Cache

Essential Formulas

Lines

\frac{Cache}{Block}

Index

lo g_{2} (Lines)

Offset

lo g_{2} (Block)

Tag

Addr - I - O

Key Points:

Direct-mapped: one block → one line
"Total tag storage" ≠ "tag bits"
Cache size ≤ main memory size

Problem-Solving Checklist

Identify given information
Determine addressing mode (byte/word)
Calculate number of lines
Find index and offset bits
Calculate tag bits by subtraction
Verify: Tag + Index + Offset = Address

Quick Reference: Set-Associative Cache

Quick Reference

Lines

C / B

Sets

Lines / K

Index

lo g_{2} (Sets)

Tag

A - I - O

Problem-Solving Checklist

Identify given info
Determine forward/reverse
Calculate lines & sets
Find index & offset
Calculate tag or $K$

Conflict Misses — Quick Checklist

Six-step checklist

Word address? → multiply by word size in bytes.
Find $B$ (block size) and $L$ (number of lines).
Line = (address ÷ B) mod L for each address.
Group addresses by line.
Simulate or use shortcut: 1 address/line → 1 miss then hits; k addresses/line → every access misses.
Sum hits and misses across all rounds.

Remember: conflict miss = two different blocks, one line, alternating access. That is the whole game.

Write Policies — Quick Reference

Write policies

Write-through: write hit → update cache + memory
Write-back: write hit → update cache, set dirty bit

Allocation policies

Write-allocate: write miss → load into cache, then write
No-write-allocate: write miss → write to memory, cache unchanged

Replacement policies

LRU: evict least recently accessed
FIFO: evict oldest loaded
Random: evict any line randomly

Remember: write-back needs dirty bit, write-through does not. Writebacks occur only in write-back on dirty eviction.

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.

cache memory memory hierarchy and address translation short notes

Quick Reference: Direct-Mapped Cache

Essential Formulas

Problem-Solving Checklist

Quick Reference: Set-Associative Cache

Quick Reference

Problem-Solving Checklist

Conflict Misses — Quick Checklist

Try a question

Login to view the complete short notes

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 Short Notes for GATE CS

Quick Reference: Direct-Mapped Cache

Essential Formulas

Problem-Solving Checklist

Quick Reference: Set-Associative Cache

Quick Reference

Problem-Solving Checklist

Conflict Misses — Quick Checklist

Write Policies — Quick Reference

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 short notes in this unit