Parallelism and Multicore

Why parallelism

For decades, processors got faster mainly by raising the clock frequency. Around the mid-2000s that stopped: higher frequency needed higher voltage, and power (which grows roughly with voltage squared times frequency) became impossible to cool. This is often called the end of Dennard scaling. Transistor counts kept growing, so architects spent the extra transistors on doing more work at the same time instead: more instructions per cycle inside one core, wider vector units, several hardware threads per core, many cores per chip, and GPUs with thousands of simple lanes.

This lesson tours all of those levels. Interviewers commonly ask about Flynn's taxonomy, superscalar versus pipelined execution, out-of-order execution and register renaming, what Spectre is at a high level, SIMD, SMT (hyper-threading), cache coherence and the MESI protocol (often with a state-transition walkthrough), false sharing, why memory fences exist, how a GPU differs from a CPU, and Amdahl's law calculations. It builds on pipelining and cache memory; the software side of threads and locks is in threads and synchronization.

Flynn's taxonomy

Michael Flynn's 1966 classification sorts machines by how many instruction streams and data streams they process at once.

            single data          multiple data
          +----------------+-------------------+
single    |     SISD       |       SIMD        |
instr     |  one core      |  vector unit      |
          +----------------+-------------------+
multiple  |     MISD       |       MIMD        |
instr     |  (rare)        |  multicore, cluster|
          +----------------+-------------------+

Real chips mix classes: a multicore CPU is MIMD across cores and SIMD within each core's vector unit. GPUs are described with Nvidia's term SIMT (single instruction, multiple threads), covered later.

Instruction-level parallelism

Instruction-level parallelism (ILP) is the overlap of independent instructions from a single thread. Pipelining is the first step: different instructions occupy different stages. Two further ideas push ILP much further.

Superscalar execution

A superscalar processor fetches, decodes and issues more than one instruction per cycle into several execution units. A 4-wide superscalar core can, in the best case, complete 4 instructions per cycle, an IPC (instructions per cycle) of 4, or a CPI of 0.25.

Scalar pipeline (1 instruction per cycle):
cycle:   1   2   3   4   5   6
I1      IF  ID  EX  MEM WB
I2          IF  ID  EX  MEM WB

2-wide superscalar (2 per cycle):
cycle:   1   2   3   4   5
I1      IF  ID  EX  MEM WB
I2      IF  ID  EX  MEM WB
I3          IF  ID  EX  MEM WB
I4          IF  ID  EX  MEM WB

The limit is dependences. If I2 needs I1's result, they cannot execute in the same cycle. Real code has many dependences, branches and cache misses, so typical IPC on general code is well below the machine's width.

A contrasting approach is VLIW (very long instruction word): the compiler packs independent operations into one wide instruction, and the hardware does no dependence checking. It simplifies hardware but depends heavily on the compiler and is common in DSPs rather than general-purpose CPUs.

Out-of-order execution

In an in-order processor, if one instruction stalls (say, waiting for a cache miss), everything behind it waits, even independent instructions. An out-of-order (OoO) processor lets later independent instructions execute as soon as their operands are ready, while still making the results appear in program order.

Program order:
  I1: load  r1, [r2]      ; cache miss, 200 cycles
  I2: add   r3, r1, 4     ; depends on I1 -> must wait
  I3: mul   r4, r5, r6    ; independent  -> can run now
  I4: sub   r7, r4, 1     ; depends only on I3 -> can run now

In order, I3 and I4 wait 200 cycles behind I2. Out of order, they finish long before the load returns. The main structures (detailed in the modern processors lesson) are:

• Reservation stations / issue queue: instructions wait here until their source operands are ready, then are dispatched to an execution unit.
• Register renaming: removes false dependences.
• Reorder buffer (ROB): keeps instructions in program order so they can retire (commit) in order.

Register renaming

Three kinds of data dependence exist between instructions:

• RAW (read after write): a true dependence. I2 reads what I1 wrote. Must be respected.
• WAR (write after read): an anti-dependence. I2 writes a register that I1 still needs to read.
• WAW (write after write): an output dependence. Both write the same register; the final value must be the later one.

WAR and WAW are false (name) dependences: they exist only because the ISA has a small number of register names, not because data flows between the instructions. Register renaming maps each architectural register (like r1) onto a much larger pool of physical registers. Every new write gets a fresh physical register, so false dependences vanish.

