Four Kinds of Parallelism

They differ along every axis that matters: who creates the parallelism, what the work has to look like to qualify, what it costs to use, and what goes wrong when it does not fit. Reading them as one thing called "parallelism" makes every one of those distinctions invisible.

Note especially the ordering by risk. Instruction-level parallelism is extracted by hardware and cannot produce a wrong answer. Data-level parallelism is generated by the compiler or by explicit vector code and is still single-threaded, so it also cannot race. Thread-level and core-level parallelism introduce shared mutable state and everything that comes with it — synchronisation, coherence traffic, and a class of bugs the first two cannot produce.

They also compose multiplicatively rather than exclusively. A well-optimised numeric kernel typically uses all four: independent chains within an iteration, vector instructions across elements, and several threads on several cores. Each layer multiplies the one below, which is why fixing the bottom layers first pays off at every layer above.

The requirements are genuinely different, and a problem can qualify for one and not another. A loop summing an array qualifies for all four. A loop walking a linked list qualifies for essentially none — the dependency chain kills instruction-level parallelism, the irregular addresses kill vectorisation, and splitting a traversal across threads requires knowing where the list is, which you do not until you have walked it.

That asymmetry is the practical point. Before asking how to parallelise, ask what shape the work has. If the data is contiguous and the operation uniform, the cheap mechanisms apply and should be used first. If the work is a serial chain through memory, no amount of threading helps and the real fix is a different data structure (Both Are O(n). One Is Far Slower., Data-Oriented Design, Without the Dogma).

The ordering that follows is: fix the dependency structure, then vectorise, then thread. Each step makes the next more effective, and each is cheaper and safer than the one after it. Reversing the order is how teams end up with a threaded implementation of a memory-bound loop that scales to two cores and then stops.

The multiplication is not unlimited, and the ceiling is usually memory. Vectorising increases the rate at which a core consumes data; threading increases the number of cores consuming it. Both push against finite memory bandwidth, and a kernel that was compute-bound in scalar single-threaded form is frequently bandwidth-bound after both transformations (When the Memory Bus Is the Bottleneck).

This is why the four mechanisms should be applied with measurement between them rather than all at once. The transformation that would have given a large speedup on a compute-bound loop gives very little once the loop has become bandwidth-bound, and the counters will say so — the same reasoning Busy Is Not the Same as Working formalises.

The second ceiling is Amdahl-shaped and applies only to the threaded mechanisms: whatever fraction of the work is serial bounds the total speedup regardless of core count. Instruction- and data-level parallelism do not have this property in the same form, because they operate within the serial portion rather than around it — another reason to exhaust them first.