8.1 Definition

In fork–join parallelism, control flow forks (divides) into multiple flows that join (combine) later. After the fork, one flow turns into two separate flows. Each flow is independent, and they are not constrained to do similar computation. After the join, only one flow continues.

For example, consider forking to execute B() and C() in parallel and then joining afterwards. The execution of a fork–join can be pictured as a directed graph, as in Figure 8.1. This figure also demonstrates the graphical notation we will use for the fork and join operations.

Often fork–join is used to implement recursive divide-and-conquer algorithms. The typical pattern looks like this:

void DivideAndConquer( Problem P) {

 if(P is base case) {

  Solve P;

 } else {

  Divide P into K subproblems;

  Fork to conquer each subproblem in parallel;

  Join;

  Combine subsolutions into final solution;

 }

}

It is critical that the subproblems be independent, so that they can run in parallel. Nesting K-way fork–join this way to N levels permits K^N-way parallelism. Figure 8.2 shows three-level nesting, resulting in eight parallel flows at the innermost level. The algorithm should be designed to put the vast majority of work deep in the nest, where parallelism is high. Section 8.6 shows how to formally analyze the speedup of fork–join.

Selecting the size of the base case for parallel divide-and-conquer can be critical in practice. It should allow the recursion to go deep enough to permit plenty of parallelism. However, the recursion should not be too deep; in particular, it should not result in subproblems so fine grained that scheduling overheads dominate. Section 8.4 offers more guidance on this point. Also, the problem division and combine operations which appear before and after the fork and join operations should be as fast as possible, so they do not dominate the asymptotic complexity and strangle speedup.

8.2 Programming Model Support for Fork–Join

Programming model support for fork–join has to express where to fork and where to join. Cilk Plus, TBB, and OpenMP express fork–join differently. Cilk Plus uses a syntactic extension, TBB uses a library, and OpenMP uses pragma markup, but the fundamental parallel control flow is the same for all. There are, however, subtle differences about which threads execute a particular part of the parallel control flow, as Section 8.5 will explain. As long as you do not rely on thread-local storage, the difference is immaterial for now.

When reading the following subsections, pay attention not only to the different ways of expressing fork–join but also to how variables outside the fork–join are captured and referenced. This is particularly relevant when there is an increment of an index variable, such as ++i in the example.

8.3 Recursive Implementation of Map

One of the simplest, but most useful, patterns to implement with fork–join is map. Although both Intel TBB and Cilk Plus have concise ways to express map directly, the map pattern is nonetheless a good starting example for parallel divide-and-conquer, because it implements a familiar pattern. It also gives some insight into how Cilk Plus and TBB implement their map constructs. They really do use the divide-and-conquer approach to be described, because it efficiently exploits the underlying work-stealing mechanism explained in Section 8.5. Furthermore, you may eventually need to write a version of the map pattern with features beyond the built-in capabilities—for example, when fusing it with other patterns—so knowledge of how to implement map efficiently using fork–join is useful.

Consider the following Cilk Plus code:

cilk_for(unsigned i=lower; i<upper; ++i)

 f(i);

The cilk_for construct can be implemented by a divide-and-conquer routine recursive_map, which is called like this:

if(lower<upper)

 recursive_map(lower,upper,grainsize,f)

The conditional eliminates needing to deal with the empty case inside the routine. Listing 8.1 shows the recursive_map routine. The parameter grainsize controls the size of the base case. In Cilk Plus, the compiler and runtime choose the size of the base case based on considerations that will be discussed in Section 8.4.

Figure 8.4 illustrates the execution of recursive_map(0,9,2,f), which maps f over the half-open interval [0,9) with no more than two iterations per grain. Arcs are labeled with [lower,upper) to indicate the corresponding arguments to recursive_map.

Now consider an optimization. In Listing 8.1, no explicit cilk_sync is necessary because every function with cilk_spawn performs an implicit cilk_sync when it returns. Except for this implicit cilk_sync, the routine does nothing after its last call. Hence, the last call is what is known as a tail call. In serial programming, as long as local variables can be overwritten before the last call, a tail call can be optimized away by the following transformation:

Applying these rules literally to the previous example yields the code in Listing 8.2. This code can be cleaned up by removing redundant updates and structuring the goto as a while loop, resulting in the concise code in Listing 8.3.

Similar tricks for converting tail calls to iteration applies to TBB, as will be shown in Listings 8.12 and 8.13 of Section 8.9.2.

8.4 Choosing Base Cases

In parallel divide-and-conquer, there are often two distinct base cases to consider:

They sometimes differ because they are guided by slightly different overhead considerations. The alternative to parallel recursion is serial recursion, which avoids parallel scheduling overheads. The alternative to serial recursion is a serial iterative algorithm, which avoids calling overheads. However, these two overheads are often at different scales so the optimal sizes for the base cases are often different.