Before renaming                   After renaming
I1: r1 = r2 + r3                 p10 = p2 + p3
I2: r4 = r1 * 2      (RAW on r1) p11 = p10 * 2
I3: r1 = r5 - 1      (WAW with I1, WAR with I2)
                                 p12 = p5 - 1    <- independent now
I4: r6 = r1 + r4                 p13 = p12 + p11

After renaming, I3 can execute in parallel with I1 or I2. A register alias table (RAT) records which physical register currently holds each architectural register.

The reorder buffer and precise exceptions

Executing out of order is safe only if the outside world sees in-order behaviour. The reorder buffer is a circular queue holding every in-flight instruction in program order. Instructions are inserted at the tail when decoded, marked complete when they finish executing (in any order), and retire from the head only when they and all older instructions are complete. Retirement is when results become architecturally visible: the register mapping becomes permanent, and stores are released to memory.

Reorder buffer (head = oldest)

head -> [I1 load  : waiting ] [I2 add : waiting ] [I3 mul : done]
        [I4 sub   : done    ] [I5 ...           ]          <- tail
I3 and I4 finished early, but cannot retire until I1 and I2 retire.

This gives precise exceptions: if I1 faults, everything after it is discarded, and the OS sees a state exactly as if instructions up to I1 had run in order. The same mechanism lets the processor throw away wrongly speculated work.

Speculative execution

Branches appear every five or so instructions in typical code. Waiting to resolve each one would starve a wide out-of-order core. So the core predicts the branch direction and target and keeps fetching and executing down the predicted path: speculative execution. If the prediction was right, the work is kept. If wrong, every instruction after the branch is flushed from the ROB, the renaming state is rolled back, and fetch restarts on the correct path. The cost of a misprediction is roughly the depth of the pipeline front end, typically around 10 to 20 cycles on modern cores.

Spectre at a conceptual level

Rolling back speculative work restores registers and memory, but not everything. Speculatively executed loads still bring lines into the cache, and that cache footprint can be measured afterwards by timing accesses. Spectre (disclosed in 2018) uses this.

/* Variant 1 shape: bounds-check bypass */
if (x < array1_size) {               /* predictor trained to say "true" */
    y = array2[array1[x] * 4096];    /* runs speculatively with bad x */
}

1. The attacker trains the branch predictor by calling the code many times with valid x.
2. They then pass an out-of-bounds x while array1_size is not in the cache, so the bounds check takes a long time to resolve.
3. The core speculatively reads array1[x], a secret byte outside the array, and uses it to index array2, which loads one particular line of array2 into the cache.
4. The branch resolves, the work is squashed, but the line stays cached.
5. The attacker times accesses to each line of array2; the fast one reveals the secret byte.

The lesson is that speculation is not side-effect free: microarchitectural state (caches, predictors) leaks information. Mitigations include speculation barriers (such as lfence on x86), masking array indexes so they stay in bounds even speculatively, retpolines and hardware changes for indirect branch prediction, and process isolation in browsers. Meltdown, disclosed at the same time, was a related flaw in which some processors let a faulting load forward kernel data to dependent instructions before the permission check took effect; it was fixed by separating kernel and user page tables and later in hardware.

SIMD and vector instructions

A SIMD instruction applies one operation to several data elements packed into a wide register. A 256-bit register holds eight 32-bit floats, so one AVX add performs eight additions.

256-bit vector add (8 x 32-bit floats)

 a: | a0 | a1 | a2 | a3 | a4 | a5 | a6 | a7 |
 b: | b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7 |
     +    +    +    +    +    +    +    +
 c: | c0 | c1 | c2 | c3 | c4 | c5 | c6 | c7 |   one instruction

You usually get SIMD in one of three ways: the compiler auto-vectorises simple loops at -O2/-O3; you call intrinsics (C functions that map to specific instructions); or you use libraries (BLAS, NumPy, image codecs) that already do.

/* A loop compilers vectorise readily: independent iterations,
   contiguous arrays, no aliasing (restrict). */
void saxpy(int n, float a, const float *restrict x, float *restrict y) {
    for (int i = 0; i < n; i++)
        y[i] = a * x[i] + y[i];
}

