art with code

2008-09-09

"Shared Memory" Parallelism

One thing that amazes me in discussions extolling the performance benefit of shared memory over message passing is that no one has apparently looked at the hardware in use. Because hardware has no shared memory. None. Nada. Zilch.

How a computer works in a nutshell

Accessing memory:

CPU: Hey, I'd like to read eight bytes from memory position 0x8008 to register %RAX.
Cache manager: Sure thing, wait a couple cycles. Hey L1, have you got the cache line with 0x8008?
L1: Sorry! (2 cycles if hit)
Cache manager: Hm, how about you L2? Got 0x8008?
L2: Oh, uh, sec, lemme see... nope. (9 cycles if hit)
Cache manager: Argh, OK, shit happens. DRAM, gimme 0x8008.
DRAM: Durr, 0x8008, yeah, 0x8008, yeah...
Cache manager: DRAM?
DRAM: ...
Cache manager: DRAM! 0x8008!
DRAM: Huh? Oh. Here you go. (200 cycles if hit, a couple dozen million if read from disk)

Shared memory in a cache coherent SMP machine:

CPU A: Read 0x8000!
L1: Here!
CPU B: Write %RAX to 0x8001!
Cache manager: Oh nuts. Hey CPU A, CPU B just wrote to a cache line you have, here's the new version.
CPU A: Ghh, OK. Write 0x8000!
Cache manager: CPU B! CPU A just wrote in 0x8000, you need a new version of the cache line!
CPU B: Damn it A, stop writing on my cache line!
CPU A: Your cache line? I'm so sorry, I didn't see your name on it!
...
Significant performance loss later:
Cache manager: The person who wrote this algorithm must be a some kind of retard.

Does that look like a shared memory architecture to you? No way. It's a message passing architecture, communicating in 64-byte cache lines. Treating it as shared memory will lead to performance problems.

Theoretically, a message passing system will yield the highest performance for present-day hardware. That is, if a compiler compiles the message passing in terms of CPUs talking to memory via cache lines. Anyone know whether such a mythical beast exists?

Related reading: What every programmer should know about memory, part 2: CPU caches by Ulrich Drepper.

No comments:

Blog Archive