Computer Architecture Cheatsheet

Caches

Use this Computer Architecture reference while you build software engineering projects, review code for technical interview prep, or polish examples for a software engineer resume.

Cache Fundamentals

A cache is a small, fast SRAM memory that transparently stores copies of recently-used main-memory locations. On each access the CPU checks the cache first:

Hit — data found in cache → return in hit time (~1–10 cycles)
Miss — data not found → fetch from next level, install in cache, then return

Hit rate h = hits / total accesses Miss rate m = 1 − h

Cache Organization

Every cache line (block) is identified by decomposing the memory address:

Address bits:
 [ Tag | Index | Block Offset ]
   t      s        b
where: 2^b = block size (bytes), 2^s = number of sets

Example: 32-bit address, 64-byte blocks (b=6), 256 sets (s=8): - Block offset: bits [5:0] → 6 bits - Index: bits [13:6] → 8 bits - Tag: bits [31:14] → 18 bits

Associativity

Type	Mapping	Description
Direct-mapped	1 way	Each address maps to exactly one cache line
2-way set associative	2 ways	Address maps to a set of 2 lines; choose either
4-way set associative	4 ways	Set of 4; most common for L1
8-/16-way	8–16 ways	L2/L3 common
Fully associative	Any line	Any address → any cache slot; victim caches, small L1 TLBs

Trade-offs:

Property	Direct-mapped	High associativity
Hit time	Lowest (1 comparison)	Higher (parallel comparisons)
Conflict misses	High	Low
Hardware cost	Low	Higher (more comparators)

The Three C's of Cache Misses

Miss type	Cause	Solution
Compulsory (cold)	First access to a block — always misses	Prefetching
Capacity	Cache too small to hold working set	Larger cache
Conflict	Multiple addresses map to same set	Higher associativity, victim caches
(Coherence)	Invalidations in multi-core systems	Better protocols

Replacement Policies

Policy	Description	Hit rate
LRU (Least Recently Used)	Evict the line not used for longest time	Best practical
Pseudo-LRU	Approximation using tree bits	Close to LRU, cheaper
FIFO	Evict oldest-installed line	Suffers Belady's anomaly
Random	Evict a random line	Surprisingly competitive; simple
Optimal (Bélády)	Evict line used farthest in future	Theoretical lower bound; offline only

Write Policies

Write-Hit

Policy	Description	Pros	Cons
Write-through	Update cache AND memory on every write	Memory always consistent	High memory bandwidth
Write-back	Update cache only; write to memory on eviction	Low bandwidth	Complexity; dirty bit needed

Write-Miss

Policy	Description
Write-allocate	Fetch block into cache, then modify (pair with write-back)
No-write-allocate	Write directly to next level; don't bring into cache (pair with write-through)

Most modern caches: write-back + write-allocate.

Cache Parameters and Their Effects

Parameter	Increasing it →
Cache size	Fewer capacity misses; higher hit time; more area/power
Block size	Fewer compulsory misses (spatial locality); more conflict misses (fewer sets); larger miss penalty
Associativity	Fewer conflict misses; higher hit time (more comparators)
Number of levels	Better AMAT; more complexity

Typical Cache Hierarchy (Modern CPU)

Level	Typical size	Latency	Associativity	Shared?
L1-I	32–64 KB per core	3–5 cycles	8-way	Per core
L1-D	32–64 KB per core	4–5 cycles	8-way	Per core
L2	256 KB–2 MB per core	12–15 cycles	8-way	Per core
L3 (LLC)	8–64 MB	30–50 cycles	16-way	Shared
L4 (eDRAM)	64–128 MB (rare)	~50–100 cycles	—	Shared

Prefetching

Bring blocks into cache before they are demanded.

Type	Description	Example
Hardware sequential prefetch	Detect stride, fetch next lines	Detect A[0], A[1], A[2] → prefetch A[3]
Stride prefetcher	Detect arbitrary stride Δ	A[0], A[4], A[8] → stride 4
Software prefetch	Compiler/programmer inserts `__builtin_prefetch()`	Can prefetch non-trivial patterns
Next-line prefetch	Always prefetch the next cache line	Simple, effective for streaming

Cache Performance Example

Direct-mapped, 1 KB cache, 16-byte lines (4-bit offset, 6-bit index, 22-bit tag):

Access pattern A[0], B[0], A[1], B[1] where A and B map to the same set:

Access    Cache state                    Result
A[0]      Set 0: [A[0] block]            Miss (cold)
B[0]      Set 0: [B[0] block]            Miss (conflict — evicts A)
A[1]      Same set as A[0]               Miss (conflict — evicts B)
B[1]      Same set as B[0]               Miss (conflict — evicts A)

100% miss rate despite data fitting in cache — classic conflict miss (thrashing). Fix: 2-way associativity or padding B to a different cache set.

Inclusion and Exclusion

Policy	Description	Trade-off
Inclusive L2	Every L1 line is also in L2	Simplifies coherence (can invalidate from L2); wastes L2 space
Exclusive	L1 and L2 hold disjoint sets	Maximizes total capacity
Non-inclusive / Non-exclusive (NINE)	Neither guaranteed	Modern LLC approach (Intel L3)

Cache Coherence (see Memory Hierarchy for MESI)

On a write to a shared line: - Invalidation protocol (MESI/MOESI): broadcast invalidation; other copies become Invalid - Update protocol: broadcast new value to all copies; lower bandwidth but more traffic

Invalidation dominates in practice.

Virtual vs Physical Caches

Cache type	Tags use	Look up before TLB?	Problem
Physically indexed, physically tagged (PIPT)	Physical addresses	No (after TLB)	Safe; correct; slower
Virtually indexed, physically tagged (VIPT)	VA index, PA tag	Parallel with TLB	Aliasing possible if VA index > page offset bits
Virtually indexed, virtually tagged (VIVT)	Virtual addresses	Yes (before TLB)	Aliasing and homonym problems

Modern L1 caches are usually VIPT designed so that the index bits fall within the page offset, making them effectively PIPT (no aliasing).