GATE CS

Memory hierarchy, performance and cache mapping

A memory hierarchy gives the processor close to cache speed at close to main-memory cost per bit, and it works because programs show locality of reference. Hit ratio and average access time measure how well it works. The access time depends on a convention you must fix first: hierarchical access (a miss costs the cache check plus the memory time) or simultaneous access (a miss costs the memory time only). Direct-mapped, set-associative and fully associative mapping decide where a block may live and how the address splits into tag, index and offset. Replacement and write policies decide what happens on a conflict and on a write. The same average-time reasoning extends to multilevel caches (with local and global miss rates), interleaved main memory, memory built from smaller chips, and disk access time. Knowing each formula's exact conditions is what separates a right answer from a near miss: hierarchical vs simultaneous, local vs global miss rate, average vs worst case.

22 previous-year questions · 21 solved · 5 practice questions

Memory Hierarchy and Average Access Time

A computer's memory system is built as a hierarchy: registers, cache, main memory, secondary storage. The reason is that fast memory costs more per bit and cheap memory is slow. A hierarchy works because programs show locality of reference. Temporal locality: a location used now is likely to be used again soon. Spatial locality: locations near it are likely to be used soon. Two quantities describe how well the hierarchy works: the hit ratio and the average access time. The average access time depends on one convention that must be fixed before calculating. Is the lower level accessed only after a cache miss has been detected (hierarchical, or serial, access), or at the same time as the cache (simultaneous, or parallel, access)?

HIT RATIO

h = \frac{N _{hi t}}{N _{hi t} + N _{mi ss}}

The fraction of memory references satisfied directly by the cache. Miss ratio $= 1 - h$ .

AVERAGE ACCESS TIME, HIERARCHICAL (SERIAL) ACCESS

T_{a v g} = h \cdot T_{c} + (1 - h) \cdot (T_{c} + T_{m}) = T_{c} + (1 - h) \cdot T_{m}

Use this when main memory is accessed only after the cache lookup has missed, so a miss costs $T_{c} + T_{m}$ . $T_{m}$ is the time to get the needed data from main memory. If the question says a whole block is transferred into the cache on a miss and gives the block-transfer time, use that time as the miss cost in place of a single-word $T_{m}$ .

AVERAGE ACCESS TIME, SIMULTANEOUS ACCESS

T_{a v g} = h \cdot T_{c} + (1 - h) \cdot T_{m}

Use this when the cache and main memory are looked up in parallel. On a miss, the cache-check time is hidden inside the longer memory access and is not added again.

AVERAGE ACCESS TIME FROM A STATED MISS PENALTY

T_{a v g} = T_{hi t} + (1 - h) \cdot T_{p e na l t y}

The miss penalty is the EXTRA time a miss costs on top of the hit time. With hierarchical access and $T_{p e na l t y} = T_{m}$ , this is the same as the hierarchical formula above.

WORKED EXAMPLE

A cache has $T_{c} = 4$ ns and main memory has $T_{m} = 100$ ns. Access is hierarchical (serial), and the hit ratio is $0.95$ . Find the average access time.

Solution

Hierarchical formula: $T_{a v g} = h T_{c} + (1 - h) (T_{c} + T_{m})$ .
$T_{a v g} = 0.95 \times 4 + 0.05 \times (4 + 100) = 3.8 + 0.05 \times 104 = 3.8 + 5.2 = 9.0$ ns.
Check with the simplified form: $T_{c} + (1 - h) T_{m} = 4 + 0.05 \times 100 = 9.0$ ns.

Answer: 9.0 ns

EXAM TIP

Before using a formula, decide which access model the question describes. Under hierarchical access a miss costs $T_{c} + T_{m}$ ; under simultaneous access it costs $T_{m}$ . The two give different answers. In the example above, simultaneous access would give $0.95 \times 4 + 0.05 \times 100 = 8.8$ ns, not 9.0 ns. If the question leaves the model open, write down the assumption you used.

Cache Mapping Techniques and Address Structure

A cache holds copies of a small subset of main-memory blocks. Direct-mapped: each memory block maps to exactly one cache line. It is the simplest and needs only one tag comparison, but blocks that map to the same line evict each other (conflict misses). Fully associative: a block may go into any line. There are no conflict misses, but every line's tag must be compared in parallel, which is expensive hardware. Set-associative ( $k$ -way): the cache is divided into sets of $k$ lines each. A block maps to exactly one set but can occupy any of the $k$ lines within it. Direct-mapped and fully associative are the special cases $k = 1$ and $k = number of lines$ .

Splitting a physical address into tag / index / offset

