Parallelism

The big picture and the vocabulary

Think of a kitchen. One cook making 100 sandwiches does one at a time. Four cooks at four tables make them together. The sandwich is the work, each cook is a worker, and the cooks are working in parallel because they all cook at the very same moment.

Words you will meet

A speed-up is "how many times faster". If a job takes 120 seconds alone and 20 seconds with helpers, the speed-up is 6. Most of this area is about why that number is usually smaller than the number of helpers.

Data parallelism and task parallelism

There are two big ways to cut a job into pieces. In the sticker album, you can give each friend a part of the stickers (same job, different stickers). Or you can give each friend a different chore: one cuts, one glues, one writes labels.

When can a loop be shared?

A loop can become data parallelism when its iterations are independent: no turn reads a value that another turn writes. Then the turns can run in any order, even at the same time. Size and speed of the turns only affect performance, not correctness.

Task parallelism has a ceiling

Say three independent tasks take 6 s, 3 s and 3 s. Each runs on its own core. The total time is the longest task, 6 s, even on a 16-core machine. The speed-up is 12 / 6 = 2. Only splitting the data inside the tasks could use the other cores.

Tasks can also depend on each other. The longest chain of dependent tasks is the critical path. No number of processors makes the program faster than that chain. Example: A (4 s), B (3 s), D (5 s) are free, C (2 s) needs A and B, E (1 s) needs C and D. The chain A, C, E takes 4 + 2 + 1 = 7 s. The total work is 15 s, so the best speed-up is 15 / 7, about 2.1.

A(4) --\
         +--> C(2) --\
B(3) --/             +--> E(1)
D(5) ---------------/

longest chain: A -> C -> E = 7 s

Three traps

• Unequal pieces. Counting primes by trial division costs more for big numbers. If 4 workers get 4 equal blocks of numbers, the worker with the highest block finishes last and the others sit idle.
• Pieces that are too small. Creating one task for each of 10 million tiny iterations costs more than the work itself. Group the iterations into chunks. This is granularity.
• Too many threads. If 8 requests each start 8 threads on an 8-core machine, 64 threads fight for 8 cores. This is called oversubscription. It adds switching and cache fights and gives no extra speed. Use one pool of workers sized to the cores.

Speed-up, efficiency and scalability

How do we say that a parallel program is "good"? We measure it. Two numbers do most of the job.

• Speed-up: S(N) = T(1) / T(N). It is the time with 1 worker divided by the time with N workers, both in wall-clock time. The dream is S(N) = N, called linear speed-up.
• Efficiency: E(N) = S(N) / N. It tells how much of each worker turned into gain. With linear speed-up, E is 1, or 100%.

Example: a program takes 120 s with 1 worker and 20 s with 8 workers. Speed-up is 120 / 20 = 6. Efficiency is 6 / 8 = 75%. A quarter of the capacity you paid for did not turn into gain: 120 s of work used 8 x 20 = 160 s of workers.

Efficiency usually falls

A table of speed-ups can fool you because the speed-up keeps rising while each new worker helps less. Look at efficiency:

Strong and weak scaling

Weak scaling example: 1 worker solves a problem of size n in 50 s. 8 workers solve a problem of size 8n in 62.5 s. The weak efficiency is 50 / 62.5 = 80%. The scaled speed-up (time one worker would need for the big problem, divided by the real time) is 8 x 0.8 = 6.4.

Compare against the right baseline

The parallel program with 1 worker already pays for splitting and waiting. If you divide by that time, the program looks better than it is. This repository uses the best sequential program as the baseline (absolute speed-up). Example: the sequential program takes 10 s, the parallel one takes 12.5 s with 1 thread and 3.125 s with 4 threads. Relative to itself, 12.5 / 3.125 = 4 looks perfect. Real speed-up: 10 / 3.125 = 3.2.

Can the speed-up be more than N?

Sometimes yes, and it is called superlinear speed-up. It happens when parallel work is cheaper, not just divided. The most common cause is the cache: the whole array does not fit in the cache of one core, but one eighth of it does, so each core reads from fast memory. Another cause is a search where one worker finds the answer early and stops the others.

Amdahl's and Gustafson's laws

