Multicore Processors and Shared Memory

Since about 2005, processors have not become much faster at running one program, so chip makers have put more cores on each die instead. A multicore processor can run many programs, or many parts of one program, at once. But the cores usually share memory, and that creates two hard problems: keeping their cached copies consistent, and writing programs that use them well. This article explains why multicore happened, how shared memory works, what limits scaling, what false sharing is, and how the chapter's later topics fit together.

12 min read | Intermediate

What You'll Learn

• Explain why the industry moved to multiple cores
• Describe a shared-memory multicore and how threads communicate
• Use Amdahl's law to estimate how speedup scales with cores
• Explain the problems of a data race and false sharing

Why Multicore

For decades, each new chip generation brought smaller transistors, which ran faster at lower voltage, so that frequency rose and power stayed in check. Around 2005 this ended. Voltage could not fall much further without leakage getting out of control, so power density became the limit, as Pipeline Depth vs Frequency explains. But transistors kept getting smaller, and there were more of them. The question became what to do with them.

Making one core larger gives weak returns: doubling a core's area gives roughly the square root of 2, about 40 percent, more speed, according to a rule of thumb from Intel engineer Fred Pollack known as Pollack's rule. Two smaller cores give up to double the throughput for the same area. And because power rises steeply with frequency, two cores at a lower voltage and frequency can use the same power as one fast core, and do more work. PPA Trade-offs and Amdahl's Law gives the numbers. The catch is that this extra throughput only helps software that can use it.

Shared Memory

The usual arrangement gives each core private caches, with a shared last-level cache and memory:

All the cores see one address space. A program's threads, parts that run independently, share the same memory. One thread writes a value, and another reads it. This shared-memory model is the common way of programming a multicore, because threads can pass data just by handing over pointers.

The hardware must support two promises, and each has its own article in this chapter:

• Coherence: every core sees the same value for a memory location. With private caches, several copies can exist, and hardware has to keep them in step. Cache Coherence Protocols explains how.
• Consistency: a rule about the order in which writes to different locations become visible to other cores. Memory Consistency, Atomics and Fences covers that.

Some large systems take a different approach: separate memories and explicit messages, as in clusters of servers. Message passing scales further, but it is harder to program for fine-grained work. Inside one chip, shared memory is the norm, though the hardware underneath is itself passing messages over an interconnect.

How Much Do More Cores Help?

Amdahl's law sets the limit. If a fraction s of a program must run serially, the speedup on n cores is:

speedup = 1 / (s + (1 - s) / n)

Even a program that is 95 percent parallel gets only about 15 times faster on 64 cores. With 25 percent serial work, it can never reach 4. Real programs do worse than this, because they lose time to communication and to waiting. These delays grow with the core count, and sometimes adding more cores makes a program slower.

Amdahl's law assumes a fixed problem size. Gustafson's law takes a different view: people use bigger machines for bigger problems, and the parallel part often grows while the serial part doesn't. A weather simulation with four times the cores runs at higher resolution, rather than finishing four times sooner. Both views are correct for different situations.

Threads Need Coordination

Threads that share data must take care. Consider two threads that each add 1 to a shared counter:

lw   a5,0(a0)       # read the counter
addi a5,a5,1        # add 1
sw   a5,0(a0)       # write it back

If both read the value 10 at the same moment, they both write 11, and one increment is lost. Two threads running code like this, without coordination, have a data race. The result depends on timing, so it appears only sometimes, which makes it very hard to debug. Programs need atomic operations, which do a read-modify-write as a single step, and locks, which let one thread at a time into a section of code. Those need hardware support, and Memory Consistency, Atomics and Fences shows real RISC-V code for them.

Sharing Costs Time

Passing data between cores is much slower than it seems. A cache line written by one core and read by another must move through the coherence system, which can take tens to over a hundred cycles, compared with a few for a local L1 hit. A program whose threads share a lot of data can spend much of its time moving lines around.

False Sharing

A nasty special case is false sharing. Coherence works on whole cache lines. If two threads update two different variables that happen to be in one 64-byte line, the hardware treats this as sharing. The line bounces between the two cores on every write, although they share no data at all.

struct counters {
    long a;         // updated only by thread 1
    long b;         // updated only by thread 2, in the same cache line
};

Each thread has its own variable, and there is nothing wrong in the logic, yet the program can run many times slower than one with those variables on separate lines. The fix is to place each thread's variables on their own line, with padding or alignment. It's a good example of something in the hardware, the line size, showing up in program speed. Performance tools can often detect this kind of contention.

What Else Cores Share

Besides data, cores compete for hardware. They share the last-level cache, so one program that scans a huge array can push out another's data. This is the noisy neighbor problem, and in cloud servers it can make one customer's speed depend on what another is doing. They also share memory bandwidth, and the chip's power budget: when all the cores are busy, each may run at a lower frequency than one could reach alone. That is why a chip's single-core "turbo" frequency is higher than its all-core frequency. Some processors provide cache partitioning and bandwidth controls, so that important work can have a guaranteed share.

How Software Uses Many Cores

Software has several ways to use the cores. The simplest, and very common, is running independent programs side by side, which needs no change at all. A server handling many users is a natural fit: each request is independent, and nothing is shared except the database. A program can also create threads itself, using a library such as POSIX threads, or use a framework such as OpenMP, which splits a loop across the cores with a single annotation. A common design keeps a queue of tasks and a set of worker threads, so that the work spreads itself evenly.

Whatever the method, a good parallel program does most of its work on private data, and communicates rarely. Designing for this is as much a matter of the data's layout as of the code. A rule of thumb is to give each thread its own data, and share only what really must be shared.

Kinds of Multicore

Identical cores are called symmetric multiprocessing (SMP): any thread can run on any core, and the OS shares them out. Heterogeneous multicore mixes different cores, usually fast and efficient ones, so that background work uses little power. Their scheduling is harder, since the OS must pick the right core for each task. Many chips also have asymmetric designs, with small processors dedicated to tasks such as power management or security, running their own firmware. Those are part of the SoC rather than the application processors, and What Is in an SoC describes them.

Interrupts and Booting With Many Cores

A multicore system needs some extra pieces. Each core has its own mhartid, so that boot code can tell which core it is running on, as Privilege Levels and CSRs mentions. Usually one core starts first and wakes up the others. Cores also need to signal each other, for example to request a TLB flush. This uses inter-processor interrupts, and it adds costs, such as the shootdowns in TLBs and Page Table Walks. An interrupt controller steers device interrupts to a suitable core.

Multicore also makes debugging harder. A problem may appear only when threads run in a particular order, and adding a debug print can change that order, so that the problem disappears.

Testing parallel code needs its own tools. A race detector watches memory accesses and reports two threads touching one location without synchronization, even on a run where nothing went wrong. Running more threads than cores helps to shake out failures that depend on timing.

Common Mistakes