Parallel algorithms organise a computation so that independent operations can run at the same time while dependent operations remain correctly ordered. Their gold standard is a correct result with a defensible account of total work, the longest dependency chain, data movement and measured performance. Adding processors helps only when the algorithm exposes useful work that those processors can perform.
The first question is therefore not “How many cores do I have?” It is “Which results must exist before the next operation can begin?” This guide answers that question through reductions, prefix sums, filtering, matrix multiplication and small scheduling calculations. It distinguishes mathematical speedup from real elapsed time and shows how to investigate a result that becomes slower or incorrect when parallelised.
The worked numbers are constructed teaching examples, not hardware benchmarks. Start with the Gold Standard master for the wider collection, the Education parent for learning that transfers, or the How X Works hub for related mechanisms.
Choose your parallel algorithms route
Chapters 1–3: Model dependencies
Chapters 4–6: Build useful primitives
Chapters 10–12: Protect correctness
Chapter index
Model dependencies · Chapters 1–3
1. Begin with dependencies rather than processor counts
Build useful primitives · Chapters 4–6
4. Reduce many values through a tree
Measure scaling · Chapters 7–9
7. Calculate speedup without hiding the baseline
Protect correctness · Chapters 10–12
10. Protect shared state and numerical meaning
Diagnose and continue · Chapters 13–14
CHAPTER 1 OF 14 · Model dependencies
1. Begin with dependencies rather than processor counts
What may happen together
Suppose four files each need a checksum, followed by one report containing all four checksums. If the files are independent, their checksums can be calculated concurrently. The report must wait for all four results. Running the report early is not an optimisation: it changes the result by omitting information that the task requires.
Represent each operation as a vertex and each required precedence as an arrow. For a terminating computation whose operations have been expanded, these dependencies form a directed acyclic graph. The graph need not impose a single order on every pair of operations. Two vertices with no dependency path between them may be eligible to run together, subject to the machine and the algorithm’s access rules.
Concurrency describes overlapping progress among activities; parallel execution means operations actually run simultaneously on multiple resources. A single processor can interleave tasks without executing them simultaneously. Conversely, an algorithm can contain abundant potential parallelism even when its present implementation uses one core. Keep the structure of the algorithm separate from the resources available to execute it.
Decide what a result means
Before drawing the graph, specify inputs, outputs and permissible variation. A sorting task may require ascending keys, stability among equal keys, or both. A numerical sum may require a tolerance rather than bitwise identity with a particular sequential order. A filter may need to preserve the order of surviving records. These are observable requirements, not optional details to settle after a speed measurement.
For the checksum report, also distinguish completion from success. A failed worker should not silently contribute an empty checksum. The coordination rule must identify failed work and decide whether to retry, report failure or stop. An algorithm that finishes quickly by skipping a required task has not solved the same problem.
The specialist guide to algorithms, binary search and Big-O supplies the sequential foundations. Parallel analysis adds another obligation: explain which operations can overlap without changing the meaning of the computation.
Two quantities answer different questions
Work W counts the total primitive operations in the chosen computation. Span S counts the length of its longest dependency chain, using the same unit-cost model. Work tells us how much effort is present; span tells us how quickly unlimited ideal processors could finish that graph. Neither quantity is automatically a number of seconds on a real machine.
On P processors, execution time T cannot be smaller than W/P, because P processors perform at most P unit operations per step. It also cannot be smaller than S, because the operations on a dependency chain cannot overlap. Thus T is at least max(W/P, S). With integer time steps, the work bound can be rounded up to the next integer.
For two computations performed sequentially, add their work and their spans. For independent computations performed in parallel, add their work but take the maximum of their spans, then account for any explicit fork, join or combining operations. This gives a practical way to analyse a recursive program without drawing every vertex.
A deliberately small comparison
Consider eight unit tasks. In one graph they form a chain, giving W = 8 and S = 8. In another they are all independent, giving W = 8 and S = 1 before any collection overhead. Four ideal processors require at least eight steps for the chain but can execute the independent tasks in two steps. Equal work does not imply equal parallel opportunity.
The ratio W/S is often called the computation’s parallelism. It is an average measure of available opportunity, not a promise that exactly that many operations are ready at every moment. A graph can have a wide middle and narrow beginning and end. Those narrow portions still matter to total completion time.
CMU’s work-and-span treatment formalises these measures. Whenever a resource claim seems surprising, return to the units. Counting a whole matrix multiplication as one vertex while counting each scalar addition elsewhere makes the comparison meaningless unless that abstraction is explicitly justified.
Ready operations and finite workers
A scheduler assigns ready operations to processors. An operation is ready only after all its dependencies have finished. A greedy scheduler avoids leaving a processor idle when suitable ready work exists, but cannot manufacture work that is blocked by a dependency. Idle time is therefore not automatically evidence of a poor scheduler.
Take a computation with three successive layers containing four, two and one unit operations. Every operation in a layer waits for the previous layer in this teaching model. Work is seven and span is three. With four processors, the layers take one step each, so total time is three. With two processors, they take two, one and one steps, for total time four. With one processor, all seven operations execute sequentially.
For a level-by-level schedule, layer i with wᵢ operations takes ceil(wᵢ/P) steps. Summing gives a bound no greater than W/P + S, up to the conventions used for layers and integer rounding. Together with the lower bounds, this explains why work and span are useful predictors in an idealised model. CMU’s scheduling notes discuss this relationship and greedy schedules.
What the bound leaves out
The ideal model does not charge realistic costs for discovering tasks, synchronising processors, fetching remote memory or transferring data. A runtime with expensive task creation can lose to a sequential loop on a small input even when the graph has a short span. This is not a contradiction of the model; the implementation has costs the simple model omitted.
A useful diagnostic experiment records both the intended task graph and the actual worker timeline. If the graph exposes ready work but processors are idle, examine scheduling or resource restrictions. If no work is ready, examine the dependency chain. If processors are busy but progress is slow, examine excess work, contention or data movement. These are different failure modes and call for different repairs.
Eight inputs, seven additions
Sum the exact integers 3, 1, 4, 1, 5, 9, 2 and 6. A left-to-right accumulator requires seven dependent additions. A balanced tree first forms 4, 5, 14 and 8; its next level forms 9 and 22; its final addition gives 31. Both procedures use seven additions. The tree has only three addition levels.
For n inputs where n is a power of two, this reduction has n − 1 additions and log₂ n addition levels. A non-power-of-two input can be handled by uneven subtrees or by padding with the operation’s identity when appropriate. Padding is a mathematical choice: zero is an identity for addition but not for multiplication, whose identity is one.
The invariant is that every intermediate value represents the combination of a known, disjoint group of original inputs. At the final node those groups cover the input exactly once. This is a stronger correctness argument than observing that several test sums happened to match.
Associativity is the permission to regroup
An operation is associative when regrouping does not change its result: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). Parallel reduction needs a suitable associative combining operation to justify the regrouping. It need not be commutative if the algorithm preserves the original order. String concatenation is associative but exchanging the strings changes the answer.
Subtraction is not associative: (10 − 3) − 2 is five, while 10 − (3 − 2) is nine. A program that replaces an arbitrary sequential fold with a tree can therefore be wrong even with perfect synchronisation. Floating-point addition needs its own treatment because finite-precision rounding also makes regrouping observable.
Use the Blelloch and Maggs parallel algorithms reference for reductions and other sequence primitives. For implementation, first identify the algebraic operation and its identity, then verify that the data representation preserves the properties on which the proof depends.
CHAPTER 5 OF 14 · Build useful primitives
5. Compute every prefix, not only the final total
Inclusive and exclusive answers
For input 3, 1, 4, 1, the inclusive prefix sums are 3, 4, 8, 9. The exclusive prefix sums are 0, 3, 4, 8: each position contains the sum of earlier inputs, excluding its own. Both operations are commonly called scans, so an interface must say which convention it uses.
A naive implementation launches one task per output and has each task sum its entire prefix. That exposes parallel tasks but uses 1 + 2 + … + n = n(n + 1)/2 additions if each task starts from zero. It has replaced a linear-work problem with quadratic work. Running many tasks is not enough; duplicated effort can erase the gain.
A tree carries totals upward and offsets downward
For the four-element exclusive scan, first compute the totals of the two halves: four and five, then total nine. Give the root an incoming offset of zero. The left half receives zero; the right half receives zero plus the left total, namely four. Within the left half, the leaves receive zero and three. Within the right half, they receive four and eight. The outputs are therefore 0, 3, 4, 8.
At every subtree, its incoming offset equals the sum of all elements before that subtree. The left child inherits it; the right child receives it combined with the left child’s total. This invariant explains the downward pass and extends to order-preserving scans for associative operations with an identity.
The upward and downward passes each have logarithmic depth and together perform linear work. Exact operation counts depend on implementation conventions, including whether assignments and identity operations are counted. State those conventions instead of comparing a count of arithmetic operations with a count of all instructions.
Scans are useful when output positions depend on how many earlier items qualify. They turn a seemingly sequential dependence on “everything before me” into a structured combination of reusable partial results. The next chapter makes that connection concrete through stable filtering.
Assign unique destinations
Suppose six records arrive in the order A, B, C, D, E, F, and the selection flags are 1, 0, 1, 1, 0, 1. An exclusive sum of the flags is 0, 1, 1, 2, 3, 3. Each selected record writes to the destination equal to its prefix: A to zero, C to one, D to two and F to three. The output is A, C, D, F.
The total number of selected records is four. It can be obtained from the final exclusive prefix plus the final flag. For an empty input, handle the total explicitly rather than reading a nonexistent last element. Empty and all-rejected inputs are important correctness cases because they exercise allocation and boundary logic.
Why writes do not collide
If selected item i precedes selected item j, the prefix at j includes the one contributed by i and possibly other selected items. Therefore j’s destination is strictly larger. Distinct selected items have distinct destinations, and their original order is preserved. Rejected items do not write, so repeated prefix values at rejected positions cause no collision.
This construction avoids an uncontrolled shared output counter. A counter protected by an atomic increment might allocate unique positions, but the order in which workers claim them can differ from the input order. That version may be correct for unordered collection and incorrect for stable filtering. The required output semantics decide which is acceptable.
One real application is compacting valid records before a more expensive calculation. Another is allocating space for variable-length output: replace each binary flag with the number of output items generated by that input, then scan those lengths. The resulting offsets locate nonoverlapping output regions. Check for integer overflow in the accumulated lengths before allocating memory.
This pattern separates deciding output size from writing output. It adds passes over the data but makes ownership of each destination explicit. A worthwhile performance study counts those passes and allocation costs rather than assuming that removing a lock must make the entire pipeline faster.
A fixed workload example
Suppose a sequential computation takes 100 seconds: 20 seconds are serial and 80 seconds can be perfectly divided among P processors. Ignoring overhead, T(P) = 20 + 80/P. Four processors give 40 seconds and speedup 100/40 = 2.5. Eight processors give 30 seconds and speedup about 3.33. Unlimited processors approach 20 seconds, so the speedup limit is five.
This is an Amdahl-style fixed-workload model. It does not predict every application or every input. The serial fraction can change when the input, algorithm or implementation changes. It does show why accelerating only the already-parallel portion has diminishing returns while the serial component remains fixed.
Add costs before making a decision
Now introduce a deliberately simple coordination cost of two seconds for each additional processor. The model becomes 20 + 80/P + 2(P − 1). Four processors take 46 seconds; eight take 44; sixteen take 55. More resources eventually make this constructed workload slower. These are calculations from the stated model, not measurements from a particular computer.
Parallel efficiency is speedup divided by processor count. Under the overhead-free four-processor calculation, efficiency is 2.5/4 = 62.5%. That figure is not itself a judgement of usefulness: a substantial reduction in completion time can be valuable even when efficiency is below one. Resource cost, deadlines and alternative uses of the processors also matter.
Always name the sequential baseline. Comparing a parallel algorithm with a deliberately weak sequential implementation exaggerates the practical benefit. Compare with a credible method solving the same problem to the same accuracy, and report whether the parallel algorithm on one processor performs extra work.
LLNL’s introduction to parallel computing discusses scaling limits, communication and decomposition. Its general principles guide the questions to ask; your own measured workload determines whether the proposed processor count helps.
Hold the right thing constant
Strong scaling keeps the total problem fixed and asks what happens as processor count grows. Weak scaling increases the problem with the processor count, often keeping work per processor approximately constant. A good weak-scaling result does not establish that the original small problem finishes faster.
Imagine a synthetic workload of one million independent items per processor. One processor handles one million; four handle four million. If both runs take ten seconds, throughput has grown fourfold while completion time has stayed constant. This can be an excellent result, but calling it a fourfold speedup for a fixed one-million-item job would describe an experiment that was not performed.
Record an honest experiment
For strong scaling, retain the same input and output contract across processor counts. For weak scaling, record the input-size rule explicitly. Include setup, transfer, computation and output times, or state clearly which are excluded. A timing that excludes uploading data to an accelerator measures a different boundary from the user’s total wait.
Repeat measurements under comparable conditions. Report variation and explain warm-up, caching and any one-time compilation or initialisation. Check the result after each run. A fast wrong answer should not enter the performance comparison as a successful execution.
The National Supercomputing Centre Singapore article connects parallel computing to research infrastructure, allocation and scientific verification. The algorithmic lesson is independent of access to a large machine: even a small experiment can distinguish fixed-size speedup from increased throughput.
A learning report should include a question before its graph. “How quickly can we finish this fixed dataset?” and “How much data can we process in ten minutes?” are both useful, but they call for different plots and interpretations. Choose the experiment that matches the decision rather than the one that produces the most impressive rising line.
Arithmetic is only part of the cost
A worker cannot operate on data it has not received. On a multicore machine, fetching data from memory can dominate arithmetic. On a cluster, messages and network transfers add latency and bandwidth limits. On an accelerator, transfers between memory spaces can matter. A short span in an arithmetic-only graph does not eliminate these costs.
Consider a model where sending a message takes α + βm time, with α the startup latency, m its size and β the time per unit of data. Sending 100 separate messages of one unit costs 100α + 100β; one message containing all 100 units costs α + 100β. Batching saves 99 startup charges, though it may require waiting for data and storing a larger buffer.
This calculation explains why task granularity matters. Tiny tasks offer many scheduling choices but incur more task-management and communication overhead. Large tasks amortise overhead but can leave processors idle when one task takes much longer than the others. Choose granularity from the actual dependency and data pattern.
Balance work, not merely item counts
Suppose four tasks cost 8, 1, 1 and 1 time units. Assigning one task to each of four workers finishes in eight units, not 11/4. Equal task counts have not balanced work. If the eight-unit task can be divided into independent pieces, a finer decomposition may help. If it is an indivisible dependency chain, the limitation is structural.
Dynamic scheduling can assign new tasks to workers as they finish. It can improve balance, but the shared queue and movement of data can add overhead. Static assignment can be efficient when costs and locality are predictable. Neither approach is universally best.
When inspecting a slow run, identify whether workers are waiting for tasks, data or dependencies. A utilisation percentage alone cannot distinguish these. A busy processor may be doing useful arithmetic, redundant computation or coordination. The repair should target the measured bottleneck rather than simply increasing the number of threads.
CHAPTER 10 OF 14 · Protect correctness
10. Protect shared state and numerical meaning
A lost update is a correctness failure
Two workers each want to increment a shared counter initially zero. If both read zero, both compute one and both write one, the final result is one instead of two. This interleaving exposes why a read-modify-write sequence needs an appropriate synchronisation mechanism when several workers may access it concurrently.
One repair is an atomic increment supported by the programming model. Another is a private counter per worker followed by a reduction. These repairs have different contention, memory and aggregation costs. A lock can protect a larger invariant involving several fields, but holding it around the entire computation may serialise the useful work.
Do not assume that a program is safe merely because a failure has not appeared in testing. Scheduling changes can expose rare interleavings. Start with ownership rules: which worker writes each location, which locations are shared, and what establishes ordering before a reader uses a result? Tests complement those rules rather than replacing them.
Floating-point addition changes under regrouping
In finite-precision arithmetic, very small additions to a sufficiently large value can be rounded away. Consequently, adding a large positive number, its negative and a small number in different groupings can yield different answers. This is not necessarily a data race. It can be the predictable effect of a different reduction tree.
Define whether the task requires bitwise reproducibility, a fixed reduction order, or a numerical accuracy tolerance. Then use an appropriate numerical method and verify the error. A deterministic tree can improve repeatability while still producing rounding error. A tolerance must be justified by the numerical problem, not enlarged merely to conceal a mismatch.
Exact integer examples in earlier chapters assume arithmetic does not overflow. Machine integers can violate that assumption. Before using a scan to allocate output storage, establish that the sum of lengths is representable. Correct parallel ordering cannot repair an arithmetic representation that has already lost the required value.
CHAPTER 11 OF 14 · Protect correctness
11. Apply the model to matrix multiplication
Independent outputs, dependent partial sums
For ordinary dense multiplication C = AB, output entry Cᵢⱼ is the sum of AᵢₖBₖⱼ over k. Different output entries can be computed independently if each owns its output location and A and B remain unchanged. Within one entry, products can also be generated independently and combined through a reduction.
Use A with rows (1, 2) and (3, 4), and B with rows (5, 6) and (7, 8). The outputs are 19, 22, 43 and 50. For example, C₁₁ = 1 × 5 + 2 × 7 = 19. Four workers can each calculate one output entry without sharing an accumulator. Alternatively, eight product tasks can feed four addition tasks.
Under a unit-cost model that counts scalar multiplications and additions, the latter graph has eight multiplication operations and four additions: work twelve and span two. These counts exclude data access and task creation. They describe the arithmetic graph, not an expectation that twelve real instructions complete in two clock cycles.
Why blocking changes practical performance
For larger matrices, an implementation can reuse portions of A and B while producing a block of C. This improves locality when the blocks fit the relevant memory level. The point is not merely to distribute output entries but to avoid repeatedly fetching the same data from a slower location.
Selecting block sizes requires knowledge of the implementation and hardware. A block that is too large can lose the intended locality; one that is too small can incur unnecessary loop or task overhead. Measure complete performance and preserve the arithmetic contract, especially when different reduction orders change floating-point results.
This example brings together three levels of reasoning. The mathematical formula determines correctness. The dependency graph exposes legal parallel work. The memory layout and execution environment determine how efficiently that work is performed. Confusing the levels leads to claims such as “every matrix entry is independent, so performance must scale linearly”, which the data movement costs do not support.
CHAPTER 12 OF 14 · Protect correctness
12. Test transfer by changing one assumption
Stable becomes unordered
Return to the six-record filter. If output order is irrelevant, workers may have more freedom in assigning destinations. If the next stage assumes chronological order, that freedom disappears. A result containing the correct records in a different order can still violate the pipeline contract. State which property changed before selecting a new implementation.
Shared memory becomes distributed memory
An algorithm that repeatedly reads a neighbour’s value cheaply in shared memory may require messages when those values live on different nodes. The mathematical dependencies remain, but the cost model changes. Group communication, keep data near its users or reconsider the decomposition. Do not carry a shared-memory performance claim unchanged into a distributed setting.
A reduction operation becomes nonassociative
Replace addition with subtraction in the eight-value tree. The original grouping argument no longer applies. A repair might retain the sequential semantics or reformulate the mathematical problem into an associative combination, if such a reformulation is valid. Simply increasing precision or adding a barrier does not make subtraction associative.
The input becomes much smaller
A parallel implementation may be worthwhile on a million items and wasteful on sixteen. A hybrid method can switch to sequential work below a chosen threshold. That threshold is an implementation decision to measure, not an asymptotic theorem. Check both correctness and performance at the boundary where the switch occurs.
For each exercise, explain the old assumption, the changed condition and the evidence needed for a replacement claim. This is the transfer standard developed by the Education guide. Remembering a speedup formula is useful; knowing when its assumptions have stopped describing the task is more useful.
CHAPTER 13 OF 14 · Diagnose and continue
13. Diagnose failures and answer common questions
Start with the symptom
If answers vary unexpectedly across runs, inspect ownership, synchronisation and numerical order separately. If the answer is correct but slower with more workers, examine task overhead, memory bandwidth, communication, load imbalance and the serial portion. If scaling stops abruptly, check whether the input per worker has become too small or a shared resource has saturated.
If some workers finish early, compare actual work assigned rather than the number of records. If memory consumption grows rapidly, check duplicated inputs, temporary buffers and per-worker state. If a benchmark shows an extraordinary speedup, verify that both versions perform the same work to the same accuracy and include the same timing boundary.
Does every loop parallelise?
No. Iterations may depend on earlier iterations or share state in ways that constrain ordering. Some dependencies can be removed through a different algorithm, such as replacing a sequential prefix accumulation with a scan. Others reflect the required semantics and must remain.
Is a GPU always the right choice?
No. The useful choice depends on the computation’s regularity, data size, transfer costs, memory use and supported operations. This guide explains the questions to ask rather than recommending a device. A hardware label alone does not establish that an algorithm will run well.
Is parallelism the same as streaming?
No. Parallelism concerns simultaneous work; streaming concerns processing data under constraints such as limited memory and few passes. A computation can be both. The Streaming Algorithms root explains sampling, sketches and memory limits that may interact with a parallel implementation.
Can I prove correctness from benchmark agreement?
Agreement on tests is valuable evidence but does not establish correctness for all inputs or interleavings. Combine small exact oracles with invariants, ownership arguments and relevant arithmetic assumptions. Include empty inputs, one-element inputs, uneven sizes, repeated values and extreme representable values. Each tests a different part of the contract.
Produce evidence at each stage
First, draw dependency graphs for a checksum report, a reduction and a matrix product. Count work and span using a declared operation model. Construct schedules for one, two and four workers. Explain which idle periods are unavoidable and which arise from your chosen schedule.
Second, implement exact-integer reduction, exclusive scan and stable filtering on small arrays. Compare against a simple sequential oracle. Check the eight-value sum of 31 and the six-record output A, C, D, F, then change sizes and values. For every selected record, verify that its destination is unique and its relative order is preserved.
Third, make a scaling experiment with a clearly fixed workload. Record total runtime, computation time if separately measured, processor count, input size, output correctness and variation across repeated runs. Explain the baseline. Do not mix a changing dataset with a fixed-size speedup graph.
Finally, select an application and justify its decomposition. The NSCC article provides a route into scientific computing infrastructure. The algorithm complexity article helps compare alternative procedures before distributing their work.
Technical sources and next reading
Blelloch and Maggs, Parallel Algorithms covers computation models, sequence operations, graphs, sorting and numerical algorithms. CMU’s work-and-span chapter develops the cost model, while Parallel Computing: Theory and Practice discusses schedules and dependency graphs.
LLNL’s Introduction to Parallel Computing supplies the systems perspective on decomposition, communication, memory architectures and scaling. These sources support the general mechanisms; the numerical examples here are explicitly constructed calculations that can be checked independently.
A finished project should state what is computed, why concurrent operations preserve it, what limits speedup, and how the result was tested. Return to the Gold Standard master to choose another subject, or use How X Works to connect the algorithm to the system in which it operates.