You are making a pizza. The dough must rest 10 minutes, and only one person can wait for it. Ten cooks cannot rest the dough faster. This waiting part is the serial part. The rest (cutting toppings) can be shared.

Amdahl's law

Call s the share of the sequential time that cannot be parallelised (0.1 means 10%). Only the other part, 1 - s, shrinks when we add N workers:

S(N) = 1 / ( s + (1 - s) / N )

N -> very big:   S -> 1 / s

The term (1 - s) / N is the parallel part after it is shared among N workers, as a fraction of the original time. The speed-up never goes above 1 / s. With s = 10%, the ceiling is 10, even with a thousand processors, because the serial 10% still runs on one worker.

Practice with numbers:

1. 80% parallel, 4 processors: the time becomes 0.2 + 0.8 / 4 = 0.4, so the speed-up is 2.5.
2. A program of 100 s with 10 s of serial work must finish in 25 s. Then 10 + 90 / N is at most 25, so N is at least 6 (not the 4 of the linear guess).
3. Serial fraction 25%: with 8 processors S is 2.91, with 16 it is 3.37. Double hardware, only about 16% more speed. Near the limit, each new worker pays back less.

Gustafson's law

Gustafson looks at the same story from another side. When we get more workers, we usually do not run the same small problem faster: we run a bigger problem in the same time (a sharper image, a finer weather map). The parallel part grows with the problem, the serial part hardly does. The scaled speed-up is:

S(N) = s' + (1 - s') * N

s' = serial fraction measured in the PARALLEL run

Example: a run on 16 processors spends 10% of its time in serial code. S = 0.1 + 0.9 x 16 = 14.5.

Do the two laws disagree?

No. They are the same computation with the serial fraction measured on different baselines. Amdahl measures s on the time of the sequential run. Gustafson measures s' on the time of the parallel run and rebuilds what one processor would need. The link is s = s' / (s' + (1 - s') x N). A fraction that looks big in parallel time is small in sequential time.

Fitting the law to real numbers

The Karp-Flatt metric turns Amdahl upside down. From one measured speed-up S on N processors, it gives the serial fraction that would explain it: s = (1/S - 1/N) / (1 - 1/N). Example: S = 4 on N = 8 gives (0.25 - 0.125) / 0.875, about 14%.

Then watch how s behaves as N grows. If it stays constant, the lost speed comes from really serial code. If it grows (5% on 2 processors, 8% on 4, 14% on 8), the cause is overhead: waiting, cache fights, unbalanced load. Making the serial code shorter would not fix that.

Fork-join and work stealing

A teacher asks you to add up all the numbers of a long list. You cut the list in two and ask a friend to add one half while you add the other. Then you wait for the friend and add the two answers. You just did fork-join.

• Fork: a task creates sub-tasks that may run in parallel.
• Join: the task waits for all of them before going on.
• Every fork has its join, so the program becomes sequential again at clear points, and the result is easy to reason about.

The join is also a safety rule. When it returns, everything the other worker did has already happened and is visible. If you read the friend's partial count before the join, you may get a half-finished value or a data race.

sum(0..800)
  fork -> sum(0..400)     sum(400..800)
            fork            fork
          200  200        200  200
          (leaves: add them in one loop)
  join <- add the two halves

The cutoff (grain size)

We keep splitting until a piece is smaller than a limit called the cutoff, and then we add it with a plain loop. Cutoff too small: more time is spent creating and scheduling tasks than adding. Cutoff too large: too few tasks, and some cores have nothing to do. A good grain costs much more than the overhead of one task and still gives many more tasks than cores.

Static and dynamic splitting

Imagine an image of 8 rows. Rows 0 to 3 cost 2 ms each, rows 4 to 7 cost 10 ms each. Two workers:

The dynamic way costs one access to the shared counter per piece, a small price for balance.

Work stealing

Modern pools (Java fork-join, Rayon in Rust, Go, Cilk) use work stealing. Each worker has its own list of tasks, a deque. It works from its own end, newest task first (LIFO). When its list is empty, it steals a task from another worker, taking from the opposite end, the oldest task.

Why the oldest task? In a divide-and-conquer recursion, the oldest task is usually the biggest, so one steal brings a lot of work. The newest task is small and its data is still warm in the owner's cache. Another gain: with a single central queue, every worker fights for the same door. With stealing, the normal path is local, and workers talk to each other only when someone is idle.