What blocks vectorisation: dependences between iterations (a[i] = a[i-1] + 1), possible pointer aliasing, complex control flow inside the loop, non-contiguous (strided or gathered) data, and function calls the compiler cannot inline. Vector architectures in the classic Cray sense, and modern SVE and RVV, add a vector-length register so the same code runs on hardware with different widths.

Hardware multithreading

A single thread often leaves a core idle: it waits for a cache miss, or it simply lacks enough independent instructions to fill all execution units. Hardware multithreading keeps several threads' state (program counters, architectural registers) inside one core so the core can switch between them or mix them.

• Coarse-grained multithreading: run one thread until it hits a long stall (such as a last-level cache miss), then switch to another. Switching costs a few cycles of pipeline refill, so it only hides long stalls.
• Fine-grained multithreading: switch threads every cycle, round-robin, skipping stalled ones. Hides short stalls too, but a single thread runs slower because it gets only a share of cycles. Used in some throughput-oriented designs and in GPUs.
• Simultaneous multithreading (SMT): in a superscalar out-of-order core, issue instructions from several threads in the same cycle, filling execution slots one thread alone would leave empty. Intel markets its 2-way SMT as Hyper-Threading; AMD and IBM POWER also use SMT (POWER up to 8-way).

Issue slots per cycle (4-wide core), letters = thread, . = empty

           cycle 1   cycle 2   cycle 3   cycle 4
no MT      A A . .   A . . .   . . . .   A A A .
coarse     A A . .   A . . .   B B B .   B B . .   (switch on stall)
fine       A A . .   B B B .   A . . .   B B . .   (switch each cycle)
SMT        A A B B   A B B B   B B . .   A A A B   (mix in one cycle)

SMT threads share caches, TLBs, execution units and branch predictors. Two hyper-threads are therefore not two cores: depending on the workload, the second thread may add a modest throughput gain, nothing, or even slow things down by competing for cache. It also creates shared state that has been used for side channels, which is why some security-sensitive deployments disable SMT.

Multicore and shared caches

A multicore processor (a chip multiprocessor) places several complete cores on one die. A typical layout:

+---------------------------------------------------------+
|  Core 0          Core 1          Core 2          Core 3 |
| +------+        +------+        +------+        +------+|
| |L1I L1D|       |L1I L1D|       |L1I L1D|       |L1I L1D||
| |  L2   |       |  L2   |       |  L2   |       |  L2   ||
| +---+---+       +---+---+       +---+---+       +---+---+|
|     +--------------+---------------+---------------+    |
|          shared L3 (last-level cache), interconnect     |
|                  memory controller  -> DRAM             |
+---------------------------------------------------------+

Private L1 and (often) L2 caches keep latency low; a shared last-level cache (LLC) lets cores share data without going to DRAM and lets a single busy core use most of the capacity. Large chips split the LLC into slices connected by a ring or mesh network, so different slices have slightly different latencies. In multi-socket servers, each socket has its own memory, giving NUMA (non-uniform memory access): local memory is faster than memory attached to another socket.

Cache coherence

Private caches create a problem. If core 0 and core 1 both cache variable X, and core 0 writes it, core 1's copy is stale. Cache coherence is the guarantee that all cores see a single, consistent value for each memory location. Formally, a coherent system ensures:

1. A read by a core returns the value of the most recent write to that location (in a well-defined order).
2. Writes to the same location are seen in the same order by all cores (write serialisation).

The standard approach is a write-invalidate protocol: before a core writes a line, all other copies are invalidated, so the writer holds the only copy. (The alternative, write-update, broadcasts every new value to all sharers; it costs much more bandwidth and is rarely used.)

Snooping

In a snooping protocol, every cache controller watches (snoops) a shared broadcast medium, historically a bus, on which all misses and invalidations appear. When a cache sees a request for a line it holds, it reacts: supplies data, downgrades its state or invalidates its copy. Snooping is simple and fast for a handful of cores, but every coherence request is broadcast to everyone, which does not scale to dozens of cores.

The MESI protocol

MESI names the four states a cache line can be in:

The E state is MESI's improvement over the simpler MSI protocol: a core that reads data no one else has gets it in E, and can later write it silently (E to M) without any bus transaction. That is the common case for private data.