For example, in the Quicksort example detailed later in Section 8.9, serial recursion continues only until there are about 7 elements to sort. It stops at a relatively short sequence because the iterative alternative is a quadratic sort, which has a higher asymptotic complexity but less overhead and a lower constant factor. However, in the same example, parallel recursion stops at about 500 elements. The parallel recursion stops for a much bigger base case problem size because the alternative is serial recursive Quicksort, which is still quite efficient at this size but avoids parallel overheads.

Given a machine with P hardware threads, it is tempting to choose a parallel base case such that there are exactly P leaves in the tree of spawned functions. However, doing so often results in poor performance, because it gives the scheduler no flexibility to balance load, as noted in Section 2.6.6. Even if the leaves have nominally equal work and processors are nominally equivalent, system effects such as page faults, cache misses, and interrupts can destroy the balance. Thus, it is usually best to overdecompose the problem to create parallel slack (Section 2.5.6). As the next section explains, the underlying work-stealing scheduler in Cilk Plus and TBB makes unused parallel slack cheap for fork–join parallelism.

Of course, overdecomposition can go too far, causing scheduling overheads to swamp useful work, just as ordinary function calls can swamp useful work in serial programs. A rough rule of thumb is that a cilk_spawn costs on the order of 10 non-inlined function calls, and a TBB spawn costs on the order of 30 non-inlined function calls, excluding the cost of data transfer between workers if parallelism actually occurs. Basic intuitions for amortizing call overhead still apply—only the relative expense of the call has changed.

When the leaves dominate the work, you should also consider whether vector parallelism can be applied, as in the Karatsuba multiplication example (Listing 8.6).

8.5 Load Balancing

Cilk Plus and TBB efficiently balance the load for fork–join automatically, using a technique called work stealing. Indeed, as remarked earlier, the work-stealing technique is so effective for load balancing that both frameworks implement their map operations (cilk_for and tbb::parallel_for) using fork–join algorithms.

In a basic work-stealing scheduler, each thread is called a worker. Each worker maintains its own double-ended queue (deque) of tasks. Call one end of the deque the “top” and the other end the “bottom.” A worker treats its own deque like a stack. When a worker spawns a new task, it pushes that task onto the top of its own deque. When a worker finishes its current task, it pops a task from the top of its own deque, unless the deque is empty.

When a worker’s deque is empty, a worker chooses a random victim’s deque and steals a task from the bottom of that deque. Because that is the last task that the owner of the deque would touch, this approach has several benefits:

Overall, the net effect is that workers operate serially depth-first by default, until more actual parallelism is required. Each steal adds a bit of parallel breadth-first execution, just enough to keep the workers busy. The “just enough” part is important. Always doing breadth-first execution leads to space exponential in the spawning depth, and the worst spatial locality imaginable! Cilk Plus formalizes the “just enough” notion into some strong guarantees about time and space behavior.

Before going into the Cilk Plus guarantees, it is worth understanding why they will not always apply to TBB also. Cilk Plus and TBB differ in their concept of what is a stealable task. The code fragments in Listing 8.4 will be used to show the difference. The Cilk Plus and TBB fragments show poor style, because the code will probably perform much better if written as a map instead of a serial loop that creates tasks. But it serves well to illustrate the stealing issue, and sometimes similar code has to be written when access to the iteration space is inherently sequential, such as when a loop traverses a linked list.

For each spawned f(i), there are two conceptual tasks:

A key difference between Cilk Plus and TBB is that in Cilk Plus, thieves steal continuations. In TBB, thieves steal children.

Figure 8.5 diagrams the difference, assuming there are plenty of workers to steal work. The left side shows Cilk Plus execution, which uses steal-continuation semantics. The initial worker sets i=0 and spawns f(0). The worker immediately starts executing f(0), leaving the continuation available to steal. Then another worker steals that continuation and continues execution of the loop. It updates i and executes f(1). The next worker steals the further continuation of the loop and executes f(2). The key point is that the loop advances only when there is a worker ready to execute another iteration of it.

The right side shows TBB execution, which uses steal-child semantics. The initial worker sets i=0 and spawns f(0). It leaves f(0) available to steal and proceeds to go around the loop again. It thus executes all iterations of the loop before attending to spawned work. Furthermore, if it does pick up an iteration afterward, f(n-1) is topmost on its deque, so it executes f(n-1) first, the reverse order of the serial code.

This difference has a major impact on stack space guarantees. In the Cilk Plus execution, each worker is working on a call chain in a state that would have existed in the serial program. Thus, Cilk Plus can guarantee that, if a program takes stack space for serial execution, it takes no more than stack space when executed by P workers.¹ However, if run with a single worker, the TBB code creates a state where the for loop completes, but none of the calls to f(i) has yet started, a nonsensical state for the original program. Assuming each spawned call takes Θ (1) space to represent on the stack, the TBB program takes Θ (n) stack space, even if no parallelism is being exploited.