Work and span

• Work T1: the time with 1 processor (the sum of all operations).
• Span Tinf: the time with unlimited processors (the critical path).
• A greedy scheduler guarantees Tp <= T1 / P + Tinf. No scheduler beats max(T1 / P, Tinf).
• Parallelism is T1 / Tinf. It caps the speed-up for any number of processors.

Examples: T1 = 240 s and Tinf = 6 s on P = 8 gives at most 240 / 8 + 6 = 36 s. T1 = 1,000 s and Tinf = 10 s has parallelism 100, so 100 processors are enough to get near the limit and the other 900 of a 1,000-processor machine are wasted.

Parallel reductions and sorting

A reduction squeezes many values into one: the sum of a list, the biggest number, the count of primes. In the sequential way you walk the list with one running total. In parallel, you give each worker a chunk, each one reduces its chunk into its own local variable, and at the end the partial results are combined.

Since each worker writes only to its own partial result, nobody fights during the work.

Which operators are safe?

A chunked reduction computes (a op b) op (c op d) instead of ((a op b) op c) op d. These agree for every input only if the operator is associative: the grouping does not matter.

Proof for subtraction with [8, 4, 2, 1]: sequential ((8 - 4) - 2) - 1 = 1. In two chunks, (8 - 4) - (2 - 1) = 3. Different, so subtraction cannot be reduced in parallel.

The tree reduction

With unlimited processors, combine the values in pairs, then the pairs of pairs, and so on. The number of values halves at every step.

8 values:  a b c d e f g h
step 1:    ab  cd  ef  gh
step 2:     abcd    efgh
step 3:       abcdefgh

The number of steps (the depth) is ceil(log2 n). The total number of operations is still n - 1, just like the sequential way. For 1,000 values: 10 steps and 999 operations.

Prefix sum (scan)

A prefix sum gives at each position i the combination of elements 0 to i. The usual loop uses the previous result, so it looks impossible to parallelise. With an associative operator it is solved in two passes over a tree: the up-sweep stores the sum of each block, and the down-sweep gives each position the sum of everything to its left. Work is O(n), depth is O(log n): for n = 8, 3 levels in each pass.

Merge sort in parallel

Merge sort is natural for parallelism. The array is cut in the middle, and the two halves are sorted without touching each other, so they can be two parallel tasks. The dependency appears only at the merge, which needs both halves done.

But if each merge is sequential, the critical path has one full merge per level: n + n/2 + n/4 + ..., less than 2n. For n = 1,024 the work is about 1,024 x 10 = 10,240 and the span about 2,047, so the best speed-up is near 5, no matter how many processors you have. To go further, the merge itself must be parallelised.

Sample sort

With p workers, sample sort uses p - 1 values called splitters to divide the input into p buckets, one per worker. Each worker sorts its bucket, and the buckets joined in order are already sorted. The parallel time is that of the biggest bucket, so bad splitters ruin everything. The fix: take a random sample of the data, sort it, and use its quantiles as splitters. Then the buckets have almost the same size.

Map-reduce and other parallel patterns

A pattern is a recipe that people reuse. Imagine a school counting votes for the best fruit. Many helpers each read a few ballots and write down "banana: 1" for every one (that is map). Then all the "banana" notes are put in the same box (that is shuffle), and one helper per box adds them (that is reduce).

MapReduce step by step

input   map (many machines)      shuffle        reduce

book 1 -> (the,1)(cat,1)(the,1) -+
book 2 -> (cat,1)(sat,1)        -+--> the: [1,1]  -> the: 2
book 3 -> (the,1)(mat,1)        -+     cat: [1,1]  -> cat: 2
                                       sat: [1]    -> sat: 1

• Map applies the same function to each record and emits zero or more key-value pairs. Records do not depend on each other, so they run in any order on as many machines as you have.
• Shuffle moves and groups the pairs so that all the values of one key arrive at the same place. A partition function (often a hash of the key) chooses the reducer. It is usually the step that uses the network most.
• Reduce is called once per key, with all the values of that key. Different keys can be reduced in parallel.

The combiner

