Multicore and Concurrency

The power a chip uses grows with its clock speed, and faster clocks also need higher voltages, which cost even more. By the mid-2000s, processors were running into a power wall: going faster would have taken more power than a desktop could cool. But transistors kept getting smaller, so designers used the extra ones differently: two complete cores on one chip, then four, then many more. The first dual-core desktop x86 processors appeared in 2005. The computer this book was written on has twelve cores, able to run 20 threads at once.

Cores, threads and hyper-threading

Each core is a complete processor, with its own registers, pipelines (Chapter 25) and first-level caches. The cores share the main memory and usually a big last-level cache. The operating system's scheduler (Chapter 20) puts a thread on each core, so threads really do run at the same time, not just taking turns.

Many cores can also run two threads each, using simultaneous multithreading, which Intel calls hyper-threading. The core keeps two sets of registers and fetches from both threads, so when one is waiting for memory, the other can use the execution units. The two threads share almost everything else, so it's worth much less than a second core.

The processor in the computer this book was written on mixes two kinds of core: 8 big performance cores (P-cores), each running 2 threads, and 4 smaller, slower but more power-efficient efficiency cores (E-cores), one thread each. 8 × 2 + 4 = 20 threads.

Race conditions

Threads in one program share the same memory, which is what makes them useful: they can work on the same data. It's also what makes them dangerous. Take the simplest possible shared job: two threads each add 1 to a counter. In C that's counter++, but the processor does it in three steps: load the value, add 1, store it back. If two cores interleave those steps the wrong way, both load the same old value, and one increment is lost. That's a race condition: the result depends on the exact timing of the threads.

Races are notoriously hard to find. The wrong interleaving may happen once in a million runs, only on certain machines, or only when the computer is busy, and adding a print statement to investigate can change the timing enough to hide it.

Locks and atomic instructions

The cure is to make sure only one thread at a time can run the code that touches shared data, called a critical section. The usual tool is a lock, or mutex (for "mutual exclusion"): a thread must take the lock before entering, and release it after. Another thread that wants the lock has to wait.

But a lock is itself shared data. Taking it means checking that it's free and marking it taken, and two cores could do that at the same moment too. So locks rely on atomic instructions: instructions the hardware guarantees can't be interrupted halfway by another core. On x86, the lock prefix makes an instruction like add atomic, and cmpxchg ("compare and exchange") changes a value only if it still holds what you expect. RISC-V has atomic memory operations like amoadd, and a pair of instructions, load-reserved and store-conditional, that fail if anyone touched the memory in between.

Locks bring their own dangers. If thread 1 holds lock A and waits for lock B, while thread 2 holds B and waits for A, both wait forever: a deadlock. The usual rule is to always take locks in the same order. And while one thread holds a lock, others may have to wait, so too much locking makes a parallel program run one thread at a time.

Keeping caches in step

Each core has its own caches (Chapter 9). So what happens when core 0 changes a value that core 1 also has in its cache? Core 1's copy is out of date, and if it kept using it, the cores would see different memories. To prevent this, the caches follow a cache coherence protocol. The classic one is called MESI, after the four states a cache line can be in: Modified (only this cache has it, and it's been changed), Exclusive (only this cache has it, unchanged), Shared (several caches have clean copies) and Invalid.

The key rule: before a core can write to a line, every other copy must be thrown away. So writing to shared data sends messages between the cores, and costs time.

Coherence works on whole cache lines of 64 bytes, not on single variables. That leads to a sneaky slowdown called false sharing: two threads updating two different variables that happen to sit in the same cache line still bounce the line between their cores, exactly like the ping-pong in the demo. The fix is to keep data used by different threads at least 64 bytes apart.

There's one more subtlety. To go fast, cores don't always make their memory writes visible to other cores in the order the program made them. x86 keeps the order fairly strict; RISC-V allows more reordering. Programs that share data without locks must use special fence instructions, or the atomic instructions above, to put things in order. Locks include the right fences, which is one more reason to use them.

How much faster?

With 8 cores, can a program run 8 times faster? Only if all of its work can be split up. Almost every job has some part that can't: reading the input, combining the results, or a step that depends on the one before. In 1967, Gene Amdahl pointed out what this means. If a fraction p of a job can be spread over N cores, the best possible speed-up is

speed-up = 1 / ((1 − p) + p / N)

If 95% of the work is parallel, then even with a million cores the job can never run more than 20 times faster, because the last 5% still has to be done one step at a time. This is Amdahl's law.

Meanwhile, inside a real CPU

Linux's lscpu shows how the 20 logical CPUs map onto the 12 real cores. CPUs 0 and 1 are the two hyper-threads of core 0, and so on; CPUs 16 to 19 are the efficiency cores, with a lower top speed:

$ lscpu -e=CPU,CORE,MAXMHZ        (trimmed)
CPU CORE    MAXMHZ
  0    0 4800.0000
  1    0 4800.0000          ← the second thread of P-core 0
  2    1 4800.0000
 …
 14    7 4800.0000
 15    7 4800.0000
 16    8 3600.0000          ← an E-core: one thread, slower
 17    9 3600.0000
 18   10 3600.0000
 19   11 3600.0000

