Cache Memory
Cache memory is a small, fast memory placed between the CPU and main memory that holds copies of the most frequently used data and instructions. It works because of locality of reference.
CPU <--> CACHE (SRAM, fast, small) <--> MAIN MEMORY (DRAM, slow, large)
When the CPU requests a word:
HIT : the word is in the cache -> supplied immediately
MISS : the word is not in the cache -> fetch the whole BLOCK
containing it from main memory into the cache, then supply it
1. Hit Ratio and Average Access Time
Hit ratio h = (number of hits) / (total accesses)
Miss ratio = 1 - h
Average access time (simultaneous / look-through access):
T(avg) = h x T(cache) + (1 - h) x T(main)
Average access time (hierarchical access — main memory is only
consulted AFTER a cache miss is detected):
T(avg) = T(cache) + (1 - h) x T(main)
Q: Cache access time = 10 ns, main memory access time = 100 ns,
hit ratio = 0.9. Find the average access time.
Simultaneous: T = 0.9 x 10 + 0.1 x 100 = 9 + 10 = 19 ns
Hierarchical: T = 10 + 0.1 x 100 = 10 + 10 = 20 ns
Q: A system has a 95% hit ratio, cache time 5 ns and memory time 80 ns.
What is the speed-up over having no cache at all?
T(with cache) = 0.95 x 5 + 0.05 x 80 = 4.75 + 4 = 8.75 ns
T(without cache) = 80 ns
Speed-up = 80 / 8.75 = 9.14 times faster
Notice how sensitive this is: dropping the hit ratio from 95% to 90% raises the average from 8.75 ns to 12.25 ns — a 40% slowdown from a 5% change. Cache design is all about the last few percent of hit ratio.
2. Cache Mapping Techniques
The central question: where in the cache may a given main-memory block be placed?
Common setup for all three examples
Main memory : 64 K words (16-bit addresses), 12-bit data words
Cache : 512 words (2^9)
Block size : 8 words (2^3)
Number of main memory blocks = 64K / 8 = 8192 blocks
Number of cache lines = 512 / 8 = 64 lines
3. Direct Mapping
Each main-memory block maps to EXACTLY ONE cache line:
cache line number = (block number) MOD (number of cache lines)
Address breakdown:
+--------+-------+--------+
| TAG | LINE | WORD |
+--------+-------+--------+
7 bits 6 bits 3 bits = 16 bits
WORD : which word within the block -> log2(8) = 3
LINE : which cache line -> log2(64) = 6
TAG : the rest -> 16 - 6 - 3 = 7
Lookup procedure:
1. Use the LINE field to index directly into the cache (no search).
2. Compare the stored tag with the address's TAG field.
3. If equal -> HIT; use the WORD field to select the word.
If not -> MISS; fetch the block and overwrite that line.
| Advantage | Disadvantage |
|---|
| Simplest and cheapest — one comparator | Conflict misses: two hot blocks mapping to the same line evict each other repeatedly (thrashing) |
| Fastest lookup (no search) | Lowest hit ratio |
| No replacement algorithm needed | |
Worked lookup: address 3A7CH = 0011 1010 0111 1100
WORD = 100 = 4
LINE = 001111 = 15
TAG = 0011101 = 1DH
Look at cache line 15; if its tag = 1DH -> hit on word 4.
4. Fully Associative Mapping
A block may be placed in ANY cache line.
Address breakdown:
+----------------+--------+
| TAG | WORD |
+----------------+--------+
13 bits 3 bits = 16 bits
TAG = the full block number (16 - 3 = 13 bits)
Lookup: the TAG must be compared against EVERY line's tag,
simultaneously -> this requires ASSOCIATIVE MEMORY (previous lesson).
| Advantage | Disadvantage |
|---|
| Best hit ratio — no conflict misses | Needs one comparator per line — very expensive |
| Full flexibility in placement | High power consumption |
| Needs a replacement algorithm |
5. Set-Associative Mapping
The practical compromise: the cache is divided into sets; a block maps to one set, but may occupy any line within that set.
k-way set associative: each set contains k lines.
With 64 lines and 2-way associativity:
Number of sets = 64 / 2 = 32
Address breakdown:
+--------+-------+--------+
| TAG | SET | WORD |
+--------+-------+--------+
8 bits 5 bits 3 bits = 16 bits
WORD = log2(8) = 3
SET = log2(32) = 5
TAG = 16 - 5 - 3 = 8
Lookup: index the SET directly, then compare the tag against the
k lines in that set in parallel -> only k comparators needed.
Special cases:
k = 1 -> direct mapping
k = number of lines -> fully associative
Real CPUs typically use 4-way to 16-way.
Complete Mapping Comparison
| Basis | Direct | Fully associative | k-way set associative |
|---|
| Placement | One fixed line | Any line | Any line in one set |
| Address fields | Tag / Line / Word | Tag / Word | Tag / Set / Word |
| Comparators needed | 1 | Number of lines | k |
| Hit ratio | Lowest | Highest | Near-highest |
| Cost | Lowest | Highest | Moderate |
| Replacement algorithm | Not needed | Required | Required |
| Conflict misses | Many | None | Few |
| Search time | Fastest | Slowest | Fast |
6. Address Field Numericals
Q: A computer has a 32-bit address, a 256 KB cache with 64-byte
blocks, 4-way set associative. Find the tag, set and word fields.
Block size = 64 bytes -> WORD (offset) = log2(64) = 6 bits
Cache lines = 256 KB / 64 B = 4096 lines
Sets = 4096 / 4 = 1024 sets -> SET = log2(1024) = 10 bits
TAG = 32 - 10 - 6 = 16 bits
Answer: TAG 16 | SET 10 | OFFSET 6
Q: Same system, but DIRECT mapped.
Lines = 4096 -> LINE field = 12 bits
TAG = 32 - 12 - 6 = 14 bits
Q: Same system, FULLY associative.
TAG = 32 - 6 = 26 bits, and 4096 comparators are needed.
7. Replacement Algorithms
When a set is full, which line is evicted?
| Algorithm | Rule | Note |
|---|
| FIFO | Evict the oldest-loaded line | Simple; can evict a hot line |
| LRU (Least Recently Used) | Evict the line unused for the longest time | Best practical performance; needs age bits |
| LFU (Least Frequently Used) | Evict the least-accessed line | Needs counters |
| Random | Evict any line | Surprisingly close to LRU, essentially free |
| Optimal (Belady) | Evict the line needed furthest in the future | Impossible to implement — used only as a benchmark |
8. Write Policies
The cache and main memory must be kept consistent. Two policies:
WRITE-THROUGH:
Every write goes to BOTH the cache and main memory.
+ Memory is always up to date; simple; safe for DMA and multiprocessors
- Slow (every write pays the memory latency)
- Usually paired with a WRITE BUFFER to hide the latency
WRITE-BACK (copy-back):
Writes go ONLY to the cache; a DIRTY BIT marks the modified line.
The line is written to memory only when it is EVICTED.
+ Much faster; multiple writes to the same line cost one memory write
- Memory is temporarily stale -> coherence problems with DMA
- More complex
Write-miss policies:
WRITE-ALLOCATE : load the block into the cache, then write
(usual partner of write-back)
NO-WRITE-ALLOCATE: write straight to memory, do not load the block
(usual partner of write-through)
9. Types of Cache Miss — the three Cs
| Miss type | Cause | Cure |
|---|
| Compulsory (cold) | First-ever reference to a block | Prefetching, larger blocks |
| Capacity | The working set exceeds the cache size | Bigger cache |
| Conflict | Too many blocks map to the same set | Higher associativity |
10. Multi-Level Cache
L1 : split into instruction cache and data cache (Harvard style),
smallest and fastest, private to each core
L2 : unified, larger, still private (or shared by two cores)
L3 : large, shared by all cores on the chip
Average access time with two levels:
T = T(L1) + (1 - h1) x [ T(L2) + (1 - h2) x T(memory) ]
Q: T(L1)=1ns h1=0.9, T(L2)=10ns h2=0.95, T(mem)=100ns
T = 1 + 0.1 x [10 + 0.05 x 100]
= 1 + 0.1 x 15
= 2.5 ns
Summary
T(avg) = h.T(cache) + (1-h).T(main) [simultaneous]
T(avg) = T(cache) + (1-h).T(main) [hierarchical]
Direct : TAG | LINE | WORD, 1 comparator, conflict misses
Associative: TAG | WORD, n comparators, best hit ratio
Set assoc. : TAG | SET | WORD, k comparators, the real-world choice
Replacement: FIFO, LRU, LFU, Random
Write policy: write-through (safe, slow) vs write-back (fast, dirty bit)
Three Cs : compulsory, capacity, conflict
One level of the hierarchy remains: the mechanism that makes a program believe it has more memory than the machine physically contains.