Sending a million (the, 1) pairs through the network is silly. A combiner is a small reduce run inside each map task, before the shuffle. With 3 map tasks that each emit 1,000 pairs of 50 distinct words, the combiner leaves only 50 records per task, so 150 records go to the shuffle instead of 3,000. It is valid only when the operation is associative and commutative, like a sum. An average cannot be combined this way unless you also carry the count.

Failures and hot keys

• Re-execution. If a worker dies in the middle of a map task, the master runs the same task on another node. This is safe because the input is not changed and the map function is pure (same input, same output, no side effects). It is called an idempotent task. A map that writes into a database or reads the clock could duplicate or change results.
• Hot key. If one key holds 55% of all pairs, one reducer gets that much and the phase ends when it ends. Doubling the number of reducers only moves the other keys around. Fixes: a combiner, or splitting the hot key into subkeys and adding in two steps.

Other patterns

Scatter-gather example: a search sends one query to 20 index partitions and waits for all. Nineteen reply in 20 ms and one in 200 ms. The merge takes 5 ms. The answer arrives after 205 ms, because one slow helper decides.

Stencil example: a[i] = (a[i-1] + a[i+1]) / 2 written into the same array breaks when threads split the index range, because a cell may already hold a new value when its neighbour reads it. Double buffering makes the result independent of the order.

Determinism and reproducibility

If you ask a calculator "2 + 2" ten times, you always get 4. A deterministic parallel program is like that: its output depends only on its input. The scheduler may interleave the threads differently on every run, but all ways lead to the same answer. This is what lets you test the parallel version by comparing it with the sequential one.

Data race and race condition

A data race happens when two threads touch the same memory location, at least one writes, and nothing orders the accesses (no lock, no atomic operation, no join). The final value depends on luck. In C and C++ the behaviour is then undefined. Safe Rust rejects such code at compile time.

A race condition is wider: a result that depends on how the threads interleave. You can have a race condition without a data race. Look at this check-then-act code, where each method locks the account inside:

// two threads run this at the same time, balance starts at 100
if acct.Balance() >= 100 { // locks, reads, unlocks
	acct.Withdraw(100) // locks, subtracts, unlocks
}

Both threads see 100, both withdraw, and the balance ends at -100. The decision made in the check was no longer true when the action ran. The fix is to make the check and the action one atomic step (a single critical section, or one method that checks and withdraws).

Why parallel sums are exactly equal, or not

Counting primes with local counters and adding them after the join gives exactly the sequential answer for any number of threads. Integer addition is associative and commutative, so the grouping does not matter. Comparing with exact equality is fine.

Decimal numbers (floating point, like double) are different. Every addition rounds its result to the nearest value the computer can store, so (a + b) + c may differ from a + (b + c). Take [1e16, -1e16, 1.0] where the neighbours of 1e16 are 2 apart. Left to right: (1e16 - 1e16) + 1 = 1. Splitting as [1e16] and [-1e16, 1.0]: the second partial is -1e16 + 1, which rounds back to -1e16, and the total is 0. Another answer, by a lot.

Random numbers and output order

• Random numbers. In a Monte Carlo simulation with tasks handed out dynamically, tie the randomness to the task index, not to the thread. Each task builds its generator from a seed computed from the base seed and its index, ideally with a generator made for independent streams.
• Output order. Workers finish in an unpredictable order. Make each result carry its logical position: write result i to slot i, or return partial results with their index and combine them in index order after the join. The execution order stays free, and the output order stays fixed.

Time is not deterministic

Even when the result is identical, the time varies: 410 ms in one run, 470 ms in the next. The scheduler, the load of the machine, the cache state and the CPU frequency all change. A reproducible benchmark uses the same input and machine, leaves the warm-up out, repeats the run several times, reports the spread together with the central value, and records the machine, versions and exact command.

False sharing and cache effects

Memory is slow, so each core keeps a small fast copy of what it uses, called the cache. But the cache does not keep single variables. It keeps blocks called cache lines, usually 64 bytes. Touch one byte and the whole 64-byte block comes in.

False sharing

When a core writes to a line, the copies of that line in the other cores are invalidated (thrown away) so everybody stays coherent. If variables of different threads sit in the same line, the cores keep stealing the line from each other, though they share no real data. This is false sharing.

