Cache Memory Principles

Computer Organization & Embedded System — Computer Arithmetic and Memory System, NEC licence examination syllabus (Nepal Engineering Council).

Cache Memory Principles: the CPU's shortcut to speed

Why your computer feels fast even though RAM is "slow."

Cache sits between the CPU and main memory, holding copies of recently-used data. When the CPU asks for data, cache is checked first.

A hit means the data was found in cache — fast. A miss means it wasn't, so the CPU must fetch it from main memory (slow), and typically that data + its neighbours get copied into cache for next time.

Average memory access time = h × tc + (1 − h) × tm h = hit ratio, tc = cache access time, tm = main memory access time (some versions add tm again for the miss penalty — check your textbook's exact formula)

💡 Numerical type: "Given hit ratio 0.9, cache time 10ns, memory time 100ns, find average access time." Practice a few variations, including finding the hit ratio when average time is given.

Splitting an address — the guaranteed numerical

Every cache question reduces to dividing the address into three fields. Take a 32-bit address, a 64 KB cache and 16-byte blocks.

Number of lines = 64 KB ÷ 16 B = 4,096 lines DIRECT MAPPED — each block has exactly one possible line offset = log₂(16) = 4 bits which byte within the block index = log₂(4096) = 12 bits which line it must go in tag = 32 − 12 − 4 = 16 bits which block is actually there ───────── 32 bits ✓

4-WAY SET ASSOCIATIVE — 4 lines per set sets = 4096 ÷ 4 = 1,024 sets offset = 4 bits index = log₂(1024) = 10 bits which SET (not which line) tag = 32 − 10 − 4 = 18 bits ───────── 32 bits ✓

Notice the trade. Associativity reduces the index — you are choosing between fewer sets — which means the tag must grow to make up the difference. That is a real storage cost: 4,096 × 16 bits is 8.0 KB of tags direct-mapped, against 4,096 × 18 bits = 9.0 KB at 4-way, on top of the data itself.

💡 The check that catches most errors: the three fields must add to the address width. If your offset, index and tag do not sum to 32, something is wrong before you go any further.

What associativity buys for that cost

🎯 Where each block may go

Direct mappedExactly one line. Fastest lookup — check one place — but two hot blocks mapping to the same line evict each other repeatedly even in an empty cache.

Set associativeAny of n lines in its set. Those two blocks can now coexist.

Fully associativeAny line at all. Best hit rate, but every line's tag must be compared at once — expensive, so it is used only for very small caches.

The failure associativity fixes is a conflict miss: a miss that happens although the cache has free space, purely because two addresses compete for one line. Direct-mapped caches suffer them badly; fully associative caches cannot have them at all.

💡 Write policy is the other standard question. Write-through updates memory on every write — simple and always consistent, but slow. Write-back updates only the cache and writes to memory when the line is evicted, marked by a dirty bit — much faster, at the cost of memory being temporarily stale, which matters enormously once several cores share it.

Syllabus points

Cache/main-memory structure, block/line
Hit, miss, hit ratio
Average access time (numericals)

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.