Parallelism: multicore, threads, synchronisation and cache coherence

Until the early 2000s programs got faster on their own, with each new processor generation, thanks to higher frequencies. Then frequency stopped rising (Electronic Devices lesson on CMOS logic), and the extra transistors were used to put several processors, the cores, on the same chip. Since then, to go faster, programs must be written to work in parallel. In this lesson we cover threads, the problem of race conditions, synchronisation, cache coherence and the other forms of parallelism.

Multicore processors

Each core is a complete processor, with its own pipeline and private caches; the cores share the last-level cache and memory. The operating system assigns threads to the cores: independent streams of execution, which may belong to different programs or to the same program. Threads of the same program share memory, which is both their strength (they exchange data without copying it) and their danger.

The race condition

Two threads each increment the same counter a million times:

int counter = 0;

void *work(void *arg) {
    for (int i = 0; i < 1000000; i++)
        counter++;
    return NULL;
}

The expected result is 2 000 000, but running the program gives lower values, different every time. The reason: counter++ is not a single operation, but three instructions (load, add, store). If both threads load the same value, say 41, before the other has stored, both write 42: one increment is lost. This is a race condition: the result depends on the random order in which the threads run. These bugs are among the hardest to find, because they occur rarely and disappear when you try to observe them.

Synchronisation

• Mutual exclusion (mutex): a lock that only one thread at a time can hold. The part of code accessing shared data, the critical section, is enclosed between lock and unlock:

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void *work(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&m);
        counter++;
        pthread_mutex_unlock(&m);
    }
    return NULL;
}

• Atomic operations: the hardware provides instructions that read, modify and write a variable indivisibly (in C, atomic_fetch_add). For a counter they are much more efficient than a mutex.

Synchronisation has a cost and brings new dangers: deadlock, when two threads each wait for a lock held by the other, and loss of parallelism, when threads spend more time waiting for each other than working. The best solution is often to avoid sharing: each thread adds into its own private counter, and only at the end are the partial results added.

Cache coherence

If two cores hold a copy of the same data in their caches and one modifies it, the other must not keep reading the old value. A coherence protocol such as MESI tracks the state of each line in each cache (Modified, Exclusive, Shared, Invalid): before writing, a core invalidates the others’ copies. The programmer does not see it, but pays its effects:

• false sharing: two threads write different variables that sit in the same 64-byte line; the line bounces continuously between the two cores’ caches, and the program slows down a lot without really sharing anything. It is avoided by spacing out data used by different threads.

Other forms of parallelism

• SIMD (single instruction, multiple data): instructions operating on vectors of 4, 8 or 16 numbers at once (SSE, AVX on PCs, NEON on ARM). Compilers use them automatically in simple loops; they are why audio, video and neural networks run fast even on the CPU.
• GPUs: thousands of simple units running the same program on different data. Born for graphics, they have become the engine of scientific computing and artificial intelligence. They work very well on highly regular problems with lots of data, poorly on code full of conditions.
• Instruction-level parallelism: the kind exploited automatically by superscalar and out-of-order processors (lesson on the pipeline).

How much is gained

Amdahl’s law returns: with 95% of the program parallelisable, 16 cores give at most a speedup of 9.1 and infinitely many cores 20. Moreover, threads must synchronise and shared memory has limited bandwidth. Gustafson’s law offers a more optimistic view: in practice, with more cores one does not solve the same problem faster, but a bigger problem in the same time (a finer simulation, an image with more pixels), and there the parallel part grows and the speedup approaches the number of cores.