one 64-byte cache line (8 counters of 8 bytes)
[c0][c1][c2][c3][c4][c5][c6][c7]
  ^   ^   ^   ^   ^   ^   ^   ^
  8 threads on 8 cores, each adds to its own ci
  -> the line bounces between the cores

Counting who interferes with whom: the byte offset divided by 64 gives the line. 16 counters of 8 bytes starting at a line boundary: counters 0 to 7 are in line 0 and 8 to 15 in line 1. Thread 3 fights with the 7 other threads of its group, and the two groups do not disturb each other.

How to spot it

The signature: no locks, every core at 100%, parallel time equal to or worse than the sequential one (for example 2.0 s with 1 thread and 3.1 s with 4), and a drastic improvement (to 0.52 s) when you only move the counters 64 bytes apart. The cores are busy, but waiting for the line to come back.

How to fix it

• Accumulate in a local variable inside the hot loop and hand over the total once, after the loop. The line a worker modifies is then its own, and merging happens once per worker.
• Pad or align each counter to its own line, for example alignas(64) in C++. The price is memory: 8 bytes become 64, so an array of 8 such structs grows from 64 to 512 bytes.

Spatial locality

Because a miss loads a whole line, using neighbouring data is cheap. A 1024 x 1024 matrix of 4-byte integers stored by rows: one miss brings 16 integers, so walking row by row misses 1 time in 16, about 65,536 misses in total (1,048,576 / 16). Walking by columns jumps 4,096 bytes each step. If the cache cannot hold the 1,024 lines of one column, every access misses: 16 times more.

CPU-bound against memory-bound

A loop that counts primes uses almost no memory, and each core brings its own computing power, so it scales almost linearly (7.6 times with 8 threads). A loop that sums a 16 GiB array depends on the throughput of the memory channels, one resource shared by all cores. When it saturates, more threads just split the same bandwidth: 2.9 times with 4 threads and no gain at 8.

SIMD and vectorisation

Parallelism also lives inside one core. Picture a stamp that prints 8 dots at once instead of 1. That is SIMD, short for Single Instruction, Multiple Data. A vector register holds several numbers of the same type, and one instruction adds, multiplies or compares all of them together.

It is independent of threads, and the two can be combined. In Flynn's taxonomy:

Lanes

The number of elements per instruction (the lanes) is the register width divided by the element width. A 256-bit register and 32-bit floats give 256 / 32 = 8 lanes. That is also the ceiling of the gain for the loop body. In practice you get less because of the remainder loop, memory access and lower clock on some CPUs.

When n is not a multiple of the width, the compiler makes two loops: the vector loop runs floor(n / 8) times and the remainder loop handles the last n mod 8 elements one by one. For 1,003 floats: 125 vector iterations (1,000 elements) and 3 scalar ones. On short arrays the remainder can hide the SIMD gain.

Auto-vectorisation

The compiler can do this by itself. It analyses a scalar loop and, if it can prove the result does not change, it emits vector instructions. You help it by keeping the loop simple: independent iterations, no opaque function calls, no doubtful overlap of arrays.

What blocks vectorisation

• Loop-carried dependence. In a[i] = a[i-1] + b[i] each element needs the one just written (a prefix sum), so 8 elements cannot be computed together. But a[i] = a[i+1] + b[i] is fine: the value read is always the original one.
• Pointer aliasing. With float *dst, const float *src, the compiler must admit that the two may overlap, which would create a dependence. It adds a run-time check, or you remove the doubt with the restrict qualifier in C. Rust's &mut and & slices already guarantee no overlap.
• Branches per element. A vector has one flow of control, so if (a[i] > 0) b[i] = a[i] * 2 becomes data: the comparison builds a mask, the work is done in all lanes, and the mask decides what is stored (if-conversion). The cost is doing work that is thrown away, so the gain drops when the branch is expensive and rarely taken.

// vectorises: iterations are independent
for (int i = 0; i < n; i++) c[i] = a[i] + b[i];

// does not: each step needs the previous result
for (int i = 1; i < n; i++) a[i] = a[i - 1] + b[i];

GPU computing basics

A CPU is like 8 very clever professors: each solves hard, different problems quickly. A GPU (graphics processing unit) is like a stadium full of thousands of students, each one simple, all told to do the same small calculation at the same time on different numbers.

The kernel

