Parallel Processors and Multicore

Parallel computers carry out operations at the same time. They can reduce latency, the time one job takes, or increase throughput, the number of jobs finished per second. Those goals lead to different ways of splitting work.

The power wall

Raising the clock rate once made each generation of processors faster. Dynamic power roughly follows $P\approx C{V}^{2}f$: capacitance times voltage squared times switching frequency. Voltage matters twice in that product. Reducing both voltage and frequency by 15% gives ${0.85}^2\times 0.85=0.614125$ of the original dynamic power, about 61%.

Voltage could not keep falling enough to offset higher clock rates. Leakage and heat made continued frequency growth too costly. This power wall pushed the industry toward multicore chips in the mid-2000s. A multicore chip places several processor cores on one chip; a multiprocessor system has at least two processors. More modest cores can deliver more total work per joule, provided there is enough work to share.

Four places to find parallel work

ILP is found mainly by hardware and compilers. Pipelining, multiple issue, and out-of-order execution overlap instructions while preserving the program's required results. Dependencies and branches limit the available overlap.

DLP appears when many elements need the same calculation. SIMD instructions, vector processors, and GPUs exploit this regularity. TLP requires work to be divided into threads by code, a library, or a compiler. A thread has its own program counter, registers, and stack; threads in one process share its address space. Separate processes have separate address spaces.

Request-level work needs little cooperation between jobs. Adding servers can therefore increase capacity nearly in proportion to the added resources. Running several independent programs on a laptop also uses otherwise idle cores, increasing overall throughput even when none of those programs is parallelized internally.

Concurrent tasks and simultaneous execution

Concurrency means tasks make progress during overlapping periods. One core can do this by taking turns between them. Parallelism means operations execute at the same instant on separate hardware. A single-core system can keep several programs in progress without executing their instructions simultaneously.

A program with one sequential thread does not divide itself across eight cores simply because they exist. The extra cores can run other work, but shortening this program requires parallel work within it. Even after work is split, any remaining sequential part still limits the gain.

A processor can contain many arithmetic units without following many independent instruction streams. Flynn's taxonomy classifies hardware by its instruction streams and data streams, so the first step is to choose the level of the machine being described.

The four hardware classes

A conventional single-core processor is SISD even when its pipeline overlaps several instructions. Superscalar issue does not by itself create independent program counters or turn the core into MIMD hardware.

A SIMD instruction might add eight pairs of 32-bit floats in a 256-bit register. It has eight lanes of arithmetic, but they follow one instruction. Fixed-width SIMD extensions include x86 SSE and AVX and Arm Neon; vector architectures also fit the SIMD class. Regular array calculations fit well because many elements need the same operation.

MIMD processors choose their instructions independently. Multicore chips, shared-memory multiprocessors, and clusters fit this class. The cores can run different programs, or copies of the same program that reach different branches at different times.

MISD completes the two-by-two classification. It has few clear practical examples. Some fault-tolerant systems and processing pipelines are described this way, but their classification depends on how their streams are defined.

One program can still have many instruction streams

SPMD, single program, multiple data, is a programming style. Each worker runs a copy of the same program and uses its ID to select its share of the data. Workers have independent execution state, so SPMD commonly runs on MIMD hardware.

For four cores summing 4,000 values, core ID $i$ handles indexes $1000i$ through $1000i+999$. Core 0 handles 0–999; core 3 handles 3000–3999. Each produces a partial sum, and those four sums are combined. The shared program text does not require all four cores to issue the same instruction in the same cycle.

Classify each level separately

Consider an eight-core CPU whose threads use AVX instructions. Across cores it is MIMD: the cores advance independently. Inside an AVX operation it is SIMD: one instruction controls several lanes. Counting all the arithmetic units together would hide this structure.

A cluster running copies of one scientific program is likewise MIMD hardware using SPMD software. Its nodes communicate through messages. A GPU combines many independently scheduled thread groups with SIMD-like execution inside each group; NVIDIA calls its thread-based execution style SIMT.

To classify a description, ask who chooses the next instruction. Then ask whether that instruction processes one data element or several. The number of source files, programs installed, or arithmetic units alone cannot answer those two questions.

A cache miss can leave a core waiting hundreds of cycles. Hardware multithreading keeps several threads' execution states inside one core so useful instructions from another thread can run during that wait.

What is duplicated and what is shared

Each hardware thread has its own program counter and register state. The threads share the core's execution units, caches, and access to memory bandwidth. Keeping state in hardware makes switching much faster than saving and restoring an operating-system process, which can cost thousands of cycles. Hardware can switch in a cycle or less.

