Multicore Processors and Thread-Level Parallelism

Thread-level parallelism (TLP) is parallelism that comes from executing multiple, largely independent streams of instructions — threads — concurrently, rather than from finding independent instructions within a single stream, which is instruction-level parallelism (ILP). A thread is a sequence of instructions with its own program counter and register state that can, in principle, be scheduled and executed independently of other threads. Threads can belong to the same process (sharing an address space) or to different processes (separate address spaces), and both kinds are candidates for TLP. A multicore processor (or chip multiprocessor, CMP) is a single integrated circuit containing two or more independent processing cores, each capable of executing its own instruction stream, typically sharing some on-chip resources — most commonly a last-level cache (LLC) and the path to main memory — while keeping other resources, such as L1 caches, register files, and execution pipelines, private to each core. This is the crucial structural fact that everything else in this article builds on: multicore is not "one CPU doing several things"; it is several CPUs on one chip, wired together by an on-chip interconnect and a shared memory system. The reason multicore exists at all is a piece of physics that follows directly from the CPU time equation. Dynamic power dissipated by a CMOS circuit is approximately ``` P_dynamic ≈ C · V² · f ``` where `C` is switched capacitance, `V` is supply voltage, and `f` is clock frequency. Historically, chipmakers could raise `f` and lower `V` together (a benefit called voltage scaling), keeping power roughly constant even as speed rose — this was the essence of Dennard scaling. Around the mid-2000s, at process nodes near 90–65 nm, Dennard scaling broke down: threshold voltages could not keep shrinking without leakage current (and therefore static power) exploding, so `V` stopped falling. With `V` roughly fixed, power now grows directly with `f`, and — because pushing clock speed higher within one pipeline also requires deeper pipelining and more aggressive out-of-order and speculative logic, all of which burn additional transistors and power for shrinking ILP gains — the payoff per watt for chasing higher clock frequency collapsed. Architects instead asked: what if we take the power budget we would have spent on one faster core, and spend it on several slower, simpler cores instead? Because power scales roughly linearly with the number of cores at fixed frequency and voltage, but each additional core can, in the best case, add a full core's worth of throughput, multicore offered a way to keep raising aggregate performance within a fixed power envelope — provided software could actually put multiple cores to use.