The example also illustrates another difference. In the TBB code, the worker that enters the loop is the worker that continutes execution after f(i) finishes. If that worker executes g.wait() and not all f(i) are finished, it tries to execute some of the outstanding f(i) tasks. If none of those is available, it either idly waits or goes off on an errand to find temporary work to keep it busy. If, in the meantime, the other spawned f(i) finishes, further progress is blocked until the original worker returns from its errand. Thus, TBB scheduling is not always greedy (Section 2.5.6), which in turn means that, strictly speaking, the lower bound on speedup derived in Chapter 2 does not apply.

In the Cilk Plus code, workers never wait at a cilk_sync. The last worker to reach the cilk_sync is the worker that continues execution afterwards. Any worker that reaches the cilk_sync earlier abandons the computation entirely and tries to randomly steal work elsewhere. Though random stealing deviates from ideal greediness, in practice as long as there is plenty of parallel slack the deviation is insignificant and Cilk Plus achieves the time bound in Equation 2.9 (page 64).

TBB can implement steal-continuation semantics, and achieve the Cilk Plus space and time guarantees, if continuations are represented as explicit task objects. This is called continuation passing style. Unfortunately, it requires some tricky coding, as Section 8.9.2 will show.

Cilk Plus and TBB have different semantics because they are designed with different tradeoffs in mind. Cilk Plus has nicer properties but requires special compiler support to deal with stealing continuations, and it is limited to a strict fork–join model. TBB is designed as a plain library that can be run by any C++ compiler and supports a less strictly structured model.

The stealing semantics for OpenMP are complex and implementation dependent. The OpenMP rules [Boa11] imply that steal-child must be the default but permits steal-continuation if a task is annotated with an untied clause. However, the rules do not require continuation stealing, so the benefits of these semantics are not guaranteed even for untied tasks in OpenMP.

8.6 Complexity of Parallel Divide-and-Conquer

Computing the work and span of the basic fork–join pattern is straightforward. Suppose execution forks along multiple paths and rejoins. The total work T₁ is the sum of the work along each path. The span T_∞ is the maximum span of any path.

More formally, let denote the fork–join composition of B and C, as introduced earlier in Figure 8.1. The overall work and span are:

Realistically, there will be some overhead for forking and joining. The burdened span (see Section 2.5.6) includes this overhead, typically a small constant addition for the synchronization plus the cost of communicating cache lines between hardware threads.

Since parallel divide-and-conquer is a recursive application of fork–join composition, analyzing the work and span in a recursive divide-and-conquer algorithm is a matter of defining recurrence relations for T₁ and T_∞ and solving them. Typically, the recurrences for T₁ and T_∞ have similar form but differ in constant factors, which can cause them to have quite different asymptotic solutions. Though solving arbitrary recurrence relations can be difficult, the relations for divide-and-conquer programs often have a form for which a closed-form solution is already known.

The following discussion presents a simplified form of the Master method [CLRS09], which suffices for the most common cases. It assumes that the problem to be solved has a size N and the recursion has these properties:

Here time means either T₁ or T_∞, depending on context, so to explain the generic math an unadorned T will be used.

Let T (N) denote the time required to execute a divide-and-conquer algorithm with the aforementioned properties. The recurrence relations will be:

There are three asymptotic solutions to this recurrence:

8.1

8.2

8.3

None of the solutions mentions c or e directly—those are scale factors that disappear in the Θ notation. What is important is the value of log_ba relative to d.

The intuition behind these solutions is as follows. A full proof is given in Cormen et al. [CLRS09]. Start by partitioning the program’s recursive call tree level by level, with the levels labeled, from top to bottom, as N, N/b, N/b², N/b³, and so on. The three cases in the solution correspond to which levels dominate the work. Let r be the work at level N/b divided by the work at level N. Each problem has a subproblems that are proportionately smaller by 1/b. Each problem will require cN^d work itself and have a children requiring c(N/b)^d work on the next level down. So, . Three distinct cases arise, as illustrated in the diagrams in Figure 8.6 for some specific values of a and b, with c = d = e = 1. The general cases and their corresponding illustrations are:

A useful intuition for effective parallelization can be drawn from these general notions. Ideally, the subproblems are independent and can be computed in parallel, so only one of the subproblems contributes to T_∞. So a = 1 in the recurrences for T_∞, and consequently . Since for any real program, only two of the closed-form solutions apply to T_∞:

Thus, for divide-and-conquer algorithms that fit our assumptions, T_∞ can be logarithmic at best, and only if the divide and combine steps take constant time.

Sometimes, as for the Merge Sort in Chapter 13, constant-time divide and combine is not practical, but logarithmic time is. The recurrences for such algorithms replace the cN^d term with a more complicated term and are beyond the scope of this discussion. See Cormen et al. [CLRS09] for a more general form of the recurrences and their closed-form solution, and Akra and Bazzi [AB98] for an even more general form.

8.7 Karatsuba Multiplication of Polynomials