The operating system sees each hardware thread as a logical processor. Eight physical cores with two hardware threads per core expose 16 logical processors. That count describes available thread contexts, not 16 complete physical cores.

Three scheduling approaches

Fine-grained scheduling can rotate among ready threads even when the previous thread could continue. Coarse-grained scheduling keeps running that thread until a costly stall justifies switching. SMT uses a multiple-issue, dynamically scheduled core: instructions from different threads can occupy different free issue slots during one cycle. Register renaming keeps their state separate. Intel's Hyper-Threading is an SMT implementation; some IBM POWER processors support eight hardware threads per core.

Work through latency hiding

Suppose a thread computes for 20 cycles and then waits 200 cycles for memory. Its cycle is 220 cycles long. Alone, useful work occupies $20\mathrm{/}220\approx 0.091$, or 9.1% of the time.

With four threads, freely staggered work, and no switching cost or added contention, useful work can occupy $4\times 20\mathrm{/}220\approx 0.364$, or 36.4%. The core still has gaps because four 20-cycle bursts cannot cover the waiting periods.

Eleven threads provide 220 cycles of compute bursts in total. While one waits for 200 cycles, the other ten can each compute for 20. This ideal schedule keeps the core busy. Real performance also depends on whether those threads compete for memory and execution resources.

Throughput and a thread's completion time

Multithreading primarily increases throughput. A particular thread may take longer because other threads use cycles and cache space it would otherwise receive. Two hardware threads sharing one arithmetic unit cannot both gain the capacity of a second full core.

If both threads already demand the same fully occupied execution units, SMT has little spare capacity to fill. If one stalls while the other can execute, sharing is useful. GPUs apply latency hiding at a larger scale by keeping many thread groups ready for their schedulers.

A parallel machine is useful when it changes elapsed time. Speedup compares the best sequential run with the parallel run; efficiency compares that gain with the number of processors used.

Start with measured time

For $p$ processors, $S(p)=T_1\mathrm{/}{T}_p$ and $E(p)=S(p)\mathrm{/}p$. A 100 s sequential job that finishes in 16 s on eight cores has speedup $100\mathrm{/}16=6.25$. Its efficiency is $6.25\mathrm{/}8=0.78125$, about 78%. Measure wall-clock time for both runs, using the same fixed job.

Divide time into improved and unchanged parts

In Amdahl's law, $f$ is the fraction of the original execution time that an enhancement accelerates. It is a time fraction, not a fraction of source-code lines. If that part becomes $s$ times faster, then

The unchanged part still takes its full original time. For ideal parallel division across $p$ processors, set $s=p$. This model excludes communication, imbalance, and synchronization overhead; those costs can make measured time longer.

With 90% parallel time and ten processors, normalized time is $0.1+0.9\mathrm{/}10=0.19$. Speedup is $1\mathrm{/}0.19\approx 5.26$, and efficiency is about 53%. With 100 processors, time is $0.1+0.009=0.109$ and speedup is about 9.17. Increasing the processor count tenfold has not doubled the speedup.

Find the limit before buying more processors

As processor count grows, the parallel time approaches zero. The sequential fraction remains, giving the ceiling $S_{max}=1\mathrm{/}(1-f)$. A 10% sequential fraction caps ideal speedup at 10; a 5% fraction caps it at 20. Finite processor counts approach these ceilings from below.

Amdahl's law also evaluates one faster instruction class. If multiplication takes 30% of a run and becomes four times faster, normalized time becomes $0.7+0.3\mathrm{/}4=0.775$. The whole program is only $1\mathrm{/}0.775\approx 1.29$ times faster.

Work backward from a target

To obtain speedup 90 on 100 processors, write $1\mathrm{/}90=(1-f)+f\mathrm{/}100=1-0.99f$. Therefore $f=(1-1\mathrm{/}90)\mathrm{/}0.99\approx 0.99888$. Only about 0.11% of the original time can remain sequential. A target close to the processor count demands a very small unchanged fraction.

A measured speedup can sometimes exceed the processor count. Splitting a large working set may make each part fit in cache, reducing the cost per operation. This superlinear speedup changes a premise of the simple model: parallel work is no longer just the original work divided into equal shares. Check the algorithm, data size, and cache behavior before interpreting such a measurement.

Adding processors can either shorten the same job or let a machine handle a larger job. Strong scaling and weak scaling measure these different uses, and both depend on how much useful work survives the costs of coordination.

Fixed work and growing work

Strong scaling keeps the problem size fixed. Weak scaling grows work in proportion to processor count, keeping work per processor constant. Perfect weak scaling keeps elapsed time constant while total work grows.