Where TLP comes from. Threads can be created explicitly by a programmer (`pthread_create`, `std::thread`, a task in a parallel-for), spawned implicitly by a runtime (a thread pool, a parallel compiler pass, a database's query executor splitting a scan into partitions), or exist naturally at the level of whole processes (your browser, your music player, your terminal are already independent instruction streams). The operating system's scheduler is responsible for mapping this software parallelism onto the hardware parallelism the chip provides.

The mapping problem. A multicore chip with `p` cores can run up to `p` threads truly simultaneously (ignoring Hardware Multithreading, which lets one core interleave more than one thread — that mechanism is covered separately). The OS scheduler decides which ready thread runs on which core and for how long, using techniques such as:

• Load balancing — spreading runnable threads across idle cores rather than piling several onto one core while others sit idle.
• Affinity — preferring to keep a thread on the same core (or same socket) it last ran on, because its data may still be warm in that core's private cache.
• Work stealing — a scheduling strategy (used by runtimes like Cilk, Go, and Java's ForkJoinPool) where each core has its own queue of ready tasks, and an idle core "steals" work from a busy core's queue rather than the OS re-dispatching everything centrally.

Parallel decomposition. To actually get a speedup, the programmer or compiler must split a computation into pieces that can run concurrently with limited communication. The two dominant patterns are: 1. Data parallelism — the same operation is applied independently to different pieces of data (e.g., each core sums a different quarter of an array). This is the easiest case: no communication is needed until a final combine step. 2. Task parallelism — different cores execute genuinely different code (e.g., one thread parses input while another renders output). This requires more careful synchronization because the tasks are heterogeneous. Below is language-agnostic pseudocode for a canonical data-parallel reduction — summing an array — that illustrates both the mechanism and the one subtlety that trips up almost every first attempt: avoiding a data race on the shared accumulator. ``` // Parallel array sum on a multicore machine with P cores. // Input: array A[0 .. n-1], number of cores P. // Output: total sum of A. function PARALLEL_SUM(A, n, P): chunk_size = ceil(n / P) partial = new array of size P, initialized to 0 // Fork: launch one thread per core, each owns a private accumulator parallel for t = 0 to P-1: start = t chunk_size end = min(start + chunk_size, n) local_sum = 0 for i = start to end-1: local_sum = local_sum + A[i] // no shared writes here partial[t] = local_sum // one write per thread, no conflict // Join: wait for all P threads to finish before combining barrier() total = 0 for t = 0 to P-1: total = total + partial[t] // sequential, but O(P), P << n return total ``` The key design choice is that each thread accumulates into its own `local_sum` and writes to a distinct* slot `partial[t]`, so no two threads ever write the same memory location during the parallel phase — this is what makes the fork region race-free without needing a lock. Only the small, sequential combine step touches shared state, and it does so after a `barrier()`, a synchronization primitive that blocks until every thread has arrived, guaranteeing all `partial[t]` writes are visible before any thread reads them. Contrast this with the naive-but-broken version where every thread does `total = total + A[i]` directly on one shared `total`: two cores can both read the same old value of `total`, both add their piece, and both write back, silently losing one of the additions — a classic race condition.

Where the speedup ceiling comes from. Suppose a program's execution time on one core is `T₁`, and a fraction `f` of that time is inherently serial (cannot be parallelized: setup, I/O, sequential dependencies), while the remaining fraction `(1 − f)` is perfectly parallelizable across `p` cores. By Amdahl's Law, execution time on `p` cores is ``` T_p = f · T₁ + (1 − f) · T₁ / p ``` so speedup is ``` S(p) = T₁ / T_p = 1 / ( f + (1 − f)/p ) ``` As `p → ∞`, `S(p) → 1/f`. This is the fundamental reason multicore is not a free lunch: if 10% of a program's work is inherently serial (`f = 0.1`), no number of cores can push speedup above `10×`, no matter how many cores you add. This bound justifies the entire engineering emphasis in parallel software on minimizing the serial fraction — reducing lock contention, avoiding single-threaded bottleneck stages, and re-architecting algorithms (not just "adding threads") to shrink `f`.

Space and hardware cost. Each additional core adds roughly a fixed increment of die area (for its pipeline, registers, and private caches) and a roughly fixed increment of dynamic power at a given voltage and frequency — so an `p`-core chip costs approximately `O(p)` in area and power relative to a single core, assuming the shared LLC and interconnect grow sub-linearly (which is realistic, since bus/ring/mesh interconnects and shared caches are engineered to scale better than one-core-per-resource). This is the other half of the multicore argument: for a fixed power and area budget, you can either buy one core running much faster (with power growing worse than linearly in frequency, due to needing higher voltage and deeper, more complex pipelines) or `p` simpler cores running at a sustainable frequency (with power growing exactly linearly in `p`) — and once Dennard scaling ends, the second option dominates for any workload with usable parallelism.

Correctness argument for parallel decomposition. A parallel algorithm is correct if, for any interleaving of the threads' instructions permitted by the hardware and the synchronization primitives used, the final result equals what a correct sequential version would produce. For the `PARALLEL_SUM` example above, correctness follows from two invariants maintained by the code: 1. Disjoint-write invariant: during the parallel phase, thread `t` only ever writes to `A[start..end-1]` (read-only) and `partial[t]` (its own slot) — no two threads write to the same memory location, so there is no data race and the outcome cannot depend on interleaving. 2. Happens-before invariant: the `barrier()` establishes that every write to `partial[·]` in the fork phase happens-before every read of `partial[·]` in the combine phase, for every thread, so the combine loop always sees fully-written, final values, never partially-updated or stale ones. Given these invariants, `Σ partial[t]` over all `t` is exactly `Σ A[i]` over all `i`, partitioned without overlap or omission, by the same argument that justifies splitting any finite sum into disjoint contiguous chunks — so the parallel algorithm computes the identical value the sequential loop would.

Honest tradeoffs. Multicore speedup is bounded above by Amdahl's Law and in practice further reduced by: (a) synchronization overhead (locks, barriers, atomic operations cost cycles that a single-threaded program never pays); (b) memory contention — multiple cores sharing one LLC and one memory bus can bottleneck on bandwidth even when compute is perfectly parallel; (c) cache-coherence traffic, the cost of keeping private caches consistent when cores write to shared data (detailed under Cache Coherence); and (d) load imbalance, where uneven work assignment leaves some cores idle while others are still computing, which effectively increases the serial fraction `f` in Amdahl's Law even though no single instruction is truly "serial."

Consider an image-processing pipeline that runs in `T₁ = 100 ms` on one core, broken into three stages: load (5 ms, strictly sequential — reading one file), filter (90 ms, embarrassingly data-parallel — apply a convolution independently per row), and write (5 ms, strictly sequential — writing one output file). The serial fraction is `f = (5 + 5)/100 = 0.10`.

Trace through the `p = 4` row by hand using `PARALLEL_SUM`-style reasoning: the filter stage's 90 ms of work is split into four chunks of rows, one per core, each taking `90/4 = 22.5 ms` if perfectly balanced; a barrier after filtering ensures all four cores finish before the sequential write stage begins; total time is `5 (load) + 22.5 (filter) + 5 (write) = 32.5 ms`, matching the table. Notice the diminishing-returns curve: going from 1 to 2 cores buys `0.82×` of extra speedup, but going from 32 to 64 cores buys essentially nothing, because the fixed 10 ms serial cost increasingly dominates. This table is the concrete, numerical face of Amdahl's Law, and it is exactly why real multicore chip designs stop adding cores once a workload's serial fraction makes additional cores useless — the reason server chips top out at tens of cores for general workloads while GPUs, running workloads with `f ≈ 0`, scale to thousands of simpler execution units instead.

The move to multicore was not the invention of one person but the convergence of decades-old ideas in multiprocessing with a sudden, industry-wide power constraint. Symmetric multiprocessing (SMP) — multiple full processors sharing memory — long predates single-chip multicore, and the operating-system scheduling and cache-coherence theory it required were largely worked out in the 1970s–1990s for multi-chip systems, before being repurposed, essentially unchanged in spirit, for multi-core-on-one-die designs after 2001.

Multicore is the substrate underneath essentially all modern computing. Every smartphone system-on-chip ships with multiple CPU cores (often paired with GPU cores and dedicated accelerators) so that the OS can run the UI, background sync, and sensor processing concurrently without one blocking another. Server processors from AMD, Intel, and Arm-based designs (Ampere, AWS Graviton) now ship with dozens to well over a hundred cores per socket, because data-center workloads — web request handling, database query execution, virtual machine hosting — are naturally composed of many independent tasks, giving `f` close to zero and letting Amdahl's Law work in the industry's favor. Operating system kernels (Linux's CFS scheduler, Windows' scheduler) are built around multicore load balancing and affinity as first-class concerns. Databases parallelize query execution across cores for joins, scans, and sorts. Web browsers run rendering, JavaScript execution, and networking on separate threads or processes pinned to different cores. Compilers and runtimes (OpenMP, Intel TBB, Java's fork/join framework, Go's goroutine scheduler) exist specifically to make expressing and scheduling TLP tractable for ordinary application programmers. And the ideas here scale directly upward into Warehouse-Scale Computing, where the same reasoning about serial fractions, load balancing, and shared-resource contention reappears at the level of thousands of machines instead of a handful of cores — and downward into Hardware Multithreading and Cache Coherence, the two mechanisms that determine, respectively, how much parallelism a single core can absorb internally and how correctly and efficiently multiple cores can share memory at all.

:::quiz[In the PARALLEL_SUM pseudocode, why is writing to partial[t] instead of a shared total variable important?]

• It makes the code shorter and easier to read
• It ensures each thread writes to a distinct memory location, eliminating the data race that a shared accumulator would create ✓
• It reduces the total number of additions performed
• It removes the need for a barrier before combining results

Ask the tutor: How does cache coherence actually keep private per-core caches consistent when multiple cores read and write shared data?