Polynomial multiplication serves as an example of applying the the Master method to real code. Before delving into the fork–join algorithm and its analysis, let’s consider the basic flat algorithm for multiplying polynomials A and B, each with n coefficients. The flat algorithm is essentially grade-school multiplication, except no carries propagate between terms. Listing 8.5 shows the flat algorithm implemented with Cilk Plus array notation.

Input arrays a and b each hold n coefficients of polynomials A and B, respectively. Output array c holds the coefficients of the output polynomial C.

The flat algorithm is concise and highly parallel for large n, but unfortunately creates Θ(n²) work. Karatsuba’s multiplication algorithm is a fork–join alternative that creates much less work. A slightly different form of it is sometimes used for multiplying numbers with hundreds of digits. Both forms are based on the observation that can be expanded to using only three multiplications:

The final expansion can be calculated as . Each of the three multiplications can be done by recursive application of Karatsuba’s method. The recursion continues until the multiplications become so small that the flat algorithm is more efficient.

The interpretation of K depends on the meaning of multiplication:

For example, to do the radix 10 multiplication problem 1234 ⋅ 5678, K is initially 100, so the problem can be written as . The three requisite multiplications are:

Each of these can be done via Karatsuba’s method with K = 10. Carry propagation can be deferred to the very end or done on the fly using carry-save addition.

Listing 8.6 shows Cilk Plus code for Karatsuba multiplication. Translation to TBB is a matter of using task_group instead of cilk_spawn/cilk_sync, and it is possible to translate this code to OpenMP using tasking constructs.

The parameters are similar to those in Listing 8.5. The type temp_space, described in more detail in Section 8.7.1, holds scratch space for computing . The statements conditional on n&1 do a little extra work required for odd-length sequences and can be ignored to get the general idea of the algorithm.

A coding point worth mentioning is that is computed separately before adjusting the final product in c. The reason why is that t₀ and t₂ are stored in array c. It would be incorrect to merge lines 22 and 25 into a single line like this:

c[m:2∗m-1] += t[0:2∗m-1] - c[0:2∗m-1] - c[2∗m:2∗ m-1]; // Wrong!

because then there would be partial overlap of the source and destination array sections. No overlap or exact overlap is okay, but partial overlap causes undefined behavior as explained in Section B.8.5. Line 27 avoids the partial overlap issue because ; thus, the array sections c[3∗m-1:2] and c[4∗m-1:2] never overlap.

To use the code for n-digit integer multiplication, make T an integral type large enough to hold n products of digits. Do the convolution, and then normalize the resulting numeral by propagating carries.

The extra work for when N is odd is insignificant, so assume N is even. Serial execution recurses on three half-sized instances. The additions and subtractions take time linear in N. The relations for T₁ are:

This is case 1 in the Master method. Plugging in the closed-form solution yields:

The recurrence relations for T_∞ differ in the coefficient. There are three subproblems being solved in parallel. Since they are all similar, T_∞ is as if two of the subproblems disappeared, because their execution overlaps solution of the other subproblem. So the recurrence is:

This is case 3, with solution

The speedup limit is , so the speedup limit grows a little faster than .

The formulae also enable a ballpark estimate for a good parallel base case. We want the base case to have at least 1000 operations for Cilk Plus. Since the operation count grows as , that indicates that n = 100 is the right order of magnitude for the parallel base case.

The space complexity of Karatsuba multiplication can also be derived from recurrences. Let be the space for serial execution. The recurrence for is

This is case 3, with solution .

Finally, consider , the space required if an infinite number of threads were available:

which has the solution . Though a machine with an infinite number of threads is theoretical, there is a real, practical lesson here: Parallelizing divide-and-conquer by creating a new thread for each spawn can result in an exponential space explosion. Fortunately, there is a better way. As Section 8.5 shows, Cilk Plus work-stealing guarantees that , which enables Karatsuba multiplication to run in space , much better than exponential space.

8.8 Cache Locality and Cache-Oblivious Algorithms

Although work and span analysis often illuminates fundamental limits on speedup, it ignores memory bandwidth constraints that often limit speedup. When memory bandwidth is the critical resource, it is important to reuse data from cache as much as possible instead of fetching it from main memory. Because the size of caches and the number of levels of cache vary between platforms, tailoring algorithms to cache properties can be complicated. A solution is a technique called cache-oblivious programming. It is really cache-paranoid programming because the code is written to work reasonably well regardless of the actual structure of the cache. In practice, there are possibly multiple levels of cache, and when you write the code you are oblivious to their actual structure and size.

Optimizing for an unknown cache configuration sounds impossible at first. The trick is to apply recursive divide-and-conquer, resulting in good data locality at multiple scales. As a problem is chopped into finer and finer pieces, eventually a piece fits into outer-level cache. With further subdivision, pieces may fit into a smaller and faster cache.

