5.1.1 Reordering Computations

To parallelize reduction, we have to reorder the operations used in the serial algorithm. There are many ways to do this but they depend on the combiner function having certain algebraic properties.

To review some basic algebra, a binary operator is considered to be associative or commutative if it satisfies the following equations:

Associativity and commutativity are not equivalent. While there are common mathematical operations that are both associative and commutative, including addition; multiplication; Boolean AND, OR, and XOR; maximum; and minimum (among others), there are many useful operations that are associative but not commutative. Examples of operations that are associative but not commutative include matrix multiplication and quaternion multiplication (used to compose sequences of 3D rotations). There are also operations that are commutative but not associative, an example being saturating addition on signed numbers (used in image and signal processing). More seriously, although addition and multiplication of real numbers are both associative and commutative, floating point addition and multiplication are only approximately associative. Parallelization may require an unavoidable reordering of floating point computations that will change the result.

To see that only associativity is required for parallelization, consider the following:

The first grouping shown is equivalent to the left half of Figure 5.1, the second grouping to the right right half of Figure 5.1. Another way to look at this is that associativity allows us to use any order of pairwise combinations as long as “adjacent” elements are intermediate sequences. However, the second “tree” grouping allows for parallel scaling, but the first does not.

A good example of a non-associative operation is integer arithmetic with saturation. In saturating arithmetic, if the result of an operation is outside the representable range, the result is “clamped” to the closest representable value rather than overflowing. While convenient in some applications, such as image and signal processing, saturating addition is not associative for signed integers.

The following example shows that saturating addition is not associative for signed bytes. Let ⊕ be the saturating addition operation. A signed byte can represent an integer between −128 and 127 inclusive. Thus, a saturating addition operation 120 ⊕ 78 yields 127, not 198. Consider reduction with ⊕ of the sequence [120, 78, −90, −50]. Serial left-to-right order yields:

Tree order yields a different result:

In contrast, modular integer addition, where overflow wraps around, is fully associative. A result greater than 127 or −128 is brought in range by adding or subtracting 256, which is equivalent to looking at only the low-order 8 bits of the binary representation of the algebraic result. Here is the serial reduction with modular arithmetic on signed bytes:

Tree ordering gives the same result:

5.1.2 Vectorization

There are useful reorderings that also require commutativity. For example, suppose we want to vectorize a reduction on a processor with two-way SIMD instructions. Then we might want to combine all the even elements and all the odd elements separately, as in Figure 5.2, then combine the results. However, this reordering requires commutativity:

Note that a₁ and a₂ had to be swapped before we could group the operations according to this pattern.

5.1.3 Tiling

In practice, we want to tile¹ computations and use the serial algorithm for reduction when possible. In a tiled algorithm, we break the work into chunks called tiles (or blocks), operate on each tile separately, and then combine the results. In the case of reduce, we might want to use the simple serial reduce algorithm within each tile rather than the tree ordering. This is because, while the tree and serial reduce algorithms use the same number of applications of the combiner function, the simplest implementation of the tree ordering requires O (n) storage for intermediate results while the serial ordering requires only O (1) storage.

This is shown in Figure 5.3 for 16 inputs with four tiles of four inputs each, followed by a “global reduction” with four inputs. In practice, since synchronization is expensive, it is common for reductions to have only two phases: a local phase over tiles and a global phase combining the results from each tile. We may also use a vectorized implementation within the tiles as discussed in Section 5.1.2, although this usually requires further reordering.

5.1.4 Precision

Another issue can arise with large reductions: precision. Large summations in particular have a tendency to run out of bits to represent intermediate results. Suppose you had an array with a million single-precision floating point numbers and you wanted to add them up. Assume that they are all approximately the same magnitude. Single-precision floating point numbers only have about six or seven digits of precision. What can happen in this scenario if the naïve serial algorithm is used is that the partial sum can grow very large relative to the new values to be added to it. If the partial sum grows large enough, new values to it will be less than the smallest representable increment and their summation will have no effect on the accumulator. The increments will be rounded to zero. This means that part of the input will effectively be ignored and the result will of course be incorrect.