Bus transactions used below:

• BusRd: read a line (on a read miss).
• BusRdX (read for ownership): read a line intending to write it; all other copies must invalidate.
• BusUpgr (upgrade, or invalidate): "I already have it in S and want to write; everyone else invalidate."
• Flush: a cache with the line in M supplies or writes back the data.

MESI transitions (local processor actions)

  I --read, others have copy--> S       I --read, no other copy--> E
  I --write (BusRdX)----------> M       S --write (BusUpgr)-------> M
  E --write (silent)----------> M       E, S, M --read-----------> same

MESI transitions (snooped from other caches)

  M --BusRd (flush data)--> S           M --BusRdX (flush)--> I
  E --BusRd---------------> S           E --BusRdX----------> I
  S --BusRdX or BusUpgr---> I

Worked example: MESI on two cores

Two cores, P0 and P1, each with a private cache. Memory location X starts at 0 and is in neither cache.

Step by step:

1. P0 reads X. P0 misses and issues BusRd. No other cache holds X, so P0 loads it in E.
2. P1 reads X. P1 misses and issues BusRd. P0 snoops it, sees it holds X in E, and downgrades to S. P1 loads it in S.
3. P0 writes 5. P0 has S, so it must make sure no one else has a copy. It broadcasts BusUpgr. P1 snoops and invalidates (I). P0 moves to M and writes 5 into its cache. Memory still holds 0.
4. P1 reads X. P1 misses (its copy is invalid) and issues BusRd. P0 snoops it, holds X in M, so it flushes 5 (to P1 and memory) and drops to S. P1 gets 5 in S. Without coherence, P1 would have read the stale 0.
5. P1 writes 7. P1 issues BusUpgr; P0 invalidates. P1 goes to M.
6. P0 writes 9. P0's copy is invalid, so it issues BusRdX. P1 snoops, flushes 7 and invalidates. P0 gets the line and goes to M, then writes 9.
7. P0 writes 10. P0 already has M: a pure cache hit, no bus traffic at all.

Notice the ping-pong in steps 3 to 6: each time the writer changes, the line must travel between caches. Lines that bounce between cores like this are expensive, which is exactly what goes wrong with false sharing.

Variants you may hear about: MOESI (AMD) adds an Owned state so a dirty line can be shared without writing it back to memory first; MESIF (Intel) adds a Forward state naming the one sharer that answers requests, so not every sharer replies.

Directory-based coherence

Broadcasting every miss to every core does not scale. A directory protocol keeps, for each memory block (or each line in the LLC), an entry recording its state and which cores hold copies, for example as a bit vector with one bit per core. Requests go to the block's home node (the directory slice responsible for it), which sends invalidations or forwards only to the cores that actually have copies.

Directory entry for block B (8 cores)

+---------+-------------------------+
| state   | sharers: 0 1 2 3 4 5 6 7 |
| Shared  |          0 1 0 0 1 0 0 0 |  -> cores 1 and 4 hold B
+---------+-------------------------+

Core 6 writes B:
  core 6 --> home(B): request exclusive
  home   --> cores 1, 4: invalidate         (point to point, no broadcast)
  cores 1, 4 --> home: acknowledgements
  home   --> core 6: data + permission;  entry = Modified, owner 6

Directories cost storage (a bit per core per tracked block) and add an indirection hop, but traffic grows with the number of actual sharers rather than with the number of cores. Large multicore chips and multi-socket systems use directory-style or hybrid schemes (often with a snoop filter that tracks which lines private caches hold).

False sharing

Coherence works on whole cache lines, not on individual variables. False sharing happens when two threads write different variables that happen to sit in the same cache line. Neither thread reads the other's data, yet every write invalidates the other core's copy, and the line ping-pongs between cores exactly as in the MESI walkthrough.

#include <pthread.h>
#include <stdio.h>
#include <time.h>

#define ITERS 100000000L

struct packed { volatile long a; volatile long b; };              /* same line   */
struct padded { volatile long a; char pad[120]; volatile long b; }; /* own lines */

static struct packed p;
static struct padded q;

static void *bump(void *arg) {
    volatile long *x = arg;
    for (long i = 0; i < ITERS; i++) (*x)++;
    return NULL;
}