Consider ten sequential additions followed by an element-wise sum of two matrices. A 10 by 10 matrix needs 100 parallel additions. Total time is 110 units on one processor, 20 on ten, and 12 on fifty: speedups 5.5 and about 9.2. A 40 by 40 matrix needs 1,600 parallel additions. Times become 1610, 170, and 42 units: speedups about 9.5 and 38.3. The larger problem gives useful parallel work more weight relative to the same ten sequential additions.

Gustafson's different baseline

Gustafson's law uses the sequential time fraction measured on the parallel run. Calling that fraction $s$, scaled speedup is $S_G=s+(1-s)p$. For $s=0.05$ and 100 processors, $S_G=0.05+0.95(100)=95.05$.

Amdahl's law with 5% sequential time on the original one-processor run gives only about 16.8 on 100 processors. These fractions use different denominators and answer different questions. A scaled speedup of 95.05 does not mean the original fixed-size job finished 95.05 times sooner.

The slowest worker sets the finish time

If 400 equal work units go to eight cores, the balanced share is 50 each. Suppose one gets 120 while the other seven get 40 each. The step lasts 120 time units, so speedup is $400\mathrm{/}120\approx 3.33$. Dividing by the average load would miss the wait for the busiest core.

Thread creation, scheduling, messages, barriers, and shared-bandwidth contention also consume time. Granularity is the amount of computation between communication or synchronization events. Larger chunks reduce coordination cost per useful operation, but too few chunks can leave some workers idle.

More processors can increase time

For a fully parallel 100 s job with overhead $0.5p$ seconds, $T_p=100\mathrm{/}p+0.5p$. Ten processors take 15 s. Fourteen take about 14.14 s, close to the minimum near $\sqrt{200}$ processors. Forty take 22.5 s because their 20 s overhead outweighs the shorter useful calculation.

When reporting a result, state whether work stayed fixed or grew, and compare with the best sequential program's time. Using a slow parallel implementation running on one processor as the baseline can inflate the reported speedup.

A processor's advertised arithmetic rate is only one limit. The roofline model also asks whether memory can supply data fast enough to sustain that rate. It gives an upper bound, which helps identify a useful direction for optimization.

Count operations per DRAM byte

Arithmetic intensity is floating-point operations divided by bytes transferred between DRAM and the processor. The original roofline work calls this DRAM-based measure operational intensity. Count the traffic at that boundary, including reads and writes.

DAXPY computes $y_i=a{x}_i+y_i$ using double-precision numbers. Each element needs one multiplication and one addition: two FLOPs. Reading an 8-byte value from each array and writing 8 bytes back moves 24 bytes. Intensity is $I=2\mathrm{/}24\approx 0.0833$ FLOPs per byte. The scalar coefficient is reused; it is not a fresh DRAM load for every element in this traffic model.

Apply both limits

If peak compute is $P$ and peak memory bandwidth is $B$, the roof is $\min (P,BI)$. Bandwidth times FLOPs per byte has units of FLOPs per second. On a log-log graph, the bandwidth bound slopes upward and the compute bound is flat.

For 1,000 GFLOP/s and 100 GB/s, the ridge point is $P\mathrm{/}B=1000\mathrm{/}100=10$ FLOPs per byte. Below this intensity, the bandwidth roof is lower; above it, the compute roof is lower. DAXPY is bounded by $100(2\mathrm{/}24)\approx 8.33$ GFLOP/s, under 1% of the machine's compute peak. A kernel at intensity 2 is bounded by 200 GFLOP/s.

A memory-bound kernel can still benefit from extra cores or wider SIMD while it has too few requests in flight to use the available bandwidth. Once that bandwidth is saturated, extra arithmetic capacity does not raise its roof. Raising bandwidth or doing more useful computation per transferred byte does.

Reuse changes intensity

Multiplying two 1000 by 1000 double-precision matrices performs about $2(1000{)}^3=2\times {10}^9$ FLOPs. If each element of the two inputs and output crosses the DRAM boundary once, total traffic is 24 MB, giving about 83 FLOPs per byte. That is above the ridge of the example machine.

A naive implementation can reread matrix values repeatedly from DRAM. Blocking organizes loops around submatrices that fit in cache, so values serve many operations before being replaced. The algorithm is still matrix multiplication, but the implementation moves fewer DRAM bytes per operation.

A roof is not a measured result

A kernel can run below the bound because of dependencies, instruction overhead, poor access patterns, or insufficient parallel work. Lower ceilings show such restrictions: lack of SIMD can lower the compute ceiling, while poor access patterns lower usable bandwidth. A point below a roof needs investigation; the roof alone does not predict its exact running rate.