The tree algorithm fares better in this case. If all the inputs are about the same size, then all the intermediate results will also be about the same size. This is a good example of how reassociating floating point operations can change the result. Using a tiled tree will retain most of the advantages of the tree algorithm if the tiles and the final pass are of reasonable sizes.

The tree algorithm is not perfect either, however. We can invent inputs that will break any specific ordering of operations. A better solution is to use a larger precision accumulator than the input. Generally speaking, we should use double-precision accumulators to sum single-precision floating point inputs. For integer data, we need to consider the largest possible intermediate value.

Converting input data to a higher-precision format and then doing a reduce can be considered a combination of a map for the conversion and a reduce to achieve the higher-precision values. Fusion of map and reduce for higher performance is discussed in Section 5.2.

5.1.5 Implementation

Most of the the programming models used in this book, except OpenCL, include various built-in implementations of reduce. TBB and Cilk Plus in addition support reduce with user-defined combiner functions. However, it your responsibility to ensure that the combiner function provided is associative. If the combiner function is not fully associative (for example if it uses floating point operations), you should be aware that many implementations reassociate operations non-deterministically. When used with combiner functions that are not fully associative, this can change the result from run to run of the program. At present, only TBB provides a guaranteed deterministic reduce operation that works with user-defined combiner functions that are not fully associative.

5.2.1 Explicit Fusion in TBB

The map and reduce patterns can be fused together in TBB by combining their implementations and basically combining the first step of the reduce implementation with some preprocessing (the map) on the first pass. In practice, this can be accomplished through appropriate use of the tiled reduction constructs in TBB, as we show in Section 5.3.4.

5.2.2 Explicit Fusion in Cilk Plus

In Cilk Plus map and reduce can be fused by combining their implementations. The map and initial stages of the reduce can be done serially within a tile, and then the final stages of the reduce can be done with hyperobjects. We show an example of this in Section 5.3.5.

5.2.3 Automatic Fusion in ArBB

A map followed by a reduce is fused automatically in ArBB. You do not have to do anything special, except ensure that the operations are in the same call. Technically, ArBB does a code transformation on the sequence of operations that within serial code generation is often called loop fusion. In ArBB, however, it is applied to parallel operations rather than loop iterations.

The map and reduce operations do not have to be adjacent in the program text either, as opportunities for fusion are found by analyzing the computation’s data dependency graph. The system will also find multiple fusion opportunities—for example, a map followed by multiple different reductions on the same data. If the output of the map is the same shape as that used by the reduce operations, the fusion will almost always happen. However, intermediate random-memory access operations such as gather and scatter will inhibit fusion, so they should be used with this understanding.

ArBB does not currently provide a facility to allow programmers to define their own arbitrary combiner functions for reductions. Instead, complex reductions are built up by fusing elementary reductions based on basic arithmetic operations that are known to be associative and commutative.

5.3.1 Description of the Problem

Given two vectors (1D arrays) a and b each with n elements, the dot product is a scalar given by:

where a_i and b_i denote the ith elements of a and b, respectively. Subscripts run from 0 to n − 1 as usual in C and C++.

It is unlikely that a scalable speedup will be obtained when parallelizing such a simple computation. As with SAXPY in Section 4.2, a simple operation such as dot product is likely to be dominated by memory access time. The dot product is also the kind of computation where calling a library routine would probably be the best solution in practice, and tuned implementations of the dot product do indeed appear in BLAS libraries. However, dot product is simple and easy to understand and also shows how a map can be combined with reduce in practice.

As map and reduce are a common combination, you can use these examples as templates for more complex applications. We will also use this example to demonstrate some important optimizations of this combination without getting caught up in the complexities of the computation itself.

