Parallel processors and multicore

Since about 2005, processors have not got much faster per core: higher clock rates made chips too hot (the power wall). Instead, chips got more cores. Today, faster programs are usually parallel programs.

Flynn's taxonomy

SIMD applies one instruction to many values at once: an AVX instruction adds 8 pairs of numbers in one step. Image filters, audio and machine learning use it constantly.

Multicore and cache coherence

A multicore chip has several cores sharing memory, each with its own L1 cache. If core 0 changes a value that core 1 also has in its cache, core 1's copy is now wrong. Cache coherence protocols such as MESI prevent this: each cached block is Modified, Exclusive, Shared or Invalid, and a write by one core invalidates the copies in the others.

caches = {0: {}, 1: {}}
memory = {"x": 5}

def read(core, name):
    if name not in caches[core]:
        caches[core][name] = memory[name]
    return caches[core][name]

def write(core, name, value):
    for other in caches:              # invalidate everyone else's copy
        if other != core:
            caches[other].pop(name, None)
    caches[core][name] = value
    memory[name] = value              # (write-through, to keep it short)

print("core 1 reads x:", read(1, "x"))
write(0, "x", 9)
print("core 0 wrote 9; core 1's copy was invalidated:", "x" not in caches[1])
print("core 1 reads x again:", read(1, "x"))

GPUs

A GPU has thousands of small cores running the same program on different data (SIMT: single instruction, multiple threads). It is slow at one long chain of decisions but superb at the same arithmetic on millions of pixels, or the matrix multiplications of deep learning.

How much faster can parallel be?

Amdahl's law (from the Measuring performance lesson): with a fraction p of the work parallel and n cores, speedup = 1 ÷ ((1 − p) + p ÷ n). The serial part sets a hard limit.

Gustafson's law looks at it differently: with more cores, people solve bigger problems, and the parallel part grows with the problem. Scaled speedup = (1 − p) + p × n.

p = 0.9                                  # 90% of the work is parallel
for n in [1, 2, 4, 16, 64, 1024]:
    amdahl = 1 / ((1 - p) + p / n)
    gustafson = (1 - p) + p * n
    print(n, "cores: Amdahl", round(amdahl, 2), " Gustafson", round(gustafson, 1))

Mark lesson complete