EC-10.5 More Than One Core

What this is and why it exists

Every device a reader of this module will write software for has several cores. That includes microcontrollers now, where two cores in one small part has become ordinary.

This topic is deliberately an outline rather than a course in parallel programming. Its purpose is to leave you able to ask the right question, not to answer all of them.

The single most useful thing it teaches is where a second core does not help, because that is the case people assume away.

The vocabulary

• Core — one complete processor, of several on a chip.
• Thread — an independently scheduled flow of execution within a process.
• Process — a program with its own memory, isolated from others.
• Cache coherence — hardware keeping several cores' caches in agreement.
• False sharing — two cores contending over one cache line although they use different data.
• Memory model — the rules stating what one core is guaranteed to see of another's writes.
• Atomic operation — an update that cannot be observed half-finished.
• Memory bandwidth — how much data can move between memory and the processor per second.

The mental model

Cores multiplied because clock rates could not rise. Two cores at a lower rate use less power than one at twice the speed. Once heat became the limit, more cores was the only move left.

The cost was pushed onto software, where it still sits. A single program does not get faster on more cores unless someone made it able to use them. Making it able is the whole difficulty.

Threads and processes are the two ways to have several things running, and the difference is what they share. Threads within one process share memory, which makes communication free and makes corruption possible. Separate processes share nothing by default and must be given an explicit channel.

The choice is a trade between the cost of communication and the cost of mistakes. Threads are fast and unforgiving. Processes are safer and require more machinery to cooperate.

Cache coherence is the hardware that makes shared memory work at all. Each core has its own cache, so the same address can sit in several of them at once, and something must make them agree.

The traffic that agreement generates is invisible in the source and very visible in the timing. Two cores writing to nearby addresses can be slower than one core doing all the work. The line containing both addresses shuttles between the two caches. That is false sharing, and it is the standard first surprise in parallel programming.

The memory model is the rule set nobody expects to need. Compilers reorder memory operations when the result looks the same, and processors do too. To one core it does look the same.

To another core it does not. A write you placed before a flag can become visible after it, and code that looked correct then fails once a year on one machine. The memory model states what is actually guaranteed, and the synchronisation primitives are what you use to get more.

Locks and atomics are those primitives. A lock makes cores take turns. An atomic instruction performs one small update indivisibly.

Both work by forcing agreement between caches, and both cost far more than the instruction they replace. An atomic increment can cost tens of times an ordinary one. That is not a reason to avoid them, since incorrect fast code is worthless, but it is a reason to keep the shared parts small.

Now the part worth remembering longest: where a second core buys nothing.

Work that is one long chain of dependent steps gains nothing. Each step needs the previous result, and there is no second thing to do. Work limited by memory bandwidth rather than by computation gains little, because the extra cores wait on the same memory. Work with a large shared structure under a lock gains little, because the cores spend their time taking turns.

Recognising these before writing parallel code saves the effort of proving them the hard way. The test is simple to state: is there work that could genuinely happen at the same time, and does it touch mostly separate data? If the answer to either half is no, the second core is not the answer.

What you should now be able to explain or do

• Explain why more cores replaced higher clock rates.
• Say what threads share and what processes do not, and choose between them for a task.
• Describe cache coherence in outline and explain false sharing.
• State why a memory model is necessary, and what synchronisation buys.
• Estimate the cost of a lock or an atomic operation relative to ordinary instructions.
• Identify work that will not benefit from another core, before writing the code.

Check yourself