A SIMD extension divides a wide register into lanes. One instruction performs the same operation in every lane, making regular loops over independent elements a good fit.

Count lanes and iterations

Lanes equal register width divided by element width. A 256-bit register holds eight 32-bit floats, four 64-bit doubles, or 32 one-byte elements. SSE uses 128-bit XMM registers; AVX and AVX2 use 256-bit YMM registers. In 64-bit mode there are 16 YMM registers. AVX-512 provides 32 512-bit ZMM registers, each holding 16 floats. Arm Neon uses 128-bit registers.

For c[i] = a[i] + b[i] over 1,000 floats, eight-lane instructions process the array in 125 vector iterations. Each iteration loads two vectors, adds their lanes, and stores a vector. With 1,003 elements, 125 full iterations leave three elements. A scalar remainder loop or a masked operation handles that short tail without accessing beyond the arrays.

Eight lanes are an arithmetic capacity, not a guarantee of eightfold program speedup. Setup, remainder handling, sequential work, and memory bandwidth still take time.

Choose a layout that fills a register

Simple vector loads work well on contiguous, unit-stride elements. An array of 4-byte {x, y, z} points places consecutive x fields 12 bytes apart. A structure of arrays puts the x values together, then the y values, then the z values. Processing only x can now fill a vector with one contiguous load. Gather and scatter instructions support scattered addresses, but usually at a higher access cost.

Keep conditional work within lanes

For c[i] = (a[i] > 0) ? a[i] : 0, a compare creates a per-lane mask. A blend chooses between candidate results, or masked instructions update only the selected lanes. Inactive lanes retain or receive values according to the instruction's mask behavior.

If different lanes need long, different branches, the instructions for those paths must still be issued, with only the relevant lanes active. The group cannot give each lane a separate instruction stream. A mask preserves correctness but cannot make all those path instructions disappear.

Check iteration independence

Compilers can auto-vectorize loops; programmers can also use libraries or intrinsics such as _mm256_add_ps. The compiler must establish that simultaneous iterations preserve the result. The recurrence a[i] = a[i-1] + b[i] depends on the preceding iteration's new value and cannot be directly vectorized as independent elements. Possible pointer overlap, called aliasing, can also require a run-time overlap check or prevent vectorization.

A reduction keeps several partial sums in a register, then combines lanes. Reordering floating-point additions can change the last bits because addition is not associative. Integer sums agree when the chosen arithmetic has no overflow or uses defined modular arithmetic.

SIMD and multicore execution can combine. Eight cores each issuing one eight-lane add per cycle can perform up to 64 float additions per cycle. They still share limits such as memory bandwidth.

A vector architecture expresses an operation on a sequence of elements and stores the active vector length in a register. The same program can run on implementations with different vector-register capacities.

Separate capacity, length, and lanes

The RISC-V vector extension, RVV, version 1.0 was ratified in 2021. It provides 32 vector registers, v0 through v31. Each implementation chooses its register width, VLEN, as a power of two. Element width and register grouping determine how many elements fit.

The active length, vl, is the number of elements handled by the next vector instructions. vsetvli configures the vector operation from the remaining element count and the desired element format, returning the selected vl. Code advances by that returned value. This matters because portable code must use the actual length selected by the implementation.

Lanes are the parallel pipelines that execute the vector operation. A 32-element add on four lanes takes about eight cycles after pipeline startup. A 32-element vector does not require 32 arithmetic units. Longer vectors and more lanes are separate design choices.

Strip mine a loop

Strip mining divides a long loop into vector-sized pieces. For 100 elements and a maximum of 32 per operation, one valid sequence of lengths is 32, 32, 32, and 4. Each pass loads the next portion, computes it, stores it, and reduces the remaining count by its vl.

DAXPY over 1,000 doubles can similarly use 31 passes of 32 followed by a pass of eight, for 32 passes in all. RVV can choose other legal lengths near the end, so the loop uses the returned vl instead of assuming a particular final split. Setting the active length handles the short tail without a separate scalar remainder loop.

The loop-control pattern is:

1. Request a length for the remaining elements.
2. Load and compute that many elements.
3. Store the results.
4. Advance pointers and subtract the returned length.

One vector instruction describes many element operations, reducing fetch and decode work compared with a scalar body repeated for every element.

Feed dependent operations and noncontiguous data

Chaining lets a vector consumer start on early results before the producer has finished later elements. For a multiply followed by an add, the first product can enter the add pipeline while later products are still being formed.

A mask, commonly in RVV register v0, selects which elements update. A strided load accesses a fixed byte spacing. In a row-major 100 by 100 matrix of doubles, moving down one column advances 100 elements, or 800 bytes. Indexed loads and stores use explicit addresses for irregular data.