Offset (block-offset) bits $= lo g_{2} (block size in bytes)$ . They select a byte within a block (byte-addressable memory assumed).
Number of sets $= \frac{cache size}{block size \times k}$ , where $k$ is the associativity.
Index bits $= lo g_{2} (number of sets)$ . They select the set a block maps to. For a direct-mapped cache, sets = lines. A fully associative cache has zero index bits.
Tag bits $= address bits - index bits - offset bits$ . The tag identifies which of the many blocks that map to that set is currently stored there.
Block number $= ⌊ address / block size ⌋$ . Set (or line) number $= block number mod number of sets$ .

Property	Direct-mapped	Set-associative ( $k$ -way)	Fully associative
Where a block can go	Exactly 1 line	Exactly 1 set, any of its $k$ lines	Any line
Index bits	$lo g_{2} (lines)$	$lo g_{2} (sets)$	0
Conflict misses (same cache size)	Typically the most	Typically fewer as $k$ grows	None (only compulsory and capacity)
Tag comparators needed	1	$k$ (plus a $k$ -to-1 multiplexer)	One per line
Hit time (same cache size)	Typically lowest	In between	Typically highest

SIZE OF THE TAG DIRECTORY

Tag memory (bits) = (number of lines) \times (tag bits + extra bits per line)

Number of lines $=$ cache size $\div$ block size, whatever the associativity. The extra bits per line are whatever the question specifies. Typically that is a valid bit, a dirty bit for a write-back cache, and any replacement bits.

WORKED EXAMPLE

A cache is 256 KB, 4-way set-associative, with a 64-byte block, on a system with a 36-bit physical address ( $1 K = 2^{10}$ ). Find the tag, index and offset field widths.

Solution

Offset $= lo g_{2} (64) = 6$ bits.
Number of sets $= \frac{256 \times 1024}{64 \times 4} = \frac{262144}{256} = 1024 = 2^{10}$ , so index $= 10$ bits.
Tag $= 36 - 10 - 6 = 20$ bits.

Answer: Tag = 20 bits, Index = 10 bits, Offset = 6 bits

WORKED EXAMPLE

A 32 KB, 4-way set-associative write-back cache has 32-byte blocks. The physical address is 32 bits ( $1 K = 2^{10}$ ). Each line stores its tag, one valid bit and one dirty bit. Find the total size of the tag memory in bits.

Solution

Offset $= lo g_{2} 32 = 5$ bits.
Number of lines $= 2^{15} / 2^{5} = 1024$ . Number of sets $= 1024/4 = 256 = 2^{8}$ , so index $= 8$ bits.
Tag $= 32 - 8 - 5 = 19$ bits.
Tag memory $= 1024 \times (19 + 1 + 1) = 1024 \times 21 = 21504$ bits.

Answer: 21,504 bits

EXAM TIP

A direct-mapped cache is a 1-way set-associative cache. A fully associative cache is a set-associative cache with only 1 set. The same index and offset formulas cover all three: put $k = 1$ , or number of sets $= 1$ .

Replacement and Write Policies

A replacement policy is needed only when a block has more than one possible line to go into, that is, in set-associative and fully associative caches. A direct-mapped cache has no choice to make.

Common replacement policies

LRU (Least Recently Used): evict the line in the set that was accessed longest ago. LRU is a stack algorithm. For the same reference string, a fully associative LRU cache with more lines never has more misses than one with fewer lines. The same holds for adding ways to each set while keeping the same sets.
FIFO (First-In-First-Out): evict the line that has been resident longest, regardless of recent use. It is simple to implement (a pointer per set), but it can show Belady's anomaly: more lines, more misses, for some reference strings.
Random: evict a randomly chosen line in the set. It is the cheapest in hardware.
Optimal: evict the block whose next use is farthest in the future. It gives the fewest possible misses but needs knowledge of future references, so it serves only as a yardstick.

Aspect	Write-through	Write-back
When memory is updated	On every write to the cache	Only when a dirty block is evicted
Needs a dirty bit?	No: a cached block is never newer than memory	Yes: it marks a block as modified
Memory writes	One memory write per CPU write	One block write-back per dirty eviction, however many times the block was written
On eviction	Nothing to write back	Write back the block only if it is dirty

Write-miss policies (combine with the table above)

Write-allocate: on a write miss, the block is first fetched into the cache, then the write is applied to the cached copy. Typically paired with write-back.
No-write-allocate (write-around): on a write miss, the write goes straight to main memory and the block is NOT brought into the cache. Typically paired with write-through.

WORKED EXAMPLE

A fully associative cache has 2 lines and is initially empty. Count the misses under FIFO and under LRU for the block reference string A, B, A, C, A.

Solution

FIFO: A miss; B miss; A hit; C miss, evicting A (the oldest arrival); A miss, evicting B. Total 4 misses.
LRU: A miss; B miss; A hit (A becomes most recent); C miss, evicting B (least recently used); A hit. Total 3 misses.

Answer: FIFO 4 misses, LRU 3 misses