5.3.2 Serial Implementation

For reference, a serial implementation of dot product is provided in Listing 5.3. There is nothing special here. However, note that the usual serial expression of reduce results in loop-carried dependencies and would not be parallelizable if implemented in exactly the order specified in this version of the algorithm. You have to recognize, abstract, and extract the reduce operation to parallelize it. In this case, the serial reduce pattern is easy to recognize, but when porting code you should be alert to alternative expressions of the same pattern.

This example assumes that n is small, so the reduction accumulator can have type float. For large reductions this is unwise since single-precision floating point values may not be able to represent partial sums with sufficient precision as explained in Section 5.1.4. However, the same type for the accumulator, the input, and the output has been used in order to simplify the example. In some of the implementations we will show how to use a different type for performing the accumulations.

5.3.3 SSE Intrinsics

Listing 5.4 gives an explicitly vectorized version of the dot product computation. This example uses SSE intrinsics. SSE stands for Streaming SIMD Extensions and is an instruction set extension supported by Intel and AMD processors for explicitly performing multiple operations in one instruction. It is associated with a set of registers that can hold multiple values. For SSE, these registers are 128 bits wide and can store two double-precision floating point values or four single-precision floating point values.

When using SSE intrinsics, special types are used to express pairs or quadruples of values that may be stored in SSE registers, and then functions are used to express operations performed on those values. These functions are recognized by the compiler and translated directly into machine language.

Use of intrinsics is not quite as difficult as writing in assembly language since the compiler does take care of some details like register allocation. However, intrinsics are definitely more complex than the other programming models we will present and are not as portable to the future. In particular, SIMD instruction sets are subject to change, and intrinsics are tied to specific instruction sets and machine parameters such as the width of vector registers.

For (relative) simplicity we left out some complications so this example is not really a full solution. In particular, this code does not handle input vectors that are not a multiple of four in length.

Some reordering has been done to improve parallelization. In particular, this code really does four serial reductions at the same time using four SSE register “lanes”, and then combines them in the end. This uses the implementation pattern for reduce discussed in Section 5.1.2, but with four lanes. Like the other examples that parallelize reduce, some reordering of operations is required, since the exact order given in the original serial implementation is not parallelizable. This particular ordering assumes commutativity as well as associativity.

Other problems with the SSE code include the fact that it is machine dependent, verbose, hard to maintain, and it only takes advantage of vector units, not multiple cores. It would be possible to combine with code with a Cilk Plus or TBB implementation in order to target multiple cores, but that would not address the other problems. In general, machine dependence is the biggest problem with this code. In particular, new instruction set extensions such as AVX are being introduced that have wider vector widths, so it is better to code in a way that avoids dependence on a particular vector width or instruction set extension.

5.3.4 TBB

Listing 5.5 uses TBB’s algorithm template parallel_reduce. This template recursively decomposes a reduction into smaller subreductions and reduces each base case using a functor provided by the user. Here that functor uses std::inner_product to do serial reduction, which the compiler may be able to automatically vectorize. The base case code can also be used for map–reduce fusion, as done here: the std::inner_product call in the base case does both the multiplications and a reduction over the tile it is given. The user must also provide a functor to combine the results of the base cases, which here is the functor std::plus<float>.

The template parallel_reduce also requires the identity of the combiner function. In this case, the identity of floating point addition is float(0). Alternatively, it could be written as 0.f. The f suffix imbues the constant with type float. It is important to get the type right, because the template infers the type of the internal accumulators from the type of the identity. Writing just 0 would cause the accumulators to have the type of a literal 0, which is int, not the desired type float.

The template parallel_reduce implements a flexible reduce pattern which can be instantiated in a variety of ways. For example, Listing 5.6 shows an instantiation that does accumulation using a precision higher than the type of the input, which is often important to avoid overflow in large reductions. The type used for the multiplication is also changed, since this is a good example of a fused map operation. These modifications change float in Listing 5.5 to double in several places:

5.3.5 Cilk Plus

Listing 5.7 expresses the pairwise multiplication and reduction using Cilk Plus array notation. A good compiler can generate code from it that is essentially equivalent to the hand-coded SSE in Listing 5.4, except that the Cilk Plus version will correctly handle vector widths that are not a multiple of the hardware vector width. In fact, it is not necessary to know the hardware vector width to write the Cilk Plus code. The Cilk Plus code is not only shorter and easier to understand and maintain, it’s portable.

An explicitly thread parallel and vector parallel dot product can be expressed as shown in Listing 5.8. The variable res has a special type called a reducer. Here the reducer res accumulates the correct reduction value even though there may be multiple iterations of the cilk_for running in parallel. Even though the code looks similar to serial code, the Cilk Plus runtime executes it using a tree-like reduction pattern. The cilk_for does tree-like execution (Section 8.3) and parts of the tree executing in parallel get different views of the reducer. These views are combined so at the end of the cilk_for there is a single view with the whole reduction value. Section 8.10 explains the mechanics of reducers in detail.

Our code declares res as a reducer_opadd<float> reducer. This indicates that the variable will be used to perform + reduction over type float. The constructor argument (0) indicates the variable’s initial value. Here it makes sense to initialize it with 0, though in general a reducer can be initialized with any value, because this value is not assumed to be the identity. A reducer_opadd<T> assumes that the identity of + is T(), which by C++ rules constructs a zero for built-in types. The min expression in the code deals with a possible partial “boundary” tile, so the input does not have to be a multiple of the tile size.

Listing 5.8 shows how to modify the reduction to do double-precision accumulation. The casts to double-precision are also placed to result in the use of double-precision multiplication. These casts, like the multiplication itself, are really examples of the map pattern that are being fused into the reduction. Of course, if you wanted to do single-precision multiplication, you could move the cast to after the __sec_reduce_add. Doing the multiplication in double precision may or may not result in lower performance, however, since a dot product will likely be performance limited by memory bandwidth, not computation. Likewise, doing the accumulation in double precision will likely not be a limiting factor on performance. It might increase communication slightly, but for reasonably large tile sizes most of the memory bandwidth used will result from reading the original input.

5.3.6 OpenMP

An OpenMP implementation of dot product is shown in Listing 5.10. In OpenMP, parallelization of this example is accomplished by adding a single line annotation to the serial implementation. However, the annotation must specify that res is a reduction variable. It is also necessary to specify the combiner operator, which in this case is (floating point) addition.

What actually happens is that the scope of the loop specifies a parallel region. Within this region local copies of the reduction variable are made and initialized with the identity associated with the reduction operator. At the end of the parallel region, which in this case is the end of the loop’s scope, the various local copies are combined with the specified combiner operator. This code implicitly does map–reduce fusion since the base case code, included within the loop body, includes the extra computations from the map.

OpenMP implementations are not required to inform you if the loops you annotate have reductions in them. In general, you have to identify them for yourself and correctly specify the reduction variables. OpenMP 3.1 provides reductions only for a small set of built-in associative and commutative operators and intrinsic functions. User-defined reductions have to be implemented as combinations of these operators or by using explicit parallel implementations. However, support for user-defined reductions is expected in a future version of OpenMP, and in particular is being given a high priority for OpenMP 4.0, since it is a frequently requested feature.

5.3.7 ArBB

Listing 5.11 gives the kernel of a dot product in ArBB. This function operates on ArBB data, so the additional code in Listing 5.12 is required to move data into ArBB space, invoke the function in Listing 5.11 with call, and retrieve the result with value. Internally, ArBB will generate tiled and vectorized code roughly equivalent to the implementation given in Listing 5.8.