An example of cache-oblivious programming is dense matrix multiplication. The obvious non-recursive code for such multiplication uses three nested loops. Although choosing the right loop order can help somewhat, for sufficiently large matrices the three-loop approach will suffer when the matrices do not fit in cache. The cache-oblivious algorithm divides a matrix multiplication into smaller matrix multiplications, until at some point the matrices fit in cache. Better yet, the divide-and-conquer structure gives us an obvious place to insert fork–join parallelism.

Assume that A, B, and C are matrices, and we want to compute . A divide-and-conquer strategy is:

There are three ways to do the division, based on the following three identities:

8.4

8.5

8.6

Choosing the identity that splits the longest axis is a good choice, because then the submatrices will tend toward being square. That tends to maximize cache locality during multiplication.²

To see this, suppose A has dimensions m × k, and B has dimensions k × n. The total work T₁ to multiply the matrices is O (m n k). The total space S to hold all three matrices is . This sum is minimal for a given product m n k when m = n = k. Hence, striving to make the matrices square improves the chance that the result fits within some level of cache.

Listing 8.8 shows a pseudocode implementation. The informal notations rows(X) and cols(X) denote the number of rows and columns, respectively, of a matrix X. The first two recursive pairs of calls do parallel fork–join. They can be written in TBB using tbb::parallel_invoke. They are safe to execute in parallel because they update separate parts of matrix C. But the last recursive pair cannot execute in parallel, because both calls update the same matrix.

Since the last case is serial and equivalent to a single MultiplyAdd, it is tempting to write MultiplyAdd in a way that uses only the first two of our splitting identities. Doing so would not affect the parallelism but could seriously raise consumption of memory bandwidth. To see this, consider what would happen in the base case: A and B would be very skinny, with A wide and B tall. In extreme, A would be an m-element column matrix and B would be an n-element row matrix. Their product would be an m × n matrix, requiring one store to memory for each multiplication.

The asymptotic complexity is:

8.7

For practical purposes, rows(B) is usually much larger than either of the lg factors, so the speedup limit is ; that is, the speedup is proportional to the size of the output matrix. To see this directly from the code, observe that the code is essentially doing a fork–join recursion over the output matrix and computing inner products for each output element. Thus, it is asymptotically equivalent to computing each element of C in parallel. But writing the code to directly do that would result in poor cache behavior, because each inner product would be consuming an entire row of A and column of B at once.

It is possible to raise the speedup limit by using temporary storage, so that the serial pair of recursive calls can run in parallel, like this:

Matrix tmp = [0];

cilk_spawn MultiplyAdd(C, A0, B0);

MultiplyAdd(tmp, A1, B1); // No spawn

C += tmp;

Then , which is significantly lower than the bound in Equation 8.7. However, in practice the extra operations and memory bandwidth consumed by the final += make it a losing strategy in typical cases, particularly if the other fork–join parts introduce sufficient parallelism to keep the machine busy. In particular, the extra storage is significant. For example, suppose the top-level matrices A and B are square N × N matrices. The temporary is allocated every time the inner dimension splits. So the recurrences for the serial execution space S are:

which has the solution:

Since Cilk Plus guarantees that , the space is at worst . That is far worse than the other algorithm, which needs no temporary matrices and thus requires only space.

There are other recursive approaches to matrix multiplication that reduce T₁ at the expense of complexity or space. For example, Strassen’s method [Str69] recurses by dividing A, B, and C each into quadrants and uses identities similar in spirit to Karatsuba multiplication, such that only 7 quadrant multiplications are required, instead of the obvious 8. Strassen’s algorithm runs in for multiplying matrices, and the quadrant multiplications can be computed in parallel.

8.9 Quicksort

Quicksort is a good example for studying how to parallelize a non-trivial divide-and-conquer algorithm. In its simplest form, it is naturally expressed as a recursive fork–join algorithm. More sophisticated variants are only partially recursive. This section will show how parallel fork–join applies to both the simple and sophisticated variants, demonstrating certain tradeoffs.

Serial Quicksort sorts a sequence of keys by recursive partitioning. The following pseudocode outlines the algorithm:

void Quicksort( sequence ) {

 if( sequence is short ) {

  Use a sort optimized for short sequences

 } else {

  //Divide

  Choose a partition key K from the sequence.

  Permute the sequence such that:

   Keys to the left of K are less than K.

   Keys to the right of K are greater than K.

  //Conquer

  Recursively sort the subsequence to the left of K.

  Recursively sort the subsequence to the right of K.

 }

}

The two subsorts are independent and can be done in parallel, thus achieving some speedup. As we shall see, the speedup will be limited by the partitioning step.

The Quicksort examples all share the code shown in Listing 8.9, which defines the divide step. Issues for writing a good serial Quicksort carry over into its parallel counterparts. Two points of the code so far that are worth noting are:

The Cilk Plus and TBB versions of Quicksort are largely similar. The difference is in the details of how the parallel conquer part is specified.

8.10 Reductions and Hyperobjects

The recursive implementation of the map pattern can be extended to do reduction. Listing 8.14 shows such an extension of Listing 8.1 for doing a sum reduction of f (i) for i from lower (inclusive) to upper (exclusive).