EXAM TIP

The statement "FIFO performs at least as well as LRU on every reference string" is false, and the example above is a counterexample. Separately, FIFO can show Belady's anomaly. LRU, being a stack algorithm, cannot.

Types of Cache Misses and Multilevel Caches

The three Cs of cache misses

Compulsory (cold) miss: the first reference to a block. The block has never been in the cache, so this miss occurs however the cache is organised.
Capacity miss: a miss that would still occur in a fully associative cache of the same size, because the program's working set does not fit. A bigger cache reduces capacity misses.
Conflict miss: a miss that occurs only because the block was evicted by other blocks mapping to the same set, while the cache as a whole had room. Higher associativity reduces conflict misses, and a fully associative cache has none by definition.

AVERAGE MEMORY ACCESS TIME, TWO-LEVEL CACHE

A M A T = T_{L 1} + M R_{L 1} (T_{L 2} + M R_{L 2} \cdot T_{m e m})

Model: L2 is accessed only on an L1 miss, and main memory only on an L2 miss, with each lower-level time added on top (hierarchical). $M R_{L 2}$ here is the LOCAL miss rate of L2: misses in L2 $\div$ accesses that reach L2 (the L1 misses). It is not the global miss rate.

GLOBAL MISS RATE OF L2

M R_{L 2, g l o ba l} = M R_{L 1} \times M R_{L 2, l oc a l}

The fraction of ALL CPU accesses that miss in both L1 and L2 and go to main memory. If a question gives a global L2 miss rate, divide it by $M R_{L 1}$ to get the local rate before using the AMAT formula.

TWO-LEVEL AVERAGE ACCESS TIME, WRITTEN LEVEL BY LEVEL

T_{a v g} = h_{1} T_{1} + (1 - h_{1}) h_{2} (T_{1} + T_{2}) + (1 - h_{1}) (1 - h_{2}) (T_{1} + T_{2} + T_{m})

The same hierarchical model, with $h_{1}$ the L1 hit ratio and $h_{2}$ the LOCAL L2 hit ratio. Expanding gives $T_{1} + (1 - h_{1}) T_{2} + (1 - h_{1}) (1 - h_{2}) T_{m}$ , which is the AMAT formula above.

WORKED EXAMPLE

L1: hit time 1 ns, local miss rate 10%. L2: hit time 8 ns, local miss rate 20%. Main memory: 150 ns. Access is hierarchical at each level. Find the AMAT and the global miss rate of L2.

Solution

$A M A T = T_{L 1} + M R_{L 1} (T_{L 2} + M R_{L 2} \cdot T_{m e m})$ .
$= 1 + 0.10 \times (8 + 0.20 \times 150) = 1 + 0.10 \times (8 + 30) = 1 + 0.10 \times 38 = 1 + 3.8 = 4.8$ ns.
Global miss rate of L2 $= 0.10 \times 0.20 = 0.02$ , so 2% of all accesses reach main memory.

Answer: AMAT = 4.8 ns; global L2 miss rate = 2%

EXAM TIP

Higher associativity reduces conflict misses but tends to raise hit time (more tag comparisons and a wider multiplexer). A bigger cache reduces capacity misses but not compulsory misses. A larger block size reduces compulsory misses by exploiting spatial locality. With a fixed cache size, though, it means fewer blocks, and a larger block also raises the miss penalty.

Main Memory: Building It from Chips, and Interleaving

CHIPS NEEDED TO BUILD AN M X W MEMORY FROM M X B CHIPS

chips = \frac{M}{m} \times \frac{w}{b}

Here $M$ and $m$ are numbers of words, and $w$ and $b$ are bits per word. Each row places $w / b$ chips side by side to form the full word width. $M / m$ rows are stacked to supply all the words. The memory needs $lo g_{2} M$ address lines. Each chip takes the low $lo g_{2} m$ of them, and the remaining $lo g_{2} (M / m)$ high-order bits drive a decoder that selects one row.

WORKED EXAMPLE

A $64 K \times 16$ memory is to be built from $16 K \times 8$ chips ( $1 K = 2^{10}$ ). How many chips are needed, how many address lines does the memory have, and how are they used?

Solution

Chips $= \frac{64 K}{16 K} \times \frac{16}{8} = 4 \times 2 = 8$ : 4 rows of 2 chips.
Address lines $= lo g_{2} (64 \times 1024) = lo g_{2} 2^{16} = 16$ .
Each chip needs $lo g_{2} (16 \times 1024) = 14$ lines. The remaining $16 - 14 = 2$ high-order bits go to a 2-to-4 decoder that selects one of the 4 rows.

Answer: 8 chips; 16 address lines (14 to every chip, 2 to a 2-to-4 decoder)

