Cache memory is a small, very fast store that sits between the CPU and main memory and holds copies of the data the processor is most likely to need next. It exists for one reason: main memory is far slower than the CPU, and without a cache the processor would spend most of its life waiting. This is one of the most reliably tested topics in Computer Organisation and Architecture, and it is almost entirely arithmetic once you understand the structure.
Let us build it up from the hierarchy.
The memory hierarchy
Memory is organised as a hierarchy, fastest and smallest at the top, slowest and largest at the bottom:
Registers, inside the CPU, fastest of all.
Cache (typically L1, L2, L3), small and very fast.
Main memory (RAM), larger but much slower.
Secondary storage (SSD, disk), huge but slow.
As you move down, capacity and cost-per-byte improve but speed drops sharply. The cache's job is to keep the small fraction of data that is being used right now close to the CPU, so most accesses are served at cache speed rather than memory speed.
Locality: why a cache works at all
A cache would be pointless if programs accessed memory randomly. They do not, and the reason is the principle of locality:
Temporal locality: a location just accessed is likely to be accessed again soon (think of a loop counter).
Spatial locality: locations near a just-accessed address are likely to be accessed soon (think of stepping through an array).
Because of locality, when the cache fetches one word it fetches a whole block (line) of neighbouring words, betting they will be needed shortly. That bet usually pays off, which is why hit ratios in real systems are high.
Mapping techniques: where a block can go
Main memory is divided into blocks, the cache into lines of the same size. The question a mapping technique answers is: when a memory block is brought in, which cache line can hold it? There are three schemes.
Direct mapping. Each memory block maps to exactly one cache line, given by (block number) mod (number of cache lines). Simple and cheap, but if two hot blocks map to the same line they keep evicting each other. The address splits into three fields: Tag | Line | Offset.
Fully associative mapping. A block may sit in any cache line. This gives the fewest conflict misses but needs a comparator on every line to search them all in parallel, which is expensive. The address is just Tag | Offset.
Set-associative mapping. The compromise, and what real caches use. The cache is divided into sets of k lines each (a k-way set-associative cache). A block maps to one set by (block number) mod (number of sets), and may sit in any line within that set. The address splits into Tag | Set | Offset. It captures most of the flexibility of full associativity at a fraction of the cost.
A worked address-split example (direct mapping)
Suppose a byte-addressable machine with a 4 GB main memory, a 32 KB direct-mapped cache, and a 16-byte block size. Split the address.
Main memory 4 GB = 2^32 bytes, so the physical address is 32 bits.
Block size 16 bytes = 2^4, so the offset field is 4 bits.
Number of cache lines = cache size / block size = 2^15 / 2^4 = 2^11 = 2048, so the line field is 11 bits.
The tag takes the rest: 32 − 11 − 4 = 17 bits.
So the address is Tag(17) | Line(11) | Offset(4). If you instead made this a 4-way set-associative cache, the 2048 lines form 2048 / 4 = 512 = 2^9 sets, so the set field shrinks to 9 bits and the tag grows to 32 − 9 − 4 = 19 bits. That trade, fewer index bits and a wider tag as associativity rises, is a favourite exam point.
A worked hit-ratio and access-time example
The payoff metric is the average memory access time (AMAT). The standard formula is:
AMAT = Hit time + Miss rate × Miss penalty
Here hit time is the time to serve data from the cache, miss rate is the fraction of accesses not found in cache (1 − hit ratio), and miss penalty is the extra time to fetch the block from main memory on a miss.
Problem. Cache hit time is 10 ns, the miss penalty (time to bring a block from main memory) is 100 ns, and the hit ratio H is 0.9. Find the average memory access time.
Miss rate = 1 − H = 1 − 0.9 = 0.1.
AMAT = 10 + (0.1 × 100) = 10 + 10 = 20 ns.
So even with only a 90 percent hit ratio, the average access is 20 ns, five times faster than the 100 ns it would take to always go to memory. Now push the hit ratio to 0.95: AMAT = 10 + (0.05 × 100) = 15 ns. A five-point gain in hit ratio cut a quarter off the access time, which is exactly why architects fight so hard for locality. In the exam you will be handed some of {hit time, miss penalty, hit ratio, AMAT} and asked for the missing one, and this single formula is the whole method.
Cache questions in GATE, UGC NET and placements
GATE CS tests this densely and numerically. Expect address-field splits for a given cache organisation, average-access-time calculations (including two-level L1/L2 caches), and questions on how associativity, block size, and write policy affect miss rate. Tag-size and number-of-lines calculations are near-guaranteed. Our GATE CS exam category sequences cache with pipelining and memory organisation.
UGC NET Computer Science favours the concepts and quick numerics: the three mapping techniques, temporal versus spatial locality, and a one-step hit-ratio calculation. Know the mapping definitions cleanly.
Placement and company tests ask the intuition, "what is a cache", "what is a cache hit and miss", "explain locality of reference", and sometimes cache-friendly code. The AMAT idea is what interviewers want you to reason about when discussing performance.
KnowledgeGate's published question bank carries over one thousand seven hundred Computer Organisation and Architecture questions, and cache memory is one of its densest sub-areas, so there is ample drill on exactly these calculations.
Practise it, do not just read it
Cache numericals are fast marks once the address split and the AMAT formula are automatic.
Work the full topic with solved numerics on the Cache Memory Organization learn module.
For GATE-depth Computer Organisation across the whole syllabus, GATE Guidance by Sanchit Sir sequences cache with pipelining and the instruction cycle.
To time yourself on these numericals under exam pressure, the GATE test series puts cache problems on the clock.
Learn the three mapping schemes, practise splitting an address into tag, line, and offset, and drill the AMAT formula until it is reflex. Do that, and cache memory turns from a numerical you dread into marks you can count on.