Both vector architectures and fixed-width extensions are SIMD in Flynn's taxonomy. Fixed-width extensions encode particular widths; RVV code expresses lengths that adapt to the available hardware. Both still need an execution order that respects the loop's data dependencies.

A CPU concentrates resources on low latency for a few threads. A GPU concentrates resources on high throughput across many data-parallel threads. Choosing between them requires looking at the whole job, including data movement.

Threads run on streaming multiprocessors

A GPU from NVIDIA contains many streaming multiprocessors, or SMs. An SM has arithmetic lanes, warp schedulers, a large register file, and fast on-chip shared memory. A “CUDA core” names an arithmetic lane, not a complete independent CPU-like core. AMD calls the corresponding processing group a compute unit.

NVIDIA groups threads into warps of 32. One issued instruction operates on the warp's active threads, each with its own register values and data. This is SIMT, single instruction, multiple threads. AMD uses wavefronts, with 32 or 64 threads depending on the architecture.

An SM keeps many warps resident. When one waits for memory, the scheduler selects another ready warp. Having more ready threads than lanes hides latency; it does not reduce the latency of an individual DRAM access.

Divergence leaves lanes inactive

If threads in one warp take different branches, the warp executes the required paths with the other threads masked off. An evenly split if-else with equally costly branches can take roughly twice the path time because both paths must execute. A branch can be harmless when its condition is uniform within each warp, even if different warps choose different paths.

Make memory accesses work together

Per-thread registers hold private values. Per-block shared memory is on-chip storage managed by the program. L1 and L2 caches serve automatic reuse, while global memory is the GPU's DRAM, such as GDDR or HBM.

When 32 threads read consecutive 4-byte words, their 128-byte range can be served by a small number of wide transactions. This coalescing uses bandwidth efficiently. Scattered addresses can require many transactions for the same useful data. Shared-memory reuse can further reduce repeated global-memory traffic.

Include the transfer time

For a discrete GPU, inputs and results cross a link such as PCIe or NVLink. Sending 800 MB and receiving 400 MB at an effective 20 GB/s transfers 1.2 GB in 0.06 s, or 60 ms. Adding a 10 ms kernel gives 70 ms overall. A CPU finishing in 50 ms wins this comparison despite the much faster GPU calculation.

Keeping data on the GPU across several kernels avoids repeated transfers. Large, regular jobs can also provide enough useful arithmetic to outweigh movement and launch costs. Small, sequential, branch-heavy jobs often favor a CPU.

Specialize further when the work allows it

A heterogeneous system uses the CPU to run the program and operating system and an accelerator for suitable parts. Domain-specific accelerators such as TPUs and NPUs devote hardware to a narrower task, often matrix multiplication with 8-bit integers or 16-bit floating point. Specialization can improve performance per watt in that domain, while reducing the range of work the hardware handles well.

A GPU kernel runs once per launched thread. The host launches a grid of thread blocks, and each thread computes which part of the data it owns. CUDA calls the CPU the host and the GPU the device; OpenCL uses the related terms work-item and work-group.

Calculate a unique index

For a one-dimensional launch, the element index is blockIdx.x * blockDim.x + threadIdx.x. With 256 threads per block, thread 5 in block 2 handles element 517: the two preceding blocks account for 512 elements, and the thread adds an offset of five. Thread and block indexes start at zero.

A SAXPY kernel applies one multiply and one add to each float:

__global__ void saxpy(int n, float a, float *x, float *y) {
    int i = blockIdx.x * blockDim.x + threadIdx.x;
    if (i < n) {
        y[i] = a * x[i] + y[i];
    }
}

The grid replaces the ordinary loop over elements. Each active thread updates its own y[i]; neighboring threads use neighboring addresses, supporting coalescing.

Round the block count up

For 1,000,000 elements and 256 threads per block, the grid needs $\lceil 1000000\mathrm{/}256\rceil =3907$ blocks. These launch 1,000,192 threads. The last 192 have indexes outside the array, so the condition i < n prevents their memory accesses. Rounding down would launch too few threads and leave valid elements untouched.

A block of 256 threads forms eight warps. Blocks can be assigned to any SM and execute in any order. Program correctness must not depend on block 0 finishing before block 1.

Organize host and device work

A typical host allocates device storage, copies the inputs, launches saxpy<<<3907, 256>>>(n, 2.0f, d_x, d_y), and obtains the results. Launch is asynchronous: the CPU can continue while the kernel runs. The host must wait through synchronization or a suitable blocking result copy before it uses the finished data.

