Advanced Algorithms · Lecture Notes
Chapter 9: Parallel Algorithms
Even a laptop today has several processor cores. A sequential algorithm uses only one of them while the others sit idle. A parallel algorithm splits the work into pieces, solves the pieces at the same time on different processors, and combines the results. These notes first explain why parallelism is needed and what costs it brings. They then present the classification of parallel computers, the PRAM model, and the performance measures: speedup, efficiency, cost, Amdahl's law, work, and depth. The basic techniques are run step by step on small examples: tree summation, prefix sums, pipelining, and the pipelined tree. In the last part the same ideas are built in Java. We write merge sort with Fork/Join, word count with MapReduce, and matrix multiplication with row tasks. The race condition caused by shared state is shown by measurement.
Learning outcomes
- Concepts
- Explain the divide, assign, solve, and combine structure of a parallel algorithm, and the gains and difficulties it brings (communication, synchronization, load balancing).
- Models and measures
- Recognize Flynn's classes, the memory architectures, and the PRAM model; compute speedup, efficiency, cost, work, and depth; apply Amdahl's law and Brent's theorem.
- Basic techniques
- Trace PRAM tree summation, parallel prefix sums, the pipeline, and the pipelined tree step by step; find the number of rounds and steps.
- Parallelism in Java
- Read parallel merge sort with Fork/Join, MapReduce, and data-parallel examples; recognize and prevent race conditions.
9.1The idea of a parallel algorithm
Suppose a single teacher grades the 1000 exam papers of a class. At about 36 seconds per paper the job takes 10 hours. If the same papers are shared among 10 teachers, each reads 100 papers and the job finishes in about 1 hour. But this calculation is incomplete. Handing out the papers takes time. Collecting the grades into a single list after everyone finishes also takes time. If one teacher is late, the other nine wait for that teacher. The whole subject of parallel algorithms is hidden in this small example: the work is split, the pieces are done at the same time, and the results are combined. The cost of splitting and combining takes back part of the gain.
9.1.1Why parallelism?
Some jobs take very long on a single processor. Analyzing a data set with billions of rows, running a weather model days ahead, and training a neural network on thousands of images are of this kind. There are two ways to shorten such jobs: make the single processor faster, or split the work among several processors.
For many years the first way was enough. Processor clock speeds doubled every few years, and the same program ran faster without any change. Since the mid-2000s this growth has almost stopped. Raising the clock speed increases heating and power consumption to unacceptable levels. Manufacturers began placing several cores on a single chip instead. Today performance growth comes largely from the number of cores. A program benefits from this growth only if it can split its work among cores.
A parallel algorithm is an algorithm that solves a problem using several processors (or cores) working at the same time. Each processor does a part of the work; when necessary the processors exchange data and coordinate among themselves.
The phrase "at the same time" in the definition is important. A single-core computer also appears to run several programs "at the same time". In reality the operating system switches rapidly between programs, and only one runs at any instant. In a parallel algorithm, several processors really do work in the same time slice. In these notes the words processor, core, and thread are used, depending on context, with the same meaning: "a computing unit that can work independently".
9.1.2Divide, assign, solve, combine
The skeleton of a parallel algorithm usually consists of four steps. The problem is first divided into pieces that are as independent of each other as possible. The pieces are assigned to different processors. The processors solve their pieces at the same time. Finally the partial results are combined to obtain the result of the original problem. Figure 9.1 shows this flow for four processors.
This structure resembles divide and conquer. In divide and conquer, too, the problem is split into subproblems and the results are combined. The difference lies in how the subproblems are solved. In sequential divide and conquer the subproblems are solved one after another. In a parallel algorithm the independent subproblems are solved at the same time. For this reason divide-and-conquer algorithms are among the algorithms best suited to parallelization.
A group of people carrying out a joint task is a good analogy. When a house is being moved, one person packs the books, one the kitchen, and one the clothes. When everyone finishes, the boxes are loaded onto the same truck. Two conditions are needed for the work to speed up. First, the pieces must really be independent: the person packing the kitchen should not wait for the one packing the books. Second, the pieces must be of roughly equal size: if the books take two hours and the clothes ten minutes, the person packing clothes sits idle most of the time.
Parallel computing is the foundation of high-performance computing (HPC). Areas such as big data analysis, scientific simulation, and machine learning rely heavily on parallel algorithms today.
9.1.3Gains and difficulties
Parallelism has three basic gains:
- Speedup. The same job finishes in less time. A weather forecast model is ready this evening instead of tomorrow morning.
- Scalability. Large problems that do not fit in the memory or disk of a single machine can be solved by distributing them across many machines.
- Efficient use of hardware. All the cores of the computer and the graphics processor (GPU) do work; idle hardware decreases.
These gains also have a price:
- Splitting and combining require extra effort. Dividing the problem into pieces and combining the partial results are extra operations that a sequential algorithm does not have.
- Communication and synchronization add overhead. Processors must exchange data and wait for each other. No useful work is done during this time.
- Load balancing is needed. The work must be distributed evenly among processors. The piece that takes longest determines the time of the whole job.
- Debugging is hard. Parallel programs suffer from bugs such as race conditions and deadlock. These bugs may not show up on every run.
- Some problems are inherently sequential. If a step needs the result of the previous step, those steps cannot be done at the same time.
The last item draws the theoretical limit of parallelism. Consider a recurrence of the form xk = f(xk−1), where f is an arbitrary function. To compute x5, x4 must be known, and for x4, x3. This is a chain of data dependencies. However many processors there are, the links of the chain are computed one by one. Such a computation cannot be parallelized.
Not every chain is this rigid, though. The recurrence yi = yi−1 + xi has the same structure at first glance. But because addition is associative, the parentheses can be rearranged and the computation can be done in parallel in a tree shape. This idea is treated in detail in the section on prefix sums. Whether a chain can be parallelized depends on the algebraic properties of the operation in the chain.
Assuming every loop can be parallelized. In the loop for (i = 1; i < n; i++) x[i] = x[i - 1] * x[i - 1] + 1;, every iteration reads the value written by the previous one. If the iterations of the loop are distributed to different threads, a thread reads a value not yet computed and the result is wrong. Before parallelizing, check whether there are data dependencies between iterations.
9.1.4Application areas
The problems where parallelism pays off share one feature: most of the work can be split into small pieces independent of one another. Four typical examples follow:
- Matrix multiplication. It is a basic operation of scientific computing. In the product C = A · B, each row of the result matrix, even each cell, can be computed independently of the others. At the end of these notes a Java solution is given that works with one task per row.
- Image processing. In operations such as edge detection, blurring, and object recognition, the same computation is done for each pixel or each block of pixels. This is the clearest example of data parallelism. Graphics processors contain thousands of small cores for exactly this kind of work.
- Computational fluid dynamics. In designing aircraft, ships, or cars, the flow of air and water is simulated. The flow field is divided into a grid and each region is given to a processor. At each time step the processors share boundary values only with neighboring regions.
- Genetic algorithms. The fitness values of the individuals in a population are independent of one another and can be computed at the same time. In problems such as scheduling and route finding, this evaluation is the most expensive part of the job.
9.2Models of parallel computation
To design and analyze a parallel algorithm, we must first decide what kind of machine it will run on. For sequential algorithms this question is rarely asked. Every computer works more or less the same way: a processor executes instructions in order and accesses memory. Parallel machines, however, differ greatly from one another. What varies is whether the processors run the same instruction or different ones, whether they share memory, and how they communicate. This section describes two viewpoints that classify parallel machines, and the PRAM model used in theoretical analysis.
9.2.1Flynn's classification
In 1966 Michael Flynn classified computers by two questions. The first question is how many instruction streams are executed at the same time. The second is how many data streams are processed at the same time. Because the answer to each question can be "single" or "multiple", four classes arise. Table 9.1 summarizes these classes. The class names are formed from initials: S stands for single, M for multiple, I for instruction, and D for data.
| Class | Expansion | Meaning | Example |
|---|---|---|---|
| SISD | Single Instruction, Single Data | one instruction stream, one data stream | classic single-core processor |
| SIMD | Single Instruction, Multiple Data | the same instruction on many data items at once | vector instructions (AVX), GPU |
| MISD | Multiple Instruction, Single Data | different instructions on the same data | rare; fault-tolerant systems |
| MIMD | Multiple Instruction, Multiple Data | each processor runs its own program on its own data | multicore CPU, clusters |
SISD is the classic machine assumed by sequential algorithms. In every clock step a single instruction is executed on a single data item.
A SIMD machine has a single control unit, but this unit applies the same instruction to many data items at the same time. The vector instructions of modern processors are of this kind. For example, an addition instruction in the AVX instruction set adds eight 32-bit floating-point numbers to eight other numbers in a single step. Graphics processors apply the same idea on a much larger scale. SIMD is very effective for jobs where the same operation is applied to every element of an array. In branching code, where different elements follow different paths, its efficiency drops.
MISD is rare in practice. The same data is processed with different instructions. In fault-tolerant systems such as aircraft control systems, the same input is computed independently on several separate units and the results are compared. This arrangement is given as an example of the MISD class.
MIMD is the most general class. Each processor runs its own program on its own data, independently of the others. Multicore personal computers and clusters, in which many computers are connected by a network, are MIMD machines.
Flynn's classification also helps to tell the two forms of parallelism apart. In data parallelism the same operation is applied to different parts of the data at the same time; this is the SIMD style. In task parallelism, different tasks are executed at the same time; this is the MIMD style. A web server preparing different pages for different clients at the same time is task parallelism. Raising the brightness of all the pixels of an image by the same ratio is data parallelism.
9.2.2Memory architectures
MIMD machines are divided into two by the way they organize memory. Figure 9.2 shows the two layouts side by side.
In the shared memory layout all processors see the same address space. A value one processor writes to memory can be read directly by another processor. Communication is therefore cheap: instead of moving data, it is enough to use a common variable. The price is controlling concurrent access. If two processors try to change the same variable at the same time, the result can be corrupted; accesses must therefore be ordered with a synchronization mechanism. Java threads and the ForkJoinPool class, and OpenMP for C and Fortran, are tools for this layout. The cores of a single computer work with shared memory.
In the distributed memory layout each node has its own memory. A node cannot directly access another node's memory. If data is needed, its owner sends it over the network as a message. This layout scales very well: thousands of nodes can solve the same problem. But communication is expensive. Sending a message over the network can take hundreds of times longer than reading from local memory. Programs written for this layout try to minimize the number of messages. The MPI (Message Passing Interface) library, widely used in scientific computing, and Hadoop MapReduce are distributed memory tools.
In these notes the Java examples run on shared memory. The pipeline and pipelined tree examples, however, assume a distributed layout in which processors exchange messages only with their neighbors. MapReduce too was originally designed for distributed memory; the Java example here shows the same idea on a single machine.
9.2.3The PRAM model
When analyzing sequential algorithms, a simplified model is used instead of a real computer: the RAM (Random Access Machine) model. In this model every basic operation and every memory access takes one unit of time. Details such as caches, virtual memory, and pipelining are ignored. The model does not reflect reality exactly, but it is accurate enough for comparing algorithms. A similar model is needed for parallel algorithms.
The PRAM (Parallel Random Access Machine) is the parallel counterpart of the RAM model. It consists of p processors, a shared memory, and a shared clock. The processors step in lockstep. In each step every processor reads from memory, does a local computation, and writes to memory. A step takes O(1) time. The cost of communication and synchronization is ignored.
The model's strongest assumption is that communication is free. On a real machine it takes time for two processors to share a value; in the PRAM, a value written by one processor can be read by all processors in the next step. The processors working with a shared clock also makes synchronization free. When a round ends, it is certain that all processors have finished that round. These assumptions are not realistic, but they serve a purpose. By setting aside communication and hardware details, the model measures an algorithm's inherent parallelism. If an algorithm cannot run in parallel even on a PRAM, it cannot run in parallel on a real machine. An algorithm that runs fast on a PRAM slows down on a real machine by an amount that depends on the communication cost.
There is one more problem with shared memory: what happens if several processors access the same memory cell in the same step? The PRAM variants are named by the answer given to this question. Table 9.2 shows three common variants.
| Variant | Read | Write |
|---|---|---|
| EREW | exclusive | exclusive |
| CREW | concurrent | exclusive |
| CRCW | concurrent | concurrent |
Exclusive access means that only a single processor can access the same cell in one step. In concurrent access, several processors can access the same cell in the same step. EREW is the most restrictive variant and CRCW the most powerful. Concurrent reading is harmless: everyone reads the same value. Concurrent writing, however, requires a rule. If three processors try to write 5, 7, and 9 to the same cell, which value remains in the cell? The common rules are these:
- Common rule: A write is valid only if all processors write the same value.
- Arbitrary rule: One of the processors is chosen at random and its value is written.
- Priority rule: The value of the processor with the smallest number (highest priority) is written.
If an algorithm works on EREW, it also works on CREW and CRCW, because the stronger model allows every operation of the weaker one. The converse is not always true. So when stating which model an algorithm works on, the weakest possible model is chosen. The tree summation and prefix sum algorithms examined in these notes manage with EREW.
In a PRAM algorithm, each of n processors wants to read a single threshold value in shared memory and compare it with its own element. In which model is this done in one step?
All processors read the same cell in the same step; this is concurrent reading. There is no writing. CREW suffices, and the operation finishes in one step. On EREW, however, only one processor can read the same cell in one step. The value must first be replicated by copying. In the first step one processor copies it, giving 2 copies; in the second step 2 processors copy it, giving 4 copies. The number of copies doubles every step. n copies are reached in ⌈log2 n⌉ steps. This example shows that the choice of model can change the time.
9.3Performance measures
Whether a parallel algorithm is good cannot be stated with a single number. An algorithm may be fast but use too many processors to be so. It may be fast with many processors, but its gain may stall as the number of processors grows. This section introduces the measures used to compare parallel algorithms.
9.3.1Speedup, efficiency, cost
All the measures rest on two times. T1 is the time of the best sequential algorithm that solves the problem on a single processor. Tp is the time of the parallel algorithm on p processors. Table 9.3 gives the three measures derived from these two times.
| Measure | Definition |
|---|---|
| T1 | time of the best sequential algorithm |
| Tp | parallel time on p processors |
| Speedup | S = T1 / Tp (ideal: S = p) |
| Efficiency | E = S / p (0 < E ≤ 1) |
| Cost | C = p · Tp |
Speedup is the ratio of the sequential time to the parallel time: S = T1 / Tp. Efficiency is the speedup per processor: E = S / p. Cost is the total time spent by all processors: C = p · Tp. A parallel algorithm whose cost is of the same order as the best sequential time, that is, with C = Θ(T1), is called cost-optimal.
Speedup tells how many times adding processors shortens the job. With p processors, a speedup of p is expected at best; this is called linear speedup. Efficiency shows how much of the processors' time goes to useful work. If E = 1, no processor has wasted any time. If E = 0.5, half of the processor time has gone to waiting, communication, or unnecessary work.
Cost measures how many "processor-seconds" in total the parallel algorithm consumes. The sequential algorithm spends T1 processor-seconds. The parallel algorithm cannot spend less than that; if it did, running the steps of the parallel algorithm in order on a single processor would give a sequential algorithm shorter than T1. That contradicts T1 being the best sequential time. So always C ≥ T1, hence S ≤ p and E ≤ 1. These bounds hold in the model; in reality cache effects or early finding in search can give S > p (superlinear speedup). When the data is split into pieces, each piece may fit in the cache; a parallel search may also find the target much earlier than in the sequential search order. A cost-optimal algorithm distributes the work done by the sequential algorithm among the processors, increasing it by at most a constant factor.
A job takes T1 = 100 s with the best sequential algorithm. The parallel algorithm takes T8 = 16 s on p = 8 processors. The three measures are computed as follows:
- Speedup: S = 100 / 16 = 6.25. The job got 6.25 times shorter; the ideal value would have been 8.
- Efficiency: E = 6.25 / 8 ≈ 0.78. About 78% of the processor time went to useful work.
- Cost: C = 8 · 16 = 128 s. The sequential algorithm spent 100 s; 28 processor-seconds went to overhead.
Figure 9.4 shows the source of this overhead. When the 100 s job is split eight ways, each processor gets 12.5 s. Since each processor works for 16 s, it spent 3.5 s on communication, waiting, or combining. The total loss of the eight processors is 8 · 3.5 = 28 s; the difference between cost and sequential time is exactly this much.
There are four common reasons why speedup falls below p. The first is communication: processors do no computing while they exchange data. The second is waiting: a processor is idle while it waits for another processor's result. The third is load imbalance: processors that finish early wait for the slowest one. The fourth is sequential parts: the part of the program that cannot be parallelized always takes the same time regardless of the number of processors. The effect of the last cause is computed with Amdahl's law.
Computing speedup relative to the parallel algorithm's own time on a single processor. A parallel algorithm often does more work than the sequential algorithm. For example, Hillis–Steele prefix sums run on a single processor are slower than a sequential scan. If speedup is computed by dividing by this slow time, it looks better than it is. T1 is always the time of the best sequential algorithm.
9.3.2Amdahl's law and Gustafson's law
Almost every real program has a part that cannot be parallelized. Reading input from disk, loading settings, and merging partial results into a single output are jobs of this kind. In 1967 Gene Amdahl showed with a simple calculation the limit that this sequential part places on speedup.
Let the program's time on a single processor be T1. A fraction f of this time can be parallelized and a fraction 1 − f is sequential. On p processors the sequential part still takes (1 − f) T1. The parallel part, at best, divides exactly by p and takes f T1 / p. The total parallel time is
Tp = (1 − f) T1 + f T1 / p
Since speedup is T1 / Tp, T1 cancels and the following result is obtained.
If a fraction f of a program can be parallelized and a fraction 1 − f is sequential, the speedup attainable on p processors is at most
S(p) = 1 / ((1 − f) + f / p)
As p → ∞, S(p) → 1 / (1 − f).
The real message of the law is in the limit. However many processors are added, the term f / p approaches zero but the term 1 − f stays where it is. The sequential part limits the speedup. If 10% of the program is sequential (f = 0.9), speedup cannot exceed 10 even with infinitely many processors. If 5% is sequential, the limit is 20.
90% of a program can be parallelized: f = 0.9. What is the speedup on eight processors?
- Sequential part: 1 − f = 0.1.
- Share of the parallel part: f / p = 0.9 / 8 = 0.1125.
- Speedup: S = 1 / (0.1 + 0.1125) = 1 / 0.2125 ≈ 4.71.
- Upper limit: 1 / 0.1 = 10.
Eight processors give a speedup of about 4.7, not 8. Efficiency is 4.71 / 8 ≈ 0.59. Even though only 10% of the program is sequential, on eight processors the sequential part takes about half of the time: 0.1 / 0.2125 ≈ 0.47. As the parallel part speeds up, the share of the sequential part in the total time grows.
The curves in Figure 9.5 show this effect. The f = 0.9 curve reaches about 3.1 at 4 processors, 6.4 at 16, and 8.8 at 64. At 1024 processors it is only 9.9. Going from 64 to 1024 multiplies the number of processors by 16 but increases speedup by only 13%. Before moving a program to many processors, it is therefore more profitable to shrink its sequential part. Reducing the sequential part from 10% to 1% raises the speedup on 1000 processors from about 10 to 91.
Amdahl's law rests on an assumption: the problem size is fixed and only the number of processors grows. In practice this is often not the case. A researcher who finds more processors solves a larger problem instead of solving the same problem faster. The weather forecast is made on a finer grid, and the simulation is run with more particles. In this case the sequential part mostly stays the same, but the parallel part grows with the number of processors.
In 1988 John Gustafson put this viewpoint into a formula. Let the time of the parallel run be 1 unit. A fraction 1 − f of it is sequential and a fraction f is parallel. If the same job were done on a single processor, the sequential part would still take 1 − f. The parallel part would have to do alone the work of p processors and would take f · p. The scaled speedup is
S = (1 − f) + f · p
This is called Gustafson's law. For f = 0.9 and p = 8 we get S = 0.1 + 7.2 = 7.3. With the same values Amdahl's law gave 4.71. The two laws do not contradict each other; they answer different questions. Amdahl's law answers "how many times faster do I solve the same problem?", and Gustafson's law answers "how many times larger a problem do I solve in the same time?" According to Gustafson's law, parallelism pays off more on large problems, because the share of the sequential part in the total work shrinks.
Forgetting the sequential part in an Amdahl calculation. For f = 0.9 and p = 8 one cannot say "the parallel part speeds up 8 times, so the program speeds up about 8 times". In the correct calculation the sequential 10% stays as it is and the speedup is 4.71. If 10% of the program is sequential, speedup is bounded by 10 even at best.
9.3.3Work, depth, and Brent's theorem
Speedup and efficiency are computed for a particular number of processors. To describe an algorithm's parallelism independently of the number of processors, two quantities are used: work and depth. Both rest on viewing the algorithm's operations as a dependency graph. Each node of the graph is a basic operation. An edge u → v shows that operation v uses the result of u, that is, it cannot start before u finishes. There can be no cycles, because an operation cannot wait for its own result.
Work W is the number of all operations the algorithm performs; it equals the number of nodes in the dependency graph and gives the time on a single processor: W = T1. Depth (or span) D is the length of the longest dependency chain in the graph; it gives the time with unlimited processors: D = T∞. The ratio W / D is called the algorithm's parallelism.
The graph in Figure 9.6 has seven operations; a single processor finishes them in seven steps. Even with unlimited processors, the four operations on the red path wait for one another and cannot finish before four steps. Depth is a limit that cannot be beaten by adding processors. The parallelism is 7 / 4 = 1.75: on average 1.75 operations can be done at the same time in each step. More than two processors bring almost no benefit to this graph.
Parallelism is interpreted as the maximum number of processors that can be used profitably. If the number of processors exceeds the parallelism, some processors sit idle in most steps. The two basic lower bounds are as follows:
- Tp ≥ W / p: p processors do at most p operations in a step; W operations need at least W / p steps.
- Tp ≥ D: the operations in the longest chain wait for one another; the number of processors does not change this.
There is also an upper bound, widely used in the analysis of parallel algorithms.
A computation with work W and depth D can be executed on p processors in Tp ≤ W / p + D steps.
Divide the operations into levels. Level i contains the operations whose longest chain of predecessors has length i − 1. Operations on the same level do not wait for one another; if there were an edge between them, one would be deeper than the other. The number of levels is D. If level i has Wi operations, p processors finish this level in ⌈Wi / p⌉ ≤ Wi / p + 1 steps. The levels are executed in order. The sum over all levels is Σ (Wi / p + 1) = W / p + D. ∎
Reading the lower and upper bounds together gives max(W / p, D) ≤ Tp ≤ W / p + D. The upper bound is at most twice the lower bound. So once W and D are known, the time for any number of processors can be estimated to within a factor of two. If p is much smaller than the parallelism, the term W / p dominates and the speedup is almost linear. If p is larger than the parallelism, the term D dominates and new processors do not shorten the time.
A parallel algorithm whose work is of the same order as the time of the best sequential algorithm for the same problem is called work-efficient. An algorithm that is not work-efficient can be even slower than the sequential algorithm when processors are few. The section on prefix sums gives a concrete example of this.
n = 1024 numbers are summed with a balanced binary tree. In the first round the numbers are added in pairs, in the second round these sums are added in pairs, and so on. What are the work, the depth, and the time on 32 processors?
- Each addition reduces two values to one. To reduce 1024 values to one, W = n − 1 = 1023 additions are needed.
- In each round the number of values halves: 1024, 512, …, 1. The number of rounds is D = log2 1024 = 10.
- Parallelism: 1023 / 10 ≈ 102. Extra processors help up to about a hundred processors.
- Brent: T32 ≤ 1023 / 32 + 10 ≈ 31.97 + 10 ≈ 42 steps.
- Lower bound: T32 ≥ max(1023 / 32, 10) ≈ 32 steps.
With 32 processors the time lies between 32 and 42 steps. The sequential algorithm takes 1023 steps; the speedup lies between 24 and 32.
9.4Summation on a PRAM
The simplest and most instructive example of a parallel algorithm is the sum of n numbers. The problem is very simple, but the parallel solution contains an idea that will recur throughout the rest of these notes: a chain built with an associative operation can be turned into a balanced tree.
9.4.1The problem and associative operations
The input is n numbers; the output is their sum. The sequential algorithm starts a sum variable at zero and adds each number to it. It does n − 1 additions and takes O(n). The dependency graph of this sequential loop is a chain: each addition waits for the result of the previous one. The chain has length n − 1; depth equals work, and there is no parallelism.
What breaks the chain is that addition is associative: (a + b) + c = a + (b + c). With an associative operation the parentheses can be placed as desired. The sum of eight numbers is computed in the sequential loop as
((((((2 + 3) + 5) + 1) + 7) + 6) + 8) + 4
The same sum can also be written as follows:
((2 + 3) + (5 + 1)) + ((7 + 6) + (8 + 4))
The second form is a balanced binary tree. The four innermost additions are independent of one another and can be done at the same time. The two additions that use their results are also independent of each other. The outermost addition is done last. The additions at each level of the tree are done in parallel in the same round. Figure 9.7 shows this tree.
The same idea works for every associative operation: maximum, minimum, product, logical AND, logical OR. This general operation, which reduces an array to a single value with an associative operation, is called a reduction. If Math.max is used in the summation tree instead of addition, the largest element is found in the same rounds.
Reducing a non-associative operation with a tree. Subtraction is not associative: (8 − 4) − 2 = 2 but 8 − (4 − 2) = 6. Because the tree order uses a different parenthesization from the sequential order, the result changes. Although addition of real numbers is associative, floating-point addition on a computer is not exactly associative because of rounding. A parallel sum can differ from the sequential sum in the last digits.
9.4.2Tree summation step by step
The example sequence is 2, 3, 5, 1, 7, 6, 8, 4; its sum is 36. Eight processors p0 … p7 each hold one number. The algorithm proceeds in rounds:
- Start. The eight numbers are distributed to the eight processors, one each.
- Round 1. Four processors add neighboring pairs at the same time: 2 + 3 = 5, 5 + 1 = 6, 7 + 6 = 13, 8 + 4 = 12. The results stay in the processor on the left of each pair (p0, p2, p4, p6).
- Round 2. Two processors combine partial sums at distance 2 from each other: 5 + 6 = 11 at p0 and 13 + 12 = 25 at p4.
- Round 3. p0 finds the result 11 + 25 = 36.
Eight numbers were summed in log2 8 = 3 rounds. The sequential algorithm would have taken 7 steps. The number of additions, however, did not change: 4 + 2 + 1 = 7. The parallel algorithm did no extra work; it only changed the order. For this reason tree summation is work-efficient.
One more thing about the rounds is worth noting. In round 1 four processors work, in round 2 two, and in round 3 one. The other processors sit idle. In no round do all eight processors work; even for the first round four processors are enough. This observation will matter in the cost analysis.
9.4.3Code trace
Tree summation is written in Java as follows. The code is a sequential program, but the iterations of the inner loop are independent within the same round and are executed in parallel on a PRAM. Each iteration of the outer loop is one round.
int[] a = {2, 3, 5, 1, 7, 6, 8, 4};
int n = a.length;
for (int step = 1; step < n; step *= 2) {
// all i in the same round run in parallel
for (int i = 0; i + step < n; i += 2 * step)
a[i] = a[i] + a[i + step];
} // end of round: synchronization
// the total is in a[0]The parts of the code work as follows:
stepis the distance between the two cells added in a round. It starts at 1 and doubles each round: 1, 2, 4. The loop ends whenstepis at leastn.- In the inner loop
iruns over the multiples of2 * step. These are the cells that work in the round: 0, 2, 4, 6 in round 1; 0, 4 in round 2; only 0 in round 3. a[i] = a[i] + a[i + step]adds the partial sum on the right to the one on the left. After each round,a[i]holds the sum of the block of length2 * stepstarting ati.- The condition
i + step < nprevents a cell without a partner from reading outside the array. If n is not a power of two, some cells are left unpaired for a round and pass to the next round without waiting. - The comment at the end of the round is a reminder of synchronization. The next round must start only after all the writes of the previous round have finished.
The writes in the same round go to separate cells. The cells read also differ from round to round: in round 1, a[1], a[3], a[5], a[7] are read and are not written. No cell is accessed by two processors in the same round. An EREW PRAM is therefore enough. Table 9.4 is a trace of the code; the values were verified by running the program.
| Round | step | Parallel additions | a after the round |
|---|---|---|---|
| — | — | initial | [2, 3, 5, 1, 7, 6, 8, 4] |
| 1 | 1 | a[0] = 2 + 3 = 5; a[2] = 5 + 1 = 6; a[4] = 7 + 6 = 13; a[6] = 8 + 4 = 12 | [5, 3, 6, 1, 13, 6, 12, 4] |
| 2 | 2 | a[0] = 5 + 6 = 11; a[4] = 13 + 12 = 25 | [11, 3, 6, 1, 25, 6, 12, 4] |
| 3 | 4 | a[0] = 11 + 25 = 36 | [36, 3, 6, 1, 25, 6, 12, 4] |
| — | 8 | step = 8, loop ends | total a[0] = 36 |
a[0]; intermediate sums remain in the other cells.Intermediate sums such as a[4] = 25 and a[2] = 6 remain in the final array. The algorithm destroys the array; only a[0] is meaningful. If the original array is needed, the algorithm should be run on a copy.
How does the code work when n is not a power of two? For a = {3, 1, 4, 1, 5} (n = 5) the trace is as follows:
step= 1: fori= 0,a[0]= 3 + 1 = 4; fori= 2,a[2]= 4 + 1 = 5. Ati= 4, 4 + 1 < 5 fails;a[4]= 5 is left unpaired. The array is [4, 1, 5, 1, 5].step= 2: fori= 0,a[0]= 4 + 5 = 9. Ati= 4, 4 + 2 < 5 fails. The array is [9, 1, 5, 1, 5].step= 4: fori= 0, 0 + 4 < 5 holds;a[0]= 9 + 5 = 14.step= 8: the loop ends.a[0]= 14 = 3 + 1 + 4 + 1 + 5.
The number of rounds is ⌈log2 5⌉ = 3 and the number of additions is n − 1 = 4. The unpaired a[4] joins the addition in the last round after waiting two rounds.
9.4.4Analysis and the cost-optimal version
The time of tree summation is the number of rounds: ⌈log2 n⌉. Its work is n − 1 additions, the same as the sequential algorithm. The number of processors must equal the number of additions in the first round, that is, n / 2. For convenience in the analysis, n processors are often written; the order of magnitude does not change. The cost, however, is not good: (n / 2) · log2 n = Θ(n log n). Since the best sequential time is Θ(n), the algorithm is not cost-optimal.
The reason for the high cost was visible in the rounds. Half of the processors are idle after round 1, and three quarters after round 2. Idle processors also count toward the cost, because cost multiplies the number of processors by the whole time.
The solution is to reduce the number of processors and give each processor more work. Let p = n / log2 n processors be used. The algorithm consists of two phases:
- Local sum. The array is divided into p blocks; each block has log2 n numbers. Each processor sums its own block sequentially. This phase takes O(log n).
- Combining with a tree. The p = n / log2 n partial sums are combined by tree summation. This phase takes ⌈log2 p⌉ ≤ log2 n rounds, that is, O(log n).
The total time is still O(log n). The cost, however, becomes (n / log n) · O(log n) = Θ(n). The algorithm is now cost-optimal. Table 9.5 compares the two versions.
| Measure | n processors (n / 2 suffice) | p = n / log2 n processors |
|---|---|---|
| Time Tp | log2 n | O(log n) |
| Work W | n − 1 | n − 1 |
| Cost p · Tp | Θ(n log n) | Θ(n) |
| Cost-optimal? | no | yes |
This technique is a concrete application of Brent's theorem. In tree summation W = n − 1 and D = log2 n. For p = n / log2 n, Brent's upper bound gives W / p + D ≈ log2 n + log2 n = 2 log2 n. The time only doubles, while the number of processors falls by a factor of log2 n. For example, for n = 1024 the number of processors drops from 1024 to about 102.
For the algorithm to work correctly, a barrier is needed at the end of each round. A barrier is a coordination point that no processor can pass until all processors have reached it. Because the PRAM works with a shared clock, it provides the barrier for free. On a real machine each barrier has a cost; for this reason a small number of rounds matters on a real machine too.
Forgetting the synchronization between rounds. In a tree summation written with real threads, if the thread doing round 2 reads a[2] before all the writes of round 1 have finished, it reads the old value (5). a[0] is then computed as 5 + 5 = 10 instead of 5 + 6, and the result is wrong. Because the bug depends on timing, it may not show up on every run.
9.5Parallel prefix sums
Tree summation produces only a single result: the sum of the array. In many problems, however, a separate sum is needed for every position. The balance of a bank account after each transaction, the cumulative values of a histogram, and the position at which each item is placed in counting sort are of this kind. This section describes two parallel algorithms that compute all these values at the same time.
9.5.1The problem
The inclusive prefix sum (or scan) of the sequence x0, x1, …, xn−1 is the sequence of the values yi = x0 + x1 + … + xi for every i. In the exclusive prefix sum, position i does not include xi: y0 = 0 and yi = x0 + … + xi−1.
The inclusive prefix sum of the sequence 2 3 5 1 7 6 8 4 is 2 5 10 11 18 24 32 36. The exclusive prefix sum is the same shifted one position to the right: 0 2 5 10 11 18 24 32. One is easily obtained from the other. To go from inclusive to exclusive, subtract each position's own element; in the reverse direction, add it.
The sequential algorithm is a single loop: yi = yi−1 + xi. It does n − 1 additions and takes O(n). But it is entirely a chain: each step waits for the result of the previous one. At first sight a parallel solution looks impossible, because y7 depends on y6, and y6 on y5.
Tree summation showed the way to break this chain. In tree summation too, every intermediate sum is the sum of a block. The difference is this: tree summation stops only at the last cell, that is, at the sum of the whole array. In prefix sums, every cell has to learn its own prefix. The intermediate sums in the tree are parts of this information; what remains is to distribute them correctly.
9.5.2The Hillis–Steele algorithm
The algorithm published by W. Daniel Hillis and Guy Steele in 1986 rests on a very simple rule. For d = 1, 2, 4, …, in each round every position i ≥ d adds to its own value the value d positions to its left:
x[i] ← x[i] + x[i − d] (for every i ≥ d, in parallel in the same round)
All reads in a round must see the values from before that round's writes. On a PRAM all processors first read and then write; this condition is satisfied automatically. In a sequential simulation, a copy of the old array is kept in each round and the reads are done from the copy.
Why the algorithm is correct can be seen with an invariant. When round d is finished, every x[i] holds the sum of the window ending at i that contains at most 2d elements. At the start (before round d = 1) every cell holds only itself, that is, a window of 1 element. In round d, x[i − d] is added to x[i]. Before the round, x[i] holds the range i − d + 1 … i and x[i − d] holds the range i − 2d + 1 … i − d. The two ranges are adjacent and their sum gives the range i − 2d + 1 … i. When the window reaches the start of the array, it is cut off. After ⌈log2 n⌉ rounds the window length exceeds n and every cell holds its entire prefix.
Table 9.6 gives the result of each round for the example sequence. The values were verified with a Java program, using a simulation with copies.
| Round | Operation | Additions | x after the round | Window |
|---|---|---|---|---|
| initial | — | — | 2 3 5 1 7 6 8 4 | 1 |
| d = 1 | i ≥ 1: x[i] += x[i − 1] | 7 | 2 5 8 6 8 13 14 12 | 2 |
| d = 2 | i ≥ 2: x[i] += x[i − 2] | 6 | 2 5 10 11 16 19 22 25 | 4 |
| d = 4 | i ≥ 4: x[i] += x[i − 4] | 4 | 2 5 10 11 18 24 32 36 | 8 |
Let us check one row of the table explicitly. At the end of round d = 2, x[5] = 19. This value is the sum of the 4-element window ending at 5: x2 + x3 + x4 + x5 = 5 + 1 + 7 + 6 = 19. The computation went as follows: before the round, x[5] = 13 (6 + 7) and x[3] = 6 (1 + 5); 13 + 6 = 19.
The algorithm finished in log2 8 = 3 rounds. The depth is D = ⌈log2 n⌉. But the number of additions is 7 + 6 + 4 = 17; the sequential algorithm does 7 additions. In general, round d does n − d additions. If n is a power of two, the total work is
W = Σd = 1, 2, 4, …, n/2 (n − d) = n log2 n − (n − 1)
For n = 8 this is 24 − 7 = 17. The work is Θ(n log n), more than the Θ(n) work of the sequential algorithm. Hillis–Steele is not work-efficient. If processors are plentiful this does not matter, because the extra operations are done for free in the same round. If processors are few, the extra work adds directly to the time. For example, on a single processor Hillis–Steele takes n log n, while the sequential scan takes n.
Forgetting the copy at the start of the round in a sequential simulation. If the computation is done on the same array with i in increasing order, x[i − d] may already have been updated in this round. On the sequence 2 3 5 1, if the round d = 1 is done without a copy, x[1] = 5, then x[2] = 5 + 5 = 10, then x[3] = 1 + 10 = 11. The full prefix sum comes out in a single round; the next round adds to these values again and the result is corrupted: after round d = 2 one gets 2 5 12 16. The correct answer is 2 5 10 11. In real parallel code this error corresponds to forgetting the barrier between rounds.
9.5.3The Blelloch algorithm
The algorithm popularized by Guy Blelloch in 1990 computes prefix sums with O(n) work and O(log n) depth. It uses the array like an implicit binary tree and works in two phases. The up-sweep phase is the same as tree summation: partial sums are built from the leaves toward the root. The down-sweep phase descends from the root toward the leaves and carries to each node "the sum of all the elements to its left".
// up-sweep; x = 2 3 5 1 7 6 8 4
for (int d = 1; d < n; d *= 2)
for (int i = 2*d - 1; i < n; i += 2*d)
x[i] += x[i - d];
x[n - 1] = 0;
// down-sweep (inner loops in parallel)
for (int d = n / 2; d >= 1; d /= 2)
for (int i = 2*d - 1; i < n; i += 2*d) {
int t = x[i - d];
x[i - d] = x[i];
x[i] += t;
}
// x: exclusive prefix sumsThe parts of the code work as follows:
- Up-sweep. For d = 1, 2, 4,
x[i] += x[i - d]is done in the cells i = 2d − 1, 4d − 1, …. Its only difference from tree summation is that the sums are written to the right end of the block, its last cell, rather than to its left. At the end of the phasex[n - 1]holds the sum of the whole array. - The root is zeroed.
x[n - 1] = 0. There are no elements to the left of the root; the sum of those to its left is 0. - Down-sweep. For d = n/2, …, 2, 1, three lines run on each pair (i − d, i).
tstores the left child's old value, that is, the sum of the left subtree. The left child takes the parent's value: the elements to the left of the left subtree are the same as those to the left of the parent. The right child adds the sum of the left subtree to the parent's value: to the left of the right subtree there is, in addition to what is to the left of the parent, the left subtree. - The pairs in a round touch disjoint cells; the inner loop runs in parallel and EREW suffices.
Table 9.7 gives all the rounds of both phases for the example sequence. The values were verified by running the code.
| Phase | d | Parallel operations | x after the round |
|---|---|---|---|
| input | — | — | 2 3 5 1 7 6 8 4 |
| up | 1 | x[1] += x[0], x[3] += x[2], x[5] += x[4], x[7] += x[6] | 2 5 5 6 7 13 8 12 |
| up | 2 | x[3] += x[1], x[7] += x[5] | 2 5 5 11 7 13 8 25 |
| up | 4 | x[7] += x[3] | 2 5 5 11 7 13 8 36 |
| root | — | x[7] = 0 | 2 5 5 11 7 13 8 0 |
| down | 4 | pair (3, 7): x[3] = 0, x[7] = 0 + 11 | 2 5 5 0 7 13 8 11 |
| down | 2 | pair (1, 3): x[1] = 0, x[3] = 0 + 5; pair (5, 7): x[5] = 11, x[7] = 11 + 13 | 2 0 5 5 7 11 8 24 |
| down | 1 | pairs (0, 1), (2, 3), (4, 5), (6, 7) | 0 2 5 10 11 18 24 32 |
Let us unfold the last round one pair at a time. Pair (0, 1): t = x[0] = 2; x[0] = x[1] = 0; x[1] = 0 + 2 = 2. Pair (2, 3): t = 5; x[2] = 5; x[3] = 5 + 5 = 10. Pair (4, 5): t = 7; x[4] = 11; x[5] = 11 + 7 = 18. Pair (6, 7): t = 8; x[6] = 24; x[7] = 24 + 8 = 32. The result is 0 2 5 10 11 18 24 32; this is the exclusive prefix sum. If the inclusive result is needed, each cell's own input value is added, or the array is shifted one position to the left and the total (36) is written at the end.
The algorithm's cost is counted as follows. The up-sweep is the same as tree summation: n − 1 additions, log2 n rounds. In the down-sweep one operation is done for each internal node: again n − 1 operations, log2 n rounds. The total work is 2(n − 1); in the example, 14 operations. The depth is 2 log2 n; in the example, 6 rounds. Because the work is O(n), the Blelloch algorithm is work-efficient. It uses twice as many rounds as Hillis–Steele but its total work is smaller by a factor of log n.
At the end of the down-sweep x[5] = 18 came out. Where does this value come from?
- Cell 5 is the right child of the pair (4, 5) in the implicit tree. The parent of this pair is the left cell 5 of the pair (5, 7); its parent is in turn the right cell 7 of the pair (3, 7).
- In the first round of the down-sweep (d = 4), x[7] = 11: the sum of the elements to the left of the right half, 2 + 3 + 5 + 1 = 11.
- In round d = 2, the left child of the pair (5, 7) takes the parent's value: x[5] = 11. To the left of cells 4 and 5 there are again the first four elements.
- In round d = 1, the right child of the pair (4, 5) becomes x[5] = 11 + t. t is the left child's value left over from the up-sweep: x[4] = 7. The result is 11 + 7 = 18.
18 is indeed the sum of the five elements to the left of cell 5: 2 + 3 + 5 + 1 + 7 = 18.
9.5.4Comparing the two algorithms
| Algorithm | Work W | Depth D | Result |
|---|---|---|---|
| Sequential scan | n − 1 (7) | n − 1 (7) | inclusive |
| Hillis–Steele | n log2 n − (n − 1) (17) | log2 n (3) | inclusive |
| Blelloch | 2(n − 1) (14) | 2 log2 n (6) | exclusive |
Which algorithm to choose depends on the number of processors. If the number of processors is on the order of n, for example inside a block on a GPU, Hillis–Steele's few rounds are an advantage. If the number of processors is much smaller than n, Blelloch's small amount of work is decisive. By Brent's theorem, on p processors Hillis–Steele takes O(n log n / p + log n) and Blelloch O(n / p + log n).
Prefix sum is one of the most widely used building blocks of parallel algorithms. In parallel counting sort, the position of each key in the output is found with a prefix sum. To select and compact the elements of an array that satisfy a condition (filter), write 1 for each element that satisfies it and 0 for each that does not. The exclusive prefix sum of this 0/1 array gives the position of each selected element in the new array. In Java, the method Arrays.parallelPrefix(array, Integer::sum) modifies an array in place into its inclusive prefix sums. For the example array it gives 2 5 10 11 18 24 32 36.
Looking only at depth. Hillis–Steele finishes in O(log n) rounds, and at first glance this looks better than Blelloch. But it does O(n log n) work. On a four-core machine, for an array of a million elements, Hillis–Steele does about 20 million additions, which is 5 million per core. The sequential scan does 1 million additions on a single core. With few processors, an algorithm that is not work-efficient can be slower than the sequential algorithm.
9.6The pipeline
The algorithms so far assumed that the processors share a common memory. In this section the processors are connected as a chain and exchange messages only with their neighbors. In such a layout an important source of parallelism is the pipeline.
9.6.1The pipeline idea
A pipeline is a layout in which a job is split into consecutive stages and each stage runs on a separate processor. While a job moves from one stage to the next, the earlier stage starts the next job; thus different jobs are processed overlapped in different stages.
An assembly line in a factory is a good analogy. When a car body moves from the welding section to the paint section, the welding section starts on the next body. The time for a single car to leave the line does not shrink; every body has to pass through all the stages. But the number of cars leaving the line per unit time, that is, the throughput, grows by a factor equal to the number of stages.
Let m jobs be done in a pipeline with k stages, each stage taking one time step. In sequential execution each job takes k steps and the jobs are done one after another: k · m steps. In the pipeline the first job finishes in k steps. Each following job finishes one step after the previous one. The total time is k + m − 1 steps.
Figure 9.12 shows the line for three stages and four jobs. At the start, while the line is filling (t₁ and t₂), and at the end, while it is emptying (t₅ and t₆), some stages are idle. The line is full only at times t₃ and t₄; at those times all three stages work. If the number of jobs is very large relative to the number of stages, the fill and drain time becomes negligible and the time approaches m.
9.6.2Row sums on a chain
A concrete problem shows the use of the pipeline in parallel algorithms. Five processors p0 … p4 form a linear chain. Each processor can send messages only to its right neighbor. Each pj holds a column of 4 values; the rows are numbered 0 to 3. Putting the processors' columns side by side gives a table of 4 rows and 5 columns.
The goal is this: for every row r, let the value at pj be the sum of the values of p0 … pj in that row. This is a separate prefix sum in each row. At the end p4 holds the sum of every row. In one step each processor can send one value to its right neighbor; the receiver adds it to its own value. The values of p0 are already the result, because there is no one to its left.
The naive method processes the rows one at a time. First row 0 is carried along the chain: p0 → p1, then p1 → p2, and so on. This takes 4 steps because it passes through four links. Then row 1, row 2, and row 3 are carried in turn. The total takes 4 · 4 = 16 steps. In each step only one of the four links is used.
The pipeline method streams the rows one behind another along the chain. pj sends row r at time t = r + j. One step after row 0 sets out, row 1 sets out; row 0 is by then one link ahead. The rows advance like a wave, and most of the links work at the same time.
9.6.3Step-by-step execution
In the example the processors' columns are as follows: p0 = (2, 1, 7, 4), p1 = (3, 7, 2, 9), p2 = (3, 4, 7, 3), p3 = (6, 1, 0, 2), p4 = (8, 6, 3, 5). Which link carries which row at each step is given in Table 9.9.
| Step | p0→p1 | p1→p2 | p2→p3 | p3→p4 |
|---|---|---|---|---|
| 1 | row 0: 2 + 3 = 5 | — | — | — |
| 2 | row 1: 1 + 7 = 8 | row 0: 5 + 3 = 8 | — | — |
| 3 | row 2: 7 + 2 = 9 | row 1: 8 + 4 = 12 | row 0: 8 + 6 = 14 | — |
| 4 | row 3: 4 + 9 = 13 | row 2: 9 + 7 = 16 | row 1: 12 + 1 = 13 | row 0: 14 + 8 = 22 |
| 5 | — | row 3: 13 + 3 = 16 | row 2: 16 + 0 = 16 | row 1: 13 + 6 = 19 |
| 6 | — | — | row 3: 16 + 2 = 18 | row 2: 16 + 3 = 19 |
| 7 | — | — | — | row 3: 18 + 5 = 23 |
The table shows a diagonal pattern. Row 0 sets out at step 1 and reaches p4 at step 4. Row 3 sets out at step 4 and arrives at step 7. At step 4 the line is full: all four links work. Before that the line is filling, and after it, emptying.
Let us verify the result for one row. The values of row 2 from left to right are 7, 2, 7, 0, 3. Their sum is 7 + 2 + 7 + 0 + 3 = 19. In the pipeline this row leaves p0 at step 3 (9), reaches p2 at step 4 (16), p3 at step 5 (16), and p4 at step 6 (19). The intermediate values are also correct: the 16 at p2 is the sum of the first three values of the row.
9.6.4Code trace and analysis
The pipeline's schedule is written as a short loop. x[j][r] is the value of pj in row r. Each iteration of the outer loop is a time step; the iterations of the inner loop run in parallel in the same step.
for (int t = 0; t < m + p - 2; t++)
// all j at the same time
for (int j = 0; j < p - 1; j++) {
int r = t - j;
if (r >= 0 && r < m)
x[j + 1][r] += x[j][r];
}tis the time step, starting from zero. The loop runs m + p − 2 times; in the example 4 + 5 − 2 = 7.jdenotes the link pj → pj+1; there are p − 1 links.r = t - jis the row this link carries at timet. pj sends row r at time t = r + j.- The condition
if (r >= 0 && r < m)filters out the cases where the row has not yet set out (r < 0, while the line is filling) or all rows have already passed (r ≥ m, while the line is emptying). x[j + 1][r] += x[j][r]adds the sent value to the receiver's value.
Two observations show that the schedule is correct. First, when pj sends row r, its value is ready. pj−1 updated this value one step earlier, at time t − 1 = r + j − 1. Second, operations in the same step do not conflict. At time t, link j reads x[j][r]. Link j − 1 writes to x[j][r + 1] in the same column. The cells read and written are different.
Table 9.10 gives the additions the code performs at each step and the column of p4. The values were verified by running the code; they are the same as in Table 9.9, only with time counted from zero.
t | Active j (r = t - j) | Number of additions | p4 column |
|---|---|---|---|
| 0 | 0 (r = 0) | 1 | 8, 6, 3, 5 |
| 1 | 0 (1), 1 (0) | 2 | 8, 6, 3, 5 |
| 2 | 0 (2), 1 (1), 2 (0) | 3 | 8, 6, 3, 5 |
| 3 | 0 (3), 1 (2), 2 (1), 3 (0) | 4 | 22, 6, 3, 5 |
| 4 | 1 (3), 2 (2), 3 (1) | 3 | 22, 19, 3, 5 |
| 5 | 2 (3), 3 (2) | 2 | 22, 19, 19, 5 |
| 6 | 3 (3) | 1 | 22, 19, 19, 23 |
The general formula for the number of steps is found as follows. The last row is r = m − 1 and the last link is j = p − 2. The last row passes the last link at time t = (m − 1) + (p − 2). Since time is counted from zero, the number of steps is
m + p − 2
In the example it is 4 + 5 − 2 = 7. The naive method sends each row separately across p − 1 links: m(p − 1) = 16 steps. This result agrees with the formula k + m − 1 from the pipeline idea: here the number of stages is k = p − 1 links.
Efficiency can also be computed. The useful work is the number of additions performed: each row passes each link once, m(p − 1) additions in total. The resource used is the p − 1 links being open for m + p − 2 steps. The efficiency is
E = m(p − 1) / ((p − 1)(m + p − 2)) = m / (m + p − 2)
In the example, 4 / 7 ≈ 0.57, about 57%. If the number of rows is much larger than the number of processors (m ≫ p), efficiency approaches 1. For example, for p = 5 and m = 1000 it is 1000 / 1003 ≈ 0.997. The pipeline is effective when many independent data items pass through the same stages.
Thinking the number of steps of a pipeline is m. The line is empty at the start and takes time to fill. The last row sets out only after m − 1 steps and needs p − 1 more steps to cross the chain. For m rows and p processors the correct number is m + p − 2. For p = 6, m = 50 this difference is 4 steps; for p = 100, m = 10 it is 98 steps and changes the result completely.
9.7The pipelined tree
The pipeline idea applies not only to chains but also to trees. In this section the processors are connected as a tree and each processor holds a vector. The goal is to sum the vectors component by component at the root.
9.7.1Reduction on a tree
Let the processors form a rooted tree. Each node can send its value to its parent; the parent adds the incoming value to its own. The leaves send their values, internal nodes add what comes from their children and pass it up, and finally the total accumulates at the root. This is the message-passing form of tree summation. If the depth of the tree is h, reducing a single value takes h stages.
In the example there are seven processors. The children of the root p0 are p1 and p5. The children of p1 are p2 and p4, the child of p2 is p3, and the child of p5 is p6. The longest path is p3 → p2 → p1 → p0; the depth is h = 3.
Now let each processor hold not a single number but a vector with k components. In the example k = 3, and the components are shown in green, blue, and red. Each component is to be summed separately. A message carries a single component, and the rule is this: a node can receive at most one message per round; in the same round it may also send one message.
The naive method reduces the components one after another. First the green component is brought up to the root, then the blue, then the red. Each component reaches the root in h = 3 rounds; the naive method needs k · h = 9 rounds in total. In the pipelined tree method, while one component is moving up, the next component sets out from the leaves.
9.7.2Step-by-step execution
Each component reaches the root in three stages:
- Stage 1: p3 → p2, p4 → p1, p6 → p5.
- Stage 2: p2 → p1, p5 → p0.
- Stage 3: p1 → p0.
p1 receives messages from its two children: from p4 in stage 1 and from p2 in stage 2. p0 likewise receives from p5 in stage 2 and from p1 in stage 3. The stages must therefore take place in separate rounds. There must also be at least two rounds between stage 1 of one component and stage 1 of the next. Otherwise p1 would have to receive in the same round both the new component from p4 and the old component from p2. For this reason a new component sets out every two rounds. Table 9.11 gives the rounds.
| Round | Stage 1 | Stage 2 | Stage 3 | Additions |
|---|---|---|---|---|
| 1 | green | — | — | p3→p2: 9 + 8 = 17; p4→p1: 7 + 3 = 10; p6→p5: 2 + 3 = 5 |
| 2 | — | green | — | p2→p1: 17 + 10 = 27; p5→p0: 5 + 3 = 8 |
| 3 | blue | — | green | green p1→p0: 27 + 8 = 35; blue 5 + 5 = 10, 5 + 7 = 12, 1 + 4 = 5 |
| 4 | — | blue | — | p2→p1: 10 + 12 = 22; p5→p0: 5 + 6 = 11 |
| 5 | red | — | blue | blue p1→p0: 22 + 11 = 33; red 8 + 3 = 11, 2 + 5 = 7, 7 + 5 = 12 |
| 6 | — | red | — | p2→p1: 11 + 7 = 18; p5→p0: 12 + 1 = 13 |
| 7 | — | — | red | p1→p0: 18 + 13 = 31 |
Round 3 is the first round in which the pipeline pays off. While the green component is completed at the root, the blue component sets out from the leaves. In that round p0 receives only from p1, p1 only from p4, p2 only from p3, and p5 only from p6. The rule is not violated. p1 both receives (blue, from p4) and sends (green, to p0) in the same round.
The result is green 35, blue 33, red 31. To verify, sum all the green components: 3 + 3 + 8 + 9 + 7 + 3 + 2 = 35. Here the order is p0, p1, …, p6.
9.7.3Analysis
Each component reaches the root in h = 3 rounds. A new component starts every two rounds. The last component starts (k − 1) · 2 rounds later and finishes in h rounds. The total number of rounds is
h + (k − 1) · 2 = 3 + 2 · 2 = 7
The naive method needs k · h = 9 rounds. The gain looks small, but it grows as k grows. The pipelined tree takes 2k + 1, that is, about 2k rounds; the naive method takes 3k rounds. For example, for k = 10, 21 and 30 rounds.
That seven rounds is the best result for this tree can be seen with a simple count. The root has two children, and for each of the three components it must receive a message from each child: 6 messages in total. Since the root can receive one message per round, it needs at least 6 rounds of receiving. The first message can arrive at the earliest in round 2: the value p5 will send must first receive p6's contribution, and the value of p1 depends on an even deeper subtree. Six rounds starting from round 2 end at the earliest in round 7.
In general the number of rounds is about h + (k − 1) · c, where c is the maximum number of children of a node. A node with many children spends c rounds to receive one component, and it determines the speed of the line. If the tree is a chain (c = 1), the formula reduces to h + k − 1; this is the same as the pipeline formula k + m − 1.
Thinking a component can set out every round. Then the number of rounds comes out as h + k − 1 = 5. But if the second component sets out in round 2, p1 must receive in that round both the blue component from p4 and the green component from p2. This breaks the "one message per round" rule. Nodes with two children cut the speed of the line in half.
9.8Kinds of parallel algorithms and Java
The algorithms in the earlier sections ran on abstract models such as the PRAM or processors exchanging messages. This section builds the same ideas in a real language, Java. Java programs run on a machine with shared memory. Threads can access common objects. Instead of managing threads directly, task-based tools are mostly used.
9.8.1Three kinds of parallelism
Most parallel algorithms met in practice fit one of three patterns:
- Divide and conquer. The problem is split into independent subproblems. The subproblems are solved at the same time on different cores and the results are combined. Parallel merge sort, parallel quicksort, and blocked matrix multiplication follow this pattern.
- MapReduce. A large data set is processed on many nodes. The map step produces intermediate key–value pairs from each piece; the reduce step combines the values of the same key. Hadoop and Spark are common implementations of this pattern. Word counting, building an index for a search engine, and log analysis are typical uses.
- Data parallelism. The same computation is applied to different parts of the data at the same time. SIMD instructions and GPUs are designed for this pattern. Scientific simulation, image processing, and numerical computing use it.
The counterpart of the divide-and-conquer pattern in Java is the Fork/Join framework. Figure 9.16 shows the idea of the framework. A task forks into subtasks. The subtasks run in parallel. The main task joins, that is, waits for the subtasks to finish, and combines their results.
9.8.2Parallel merge sort with Fork/Join
Merge sort is the most familiar example of divide and conquer. The array is split in two, the two halves are sorted separately, and then the two sorted halves are merged. Sorting the two halves is independent; to run them in parallel they only need to be given to separate tasks.
class SortTask extends RecursiveTask<int[]> {
private final int[] array;
SortTask(int[] array) { this.array = array; }
protected int[] compute() {
if (array.length <= 1) return array;
int mid = array.length / 2;
var left = new SortTask(
Arrays.copyOfRange(array, 0, mid));
var right = new SortTask(
Arrays.copyOfRange(array, mid, array.length));
left.fork(); // start in parallel
right.fork();
return merge(left.join(), right.join());
}
}
// usage:
int[] s = new ForkJoinPool().invoke(
new SortTask(array));The elements of the code are as follows:
RecursiveTask<int[]>is a Fork/Join task that returns a result. The task's work is written in thecompute()method. For tasks that return no result,RecursiveActionis used.- Base case: an array with one element is already sorted and is returned as is.
- The array is split in two at the midpoint
mid.Arrays.copyOfRangemakes a copy of each half, so the two tasks do not share the same array. fork()hands the subtask to the pool and returns immediately. The task may run on another thread; the calling task continues without waiting. This operation is asynchronous.join()waits for the subtask to finish and returns its result.mergeis the familiar sequential merge that turns two sorted arrays into one sorted array; it takes O(n).new ForkJoinPool().invoke(...)runs the root task in a pool and waits for its result.
ForkJoinPool is a thread pool. Each thread in the pool has its own task queue. A thread puts a task it has fork()ed into its own queue. A thread whose queue has run empty does not wait idle; it takes a task from the other end of another thread's queue. This arrangement is called work stealing. Work stealing provides load balancing automatically: even when it is not known in advance how long each task will take, an idle core finds work.
Table 9.12 shows what the tasks do level by level for the example array 2 3 5 1 7 6 8 4. Splitting is done from top to bottom, merging from bottom to top.
| Level | Operation | Tasks | Number of parallel tasks |
|---|---|---|---|
| 0 | root | [2 3 5 1 7 6 8 4] | 1 |
| 1 | fork | [2 3 5 1] [7 6 8 4] | 2 |
| 2 | fork | [2 3] [5 1] [7 6] [8 4] | 4 |
| 3 | base | 8 single-element arrays | 8 |
| 4 | join + merge | [2 3] [1 5] [6 7] [4 8] | 4 |
| 5 | join + merge | [1 2 3 5] [4 6 7 8] | 2 |
| 6 | join + merge | [1 2 3 4 5 6 7 8] | 1 |
The program was run 11 times on a machine with 12 logical cores under JDK 21 and gave [1, 2, 3, 4, 5, 6, 7, 8] every time. Which thread did the merges, and in what order, varied from run to run. In a series of ten runs, the first merge to finish was [8, 4] five times, [2, 3] twice, [7, 6] twice, and [5, 1] once. Four separate threads carried out the four base merges. The result of a parallel program is deterministic, but the execution order is not. The guarantee for this is that the tasks do not modify shared data: each task works on its own copy and returns its result.
Producing tasks that are too fine-grained. The code creates a new task for every subarray, down to one-element arrays. For an array of a million elements this means about two million tasks. Creating a task, putting it in a queue, and waiting for it are much more expensive than comparing two numbers. In practice a threshold is chosen. For example, pieces below 1000 elements are sorted sequentially with Arrays.sort.
A small improvement can be made to the code. Instead of left.fork(); right.fork();, write left.fork(); int[] y = right.compute(); int[] x = left.join();. The calling task computes the right half itself; only the left half is given to the pool. The calling thread thus does not wait idle at join(), and the number of tasks handed to the pool is halved.
9.8.3Analysis of parallel sorting
The work of parallel merge sort is the same as the sequential version: at each level a total of n elements are merged, and there are log2 n levels. W = Θ(n log n). The depth is found by a recurrence. Because the two halves are sorted in parallel, only the depth of one of them counts. The merge is sequential and adds Θ(n) depth:
D(n) = D(n / 2) + Θ(n) = Θ(n)
Unrolling the recurrence gives n + n/2 + n/4 + … ≤ 2n. The parallelism is W / D = Θ(n log n) / Θ(n) = Θ(log n).
| Version | Work W | Depth D | Parallelism W / D |
|---|---|---|---|
| Sequential merge sort | Θ(n log n) | Θ(n log n) | 1 |
| Parallel recursion + sequential merge | Θ(n log n) | Θ(n) | Θ(log n) |
| Parallel recursion + parallel merge | Θ(n log n) | Θ(log3 n) | Θ(n / log2 n) |
The parallelism is only Θ(log n), which is quite little. For n = 106, log2 n ≈ 20; with this code, more than about 20 cores bring little benefit. The bottleneck is the final merge done by the root task. That merge walks the whole array alone, and the other cores are idle meanwhile.
To remove the bottleneck, the merge itself is parallelized. The idea is this: the median element of the larger half is chosen, and the position of this element in the other half is found by binary search. The two halves are thus each split into two pieces, and the pieces are merged independently of each other, again in parallel. The depth of this version drops to Θ(log3 n) and the parallelism becomes Θ(n / log2 n). The details are given in the book by Cormen et al. Java also has a ready-made solution: Arrays.parallelSort(array) sorts large arrays in parallel with Fork/Join.
9.8.4MapReduce
MapReduce is a programming model developed at Google in 2004 for processing large data sets on thousands of machines. The programmer writes only two functions; distributing the data, redoing work when something fails, and collecting the results are left to the framework. The model has three steps:
- Map. The input is split into pieces. Each piece is processed independently and produces intermediate key–value pairs. In word counting the pair has the form "word → count".
- Shuffle. Pairs with the same key are sent to the same reducer.
- Reduce. The values of each key are combined; in word counting they are summed.
The example has 13 words: apple, banana, apple, orange, banana, apple, banana, banana, orange, apple, cherry, banana, apple. Four threads are used. The chunk size is ⌊13 / 4⌋ = 3; the first three chunks get three words each, and the last chunk gets the remaining four words. Figure 9.18 shows the flow.
In Java the map tasks are written as Fork/Join tasks. Each task takes a list of words (part) and returns its own count map.
// Map: count the words in one part
protected Map<String, Integer> compute() {
Map<String, Integer> result = new HashMap<>();
for (String word : part)
result.merge(word, 1, Integer::sum);
return result;
}
// Main flow
for (MapTask t : mapTasks) t.fork();
List<Map<String, Integer>> partial = new ArrayList<>();
for (MapTask t : mapTasks) partial.add(t.join());
// Reduce: combine the partial results
Map<String, Integer> total = new HashMap<>();
for (Map<String, Integer> m : partial)
m.forEach((k, v) -> total.merge(k, v, Integer::sum));The parts of the code work as follows:
compute()creates a newHashMap. This map belongs only to this task.result.merge(word, 1, Integer::sum)adds the word with value 1 if it is not in the map. If it is, it adds 1 to the old value. In a single line it does "insert if absent, increment if present".- In the main flow, all map tasks are first
fork()ed; the tasks start running in parallel in the pool. Then each task's result is taken withjoin()and added to thepartiallist. All tasks are forked before any is joined. Had each task been joined as soon as it was forked, the tasks would have run one after another. - The reduce step walks over the partial maps in order. Each (key, value) pair is added to the total map with
total.merge(k, v, Integer::sum).
Table 9.14 gives the intermediate results and the reduce steps obtained by running the program. The order in which the maps are printed depends on the internal layout of HashMap. This order is determined by the hash values of the keys; with the same keys it comes out the same on every run, but it is not alphabetical.
| Step | Input | Result |
|---|---|---|
| map 0 | apple, banana, apple | banana 1, apple 2 |
| map 1 | orange, banana, apple | banana 1, orange 1, apple 1 |
| map 2 | banana, banana, orange | orange 1, banana 2 |
| map 3 | apple, cherry, banana, apple | banana 1, cherry 1, apple 2 |
| reduce partial[0] | empty map + partial[0] | banana 1, apple 2 |
| reduce partial[1] | + partial[1] | orange 1, banana 2, apple 3 |
| reduce partial[2] | + partial[2] | orange 2, banana 4, apple 3 |
| reduce partial[3] | + partial[3] | orange 2, banana 5, cherry 1, apple 5 |
The most important property of this design is the absence of shared state. Each map task has its own HashMap. The tasks do not touch one another's data; therefore no lock is needed and no race condition can occur. The combining is done in one place after all the tasks have finished. The same idea was present in tree summation: each processor produces its own partial sum, and the partial results are combined afterwards.
In the example, reduce is a single task and it handles all the keys. In a real MapReduce system the keys are divided among many reducers. For the division, hash(k) mod r is usually used, where r is the number of reducers. The same key always goes to the same reducer. The reduce step thus also runs in parallel.
The chunk sizes in the example are unbalanced: the last task gets four words and the others three each. In a small example this is unimportant. But with millions of words, one task getting much more work than the others makes the other tasks wait for it. Real systems balance the load by splitting the input into many more chunks than there are tasks.
9.8.5Data parallelism: matrix multiplication
In the product C = A · B of two n × n matrices, each cell is computed as C[i][j] = Σk A[i][k] · B[k][j]. Each row of the result matrix depends on only one row of A and the whole of B. The rows are independent of one another; each row can be computed as a separate task.
// each row is a separate task
class RowTask extends RecursiveAction {
protected void compute() {
for (int j = 0; j < n; j++) {
C[row][j] = 0;
for (int k = 0; k < n; k++)
C[row][j] += A[row][k] * B[k][j];
}
}
}
try (var pool = new ForkJoinPool()) {
for (int i = 0; i < n; i++)
pool.submit(new RowTask(i));
} // close(): waits for all tasksRowTaskis a task that returns no result (RecursiveAction). It writes the values it computes directly into the matrixC. The fieldrowholds which row the task will compute; its constructor is not shown for brevity.- Two nested loops compute the n cells of a row. Each cell needs n multiplications and additions.
- The
try (var pool = new ForkJoinPool())block hands one task per row to the pool (submit). Since Java 19,ForkJoinPoolis a closeable resource. Theclose()called when the block ends waits for all the tasks in the pool to finish.
In the example A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and B = [[9, 8, 7], [6, 5, 4], [3, 2, 1]]. When the program was run it gave C = [[30, 24, 18], [84, 69, 54], [138, 114, 90]]. Table 9.15 shows every operation performed by the row 1 task.
j | k | Operation | C[1][j] |
|---|---|---|---|
| 0 | — | start | 0 |
| 0 | 0 | + 4 · 9 | 36 |
| 0 | 1 | + 5 · 6 | 66 |
| 0 | 2 | + 6 · 3 | 84 |
| 1 | 0, 1, 2 | 4 · 8 + 5 · 5 + 6 · 2 (32, 57, 69) | 69 |
| 2 | 0, 1, 2 | 4 · 7 + 5 · 4 + 6 · 1 (28, 48, 54) | 54 |
The algorithm's work and depth are as follows. Each of the n tasks does Θ(n2) operations; the total work is W = Θ(n3), the same as the sequential algorithm. Because the tasks run in parallel, the depth is the time of a single task: D = Θ(n2). The parallelism is W / D = Θ(n). More cores than rows bring no benefit to this design. If more parallelism is needed, each cell can be made a separate task, or the matrix can be split into blocks.
There is no race condition in this code, because each task writes only to its own row. A and B are read by all tasks but no task writes to them. Concurrent reading is harmless. Only one task writes to each row of C. As long as the regions written by the tasks are disjoint, a shared matrix can be used safely.
9.9Shared state and races
In the Java examples so far, the tasks either worked on their own data or wrote to disjoint regions. This was not a coincidence but a deliberate design decision. When several threads modify the same data, the program's behavior becomes unpredictable. This section shows the source of the problem and describes the ways to solve it.
9.9.1The race condition
Let two threads increment a shared counter variable. In Java counter++ looks like a single statement. At the processor level, though, it is three steps: read from memory, increment the local copy, write to memory. If the steps of the two threads interleave, an increment can be lost. Table 9.16 shows such an interleaving.
| Time | Thread 1 | Thread 2 | counter |
|---|---|---|---|
| 1 | read (0) | 0 | |
| 2 | read (0) | 0 | |
| 3 | write 0 + 1 | 1 | |
| 4 | write 0 + 1 | 1 |
Both threads read 0 and wrote 1. The expected result is 2, but the counter is 1. The second write overwrote the result of the first. This bug is called a lost update.
A race condition is a situation in which a program's result depends on the timing of its threads, that is, on the order in which the operating system runs them. At least two threads access the same data without coordination, and at least one of them writes.
To see a race condition in a real program, the following code was written. Each of two threads increments the shared counter a million times.
public class CounterRace {
static int counter = 0; // shared state
public static void main(String[] args) throws InterruptedException {
Runnable task = () -> {
for (int i = 0; i < 1_000_000; i++)
counter++; // read → increment → write
};
Thread t1 = new Thread(task), t2 = new Thread(task);
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(counter); // expected 2000000
}
}Runnable defines the work a thread will execute; here it is a lambda expression. start() starts the thread and returns immediately; from this point the two threads run at the same time. join() makes the main thread wait until that thread finishes. println therefore runs after both loops have finished.
The program was run 30 times on a Windows machine with 12 logical cores under JDK 21, starting a fresh JVM each time. The result varied from run to run. In none of the 30 runs did the expected 2,000,000 appear. The smallest value was 1,049,868 and the largest 1,920,460; in some runs about half of the increments were lost. These numbers will differ on another machine, on another JDK version, or on the same machine at another moment. The one thing that does not change is that the result cannot exceed 2,000,000: a lost update erases an increment but never adds an extra one.
The same experiment was also done with 1000 increments per thread. This time all 20 runs gave the correct result (2000). The reason is that 1000 increments take so little time that the first thread usually finishes before the second one starts. The two threads never overlap. But this does not mean the program is correct. If the machine is busy or the timing changes, the same program can give a wrong result. This is what makes race conditions hard to debug: the bug may not show in testing and appear only in real use, by chance. In 20 runs with 100,000 increments per thread, the results varied between 109,546 and 161,741; the expected value is 200,000.
Two threads increment the shared counter (initially 0) twice each, without coordination. Each increment has the form "read, write": one more than the value read is written. What is the smallest possible result?
- T1 reads: 0.
- T2 completes its first increment: reads 0, writes 1.
counter= 1. - T1 completes its first increment: writes one more than the 0 it read, that is, 1. T2's increment is erased.
counter= 1. - T2 reads for its second increment: 1.
- T1 completes its second increment: reads 1, writes 2.
- T2 completes its second increment: one more than the 1 it read, 2, is written.
The result is 2; two of the four increments are lost. A program that tries all possible interleavings shows that with two increments each, the result can be 2, 3, or 4. By a similar scenario, as long as each thread increments at least twice, the result can drop to 2 however many increments there are.
9.9.2Preventing races
There are three basic ways to prevent a race condition.
Locks. Only one thread at a time can enter the block synchronized (lock) { counter++; }. The other thread waits until the lock is released. The read, increment, and write steps thus become an indivisible whole. The locked version gave 2,000,000 in all 20 runs.
Atomic operations. The classes in the java.util.concurrent.atomic package offer indivisible operations using the processor's special instructions. AtomicInteger.incrementAndGet() performs the read, increment, and write steps in a single atomic step.
import java.util.concurrent.atomic.AtomicInteger;
public class CounterAtomic {
static final AtomicInteger counter = new AtomicInteger();
public static void main(String[] args) throws InterruptedException {
Runnable task = () -> {
for (int i = 0; i < 1_000_000; i++)
counter.incrementAndGet(); // one atomic step
};
Thread t1 = new Thread(task), t2 = new Thread(task);
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(counter.get()); // always 2000000
}
}The atomic version printed 2,000,000 in all 10 separate runs. Concurrent data structures work on the same principle. ConcurrentHashMap allows many threads to write to the same map safely.
Avoiding shared state. The best solution is not to use a shared variable at all. Each task produces its own partial result; the results are combined after the tasks finish. Tree summation, MapReduce, and the row tasks work on this principle. In the counter example each thread increments its own local counter, and after join() the two local counters are added. This solution is both correct and the fastest, because the threads never wait.
Locks are not free. In a locked region only one thread runs at a time; the region becomes sequential. By Amdahl's law this sequential part limits speedup. Moreover, when several locks are used, there is a risk of deadlock. If T1 holds lock A and waits for B, while T2 holds lock B and waits for A, both wait forever.
Thinking that making the shared counter a volatile int solves the race. volatile ensures that a value written by one thread is immediately seen by the others. But it does not make the read, increment, and write steps of counter++ indivisible. Two threads can still read the same value and write the same value. Atomicity requires AtomicInteger or a lock.
9.9.3Concurrent graph traversal
Race conditions arise not only in counters but also in more complex data structures. Consider a parallel version of depth-first traversal. For each unvisited neighbor a new traversal task is fork()ed, and the subtrees are traversed in parallel. In the graph in Figure 9.20, the traversal starting from 1 opens two tasks for 2 and 3; these tasks in turn open new tasks for their own neighbors.
The tasks share a common set that records which nodes have been visited. There are two separate problems with this set. First, if the set is an ordinary HashSet, its internal structure can be corrupted by concurrent writes. Second, even if the set is safe, the question "is it in there?" and the "add" operation are two separate steps. Two tasks can ask about the same node at the same time, both can get the answer "no", and both visit the node. The correct code is this:
Set<Node> visited = ConcurrentHashMap.newKeySet();
if (!visited.add(next)) continue; // atomic check + addConcurrentHashMap.newKeySet() returns a set that is safe under concurrent access. The add method returns true if the element was added and false if it was already there. The check and the insertion are a single atomic operation. If two tasks try to add the same node, only one gets true, and only that one visits the node.
An experiment was done to see this difference. Each of eight threads tried to "visit" the same 100,000 nodes, 0 to 99,999, in order. Each thread counted a node only if it decided it was the "first visitor". A correct set should give 100,000 visits. Each method was run 20 times, and the results varied from run to run:
| Set | Check + add | Extra visits | Note |
|---|---|---|---|
HashSet | contains, then add | 44.821 – 147.433 | size() 104,205 – 137,960; the set was corrupted |
newKeySet() | contains, then add | 53.122 – 212.552 | the set is intact, but nodes were visited more than once |
newKeySet() | if (!add(k)) continue | 0 (in all 20 runs) | correct |
In the HashSet version size() exceeded 100,000 although the set can hold only 100,000 distinct numbers. This shows that the set's internal counter also fell into the race. The second row shows that a safe set alone is not enough: the two-step check is still open to a race. Only the atomic check and add in the third row gave the correct result on every run.
Another form of parallel traversal is used on graphs: level-synchronous breadth-first search. All the nodes of each level are expanded in parallel, and a barrier is placed at the end of the level. The next level starts after all the nodes of the previous level have been processed. In the ideal PRAM model, with enough processors, the depth is O(diameter): the number of levels does not exceed the diameter of the part reachable from the source. In a realistic model the combining and barrier steps of each level take O(log n); the depth becomes O(diameter · log n). On graphs with a small diameter and many nodes, such as social networks, this method offers a lot of parallelism.
9.9.4Parallelism tools in Java
Java offers parallelism tools at different levels. Table 9.18 summarizes which to use when.
| Tool | When? |
|---|---|
Thread, Runnable | lowest level; manual management, rarely used directly |
ExecutorService | running independent tasks in a fixed thread pool |
ForkJoinPool, RecursiveTask | divide and conquer; recursive tasks with work stealing |
list.parallelStream() | data-parallel map / filter / reduce (uses the common ForkJoinPool) |
Arrays.parallelSort | sorting large arrays in parallel |
Arrays.parallelPrefix | parallel prefix sum (scan) |
AtomicInteger, ConcurrentHashMap | safe access when a shared counter or set is needed |
The tools in the upper rows of the table give more control but need more code. The tools in the lower rows reduce the job to a single method call. For example, word counting fits into a single expression with the stream interface:
Map<String, Long> counts = words.parallelStream()
.collect(Collectors.groupingByConcurrent(w -> w, Collectors.counting()));parallelStream() splits the list into pieces and processes them on the common ForkJoinPool. groupingByConcurrent groups the words in a concurrent map and counts the elements of each group. On the 13-word example this expression gave banana 5, orange 2, apple 5, cherry 1. All the work of the MapReduce code, namely splitting, map, shuffle, and reduce, is done in a single expression. The parallelism level of the common pool is by default one less than the number of cores; on the machine where the experiment was run it was 11.
9.10Common mistakes
- Thinking p processors bring a speedup of p. Because of the sequential part, communication, and waiting, speedup stays below p. If 10% of the program is sequential, by Amdahl's law speedup cannot exceed 10.
- Computing speedup against the wrong baseline. T1 is not the parallel algorithm's time on a single processor but the time of the best sequential algorithm.
- Using a shared
HashSetor counter. Concurrent writing leads to a race condition. UseConcurrentHashMap,AtomicInteger, or local results combined afterwards. Even in a safe set, "check, then add" is two steps; look at the return value ofadd, which is a single step. - Tasks that are too fine-grained. Calling
fork()for every element pushes the task-creation overhead above the gain. Pieces below a threshold should be processed sequentially. - Forgetting synchronization between rounds. In PRAM summation, if round t + 1 starts before all the writes of round t have finished, old values are read. In a sequential simulation of Hillis–Steele, the same bug appears when the copy at the start of the round is forgotten.
- Looking only at depth. Hillis–Steele finishes in O(log n) rounds but does O(n log n) work; with few processors it can be slower than the sequential scan. When choosing an algorithm, work and depth are evaluated together.
- Miscounting the steps of a pipeline. The filling time of the line is forgotten. For m rows and p processors the number of steps is not m but m + p − 2.
- Reducing a non-associative operation with a tree. If subtraction or division is reduced with a tree, the result changes. In floating-point addition too, the parallel result can differ from the sequential result in the last digits.
- Assuming a parallel program that worked once is correct. A race condition does not show up on every run. The counter experiment with 1000 increments per thread gave the correct result in all 20 runs; the same code with a million increments gave the correct result in none of 30 runs.
9.11Summary
- A parallel algorithm divides the problem into pieces, assigns the pieces to processors, solves them at the same time, and combines the results. The price is communication, synchronization, and load balancing. A chain of data dependencies cannot be parallelized; but if the operation in the chain is associative, the chain can be turned into a tree.
- Flynn's classification divides machines into SISD, SIMD, MISD, and MIMD by instruction and data streams. Memory can be shared or distributed. The PRAM is a theoretical model with shared memory and a shared clock; the EREW, CREW, and CRCW variants differ in how they treat concurrent access to the same cell.
- Speedup is S = T1 / Tp, efficiency E = S / p, and cost C = p · Tp. In a cost-optimal algorithm C = Θ(T1). Amdahl's law gives the bound S ≤ 1 / (1 − f). Gustafson's law says that as the problem grows, the scaled speedup is (1 − f) + f · p.
- Work W is the total number of operations, and depth D is the longest dependency chain. max(W / p, D) ≤ Tp ≤ W / p + D (Brent). Parallelism W / D is the maximum number of processors that can be used profitably.
- PRAM tree summation works in log2 n rounds with n − 1 additions and manages with EREW. With n / log n processors it becomes cost-optimal.
- For prefix sums, Hillis–Steele spends log2 n rounds and n log2 n − (n − 1) work; it is not work-efficient. Blelloch finds the exclusive prefix sum with an up-sweep and a down-sweep in 2(n − 1) work and 2 log2 n rounds.
- In a pipeline with p processors and m rows, the number of steps is m + p − 2 (naive method m(p − 1)), and the efficiency is m / (m + p − 2). In a pipelined tree the number of rounds is h + (k − 1) · c; in the example 7 rounds (naive 9).
- In Java, divide and conquer is written with
ForkJoinPool:fork()hands a subtask to the pool,join()waits for its result, and work stealing balances the load. Parallel merge sort with a sequential merge has depth Θ(n) and parallelism Θ(log n). - MapReduce consists of the map, shuffle, and reduce steps. Because each map task uses its own map, no lock is needed. In matrix multiplication with row tasks too, the tasks write to disjoint regions.
- In a race condition the result depends on timing and varies from run to run. The solutions are locks, atomic operations, concurrent data structures, and, best of all, avoiding shared state.
9.12Key terms
- parallel algorithm
- PRAM model
- speedup
- efficiency
- Amdahl's law
- work / span
- prefix sum (scan)
- pipelining
- message passing
- work stealing
- race condition
- cost-optimal
- work-efficient
- Brent's theorem
- Gustafson's law
- reduction
- barrier
- lost update
- deadlock
9.13Test Yourself
n = 32 numbers are summed with PRAM tree summation. How many rounds does it take, how many additions are done in the first round, and how many in total? What is the cost with 16 processors; is the algorithm cost-optimal?
Answer
log2 32 = 5 rounds. In the first round 16 additions are done; in total 16 + 8 + 4 + 2 + 1 = 31 = n − 1. With 16 processors the cost is 16 · 5 = 80; the sequential algorithm takes 31 steps. The ratio grows like log2 n / 2 and increases without bound as n grows; the algorithm is not cost-optimal. If the blocks are first summed sequentially with n / log2 n ≈ 6 processors, the cost drops to Θ(n).
95% of a program can be parallelized. What are the Amdahl speedup and efficiency on 16 processors? What is the limit as the number of processors goes to infinity? What does Gustafson's law give if the problem size grows with the number of processors?
Answer
S = 1 / (0.05 + 0.95 / 16) = 1 / (0.05 + 0.059375) ≈ 9.14. Efficiency 9.14 / 16 ≈ 0.57. Limit 1 / 0.05 = 20. Gustafson: 0.05 + 0.95 · 16 = 15.25.
A job takes 200 s with the best sequential algorithm. The 10-processor parallel version takes 25 s. What are the speedup, efficiency, and cost? How many processor-seconds went to overhead?
Answer
S = 200 / 25 = 8, E = 8 / 10 = 0.8, C = 10 · 25 = 250 s. The overhead is 250 − 200 = 50 processor-seconds; 5 s per processor.
The Blelloch algorithm is applied to the array [1, 2, 3, 4]. What is the array after each round of the up-sweep, after zeroing the root, and after each round of the down-sweep? How many operations and rounds are used?
Answer
Up d = 1: [1, 3, 3, 7]; d = 2: [1, 3, 3, 10]. Root: [1, 3, 3, 0]. Down d = 2, pair (1, 3): t = 3,
x[1]= 0,x[3]= 0 + 3 → [1, 0, 3, 3]. Down d = 1, pair (0, 1):x[0]= 0,x[1]= 0 + 1; pair (2, 3):x[2]= 3,x[3]= 3 + 3 → [0, 1, 3, 6]. This is the exclusive prefix sum. 2(n − 1) = 6 operations, 2 log2 4 = 4 rounds.A chain of three processors has the columns p0 = (1, 2, 3, 4, 5), p1 = (1, 1, 1, 1, 1), p2 = (2, 2, 2, 2, 2). How many steps does the pipeline take, how many does the naive method take, and what is the efficiency? What does p2 hold at the end, and at which step does row 4 reach p2?
Answer
m + p − 2 = 5 + 3 − 2 = 6 steps; the naive method takes m(p − 1) = 10 steps. Efficiency 5 / 6 ≈ 0.83. p1 becomes (2, 3, 4, 5, 6) and p2 becomes (4, 5, 6, 7, 8). p1 sends row 4 at time t = 4 + 1 = 5; this is the sixth and last step.
Four processors form a chain p3 → p2 → p1 → p0 (a tree with one child per node), and each holds a vector with 5 components. The root is p0. How many rounds does the pipelined reduction take, and how many does the naive method take?
Answer
h = 3, k = 5, and every node has at most one child (c = 1). A new component can set out every round, because each node receives only one message per round. The number of rounds is h + (k − 1) · 1 = 7; the naive method takes k · h = 15 rounds.
n = 220 numbers are summed with a tree and there are 1024 processors. What are the work, depth, and parallelism? What range does Brent's theorem give for the time; what is the minimum speedup?
Answer
W = 220 − 1 = 1,048,575, D = 20, parallelism ≈ 52,429. Lower bound W / p ≈ 1024; upper bound W / p + D ≈ 1044 steps. The speedup is at least 1,048,575 / 1044 ≈ 1004; almost linear with 1024 processors. When the number of processors is much smaller than the parallelism, the depth term becomes negligible.
1000 × 1000 matrices are multiplied with row tasks. What are the work, depth, and parallelism? On a machine with 2000 cores, what is the maximum possible speedup?
Answer
W = n3 = 109 multiply-adds, D = n2 = 106 (the time of a single row), parallelism W / D = 1000. Because there are only 1000 tasks, at most half of the cores work; since Tp ≥ D, the speedup is at most 1000. For more parallelism, cell or block tasks are needed.
A student wants to find the sum of a list with a variable
long total = 0;andlist.parallelStream().forEach(x -> total += x). Why is this wrong? Does Java compile this code? How should it be written correctly?Answer
Java does not compile this code: only effectively final local variables can be used inside a lambda. If the variable is made a field, the code compiles, but
total += xconsists of read, add, and write steps, and lost updates occur between threads. The result varies from run to run. The correct version is a reduction that uses no shared state:list.parallelStream().mapToLong(Long::longValue).sum(). Each thread produces its own partial sum, and the partial sums are then combined.
9.14Further reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4th edition, 2022), chapter 26: the notions of work, span, and parallelism and the greedy scheduler bound are treated here. The detailed analysis of parallel merging and parallel merge sort is also in this chapter.
- J. JáJá, An Introduction to Parallel Algorithms (1992): a comprehensive source for the PRAM model, cost-optimal tree summation, prefix sums, and the relationships among PRAM variants.
- A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing (2nd edition, 2003): covers practical topics such as pipelining, communication costs, scalability, and programming with MPI.
- D. Lea, “A Java Fork/Join Framework” (2000): describes the design of
ForkJoinPoolin Java and its work-stealing mechanism, in the words of its author.
9.15References
- G. M. Amdahl, “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities”, AFIPS Spring Joint Computer Conference, 1967.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022 (chapter 26: Parallel Algorithms).
- J. Dean, S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters”, OSDI, 2004.
- A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing, 2nd edition, Addison-Wesley, 2003.
- J. JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
- D. Lea, “A Java Fork/Join Framework”, ACM Java Grande Conference, 2000.
Related pages: Chapter 9 slides · © Sercan Külcü. All rights reserved.