Cache questions can become dependable GATE COA marks if you can split an address and calculate average access time in under two minutes. Most mistakes come from carrying the wrong index width into a new mapping scheme or forgetting whether memory is byte-addressable. Fix one configuration, a byte-addressable 64 KB memory with a 1 KB cache and 16-byte blocks, and a single address like 0x1234 can be re-split for direct, 4-way set-associative and fully associative mapping, then reused for hit ratio, AMAT and tag directory size.
Why cache memory exists: locality and hierarchy
A large speed gap separates processors from main memory. Cache is a small SRAM buffer that keeps useful data close to the CPU. It sits below registers as L1, L2 and L3, above main memory and storage. Where cache ends, paging and the TLB take over, which is the subject of Memory Hierarchy and Virtual Memory.
Temporal locality reuses recent data, such as a loop counter. Spatial locality uses nearby data, such as consecutive array elements. A cache exploits both by moving a whole block, also called a cache line, rather than one byte at a time.
A hit finds the requested item in cache.
A miss does not find it and must access a lower level.
The hit ratio,
h, is the fraction of accesses that hit.The miss penalty is the extra time needed after a miss.
Cache address anatomy: tag, index and offset
Use this running configuration: byte-addressable main memory of 64 KB, a 1 KB cache and a 16-byte block. The address width is 16 bits because 64 KB is 2^16 bytes. The cache contains:
1 KB / 16 B = 1024 / 16 = 64 lines
For direct mapping, the byte offset needs log2(16) = 4 bits, and the line index needs log2(64) = 6 bits. The remaining 16 - 6 - 4 = 6 bits form the tag.
Now split address 0x1234, which is 4660 in decimal:
Offset =
4660 mod 16 = 4.Memory block number =
4660 div 16 = 291.Cache line =
291 mod 64 = 35.Tag =
291 div 64 = 4.
Always check that the fields cover the complete address: 6 tag + 6 index + 4 offset = 16 bits.
Three cache mapping techniques on the same address
In a direct-mapped cache, memory block 291 has exactly one home, line 35. It is simple and fast, but colliding hot blocks repeatedly displace each other.
For a 4-way set-associative cache, the same 64 lines become 64 / 4 = 16 sets. The set index is now 4 bits, while the tag grows to 16 - 4 - 4 = 8 bits. For block 291:
Set =
291 mod 16 = 3.Tag =
291 div 16 = 18.
Every doubling of associativity moves one bit from the index to the tag. In a fully associative cache, there is no index, so the tag is 12 bits and the offset is 4 bits. Block 291 may occupy any of the 64 lines.
Mapping | Tag comparisons | Conflict misses | Hardware cost |
|---|---|---|---|
Direct | 1 | Highest | Lowest |
4-way set-associative | 4 | Lower | Moderate |
Fully associative | 64 | Eliminated | Highest |
Use Cache Memory Mapping and Hit Ratio for more drills on these field splits.
Hit ratio and average memory access time
Hit ratio is usually something you derive, not something the question hands over. Scan an array of 4-byte integers in address order on the running cache. One 16-byte block holds 16 / 4 = 4 elements, so the first element of each block misses and the next three hit:
h = 3 / 4 = 0.75, miss ratio = 0.25
Widen the block to 32 bytes and one block carries 8 elements, so h = 7 / 8 = 0.875. That single line is the spatial-locality argument stated as arithmetic. Where the question gives raw counts instead, divide them: 880 hits out of 1,000 accesses is h = 880 / 1000 = 0.88.
Average memory access time depends on the lookup sequence. If cache and memory are accessed simultaneously, use:
T_avg = h x t_c + (1 - h) x t_m
If memory is accessed only after the cache reports a miss, use the hierarchical form:
T_avg = t_c + (1 - h) x t_m
The question may call t_m the main-memory time or miss penalty. Read the wording before choosing the formula.
For a single-level cache with t_c = 2 ns, h = 0.9 and t_m = 40 ns, hierarchical access gives:
T_avg = 2 + (1 - 0.9) x 40 = 2 + 4 = 6 ns
Feed the scan's own hit ratio into that same cache and block size shows up in nanoseconds: h = 0.75 gives 2 + 0.25 x 40 = 12 ns, while the 32-byte block's h = 0.875 gives 2 + 0.125 x 40 = 7 ns. Nothing changed but how much of each block the program used.
For two levels, suppose L1 takes 1 ns and hits 90 percent of the time. L2 takes 10 ns and catches 80 percent of L1 misses. Main memory takes 100 ns:
AMAT = 1 + 0.1 x (10 + 0.2 x 100)
= 1 + 0.1 x 30 = 4 ns
The nesting is the important pattern: each level adds its local miss rate multiplied by the cost of reaching the next level.
Write policies, replacement and cache misses
With write-through, every cache write also goes to memory, so a write buffer is normally needed. With write-back, a dirty bit marks a modified line for update on eviction. This saves traffic, but replacing a dirty line can require one write-back and one fetch.
Write-allocate usually pairs with write-back because the fetched block can receive later writes. No-write-allocate often pairs with write-through because a write miss can update memory without filling the cache. The traffic arithmetic for the two policies, and the hierarchical versus simultaneous choice worked over L1 and L2, are drilled at full GATE length in Cache Write Policies and Multi-Level Cache Numericals.
Replacement matters only where the cache has a choice. Direct mapping needs no policy, while associative caches may use LRU, FIFO or random replacement. In one 4-way set accessed as A B C D A E, LRU evicts B because the second access refreshed A.
The three miss classes are compulsory on a first touch, capacity when the working set exceeds the cache, and conflict when different blocks compete for the same set.
Tag directory overhead and common traps
The direct-mapped running example stores a 6-bit tag and one valid bit per line. Its directory size is:
64 x (6 + 1) = 448 bits
A write-back design also needs one dirty bit per line:
64 x (6 + 1 + 1) = 512 bits
Watch for these frequent errors:
Check whether the machine is byte-addressable or word-addressable before finding the address width.
In COA calculations, use
1 KB = 2^10 = 1024 bytes, not 1000 bytes.Recalculate index bits after changing associativity.
Include valid and dirty bits when the question asks for directory size.
Use the hierarchical formula when the stated memory time is a miss penalty.
How GATE and interviews test cache organization
GATE commonly frames cache through address splits, NAT calculations, multilevel AMAT, directory overhead and cache stalls combined with pipelining. COA is part of the GATE CS syllabus, but use the official GATE website of the current organising institute for the exact current syllabus wording and paper pattern.
Placement interviews lean towards reasoning: why set associativity reduces conflicts, what a dirty bit does, and how a larger line may exploit spatial locality while wasting bandwidth on unused bytes. CS Fundamentals for Placements by Sanchit Sir covers COA at this conceptual depth.
Before timed practice, change the running block size to 32 bytes. The cache then has 32 lines, so offset = 5 bits, index = 5 bits and tag = 16 - 5 - 5 = 6 bits. Re-deriving this yourself is more useful than memorising one split.
The short version and next step
Cache hides the speed gap between the processor and main memory.
Tag + index + offset must equal the address width.
Higher associativity trades index bits for tag bits and fewer conflicts.
AMAT is nested one level at a time using each local miss rate.
Directory bits = lines x (tag bits + status bits).
Attempt topic-wise COA tests under time pressure in the GATE Test Series, then browse the wider GATE CS Exam Preparation catalogue. After that, re-derive the 32-byte split cold, until the 6-bit tag falls out in under a minute.