Cooperate inside a block

Threads in one block can exchange values through shared memory and meet at __syncthreads(). Every thread participating in that block-wide barrier must reach it. Putting the barrier inside if (i < n) is unsafe when only some threads satisfy the condition.

For a reduction of 1,024 shared-memory values, 512 threads add pairs, then 256 combine the results, then 128, and so on. Ten halving stages leave one sum. A barrier between stages prevents a thread from consuming a partial result before its producer writes it.

An ordinary launch has no grid-wide barrier. Separate blocks can write partial sums and a second kernel can combine them, or appropriate atomic operations can update a global result. A block barrier alone cannot coordinate different blocks. A grid-stride loop is another mapping pattern: each thread handles several elements, advancing by the total grid size.

A shared-memory multiprocessor gives its processors one physical address space. Threads communicate with loads and stores to shared variables, while still keeping private values such as local partial sums.

Shared addresses can have different costs

In UMA, uniform memory access, memory access time is roughly the same from every processor. In NUMA, nonuniform memory access, a socket reaches its local memory faster than another socket's memory. The address space is shared even though the physical memory is distributed.

With 70% local accesses at 80 ns and 30% remote accesses at 140 ns, the weighted average is $0.7(80)+0.3(140)=98$ ns. Moving data near its main user reduces the remote share. Counting every access as local would underestimate time.

A common cache layout gives each core private L1 instruction and data caches, often private L2, and a shared last-level cache. A ring or mesh connects the cores and caches. Shared memory describes addressing; it does not require every core to use one common cache.

Split, compute, and reduce

To sum 64,000 values on 64 cores, each core handles 1,000 values. The 64 partial sums can be combined in a reduction tree. The number of active adders halves at each stage: 32, 16, 8, 4, 2, and 1. Six stages combine the partial results.

Using roughly 1,000 local addition steps plus six combining steps gives about 1,006 steps along the longest path, before overhead. The tree avoids making every input update one shared counter. Each stage depends on the previous stage's completed values, so the workers meet at barriers between stages.

OpenMP can express this with #pragma omp parallel for reduction(+:sum). It splits iterations, gives threads private partial sums, and combines them. POSIX threads offer more explicit control over thread management.

Make an update indivisible

An atomic read-modify-write operation makes an update indivisible as observed by other processors. Atomic swap and fetch-and-add are examples. A load followed by an ordinary store is two separate operations, so another thread can intervene.

RISC-V provides lr.w and sc.w. The load-reserved reads a word and establishes a reservation. The store-conditional attempts the write and reports success or failure. An intervening write to the reserved location makes the attempt fail; software retries. The reservation does not block other processors, and failure can also occur for other permitted reasons. These primitives support synchronization mechanisms.

Watch the shared bottlenecks

If each core can stream 15 GB/s but the socket supplies 60 GB/s, about four such streams saturate bandwidth. More cores cannot increase the socket's data rate. Communication through caches also takes work: a writer without write permission must obtain ownership and invalidate other copies. A writer already holding a Modified block can continue locally; later readers may need to fetch a new copy.

Private caches improve latency but can hold several copies of the same memory location. Cache coherence keeps those copies from giving conflicting histories of that location's writes.

Why updating memory is insufficient

Start with X = 0 in memory. Core A reads and caches zero; core B does the same. A writes one into its write-back cache. Without a coherence protocol, B can hit in its own cache and keep reading zero. Writing through to memory would not fix B's already cached copy.

Coherence works at cache-block granularity, commonly 64 bytes. A controller tracks each block's state and follows protocol rules when processors read or write it. Migration moves useful data into the cache of its current user. Replication lets several readers hold clean copies. Coherence must preserve both benefits while controlling writes.

Three required properties

If a location receives a write of one followed by a write of two, readers cannot disagree about which write came later. Observing the later write and then the earlier write would reverse that history. A fresh subsequent write could of course store the value one again; serialization concerns write events, not whether a numeric value can ever recur.

Control ownership and copies

In a write-invalidate protocol, a writer obtains exclusive write permission and invalidates other cached copies. A later read of an invalidated block misses and fetches current data. This is a coherence miss, in addition to compulsory, capacity, and conflict misses.

A write-update protocol sends new values to existing copies instead. Repeated writes can make this expensive. Snooping broadcasts coherence requests so caches can react. A directory tracks sharers and directs messages to relevant caches.

Coherence, ordering, and atomicity

Coherence concerns one location. A memory consistency model defines allowed observable orderings and results of reads and writes, including operations on different locations. Sequential consistency requires an outcome that matches one interleaving preserving each processor's program order. Relaxed models allow more reorderings; fence instructions enforce required ordering where needed.