Main memory can be built from several independent banks (modules), so that several word accesses overlap instead of happening one after another. In low-order interleaving, consecutive addresses go to different banks: the bank number is given by the low-order address bits. This suits fetching a sequential block such as a cache line, because the words sit in different banks and can be accessed together. In high-order interleaving, consecutive addresses stay in the same bank: the bank number is given by the high-order address bits. This lets independent accesses to different address regions proceed in different banks, but it gives no speedup for a single sequential block.

TIME TO FETCH AN N-WORD BLOCK FROM LOW-ORDER INTERLEAVED MEMORY WITH M >= N BANKS

T_{b l oc k} = T_{a ccess} + (n - 1) \cdot T_{t r an s f er}

Model: all $n$ banks start their access together. The first word is on the bus after $T_{a ccess}$ (the bank access time, including placing the word on the bus). Each further word, already read in its own bank, needs only one bus transfer time $T_{t r an s f er}$ . Questions may define the timing differently, for example with a separate address-send cycle. Use the question's model when it gives one.

TIME TO FETCH AN N-WORD BLOCK, NO INTERLEAVING

T_{b l oc k} = n \cdot T_{a ccess}

Same model with a single bank: each word is a full, separate access. This is the baseline against which the speedup from interleaving is measured.

WORKED EXAMPLE

Memory is organised as 4 low-order interleaved banks, each with an access time of 80 ns; the bus transfer time per word is 10 ns. Using the model above, find the time to fetch a 4-word block, with and without interleaving.

Solution

Interleaved: $T_{b l oc k} = T_{a ccess} + (n - 1) T_{t r an s f er} = 80 + 3 \times 10 = 80 + 30 = 110$ ns.
Non-interleaved: $T_{b l oc k} = n \times T_{a ccess} = 4 \times 80 = 320$ ns.

Answer: 110 ns interleaved vs 320 ns non-interleaved

EXAM TIP

The interleaved formula assumes each bank is used at most once per block ( $n \leq m$ ). If the block has more words than there are banks, some banks are used twice. A bank's second access cannot start until its first access cycle ends, so work the timing out from the question's model rather than applying this formula.

Disk Access Time

Disks sit below main memory in the hierarchy and are far slower, because an access involves mechanical motion. The time to access data on a disk is the sum of a few separate components.

DISK ACCESS TIME

T_{a ccess} = T_{see k} + T_{r o t a t i o na l} + T_{t r an s f er} (+ T_{co n t r o l l er} if given)

Seek: moving the head to the correct track. Rotational latency: waiting for the target sector to rotate under the head. Transfer: reading or writing the data once positioned. Add a controller overhead only if the question gives one. Unless stated otherwise, a given seek time is taken as the average seek time.

AVERAGE ROTATIONAL LATENCY

T_{r o t a t i o na l} = \frac{1}{2} \cdot \frac{60}{R P M}

Half the time of one revolution, in seconds (RPM = revolutions per minute). This is the AVERAGE. The worst case is a full revolution and the best case is zero.

DATA TRANSFER TIME

T_{t r an s f er} = \frac{bytes to transfer}{transfer rate}, transfer rate = sectors per track \times bytes per sector \times \frac{R P M}{60}

One track passes under the head per revolution, so the transfer rate is the track capacity times the revolutions per second. Equivalently, reading one sector takes (revolution time) $\div$ (sectors per track).

WORKED EXAMPLE

A disk spins at 7200 RPM, has an average seek time of 6 ms, and each track holds 200 sectors of 512 bytes. Find the average time to read one sector (no controller overhead).

Solution

Revolution time $= 60000/7200 \approx 8.33$ ms.
Average rotational latency $= 8.33/2 \approx 4.17$ ms.
Transfer time for 1 of 200 sectors on the track $= 8.33/200 \approx 0.0417$ ms.
Total $= 6 + 4.17 + 0.0417 \approx 10.21$ ms.

Answer: ≈ 10.21 ms

EXAM TIP

Use the average rotational latency (half a revolution) unless the question asks for the worst case (a full revolution). Convert RPM to revolutions per second before computing a transfer rate.

PREVIOUS-YEAR QUESTIONS

22 questions from the CS papers

Try each question first, then open the answer. One shows the official answer only. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS1 Q.38

GATE 2026 · CS1Q.38 · 2 marks · MCQ

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 $K$ -way set-associative cache, where $K = 2^{L}$ and $L \in {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$

Answer and solution

GATE 2026 CS1 Q.38: answer and solution

See the question in the paper

Memory hierarchy, performance and cache mapping

Memory Hierarchy and Average Access Time

Cache Mapping Techniques and Address Structure

Replacement and Write Policies

Types of Cache Misses and Multilevel Caches

Main Memory: Building It from Chips, and Interleaving

Disk Access Time

22 questions from the CS papers

5 questions to test yourself