To avoid overflow in a very large dot product, intermediate results should be computed using double precision. The alternative kernel in Listing 5.13 does this. The two extra data conversions are, in effect, additional map pattern instances. Note that in ArBB multiple maps are fused together automatically as are maps with reductions. This specification of the computation produces an efficient implementation that does not write the intermediate converted high-precision input values to memory.

5.4.1 Cilk Plus

Cilk Plus has no built-in implementation of scan. Section 8.11 shows how to implement it using the fork–join pattern. The interface to that implementation and its characteristics are explained here, however, so we can use it in the example in Section 5.6.

Our Cilk Plus implementation performs a tiled scan. It abstracts scan as an operation over an index space and thus makes no assumptions about data layout. The template interface is:

template<typename T, typename R, typename C, typename S>

void cilk_scan(size_t n, T initial, size_t tilesize,

      R reduce, C combine, S scan);

The parameters are as follows:

The actual access to the data occurs in the reduce and scan functors. The implementation is deterministic as long as all three functors are deterministic.

In principle, doing the reduction for the last tile is unnecessary, since the value is unused. However, not invoking reduce on that tile would prevent executing a fused map with it, so we still invoke it. Note that the results of such an “extra” map tile may be needed later, in particular in the final scan, even if it is not needed for the initial reductions. Technically, the outputs of the map (which need to be stored to memory for later use) is a side-effect, but the data dependencies are all accounted for in the pattern. The Cilk Plus implementation of the integration example in Section 5.6.3 this.

5.4.2 TBB

TBB has a parallel_scan construct for doing either inclusive or exclusive scan. This construct may non-deterministically reassociate operations, so for non-associative operations, such as floating point addition, the result may be non-deterministic.

The TBB construct parallel_scan abstracts scan even more than cilk_scan. It takes two arguments: a recursively splittable range and a body object.

template<typename Range, typename Body>

void parallel_scan(const Range& range, Body& body);

The range describes the index space. The body describes how to do the reduce, combine, and scan operations in a way that is analogous to those described for the Cilk Plus interface.

5.4.3 ArBB

Built-in implementations of both inclusive and exclusive scans are supported, but over a fixed set of associative operations. For the fully associative operations, the results are deterministic. However, for floating point multiplication and addition, which are non-associative, the current implementation does not guarantee the results are deterministic.

5.4.4 OpenMP

OpenMP has no built-in parallel scan; however, OpenMP 3.x tasking can be used to write a tree-based scan similar to the fork–join Cilk Plus code in Section 8.11. In practice, users often write a three-phase scan, which is what we present in this section. The three-phase scan has an asymptotic running time of . When P N, the N/P term dominates the P term and speedup becomes practically linear. For fixed N, the value of NP + P is minimized when .² Thus, the maximum asymptotic speedup is:

Although this is not as asymptotically good as the tree-based scan that takes O(lg N) time, constant factors may make the three-phase scan attractive. However, like other parallel scans, the three-phase scan requires around twice as many invocations of the combiner function as the serial scan.

The phases are:

Figure 5.6 diagrams the phases, and Listing 5.16 shows an OpenMP implementation.

Like many OpenMP programs, this code exploits knowing how many threads are available. The code attempts to use one tile per thread. Outside the parallel region the code computes how many threads to request. The clause num_threads(t) specifies this request. There is no guarantee that the full request will be granted, so inside the parallel region the code recomputes the tile size and number of tiles based on how many threads were granted. Our code would still be correct if it did not recompute these quantities, but it might have a load imbalance and therefore be slower, because some threads would execute more tiles than other threads.

Each phase waits for the previous phase to finish, but threads do not join between the phases. The first and last phases run with one thread per tile, which contributes Θ(NP) to the asymptotic running time. The middle phase, marked with omp single, runs on a single thread. This phase contributes Θ(P) to the running time. During this phase, the other m threads just wait while this phase is running. Making threads wait like this is both good and bad. The advantage is that the threads are ready to go for the third phase, and the mapping from threads to tiles is preserved by the default scheduling of omp for loops. This minimizes memory traffic. The disadvantage is that the worker threads are committed when entering the parallel region. No additional workers can be added if they become available, and no committed workers can be removed until the parallel region completes.