Neither coherent copies nor a consistent ordering makes a multi-instruction increment atomic. Suppose two threads increment a shared count initially equal to five. A possible sequence is: A reads five, B reads five, A writes six, B writes six. Every read and write can be coherent, yet the final count is six instead of seven. The program needs an atomic update or suitable synchronization to preserve both increments.

A snooping cache controller watches coherence requests on a broadcast interconnect. To trace a protocol, keep a state for each core's copy of a block and update every affected copy after each access.

Read the states as permissions

In basic MSI, a read miss sends a bus read and loads the block in S. Writing a block in S requires an upgrade to invalidate other copies. Writing from I needs a read-exclusive request to fetch data and obtain ownership. The writer ends in M. A hit in M requires no coherence transaction.

Trace five accesses

Begin with X = 0 in memory and both A and B Invalid.

1. A reads X. A bus read supplies zero. States: A = S, B = I.
2. B reads X. Another bus read supplies zero. States: A = S, B = S.
3. A writes one. Its upgrade invalidates B. States: A = M, B = I.
4. B reads X. B misses; A supplies one and downgrades to S. In basic MSI, memory becomes current too. States: A = S, B = S.
5. B writes two. Its upgrade invalidates A. States: A = I, B = M.

Each access in this trace requires a bus transaction. The fourth access is the important ownership check: memory alone still had the old value before A supplied its dirty data.

What Exclusive saves

MESI adds E for a single clean cached copy. If A reads an uncached block and no other cache has it, A receives E. A subsequent write changes E to M silently, because there are no other copies to invalidate. MSI would first load S and then send an upgrade for that write.

If another core reads while A holds E, both become S. M and E both have one valid owner, but only M contains data newer than memory.

Repeated writes and scale

A writer that has obtained M can update the block ten times without ten new invalidations. A write-update scheme would send the changed values to sharers.

Broadcast snooping becomes expensive as more cores watch every request. Directory structures reduce that fan-out. More elaborate protocols add useful states: MOESI's Owned state permits a dirty shared copy, and MESIF designates a Forward sharer to answer requests.

Broadcasting every coherence request becomes costly on large machines. A directory records which caches might hold each block so requests can go to those caches. The same block-level tracking also explains a common performance problem: false sharing.

Ask a block's home

Each block has a home directory entry recording whether it is uncached, shared, or modified and which caches hold it. Homes are distributed across nodes or directory slices, spreading storage and request handling.

A read miss goes to the home. If memory has the current data, it can supply them and the directory records the new sharer. If another cache owns a Modified copy, the home forwards the request to that owner so current data can be supplied. In a basic directory protocol, this also makes memory current again.

To write without existing Modified ownership, a core asks the home for permission. The directory sends invalidations to recorded sharers, waits for acknowledgments, and grants exclusive ownership. Repeated write hits in M then need no further coherence messages. Directory indirection adds latency, but point-to-point traffic avoids asking every cache about every block. On-chip snoop filters serve a related purpose by restricting requests to possible holders.

Estimate directory storage

A full presence vector has one bit per core per block. For 64 cores, that is 64 bits, or eight bytes. Relative to a 64-byte data block, presence bits alone cost $8\mathrm{/}64=0.125$, or 12.5%. With 256 cores, the 32-byte vector costs 50%. State bits add more. Limited sharer lists, coarser vectors, and tracking only cached blocks reduce this storage burden.

Recognize false sharing

True sharing occurs when cores exchange data through the same word. False sharing occurs when they access different variables within one cache block and at least one writes. The variables are independent in the program, but the coherence unit is larger than either variable.

Two threads increment separate 8-byte counters at 0x1000 and 0x1008. With 64-byte blocks, their block numbers are $\lfloor 4096\mathrm{/}64\rfloor =64$ and $\lfloor 4104\mathrm{/}64\rfloor =64$. Each ownership change moves permission for both counters together. Frequent alternating writes can make the block bounce between caches even though neither thread needs the other's value.

Moving the second counter to 0x1040 puts it in block 65. Padding or alignment can separate per-thread data; grouping values by their writer also helps. A local accumulator written back once reduces ownership traffic without adding padding to every value.

A writer and a reader of a neighboring variable can also suffer false sharing: the writer invalidates the reader's otherwise useful block. Two readers alone do not cause it. False sharing adds traffic and delay; it does not itself make updates to separate variables produce incorrect values. Measure access patterns and cache-line placement before changing a data layout.

A cluster connects complete computers, each with its own memory and operating system. Nodes cooperate through explicit messages. Data placement and communication cost therefore become part of the program's performance model.