static double run(volatile long *x, volatile long *y) {
    struct timespec t0, t1;
    pthread_t ta, tb;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_create(&ta, NULL, bump, (void *)x);
    pthread_create(&tb, NULL, bump, (void *)y);
    pthread_join(ta, NULL);
    pthread_join(tb, NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
}

int main(void) {
    printf("same cache line:      %.2f s\n", run(&p.a, &p.b));
    printf("separate cache lines: %.2f s\n", run(&q.a, &q.b));
    return 0;
}

Two threads each increment their own counter 100 million times. In packed the two counters are 8 bytes apart (same line); in padded they are 128 bytes apart, which separates them even on cores with 128-byte lines. Compiled with gcc -O2 -pthread and run on an Apple M2 laptop, five runs consistently gave:

same cache line:      0.14 - 0.17 s
separate cache lines: 0.03 s

The padded version was about five times faster, with identical work. (volatile is used here only to stop the compiler from collapsing the loop into one addition; it is not a synchronisation tool.) The gap is larger on many multi-socket servers, where moving a line between sockets is slower.

Fixes:

• Pad or align per-thread data to the line size: alignas(64) in C11/C++11, std::hardware_destructive_interference_size in C++17, the @Contended annotation inside the JDK.
• Give each thread a local accumulator and combine at the end (often the best fix).
• Be careful with arrays of per-thread counters indexed by thread id: they are a classic source.

True sharing, by contrast, is when threads really do access the same variable; then the cost is inherent and the fix is algorithmic (less sharing, batching updates).

Memory consistency models

Coherence talks about one location. Memory consistency is about the order in which a core's reads and writes to different locations become visible to other cores. This matters for any lock-free code and for how locks themselves are built.

Sequential consistency

Sequential consistency (SC), defined by Leslie Lamport, says the result of any execution is the same as if all cores' operations were interleaved into one global order, and each core's operations appear in that order in program order. It is the intuitive model, but it forbids many hardware optimisations.

Relaxed models and the store buffer

Real processors put a store buffer between each core and its cache, so a store can retire without waiting for the cache line. Loads may then complete before earlier stores become visible to other cores. Consider this classic test, with x and y both 0 initially:

Thread 1          Thread 2
x = 1             y = 1
r1 = y            r2 = x

Under SC, at least one store happens before both loads, so r1 == 0 && r2 == 0 is impossible. On x86, whose model is TSO (total store order), both stores can sit in their store buffers while both loads read 0, so the outcome can happen. ARM and POWER are more relaxed still: they may also reorder loads with loads and stores with stores to different addresses. Compilers reorder memory operations as well.

Why fences exist

A memory fence (barrier) is an instruction that forces ordering: operations before it become visible before operations after it. Examples: mfence on x86, dmb on ARM, fence on RISC-V. Lighter forms are acquire (no later access may move before this load) and release (no earlier access may move after this store) semantics, which is exactly what a lock needs: acquiring the lock must not let critical-section accesses float above it, and releasing must not let them sink below.

#include <stdatomic.h>

int data;                    /* ordinary variable */
atomic_int ready = 0;

void producer(void) {
    data = 42;
    atomic_store_explicit(&ready, 1, memory_order_release);
}

int consumer(void) {
    while (atomic_load_explicit(&ready, memory_order_acquire) == 0) { }
    return data;             /* guaranteed to see 42 */
}

Without release/acquire, a weakly ordered CPU (or the compiler) could make ready = 1 visible before data = 42, and the consumer could read a stale data. In practice you rarely write fences yourself: mutexes, std::atomic, Java volatile and java.util.concurrent insert the right ones. Knowing why they exist is what interviewers test.

GPUs and SIMT

A GPU (graphics processing unit) devotes its transistors to many simple arithmetic lanes instead of to big caches, branch predictors and out-of-order logic. It targets throughput (total work per second) on highly parallel problems, while a CPU targets latency (finishing one thread quickly).

Nvidia's model, SIMT (single instruction, multiple threads):

• A program, the kernel, is launched over thousands to millions of threads, grouped into blocks (thread blocks) assigned to streaming multiprocessors (SMs).
• The hardware runs threads in groups of 32 called warps (AMD's equivalent is a wavefront, 32 or 64 wide). All threads in a warp execute the same instruction at the same time on different data, like SIMD, but each thread has its own registers and appears to the programmer as an independent thread.
• Branch divergence: if threads in a warp take different sides of an if, the warp executes both sides one after the other, masking off inactive threads. Divergent code wastes lanes.
• Latency hiding by multithreading: an SM keeps many warps resident; when one waits on memory (hundreds of cycles), the scheduler switches to another ready warp at almost no cost. This replaces big caches as the main latency-hiding strategy.
• Memory coalescing: when the 32 threads of a warp access consecutive addresses, the hardware combines them into a few wide memory transactions. Scattered accesses waste bandwidth.

Amdahl's law and Gustafson's law

Amdahl's law

If a fraction p of a program's run time can be parallelised perfectly over N processors and the rest (1 − p) stays serial, the speedup is:

Speedup(N) = 1 / ((1 - p) + p / N)

As N grows without limit:  Speedup -> 1 / (1 - p)

Worked example: Amdahl

1. p = 0.9, N = 8: 1 ÷ (0.1 + 0.9 ÷ 8) = 1 ÷ (0.1 + 0.1125) = 1 ÷ 0.2125 = 4.71.
2. p = 0.9, N = 64: 1 ÷ (0.1 + 0.0140625) = 8.77.
3. Limit for p = 0.9: 1 ÷ 0.1 = 10, however many cores you add.
4. p = 0.95, N = 16: 1 ÷ (0.05 + 0.059375) = 9.14; limit 20.
5. p = 0.8, N = 4: 1 ÷ (0.2 + 0.2) = 2.5.

Going from 8 to 64 cores (8 times the hardware) took the speedup from 4.71 to only 8.77. The serial 10 percent dominates. Amdahl's law applies to any enhancement, not just parallelism: speeding up a part that takes fraction f of the time by factor s gives 1 ÷ ((1 − f) + f ÷ s).

Gustafson's law

Amdahl assumes a fixed problem size. In practice, people with more processors usually solve bigger problems in the same time (finer simulation grids, larger models). Gustafson's law measures that scaled speedup. If, on the N-processor machine, a fraction α of the time is serial:

Scaled speedup(N) = N - alpha × (N - 1)

Worked example: Gustafson

With α = 0.1:

1. N = 8: 8 − 0.1 × 7 = 7.3.
2. N = 64: 64 − 0.1 × 63 = 57.7.

The same 10 percent serial fraction gives very different conclusions. They are not contradictory: Amdahl answers "how much faster does this fixed job run?" (strong scaling), and Gustafson answers "how much more work can I do in the same time?" (weak scaling). Note that α in Gustafson is the serial fraction measured on the parallel machine, not on one processor.

Interview questions

Q1. Explain Flynn's taxonomy with examples.

It classifies machines by instruction and data streams. SISD is a classic single scalar core; SIMD applies one instruction to many data elements, as in vector units like AVX or NEON; MISD is rare, sometimes cited for redundant systems; MIMD runs different instruction streams on different data, as in multicore processors and clusters. Modern chips combine MIMD across cores with SIMD inside each core.

Q2. What is the difference between pipelining and superscalar execution?

Pipelining overlaps different stages of successive instructions, aiming for one instruction completed per cycle. Superscalar execution adds multiple parallel pipelines so several instructions can be issued and completed in the same cycle, aiming for an IPC above 1. Modern cores are both deeply pipelined and superscalar.

Q3. What problem does register renaming solve?

It removes false dependences (WAR and WAW) that arise only because the ISA has few register names. Each write to an architectural register is assigned a fresh physical register, so later instructions that reuse the name no longer have to wait for earlier readers or writers. True RAW dependences remain.

Q4. What is the reorder buffer for?

It holds in-flight instructions in program order. Instructions can execute and complete out of order, but they retire from the head of the ROB in order, which is when their results become architecturally visible. This provides precise exceptions and allows mispredicted speculative work to be discarded cleanly.

Q5. What is Spectre, conceptually?

It exploits speculative execution: a mispredicted branch causes the processor to execute instructions that access secret data, and although the results are discarded, their effect on the cache remains. An attacker measures cache timing to recover the secret. It shows that microarchitectural state is a side channel; mitigations include speculation barriers, index masking and isolation.

Q6. What is SMT, and is a hyper-thread as good as a core?

Simultaneous multithreading lets one superscalar core issue instructions from two or more threads in the same cycle, using execution slots one thread would leave idle. The threads share caches, execution units and predictors, so a second hyper-thread usually gives much less than a second core's worth of throughput, and on some workloads none.

Q7. What is cache coherence, and why is it needed?

When cores have private caches, several copies of the same memory line can exist, and a write by one core would leave the others stale. Coherence guarantees that reads return the latest write and that all cores see writes to the same location in the same order. Hardware maintains it with snooping or directory protocols, usually by invalidating other copies before a write.

Q8. Walk through MESI when two cores read and then one writes a shared line.

Core A reads first and, finding no other copy, gets the line in Exclusive. Core B reads; A snoops and downgrades to Shared, and B gets Shared. When A writes, it broadcasts an upgrade or invalidate; B moves to Invalid and A to Modified. If B reads again, A supplies the dirty data and both end in Shared.

Q9. Why does MESI have an Exclusive state?

It lets a core that reads data no other core holds later write it without any bus transaction, moving silently from E to M. Without E (plain MSI), the line would be loaded in Shared and every first write to private data would need an invalidation broadcast.

Q10. Snooping versus directory-based coherence?

Snooping broadcasts coherence requests to all caches, which watch and respond; it is simple and fast for a few cores but bandwidth grows with core count. Directory protocols keep a per-block record of sharers at a home node and send targeted messages only to those caches, scaling to many cores at the cost of directory storage and an extra indirection.

Q11. What is false sharing, and how do you fix it?

Two threads write different variables that sit in the same cache line, so coherence bounces the line between their cores on every write even though no data is actually shared. Fix it by padding or aligning per-thread data to the cache-line size, or by keeping thread-local accumulators and combining them at the end.

Q12. Why do memory fences exist?

Processors use store buffers and reorder memory operations to different addresses, and compilers reorder too, so other cores may observe a thread's writes in a different order than the program wrote them. Fences, or acquire/release operations, enforce ordering at specific points so that, for example, data written before releasing a lock is visible to the next core that acquires it.

Q13. How does a GPU hide memory latency differently from a CPU?

A CPU relies on large caches, out-of-order execution and prefetching to avoid or overlap stalls within one thread. A GPU keeps many warps resident on each multiprocessor and switches to a ready warp whenever one is waiting on memory, so the latency is hidden by sheer parallelism rather than avoided.

Q14. A program is 80 percent parallelisable. What is the maximum speedup on 4 cores and on infinite cores?

On 4 cores: 1 ÷ (0.2 + 0.8 ÷ 4) = 1 ÷ 0.4 = 2.5. On infinitely many cores: 1 ÷ 0.2 = 5. The serial 20 percent caps the speedup at 5 no matter how many cores are added.

Q15. How does Gustafson's law differ from Amdahl's?

Amdahl's law assumes a fixed problem size and shows speedup is capped by the serial fraction. Gustafson's law assumes the problem grows with the machine so run time stays fixed, giving scaled speedup N − α(N − 1), which keeps growing nearly linearly when the serial fraction is small. They measure strong and weak scaling respectively.

Key takeaways

• Power limits ended frequency scaling, so performance now comes from parallelism at every level: ILP, SIMD, multithreading, multicore and GPUs.
• Flynn's taxonomy: SISD, SIMD, MISD, MIMD; real chips mix SIMD and MIMD.
• Superscalar issue, out-of-order execution, register renaming (removes WAR/WAW) and the reorder buffer (in-order retirement, precise exceptions) extract ILP.
• Speculation is rolled back architecturally but leaves cache traces, the root of Spectre.
• SMT shares one core between threads; it is not equivalent to extra cores.
• MESI keeps private caches coherent by invalidating other copies before a write; E allows silent writes to private data; directories replace broadcasts at scale.
• False sharing makes independent variables in one cache line ping-pong between cores; padding gave about a 5 times speedup in the measured example.
• Hardware may reorder memory operations to different addresses (TSO on x86, weaker on ARM); fences and acquire/release restore the needed order.
• Amdahl caps fixed-size speedup at 1 ÷ (1 − p); Gustafson shows scaled speedup N − α(N − 1).

Next lesson

Continue with Modern processors and performance.