5.6.1 Description of the Problem

Given a function f and interval [a, b], we would like to precompute a table that will allow rapid computation of the definite integral of f over any subinterval of [a, b]. Let . The table is a running sum of samples of f, scaled by Δx:

The integral of f over [c, d] can be estimated by:

where interp(x) denotes linear interpolation on the table.

5.6.2 Serial Implementation

Listing 5.17 shows a serial implementation of the sampling and summation computation. It has a loop-carried dependence, as each iteration of the loop depends on the previous one.

Sometimes you will want to use a generic function defined in a function template as in Listing 5.18. To pass such a function as an argument, it is helpful to first instantiate it with particular types as in Listing 5.19.

Listing 5.20 shows how to compute the definite integral from two samples. It defines a helper function serial_sample that does linearly interpolated lookup on the array. Out of bounds subscripts are handled as if the original function is zero outside the bounds, which implies that the integral is zero to the left of the table values and equal to table[n−1] to the right of the table.

5.6.3 Cilk Plus

Listing 5.21 shows the Cilk Plus code for preparing the integration table. The initial mapping of the function is fused into the functor for doing tile reductions. The final scaling of the scan is fused in the functor for doing tile scans.

Scan is not a built-in operation in Cilk Plus, but we discuss its interface in Section 5.4 and its implementation in Section 8.11.

5.6.4 OpenMP

Listing 5.21 can be translated to OpenMP by making two changes:

The second change is optional, since OpenMP plus Cilk Plus array notation can be an effective way to exploit both thread and vector parallelism. Of course, this requires a compiler that supports both.

Scan is not a built-in operation in OpenMP, but we discuss its implementation using a three-phase approach in Section 5.4.

5.6.5 TBB

The TBB parallel_scan algorithm template has an internal optimization that lets it avoid calling the combiner function twice for each element when no actual parallelism occurs. Unfortunately, this optimization prevents fusing a map with the reduce portion of a scan. Consequently, the TBB implementation of the integration example must compute each sample point on both passes through a tile. The second pass has no easy way to know if the first pass occurred and, so there is no point in the first pass storing the samples. If the samples are expensive to compute, to avoid the extra computation we can precompute the samples and store them in a table before calling the scan. Here we assume the samples are relatively inexpensive to compute.

Listing 5.22 shows the code. In the TBB implementation a single templated operator() serves as both a both tiled reduce and a tiled scan. The idea behind this is that the code may have full or partial information about preceding iterations. The value of the expression tag.is_final_scan() distinguishes these two cases:

The second case occurs only if a thread actually steals work for the parallel_scan.

Method reverse_join merges two states of adjacent subranges. The “reverse” in its name comes from the fact that *this is the state of the right subrange, and its argument is the left subrange. The left subrange can be either a partial state or a full state remaining after a serial scan.

Method assign is used at the very end to update the original Body argument to tbb::parallel_scan with the Body state after the last iteration.

5.6.6 ArBB

Listing 5.23 shows the ArBB code for generating the table and Listing 5.24 shows the ArBB code for computing the integral by sampling this table.

Listing 5.23 uses a special function to generate a set of integers. Vector arithmetic converts these integers into sample positions and then uses a map to generate all the samples. Finally, a scan function computes the cumulative table. The ArBB implementation will actually fuse all these operations together. In particular, the computation of sample positions, the sampling of the function, and the first phase of the scan will be combined into a single parallel operation.

Given the table, the integral can be computed using the function given in Listing 5.24. This function can be used to compute a single integral or an entire set if it is called from a map. This code is practically identical to the serial code in Listing 5.20. The templates take care of most of the type substitutions so the only difference is the use of an ArBB collection for the table.