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.

Example in Code: Two Loops, One Line Swapped

Sum every element of a 4096×4096 matrix of doubles. Both loops do exactly 16,777,216 additions. The only difference is the order of two lines.

A — row by row

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];

Walks memory in a straight line.

~40 ms

B — column by column

for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        sum += a[i][j];

Jumps 32 KB between every access.

~400 ms

10× slower. Identical arithmetic. Identical output. No profiler that counts operations will ever tell you why.

Why — and it's entirely about the cache line

A cache line is 64 bytes = 8 doubles. C stores a matrix ROW BY ROW.

LOOP A:  reads a[0][0] -> miss, hardware fetches a[0][0..7] in one line
         reads a[0][1] -> HIT   a[0][2] -> HIT ... a[0][7] -> HIT
         1 miss buys 8 useful values.        miss rate = 12.5%

LOOP B:  reads a[0][0] -> miss, fetches a[0][0..7]   (uses ONE of them)
         reads a[1][0] -> miss, fetches a[1][0..7]   (uses ONE of them)
         every single access is a new line, and by the time it comes
         back to a[0][1] that line was evicted long ago.
         1 miss buys 1 useful value.         miss rate ~ 100%

Loop B throws away 7 of every 8 bytes the memory system hands it. It also moves 8× more data across the memory bus to do the same work.

The rule, and it fits on one line: make the innermost loop walk memory in the direction memory is stored. In C that's the last index; in Fortran and MATLAB it's the first. Get it backwards and you pay 10×.

Keep this loop in mind — in Session 10 you'll parallelise matrix multiplication, and getting the loop order wrong there costs you more than the parallelism gains you. Fix locality first, then parallelise. Adding 8 cores to a cache-hostile loop just gives you 8 cores waiting on memory.

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.

Worked Example: Watch Two Caches Disagree

A shared variable x = 5 in RAM. Two cores, each with its own private L1 cache. Assume, for now, that no coherence protocol exists.

Time	What happens	Core A's cache	Core B's cache	RAM
t1	Core A reads x	5	—	5
t2	Core B reads x	5	5	5
t3	Core A writes x = 99	99	5 ◀ stale	5
t4	Core B reads x again	99	gets 5 — a cache HIT!	5
t5	Core B writes x = 7	99	7	5
t6	Both caches flush	—	—	99 or 7 — whoever flushed last

Row t4 is the horror. Core B asked for x and got a cache hit — the fastest possible outcome — and the answer was wrong. Nothing failed. No error was raised. The hardware did exactly what caches are supposed to do.

This is worse than the race condition in Session 03. That one was a software problem — you could see it in your code and fix it with reduction. This one is below your code entirely. Your source has one variable x; the machine has three copies of it and no opinion about which is right.

You cannot fix this in software at any reasonable cost. So the hardware fixes it — every multicore chip you have ever used runs a coherence protocol that makes t3 also invalidate Core B's copy. That's the rest of this session.

The one-line definition to walk away with: a memory system is coherent if a read always returns the value of the most recent write to that location, no matter which core did either. Everything — snooping, directories, MESI — is machinery to keep that one sentence true.

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.

Worked Example: Trace MESI, Six Operations

Same two cores, same variable x — now with MESI switched on. Track the state of the cache line in each core. I = Invalid, S = Shared, E = Exclusive, M = Modified.

#	Operation	Core A	Core B	What the hardware did
0	start	I	I	Neither has it
1	A reads x	E	I	Nobody else had it → A gets it exclusive
2	B reads x	S	S	A sees B's request, downgrades E→S. Both share.
3	A writes x = 99	M	I	A broadcasts an invalidate. B's copy is killed.
4	B reads x	S	S	B misses; A supplies 99 and writes back. Both S.
5	B writes x = 7	I	M	Now B invalidates A. Roles swap.
6	A reads x	S	S	B supplies 7. A reads 7 — correct.

Compare step 4 here with t4 on the earlier slide. Same operation — B reads x after A wrote it — but now B's copy was already invalidated, so B is forced to miss and fetch the truth. The protocol works by making the fast wrong answer impossible.

Two rules generate this whole table:

Many readers are fine (multiple S). One writer means everyone else is Invalid (one M, all others I).
E exists purely as an optimisation: "I'm the only one holding this, so if I write to it I don't need to tell anybody." It saves a broadcast on the very common read-then-write pattern.

Now count the cost. Steps 3–6 are two cores politely ping-ponging one variable. Each handover costs a broadcast, an invalidate and a cache miss — roughly 100–200 cycles. Do that in a tight loop and you have built the slowest program of your life. That is the next slide, and it is the most expensive bug in this course.

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).

Worked Example: False Sharing Costs 20×

Four threads, four separate counters, no shared variables and no race condition. This code is completely correct.

The obvious version

long counter[4];

#pragma omp parallel num_threads(4)
{
  int t = omp_get_thread_num();
  for (i = 0; i < 25000000; i++)
      counter[t]++;    // own slot!
}

The padded version

struct {
    long value;
    char pad[56];   // 8+56 = 64
} counter[4];

// ...identical loop...

Version	Time	Speedup vs 1 thread
1 thread, 100M increments	0.35 s	1.0× (baseline)
4 threads, unpadded	2.10 s	0.17× — six times SLOWER than one thread
4 threads, padded	0.09 s	3.9× — near perfect

WHY — a cache line is 64 bytes. Four longs is 32 bytes.

  ONE CACHE LINE:  [ counter[0] | counter[1] | counter[2] | counter[3] | ... ]
                        ^T0           ^T1          ^T2          ^T3

  Thread 0 writes counter[0] -> it must own the LINE in state M
                             -> so threads 1,2,3 go to state I
  Thread 1 writes counter[1] -> it must own the LINE
                             -> so threads 0,2,3 go to state I
  ... 100 million times, four cores fighting over one line.

The hardware protects data at CACHE LINE granularity.
Your program shares NOTHING. The hardware sees one line and serialises it.

This is why it's called false sharing. There is no sharing in your program — only in the hardware's bookkeeping. It is invisible in the source, invisible to the compiler, and gives correct answers every time. It just runs like a machine from 1998.

How to spot it: your parallel version is slower than serial, and the code has no locks and no obvious sharing. That combination is false sharing until proven otherwise.

How to fix it — three ways, best first:

Use a thread-local variable and combine at the end — which is precisely what reduction(+:sum) does. Session 03's fix was quietly solving this too.
Pad to 64 bytes, as above. Wastes memory, works everywhere.
Restructure so threads write to far-apart regions in the first place.

The idea worth carrying out of Unit II: correctness and performance are separate problems. This code was always correct. Coherence is what makes the wrong version work, and it's also what makes it slow. The same mechanism, seen from two sides.

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.