Multicore, Coherence & Thread-Level Parallelism

thread-level parallelism

Picture a kitchen with several cooks. If a feast can be split into independent jobs — one cook on soup, one on salad, one on dessert — the cooks work at the same time and dinner is ready far sooner. But some dishes must be made in order (you cannot frost a cake before it is baked), so those steps cannot be parallelized no matter how many cooks you hire. Thread-level parallelism is exactly this: finding chunks of a program that can run as separate threads at the same time, on separate cores.

A thread is an independent stream of instructions with its own program counter and its own working registers, sharing the program's memory with its sibling threads. Where instruction-level parallelism (a different idea) overlaps tiny operations inside a single instruction stream, thread-level parallelism runs whole separate streams at once. The parallelism can come from one program deliberately spawning many threads to share a big task, or simply from many independent programs running together. A multicore chip exists precisely to cash in this kind of parallelism: give it N threads ready to run and it can run up to N of them across N cores.

The honest limit is that not all work has thread-level parallelism to find. Truly sequential work — each step needing the previous step's result — has none, and forcing it onto many cores only adds coordination overhead. Even parallel-friendly work loses some speedup to the cost of creating threads, locking shared data, and waiting at synchronization points. Thread-level parallelism is abundant in servers (thousands of independent requests) and in data-crunching (split the array), but scarce in a single user clicking through one task at a time.

Summing a million-element array on 4 cores: give each core a quarter of the array to add up, then add the four partial sums. The four quarter-sums have no dependence on each other, so they run as four parallel threads — close to a 4x speedup, minus the tiny final step of combining four numbers.

Independent partial sums parallelize cleanly; the single combining step is the irreducible serial tail that Amdahl's law warns about.

Thread-level parallelism is about separate instruction streams, not the data-parallel SIMD idea (one instruction over many data elements). A workload can have lots of one and none of the other.

Also called
TLPtask parallelism