On a CPU you write for (i = 0; i < n; i++) out[i] = f(in[i]). On a GPU you write only the body, as a function called a kernel, and launch it over an index space of n positions. Each thread receives its own thread index, which plays the role of i, and handles one element. This is correct only when iterations are independent, the same condition as for CPU data parallelism.

Why branches and pointer chasing hurt

A GPU groups threads that run the same instruction together, like the lanes of a vector. If a branch sends half the group one way and half the other, the hardware walks both paths one after the other, and throughput drops. The simple cores also lack the branch prediction and big caches that let a CPU absorb irregular code.

Is it worth the trip?

The GPU has its own memory. The data must be copied there and back, and starting a kernel has a fixed cost. So the time on the GPU has three parts: compute, transfer, launch.

Example: the CPU costs 40 ns per element. The GPU computes in 4 ns per element, copying costs 6 ns per element, and launching costs a fixed 30 ms. The gain per element is 40 - (4 + 6) = 30 ns. The break-even point is 30 ms / 30 ns = 1,000,000 elements. Below that the CPU wins. If the copy cost more than the saving in compute, the GPU would never pay off.

Amdahl still applies to any accelerator. A program takes 100 s: 80 s in a kernel and 20 s that must stay on the CPU. The kernel gets 20 times faster (4 s), and transfers add 6 s. New time: 20 + 4 + 6 = 30 s, speed-up 3.33. Without the transfers it would be 24 s and 4.17. The limit with an infinitely fast kernel is 100 / 20 = 5. The transfer is a new serial term that did not exist in the sequential version.

Shared and distributed memory

Two ways to organise helpers. In a classroom with one big blackboard, everybody reads and writes on the same board. That is shared memory. In a group of friends in different houses, each has a notebook, and they call each other to share things. That is distributed memory.

Threads share, processes on other nodes send

The threads of one process share the heap and the global variables; each one owns only its stack and registers. Communication is direct, and concurrent writes need synchronisation. In distributed memory each process sees only its own memory. Whoever has the data sends it and whoever needs it receives it. You decide what, to whom and when, and you pay the cost of copying it over the network.

Example: sum 1,000,000 integers of 8 bytes with 4 workers. With threads, each receives a pointer and a length: no byte is copied. With message passing, a master sends one quarter to each worker: 4 messages with 2,000,000 bytes each, 8,000,000 bytes out, plus 4 replies of 8 bytes, 32 bytes back, in 8 messages.

UMA and NUMA

Shared memory has two forms. In UMA (uniform memory access) every CPU needs the same time to reach any address. In NUMA (non-uniform) each node has CPUs and a memory bank close together. Local access is fast, and reading a page that lives on another node is slower. The program stays correct, but performance depends on keeping data close to who uses it.

Why distributed machines reach more processors

In shared memory, every new CPU competes for the same bus, memory bandwidth and cache-coherence traffic. In distributed memory each node is a complete computer, so there is no single point of contention. The price: all cooperation costs messages, so the algorithm must communicate little.

Distributed shared memory (DSM)

A page-based DSM builds the illusion of shared memory on top of messages. Touching an absent page raises a fault, and the handler fetches the page from another node. The unit is the whole page, so two unrelated variables x and y on the same page, written by nodes A and B, make the page bounce over the network. This is false sharing again, at a larger scale, called thrashing.

Hybrid programs

Many programs mix both: message-passing processes between nodes (for example MPI) and threads inside each node. Each layer brings its own bugs. A data race can only happen where memory is common, so among threads of the same process. A deadlock does not need common memory: two processes that each do a blocking receive from the other before sending will wait forever.

Putting it all together

This repository measured these ideas in the mini-project scaling-by-cores: it counts primes and renders a Mandelbrot image in Rust, Go and C++ with 1, 2, 4 and 8 workers, with a static split and a dynamic split. All 72 runs printed exactly the same results as the sequential programs (a deterministic reduction and one writer per pixel).

Same code, only the split changed, and the speed-up doubled. The static split gave the expensive middle rows to a few workers and the others waited. Amdahl's law read that waiting as serial code: a fitted serial fraction near 30%, in a program that has almost none. With the dynamic split it fell below 7%. The lesson: before blaming Amdahl, check that every worker is busy until the end.

A checklist for a slow parallel program

Which tool for which problem