Unit II — Parallel Architecture

Memory Hierarchy & Cache Coherence

Session 05 • 2311CSC501J — Parallel Processing

What You'll Learn

The memory wall and the cache hierarchy
Why caches work: locality & cache lines
The cache coherence problem & MESI
False sharing — why more threads can be slower

"There are only two hard things in computer science: cache invalidation and naming things."

— Phil Karlton

The Memory Wall

The CPU is starving

A core executes several instructions per nanosecond.
Main memory (DRAM) takes about 100 nanoseconds to answer.
Wait for RAM on every access → the CPU sits idle ~99% of the time.

This growing gap between fast CPUs and slow memory is the memory wall. The fix: a hierarchy of caches — a few tiny fast memories near the core, backed by bigger slower ones.

If an L1 hit were 1 SECOND, then to human scale...

  L1 cache   1 second     (the pen in your hand)
  L2 cache   ~4 seconds   (the desk drawer)
  RAM        ~2 minutes   (the library downstairs)
  SSD read   over a DAY   (a book shipped from another city)

The CPU will do almost anything to avoid the long trips.

The Memory Hierarchy

Level	Typical size	Approx. latency
Registers	~1 KB (a few dozen)	< 1 ns
L1 cache	32–64 KB / core	~1 ns
L2 cache	256 KB–1 MB / core	~4 ns
L3 cache	8–32 MB shared	~15 ns
Main RAM	8–64 GB	~100 ns
SSD / disk	256 GB–4 TB	~100 µs (SSD)

Each level is a cache for the level below it. L1→RAM is a 100× jump; RAM→SSD is another 1000×. Almost all performance work is turning misses into hits.

Why Caches Work: Locality

Temporal locality

If you used it, you'll use it again soon.

A loop counter, a running total — keep it close.

Spatial locality

If you used it, you'll want its neighbors soon.

Arrays, struct fields, sequential reads.

Hardware never fetches ONE byte. It grabs a whole 64-byte LINE:

  RAM:  [ ...  a[0] a[1] a[2] a[3] a[4] a[5] ... a[15]  ... ]
              ⌊———— one 64-byte cache line (16 ints) ———⌋

  You asked for a[0]. The cache grabbed a[1..15] for free —
  betting your next loop iteration wants them. Usually a great bet.

Remember the 64-byte cache line. It's a brilliant optimization — and later it causes the sneakiest bug in this course.

The Cache Coherence Problem

Each core has its own cache. Both read shared x = 0 — each keeps a private copy. Then Core 1 writes…

Core 1 writes x = 42 into ITS cache. Core 2 is now STALE:

   Core 1                Core 2
  ⌈——————⌉           ⌈—————⌉
  ¦ x = 42 ¦           ¦ x = 0 ¦   ← STALE! reads the WRONG value
  ⌊——————⌋           ⌊—————⌋
         \               /
        ⌈———————————⌉
        ¦  RAM:  x = 0     ¦   ← also stale
        ⌊———————————⌋

Cache coherence is the hardware's promise that, despite private caches, all cores behave as if there's a single consistent value per location. It is not free — and it's the whole reason a multicore chip is more than several CPUs glued together.

Watch: Cache Coherence & MESI

Watch how a write forces the other caches to invalidate their copy — that's the whole game.

The word to remember is invalidate: when one core writes, every other cache must throw away its stale copy before the write is allowed to complete.

Coherence Protocols

Snooping (bus-based)

Every cache listens on a shared bus. A writer broadcasts "drop your copy of x"; everyone invalidates.

+ Simple, fast for few cores

− Bus saturates; stops scaling ~8–16 cores

Directory-based

A central directory tracks who holds each line, then sends invalidations only to those cores.

+ Targeted traffic; scales to 100s of cores

− Extra hardware + a lookup step

Small chips snoop; big many-core and multi-socket systems go directory-based. The same bus-vs-fabric trade-off as Session 04's interconnects.

MESI: The Four States

State	Meaning	Others?	RAM current?
M — Modified	I changed it; my copy is the only correct one	No	No
E — Exclusive	Only cached copy, unchanged	No	Yes
S — Shared	I have a copy; others may too	Maybe	Yes
I — Invalid	Stale/empty; must not use it	—	—

Scenario: two cores, one variable x
                                 Core 1     Core 2
1. Core 1 reads x                E          I
2. Core 2 reads x                S          S
3. Core 1 writes x = 42          M          I     ← invalidate!
4. Core 2 reads x                S          S     ← coherence miss:
                                                     C1 writes back, then shares

A write to shared data invalidates every other copy. Reads are cheap; contended writes are expensive. Hold that thought.

False Sharing: The Sneaky Bug

Two threads update different variables — zero logical sharing — but the variables sit on the same 64-byte line. The line ping-pongs between caches. Adding a thread can make it slower.

BAD  — both counters on the SAME cache line:
  struct { long a; long b; } counter;   // 8 bytes apart → same line
  Thread 0 writes a → invalidates Thread 1's line
  Thread 1 writes b → invalidates Thread 0's line   ... forever.

GOOD — pad each onto its OWN line:
  struct Padded { long value; char pad[56]; };  // 8 + 56 = 64 bytes
  Padded counter[2];   // now on different lines — no invalidations

Fix: pad hot variables onto separate lines, or accumulate into a local variable and write the shared result once (exactly what an OpenMP reduction does — Session 10).

SMP vs AMP

	SMP — Symmetric	AMP — Asymmetric
Cores	Identical, equal	Different roles / power
OS	One OS over all cores	May differ per core
Memory	Shared uniformly	Often partitioned
Example	Laptop, server CPU	Phone (big.LITTLE), embedded
Tuned for	Simplicity, general load	Power efficiency, specialization

SMP with a handful of fat, equal cores is one end of a spectrum. Next session pushes to the other end — thousands of tiny GPU cores — and asks why both exist.

Recap & What's Next

Key Takeaways

The memory wall — CPUs ~100× faster than RAM — forces a hierarchy of caches.
Caches work because of locality; they move a 64-byte line at a time.
The coherence problem: a write leaves other cores holding a stale copy.
MESI + snooping/directory fix it — a write invalidates every other copy.
False sharing can make more threads slower; fix with padding.

Homework

Explain the cache coherence problem to a friend using two cores and a shared x.
Look up your CPU's L1/L2/L3 cache sizes; note the size/speed trade-off.
Come ready: "A few big CPU cores vs thousands of tiny GPU cores — why does each make sense?"

Next session: Multicore Processors & GPUs

From a few fat CPU cores to thousands of thin GPU cores — and why both exist.