1. Why Cache Memory Exists

Modern CPUs execute instructions in nanoseconds. Main memory (DRAM) takes 60–100 nanoseconds to respond. Without cache, a CPU that can execute an instruction in 1 ns would spend 99 of every 100 nanoseconds waiting for memory. The CPU would be idle almost 99% of the time — a catastrophic waste of silicon.

Cache solves this by storing frequently accessed data in a small but extremely fast SRAM (Static RAM) that responds in 1–5 nanoseconds. The challenge: cache can only hold a small fraction of main memory. Cache design is about predicting which data the CPU will need next, and keeping that data close.

2. Temporal and Spatial Locality

Cache works because real programs exhibit two forms of locality — patterns in how they access memory.

Block size (also called cache line size) directly exploits spatial locality — when any word in a block is accessed, the entire block is loaded into cache, bringing nearby words that are likely to be needed soon.

3. Cache Address Breakdown

Every memory access generates a physical address. The cache hardware splits this address into three fields to locate the relevant cache line.

What each field does:

• Block Offset: selects the specific byte within the cache block
• Index: selects which set to look in
• Tag: compared against the stored tag to confirm it is the right block

The cache also stores a valid bit (1 = line contains valid data) and optionally a dirty bit (1 = line modified, must write back on eviction).

4. Cache Mapping Types

5. Replacement Policies — LRU, FIFO, Random

When a miss occurs and the target set is full, one of the existing lines must be evicted to make room. The replacement policy decides which one.

GATE tip: LRU trace questions are common. Always update the access order on every hit, not just misses. The line evicted is the one at the “back” of the LRU queue.

6. Write Policies — Write-Through vs Write-Back

7. AMAT Formula & Multi-Level Cache

Important distinction:

• Local miss rate: misses seen by this cache level ÷ accesses to this cache level
• Global miss rate: misses that reach main memory ÷ total accesses

GATE questions on AMAT almost always use the single-level formula. Two-level AMAT appears in harder questions — read carefully whether “miss penalty” means time to reach L2 or time to reach memory.

8. Types of Cache Misses — The 3 Cs

9. GATE-Level Worked Examples

Example 1 — Address Breakdown (GATE 2021)

Problem: A cache has 128 sets, 2-way set-associative, block size = 32 bytes. The physical address is 32 bits. Find the number of tag, index, and offset bits.

Example 2 — AMAT Calculation (GATE 2022)

Problem: A system has an L1 cache with 2 ns hit time and 5% miss rate. On a miss, it accesses main memory in 100 ns. A write buffer reduces effective miss penalty by 20 ns. What is the AMAT?

Example 3 — LRU Replacement Trace (GATE 2019)

Problem: A 2-way set-associative cache has 4 sets. Consider Set 0. Using LRU replacement, trace the following accesses and find the number of misses: Blocks 0, 4, 0, 8, 4, 0, 4

10. Common Mistakes

1. Tag + Index + Offset not summing to address width
   This is the most common calculation error. Always verify at the end. If you get Tag + Index + Offset ≠ 32 (or whatever the address width is), re-examine your log₂ calculations.
2. Confusing local and global miss rate in multi-level cache
   The global miss rate reaching memory = L1 miss rate × L2 miss rate. The AMAT formula uses global miss rate for the memory penalty term, not L2’s local miss rate alone.
3. Updating LRU order only on misses, not on hits
   In LRU, every access — hit or miss — updates the recency order. A line that was hit becomes the most recently used. Only tracking misses gives wrong eviction choices.
4. Applying write-back’s dirty bit logic to write-through caches
   Write-through caches do not need a dirty bit — main memory is always up to date. Dirty bits are exclusive to write-back caches and signal that a line must be written to memory before eviction.
5. Forgetting that block size affects compulsory miss rate
   Larger blocks reduce compulsory misses (more data fetched on each miss) but can increase miss penalty (more bytes to transfer). There is a diminishing return — the optimal block size balances these two effects. GATE occasionally asks about the effect of doubling block size.

11. Frequently Asked Questions

What is AMAT in cache memory?

AMAT (Average Memory Access Time) is the weighted average time to access memory, accounting for both cache hits and misses: AMAT = Hit time + (Miss rate × Miss penalty). It is the primary metric for cache performance in GATE COA questions. For a two-level cache, the formula extends to include L2 hit time and L2 miss penalty.

What is the difference between direct mapped and set-associative cache?

A direct mapped cache has exactly one cache line per set — each memory block maps to exactly one location, making conflict misses likely. A k-way set-associative cache has k lines per set — a memory block maps to one set but can occupy any of the k positions, which dramatically reduces conflict misses at the cost of slightly more hardware to check k tags simultaneously.

How do you break down a memory address for cache?

Split the address into three fields (right to left): Block Offset = log₂(block size in bytes) bits, Index = log₂(number of sets) bits, Tag = remaining bits. For fully associative, there is no index field. Always verify that the three fields sum to the total physical address width.

What is the difference between write-through and write-back cache?

Write-through: every cache write is immediately propagated to main memory, keeping them always consistent. Uses more memory bandwidth. Write-back: writes go only to cache; a dirty bit marks modified lines; main memory is updated only when the dirty line is evicted. Uses less bandwidth but adds complexity. Write-back typically delivers better performance in high-bandwidth scenarios.