Partition data and combine results

MPI, the Message Passing Interface, gives each process a rank and operations such as send, receive, broadcast, and reduce. An SPMD program can use ranks to select each process's data. A pointer in one node's private address space is not an ordinary shared-memory reference to another node's data.

If one million values are already distributed over 100 nodes, each node sums 10,000 locally. A tree reduction combines the partial sums in seven rounds because $\lceil {\log }_{2}100\rceil =7$. Those rounds involve network messages, not just local additions. Keeping data close to its work reduces transfers.

Clusters scale with standard components, and failed hardware can be replaced. An application may still need recovery or restart after a node fails; replaceable nodes alone do not preserve an interrupted job's progress.

Measure more than link speed

Latency is the time a message takes to arrive. Link bandwidth is one link's data rate. Total network bandwidth sums link capacity and describes an ideal aggregate with all links busy. Bisection bandwidth sums the capacity crossing the lowest-capacity cut that divides nodes into equal halves.

For equal-capacity links of bandwidth $B$, compare 64-node networks using one consistent link-counting convention:

The mesh has eight rows of seven horizontal links and eight columns of seven vertical links, giving 112. Wrapping both dimensions produces the torus's 128. Each hypercube node has six neighbors, giving $64(6)\mathrm{/}2=192$ links because each link is counted at two endpoints.

Follow the cut, then consider the cost

A ring cut into two halves crosses only two links. Many messages can therefore contend at that boundary despite the ring's 64 links overall. A fully connected network crosses $32(32)=1024$ links between its two halves, but needs $64(63)\mathrm{/}2=2016$ links in total.

More links can improve bandwidth and reduce hops while increasing switch ports, cables, and power. Shared buses have a single shared communication resource; meshes and tori spread links across space. Large clusters often use multistage switched networks such as fat trees. Their usefulness depends on the traffic pattern as well as their aggregate capacity. For communication between halves of a machine, the bisection exposes a limit that the total hides.

A warehouse-scale computer combines tens of thousands of servers with power, cooling, and a network to deliver internet services. Independent requests provide parallel work, while batch frameworks such as MapReduce split large data-processing jobs across machines.

Match the design to the service

Warehouse-scale systems emphasize cost per request, energy efficiency, and availability. Software retries work, replicates data, and routes around failed machines. A supercomputer more often emphasizes one tightly coupled scientific program and a fast interconnect.

Servers connect to top-of-rack switches, which connect through higher switch levels. Extra levels add communication latency. Uplinks are often oversubscribed, meaning their capacity is below the aggregate capacity of the server links. Some nonblocking Clos-style fabrics provide enough upper capacity to avoid this restriction.

Forty servers with 10 Gbit/s links offer 400 Gbit/s to a rack switch. Four 25 Gbit/s uplinks provide 100 Gbit/s, so the ratio is 4:1. If all servers send off-rack together and share equally, each averages 2.5 Gbit/s. A lightly loaded server can use more when others are idle.

Separate facility overhead from useful computation

Power usage effectiveness, PUE, is total facility energy divided by IT equipment energy over the same period. Ten MW of steady IT load plus 1.5 MW of cooling and distribution overhead gives $PUE=11.5\mathrm{/}10=1.15$. The ideal value is 1.0. Google reported an annual fleet-wide PUE of 1.09 for 2025.

PUE measures facility overhead, not useful computations per joule. Idle or inefficient servers can waste energy inside the IT boundary even when the facility has excellent PUE.

For 50,000 servers averaging 300 W, IT power is 15 MW. At PUE 1.2, facility power is 18 MW. Sustained for 8,760 hours, that uses 157,680 MWh; overhead alone uses 26,280 MWh. Power equipment, cooling, electricity, servers, and buildings all contribute to ownership cost.

Low load can still draw substantial power

Energy proportionality means power should rise in proportion to load. A server with 150 W idle power and 300 W peak, increasing linearly, draws $150+0.3(150)=195$ W at 30% load. It uses 65% of peak power for 30% of peak work. Historical warehouse-scale measurements found many servers operating between roughly 10% and 50% utilization, making idle power important.

Plan for failures and slow responses

If 50,000 servers each average one failure per ten years, the fleet expects 5,000 failures per year, about 14 per day. That expectation motivates redundancy and retries; it does not schedule exactly 14 failures every day.

A request that needs replies from many servers waits for its slowest required reply. If each of 100 servers independently has a 1% chance of being slow, the chance none is slow is ${0.99}^{100}$. Thus at least one is slow with probability $1-{0.99}^{100}\approx 0.634$. Tail latency at one server becomes a common request-level delay when the fan-out is large.