The approach extends to any operation that is associative, even if the operation is not commutative.

Using explicit fork–join for reduction is sometimes the best approach, but other times it can be a nuisance on several counts:

Cilk Plus hyperobjects are an elegant way to avoid these drawbacks. A hyperobject is an object for which each Cilk Plus strand gets its own view. A strand is a portion of Cilk Plus execution with no intervening fork or join points. The hyperobjects described here are called reducers because they assist doing reductions. There are other kinds of hyperobjects, such as holders and splitters, that are sometimes useful, too [FHLLB09]. Listing 8.15 shows a simple example of using a hyperobject to avoid a race.

If sum were an ordinary variable of type float, the invocations of f(1) and f(2) could race updating it and not have the correct net effect, but the code is safe because variable sum is declared as a reducer. The calls f(1) and f(2) are on different strands and so each gets its own view of sum to update.

The summation of the two views happens automatically at the cilk_sync. The Cilk Plus runtime knows to add the views because sum was declared as a reducer_opadd. Method get_value gets the value of the view. It is a method, and not an implicit conversion, so you have to be explicit about getting the value. Be sure that all strands that contribute to the value are joined before getting the value; otherwise, you may get only a partial sum.

There are other reducers built into Cilk Plus for other common reduction operations. For instance, reducer_opxor performs exclusive OR reduction. Section B.7 lists the predefined reducers. You can define your own reducer for any data type and operation that form a mathematical monoid, which is to say:

For example, the data type of strings forms a monoid under concatenation, where the identity element is the empty string. Cilk Plus provides such a reducer for C++ strings, called reducer_basic_string. Section 11.2.1 walks through the steps of building your own reducer.

Generating many views would be inefficient, so there are internal optimizations that reduce the number of views constructed. These optimizations guarantee that no more than 3P views of a hyperobject exist at any one time, where P is the total number of workers. Furthermore, new views are generated lazily, only when a steal occurs. Since steals are rare in properly written Cilk Plus code, the number of views constructed tends to be low.

Figure 8.7 illustrates this point for the example from Listing 8.15. Views are distinguished by subscripts. The left graph shows the stolen case and how only one new view has to be created. Initially variable sum has a single view sum₁. If the continuation that calls f(2) is stolen, Cilk Plus creates a new view sum₂ and initializes it to T(), which by convention is assumed to be the identity element. The other strand after the fork uses sum₁ instead of constructing a new view. Now f(1) and f(2) can safely update their respective views. At the join point, sum₂ is folded into sum₁, and (not pictured) destroyed. Afterwards, sum₁ has the intended total.

The right graph shows the unstolen case, in which no new views have to be created. Since the calls f(1) and f(2) run consecutively, not in parallel, a single view sum₁ suffices. This is another demonstration of a general principle behind Cilk Plus: Extra effort for parallelism is expended only if the parallelism is real, not merely potential parallelism.

Hyperobjects are handy because they are not lexically bound to parallelism constructs. They can be global variables that are updated by many different strands. The runtime will deal with reducing the updates into final correct value.

Hyperobjects are also useful as local variables, as shown in Listing 8.16, which is another way to implement the reduction from Listing 8.14.

It is important to remember that hyperobjects eliminate races between strands of Cilk Plus execution, not races between arbitrary threads. If multiple threads not created by the Cilk Plus runtime do concurrently access a hyperobject, they will race and thus possibly introduce non-determinism.

8.11 Implementing Scan with Fork–Join

This section shows how to use fork–join to implement the scan pattern using the interface presented in Section 5.4. The code examples are Cilk Plus. The TBB template parallel_scan uses a similar implementation technique but with a twist described later.

The parallel scan algorithm [Ble93] operates as if the data are the leaves of a tree as shown in Figure 8.8. In the picture, the input consists of the sequence and an initial value initial, and the output sequence is an exclusive scan . The algorithm makes two sweeps over the tree, one upward and one downward. The upsweep computes a set of partial reductions of the input over tiles. The downsweep computes the final scan by combining the partial reduction information. Though the number of tiles in our tree illustration is a power of two, the example code works for any number of tiles.

Figure 8.9 shows the internal structure of a tree node. Let ⊕ denote the combiner operation. The term subscan here means a subsequence of the final scan sequence. The node shown computes values related to the subscan for . The subsequence is split into two halves: a leading subsequence of k elements and a trailing subsequence of elements. Let denote a reduction over m consecutive elements of the sequence, starting at index i. During the upsweep, the node computes . Let denote the initial value required for computing the subscan starting at index i. In other words, . During the downsweep, the node gets from its parent, passes it downward, and computes . These are the initial values for computing the subscans for the two half subsequences.

The tree computes an untiled exclusive scan. A tiled exclusive scan for an operation ⊕ can be built from it as follows. Label the tiles b₁, b₂, …, b_N−1. Conceptually, the steps are:

In practice, Steps steps 1 and and 3 are not separate passes, but embedded into the upsweep and downsweep passes, respectively. For an inclusive scan, change the last step to be an inclusive scan over each tile.

Listing 8.17 shows the top-level code for a tiled scan. The parameters are explained in Section 5.4 on page 164. As noted in that section, the reduction is done for the last tile even though its return value is unnecessary in order to permit fusion optimization.

Listing 8.18 shows the code for routine upsweep. It performs the upsweep for the index range i:m. The base case invokes the tile reduction functor reduce. The recursive case chooses where to split the index space, using function split (not shown), which should return the greatest power of two less than m:

The function serves to embed an implicit binary tree onto the index space. The if at the end of routine upsweep checks whether there is a tree node summarizing the index space. When m is not a power of two, there is no such node. Conceptually the missing node is for summarizing an index space larger than the requested space.

Listing 8.19 shows the code for routine downsweep. Most of the parameters are similar to those in the other routines. Parameter lastsize is the size of the rightmost tile, which might be a partial tile. Its structure closely resembles the structure of upsweep because it is walking the same tree, only it does its real work before the fork, not after the join as in upsweep. Consequently, tail recursion optimization (Section 8.3) can be applied to downsweep but not upsweep.

The work is proportional to the number of nodes in the tree, and the span is proportional to the height of the tree. So the asymptotic work-span bounds are

Unfortunately the asymptotic bounds hide a constant factor of 2 in the work, and in practice this factor of 2 can undo much of the gains from parallelization. A serial scan makes a single pass over the data, but a parallel scan makes two passes: upsweep and downsweep. Each pass requires reading the data. Hence, for large scans where data does not fit in cache, the communication cost is double that for a serial scan. Therefore, when communication bandwidth is the limiting resource for a serial scan, a parallel scan will run half as fast. Even if it does fit in the total aggregate cache, there is a communication problem, because greedy scheduling arbitrarily assigns workers to the tile reductions and scan reductions. Thus, each tile is often transferred from the cache of the worker who reduced it to the cache of the worker who scans it.

The implementation of TBB’s tbb::parallel_scan attempts to mitigate this issue through a trick that dynamically detects whether actual parallelism is available. The TBB interface requires that each tile scan return a reduction value as well. This value is practically free since it is computed during a scan anyway. During the upsweep pass, the TBB implementation uses the tile scan instead of a reduction whenever it has already computed all reductions to the left of the tile. This enables skipping the downsweep pass for all tiles to the left of all tiles processed by work-stealing thieves. In other words, execution is equivalent to a tiled serial scan until the point is reached where actual parallelism forks the control flow. This way, if two workers are available, typically only the right half of the tree needs two passes, thus averaging 1.5 passes over the data. For more available workers, the benefit starts to diminish. The trick is dynamic—tbb::parallel_scan pays the 2× overhead for parallelism only if actual parallelism is being applied to the scan.

One elegant feature of our Cilk Plus interface for scan is that sometimes the scan values can be consumed without actually storing them. For example, consider implementing the pack pattern using a scan followed by a conditional scatter, as described in Section 6.4. Listing 8.20 shows the code.

It fills an array b with the elements of array a that satisfy predicate p and returns the number of such elements found. It calls parallel_scan to compute a running sum of how many elements satisfy predicate p. A standalone scan of the sum operation would have to store the partial sums in an array. That is not necessary here, because each partial sum is consumed immediately by the assignment b[sum++] − a[j].

The scan tree in Figure 8.8 generalizes to trees of higher degree. For an N-ary scan tree, the node performs an N-ary serial reduction during the upsweep and an N-element serial exclusive scan on the downsweep. Indeed, some implementations do away with recursion altogether and use a single serial scan, as was shown by the OpenMP implementation of scan in Section 5.4. That saves synchronization overhead at the expense of increasing the span. If such a degenerate single-node tree is used for a tiled scan with tiles of size , the span is . Though not as good as the span using a binary tree, it is an improvement over the time for a serial scan, and constant factors can put it ahead in some circumstances.

8.12 Applying Fork–Join to Recurrences

Recurrences, described in Section 7.5, result when a loop nest has loop-carried dependencies—that is, data dependencies on outputs generated by earlier iterations in the serial execution of a loop. We explained how this can always be parallelized with a hyperplane sweep. However, sometimes a recurrence can also be evaluated using fork–join by recursively partitioning the recurrence, an approach that can have useful data locality properties. This section explores some tradeoffs for recursive partitioning.

For example, consider the “binomial lattice” recurrence in Figure 8.10. For the sake of a familiar example, the values shown are binomial coefficients, organized as in Pascal’s triangle. However, this particular pattern of dependencies shows up in far more sophisticated applications such as pricing models for stock options, infinite impulse response image processing filters, and in dynamic programming problems. A good example of the last is the Smith–Waterman algorithm for sequence alignment, which is used extensively in bioinformatics [SW81].