The race, for real: two threads, each adding 1 to a shared counter 10 million times, on two different cores. Unprotected, about half the updates vanished. An atomic add and a mutex both get it right, at a price:

plain counter++:  10196715  (expected 20000000)  0.021 s
atomic add     :  20000000  (expected 20000000)  0.211 s
mutex lock     :  20000000  (expected 20000000)  0.819 s

In this test the counter was marked volatile, which made GCC use three separate instructions: load, add, store. So even on one core, with the two threads just taking turns, the plain version lost 5.8 million updates, whenever the scheduler happened to switch threads between the load and the store. Without volatile, GCC turns counter++ into a single x86 instruction, but that still isn't safe between cores, because the core does it as a load, an add and a store inside. Only the lock prefix makes it indivisible. RISC-V spells out the three steps, and has a separate atomic instruction:

# x86-64 (GCC -O2)                    # RISC-V (Clang -O2, simplified)
counter++:                             counter++:
    add  QWORD PTR [counter], 1            ld   a1, 0(a0)
                                           addi a1, a1, 1
                                           sd   a1, 0(a0)
atomic add:                            atomic add:
    lock add QWORD PTR [counter], 1        amoadd.d.aqrl zero, a1, (a0)

False sharing, measured: two threads each atomically increment their own counter 50 million times. When the counters are 8 bytes apart, in one cache line, the line ping-pongs between the cores. 64 bytes apart, each core keeps its own line, and the two threads run as fast as one alone:

one thread alone:      0.195 s
same cache line:       1.048 s     ← 5 times slower: the cores fight over the line
different cache lines: 0.194 s

It's an easy mistake to make. Our first version of this test was itself slowed down by false sharing: the variable holding a pointer that both threads read happened to share a cache line with one of the counters.

Finally, scaling. Working out π by adding up 400 million terms of a series, split evenly between threads, each pinned to chosen cores:

 1 thread  (1 P-core):          0.341 s
 2 threads (2 P-cores):         0.172 s    ← 2.0 × faster
 4 threads (4 P-cores):         0.088 s    ← 3.9 ×
 8 threads (8 P-cores):         0.045 s    ← 7.6 ×
16 threads (8 P-cores × 2):     0.045 s    ← no better: hyper-threads share the core
20 threads (P- and E-cores):    0.048 s to 0.059 s   ← worse: everyone waits for the slow E-cores

This job is almost perfectly parallel, so it follows the ideal line, until it runs out of real cores. Hyper-threading didn't help at all here, most likely because both threads of a core were fighting over the same division unit. And splitting the work evenly was a mistake once the slower E-cores joined in: the fast cores finished early and sat idle. Real programs hand out smaller pieces of work as cores become free.

Try it yourself

1. Two threads each run counter++ once, starting from 0, with no lock. What final values are possible?
   Show answer

   2, if one thread finishes its store before the other loads; or 1, if both load 0 before either stores. Never 0 or 3.
2. On x86, counter++ compiles to a single instruction. Why isn't it safe without the lock prefix?
   Show answer

   Inside the core, the instruction still reads the memory, adds, and writes back. Without lock, another core can read or write the same memory between those steps. The lock prefix tells the core to keep the cache line to itself for the whole instruction.
3. 90% of a job can run in parallel. How much faster can it run on 8 cores? And on as many cores as you like?
   Show answer

   1 / (0.1 + 0.9 / 8) = 1 / 0.2125 ≈ 4.7 times faster on 8 cores. With unlimited cores, 1 / 0.1 = 10 times at most.
4. Two threads update stats.reads and stats.writes, two 8-byte counters next to each other. It's slow. How do you fix it?
   Show answer

   They share a 64-byte cache line, so it's false sharing. Put at least 64 bytes between them (padding), or align each counter to its own cache line, or let each thread count privately and add the totals at the end.
5. Thread 1 locks the "accounts" lock, then the "log" lock. Thread 2 locks "log", then "accounts". What can go wrong?
   Show answer

   A deadlock: if thread 1 gets "accounts" and thread 2 gets "log" at the same moment, each waits forever for the lock the other holds. The fix is to make every thread take the locks in the same order.

What we learned

• The power wall ended the race for clock speed, so processors now have many cores; hyper-threading runs two threads on one core.
• Threads sharing memory can suffer race conditions, like lost updates when counter++ interleaves.
• Locks protect critical sections, and are built on atomic instructions; taking locks in different orders can deadlock.
• Cache coherence (MESI) keeps the cores' caches consistent, at the cost of messages; false sharing happens when threads share a cache line by accident.
• Amdahl's law: the part of a job that can't be split limits how much more cores can help.

So far, everything has happened inside one computer. Next we connect computers together: networking, from bits on a wire to the web page you're reading.