This data dependency graph is an obvious candidate for the superscalar or “fire when ready” approach, but using this approach would give up the locality and space advantages of fork–join. A recursive fork–join decomposition of this recurrence will be explored as an alternative, and its advantages and disadvantages analyzed.

Consider a diamond-shaped subgraph where the number of points along an edge is a power of two, such as the example in Figure 8.11. The diamond can be decomposed into four subdiamonds, labeled D₀, D₁, D₂, and D₃. Diamonds D₂ and D₃ can be evaluated in parallel. Furthermore, the same approach can be applied recursively to the four subdiamonds.

The parallel base case occurs when the current diamond is so small that fork–join overheads become significant. At that point, vector parallelism can be exploited by serially iterating over the diamond from top to bottom and computing each row of points in parallel.

Here is a pseudocode sketch for the recursive pattern:

void recursive_diamond( diamond D) {

 if(D is small ) {

  base_diamond(D);

 } else {

  divide D into subdiamonds D₀, D₁, D₂, D₃;

  recursive_diamond(D₀);

  cilk_spawn recursive_diamond(D₁);

  /* nospawn */recursive_diamond(D₂);

  cilk_sync;

  recursive_diamond(D₃)

 }

}

The effort for turning this sketch into efficient code mostly concerns manipulation of memory. There is a fundamental tradeoff between parallelism and worst-case memory space, because in order to avoid a race operations occurring in parallel must record their results into separate memory locations. For the binomial lattice, one extreme is to use a separate memory location for each lattice point. This is inefficient. For a diamond with a side of width w, it requires space.

At the other extreme, it is possible to minimize space by mapping an entire column of lattice points to a single memory location. Unfortunately this mapping requires serial execution, to avoid overwriting a location with a new value before all uses of its old value complete, as shown below:

void base_diamond( diamond D) {

 for each row R in D do

  for each column i in row R from right to left

   A[i]=f(A[i-1],A[i]);

}

This serialization extends to the recursive formulation: Diamond D₁ must be evaluated before D₂, and hence fork–join parallelism could not be used.

The solution is to double the space and have two locations for each lattice point. Organize the locations into two arrays, A and B. A location in array A corresponds to a column of the lattice. A location in array B corresponds to a diagonal of the lattice. Subscripts for B start at zero and go downward for the sake of improving vectorization of the base case, as explained later.

Figure 8.12 shows the parameterized description of a diamond subgraph:

Listing 8.21 shows the code for the row updates, using vector parallelism across each row. The two vector updates can in theory be chained together. However, at the time of writing, Cilk Plus did not allow chaining of such assignments, though they will be allowed in the future.

With a positive coordinate convention for B, the vector update would look something like:

as[0:m] = f(bs[0:m:-1], as[0:m]);

bs[0:m:-1] = as[0:m];

with pointer bs being calculated slightly differently. Though the code would work, it would be less efficient because the compiler would have to insert permutation instructions to account for the fact that as and bs have strides in different directions.

Listing 8.22 shows the rest of the code. It assumes that only the topmost diamond is clipped.

One final note: Additional performance can be gained by turning off denormalized floating point (“denormals”) numbers. Their use can severely impact performance. Floating point numbers consist of a mantissa and exponent; the normalized format has a mantissa that always has a leading one (value = 1.mantissa^exponent), whereas a denormalized format has a leading zero (value = 0.mantisssa^exponent). Denormalized floating point numbers are so small (close to zero) that the exponent would underflow in the normal representation without this additional “denormal” format. Denormalized numbers help preserve important algebraic properties such as the equivalence of the equality tests x − y = 0 and x = y. Alas, denormalized numbers often require extra cycles to process. A common case of f in our example is a function that averages its inputs, which will result in the output being a bell curve. The tails of the curve will have values that asymptotically approach zero and consequently contain many denormalized floating-point values. Using options that flush denormalized numbers to zero, such as /Qftz with the Intel compiler, can greatly improve the performance of this example. This is very useful if the value of the extra numerical range is not worth the performance loss to your program. It is common to use such flush-to-zero options in high-performance code.

8.13 Summary

In this chapter we presented the fork–join pattern, which is a natural fit for parallel divide-and-conquer algorithms. Parallel divide-and-conquer generates independent subproblems, solves them in parallel, and then combines the results. Algorithms based on recursive divide-and-conquer often have very good space behavior, locality, and load-balancing properties when executed by a fork–join implementation that uses work-stealing. Speedup may, however, be limited by the speed of the divide or combine steps or by uneven division of work.

We presented the Master method for computing the asymptotic complexity of the work and span. These can be used to predict the speedup of a divide-and-conquer algorithm. Karatsuba polynomial multiplication and Quicksort were given as examples, which also demonstrated practical issues with memory allocation.

Cache-oblivious algorithms using matrix multiplication as an example were discussed, and we also presented fork–join implementations of scan and the binomial lattice recurrence.