2. Generic Parallel Algorithms

A well-known example of a recursive divide-and-conquer algorithm is quicksort, as shown in Figure 2-4. Quicksort works by recursively shuffling an array around pivot values, placing the values that are less than or equal to the pivot value in the left partition of the array and the values that are greater than the pivot value in the right partition of the array. When the recursion reaches the base case, arrays of size one, the whole array has been sorted.

We can develop a parallel implementation of quicksort as shown in Figure 2-5 by replacing the two recursive calls to serialQuicksort with a parallel_invoke. In addition to the use of parallel_invoke, we also introduce a cutoff value. In the original serial quicksort, we recursively partition all the way down to arrays of a single element.

To limit overheads in our parallel implementation, we recursively call parallel_invoke only until we dip below 100 elements and then directly call serialQuicksort instead.

A complete description of the interfaces available for parallel_for can be found in Appendix B. In the small example loop, the Range is the half-open interval [0, N), the step is 1, and the Body is f(a[i]). We can express this as shown in Figure 2-6.

When TBB executes a parallel_for, the Range is divided up into chunks of iterations. Each chunk, paired with a Body, becomes a task that is scheduled onto one of the threads that participate in executing the algorithm. The TBB library handles the scheduling of tasks for us, so all we need to do is to use the parallel_for function to express that the iterations of the loop should be executed in parallel. In later chapters, we discuss tuning the behavior of TBB parallel loops. For now, let us assume that TBB generates a good number of tasks for the range size and number of available cores. In most cases, this is a good assumption to make.

It is important to understand that by using a parallel_for, we are asserting that it’s safe to execute the iterations of the loop in any order and in parallel with each other. The TBB library does nothing to check that executing the iterations of a parallel_for (or in fact any of the generic algorithms) in parallel will generate the same results as a serial execution of the algorithm – it is our job as developers to be sure that this is the case when we choose to use a parallel algorithm. In Chapter 5, we discuss synchronization mechanisms in TBB that can be used to make some unsafe code, safe. In Chapter 6, we discuss concurrent containers that provide thread-safe data structures that can also sometimes help us make code thread-safe. But ultimately, we need to ensure when we use a parallel algorithm that any potential changes in read and write access patterns do not change the validity of the results. We also need to ensure that we are using only thread-safe libraries and functions from within our parallel code.

For example, the following loop is not safe to execute as a parallel_for since each iteration depends on the result of the previous iteration. Changing the order of execution of this loop will alter the final values stored in the elements of array a:

Imagine if the array a={1,0,0,0,...,0}. After executing this loop sequentially, it will hold {1,2,3,4,...,N}. But if the loop executes out-of-order, the results will be different. A mental exercise, when looking for loops that are safe to execute in parallel, is to ask yourself whether the results will be the same if the loop iterations are executed all at once, or in random order, or in reverse order. In this case, if a={1,0,0,0,...,0} and the iterations of the loop are executed in reverse order, a will hold {1,2,1,1,...,1} when the loop is complete. Obviously, execution order matters for this loop!

Formal descriptions of data dependence analysis are beyond the scope of this book but can be found in many compiler and parallel programming books, including High-Performance Compilers for Parallel Computing by Michael Wolfe (Pearson) and Optimizing Compilers for Modern Architectures by Allen and Kennedy (Morgan Kaufmann). Tools like Intel Inspector in Intel Parallel Studio XE can also be used to find and debug threading errors, including in applications that use TBB.

Another very common pattern found in applications is a reduction, commonly known as the “reduce pattern” or “map-reduce” because it tends to be used with a map pattern (see more about pattern terminology in Chapter 8).

A reduction computes a single value from a collection of values. Example applications include calculating a sum, a minimum value, or a maximum value.

Let’s consider a loop that finds the maximum value in an array:

Computing a maximum from a set of values is an associative operation; that is, it’s legal to perform this operation on groups of values and then combine those partial results, in order, later. Computing a maximum is also commutative, so we do not even need to combine the partial results in any particular order.

For loops that perform associative operations, TBB provides the function parallel_reduce:

As with all of the simple loop algorithms, to use a TBB parallel_reduce, we need to provide a Range (range) and Body (func). But we also need to provide an Identity Value (identity) and a Reduction Body (reduction).

To create parallelism for a parallel_reduce, the TBB library divides the range into chunks and creates tasks that apply func to each chunk. In Chapter 16, we discuss how to use Partitioners to control the size of the chunks that are created, but for now, we can assume that TBB creates chunks of an appropriate size to minimize overheads and balance load. Each task that executes func starts with a value init that is initialized with identity and then computes and returns a partial result for its chunk. The TBB library combines these partial results by calling the reduction function to create a single final result for the whole loop.

The identity argument is a value that leaves other values unchanged when they are combined with it using the operation that is being parallelized. It is well known that the identity element with respect to addition (additive identity) is “0” (since x + 0 = x) and that the identity element with respect to multiplication (multiplicative identity) is “1” (since x * 1 = x). The reduction function takes two partial results and combines them.

Figure 2-9 shows how func and reduction functions may be applied to compute the maximum value from an array of 16 elements if the Range is broken into four chunks. In this example, the associative operation applied by func to the elements of the array is max() and the identity element is -∞, since max(x,- ∞)=x. In C++, we can use std::max as the operation and std::numeric_limits<int>::min() as the programmatic representation of -∞.

We can express our simple maximum value loop using a parallel_reduce as shown in Figure 2-10.

You may notice in Figure 2-10 that we use a blocked_range object for the Range, instead of just providing the beginning and ending of the range as we did with parallel_for. The parallel_for algorithm provides a simplified syntax that is not available with parallel_reduce. For parallel_reduce, we must pass a Range object directly, but luckily we can use one of the predefined ranges provided by the library, which include blocked_range, blocked_range2d, and blocked_range3d among others. These other range objects will be described in more detail in Chapter 16, and their complete interfaces are provided in Appendix B.

A blocked_range, used in Figure 2-10, represents a 1D iteration space. To construct one, we provide the beginning and ending value. In the Body, we use its begin() and end() functions to get the beginning and ending values of the chunk of values that this body execution has been assigned and then iterate over that subrange. In Figure 2-8, each individual value in the Range was sent to the parallel_for Body, and so there is no need for an i-loop to iterate over a range. In Figure 2-10, the Body receives a blocked_range object that represents a chunk of iterations, and therefore we still have an i-loop that iterates over the entire chunk assigned to it.

A less common, but still important, pattern found in applications is a scan (sometimes called a prefix). A scan is similar to a reduction, but not only does it compute a single value from a collection of values, it also calculates an intermediate result for each element in the Range (the prefixes). An example is a running sum of the values x0, x1, ... xN. The results include each value in the running sum, y0, y1, ... yN, and the final sum yN.

On the surface, a scan looks like a serial algorithm. Each prefix depends on the results computed in all of the previous iterations. While it might seem surprising, there are however efficient parallel implementations of this seemingly serial algorithm. The TBB parallel_scan algorithm implements an efficient parallel scan. Its interface requires that we provide a range, an identity value, a scan body, and a combine body:

The range, identity value, and combine body are analogous to the range, identity value, and reduction body of parallel_reduce. And, as with the other simple loop algorithms, the range is divided by the TBB library into chunks and TBB tasks are created to apply the body (scan) to these chunks. A complete description of the parallel_scan interfaces is provided in Appendix B.

What is different about parallel_scan is that the scan body may be executed more than once on the same chunk of iterations – first in a pre-scan mode and then later in a final-scan mode.

In final-scan mode, the body is passed an accurate prefix result for the iteration that immediately precedes its subrange. Using this value, the body computes and stores the prefixes for each iteration in its subrange and returns the accurate prefix for the last element in its subrange.

However, when the scan body is executed in pre-scan mode, it receives a starting prefix value that is not the final value for the element that precedes its given range. Just like with parallel_reduce, a parallel_scan depends on associativity. In pre-scan mode, the starting prefix value may represent a subrange that precedes it, but not the complete range that precedes it. Using this value, it returns a (not yet final) prefix for the last element in its subrange. The returned value represents a partial result for the starting prefix combined with its subrange. By using these pre-scan and final-scan modes, it is possible to exploit useful parallelism in a scan algorithm.

Let’s look at the running sum example again and think about computing it in three chunks A, B, and C. In a sequential implementation, we compute all of the prefixes for A, then B, and then C (three steps done in order). We can do better with a parallel scan as shown in Figure 2-13.

First, we compute the scan of A in final-scan mode since it is the first set of values and so its prefix values will be accurate if it is passed an initial value of identity. At the same time that we start A, we start B in pre-scan mode. Once these two scans are done, we can now calculate accurate starting prefixes for both B and C. To B we provide the final result from A (92), and to C we provide the final-scan result of A combined with the pre-scan result of B (92+136 = 228).

The combine operation takes constant time, so it is much less expensive than the scan operations. Unlike the sequential implementation that takes three large steps that are applied one after the other, the parallel implementation executes final-scan of A and pre-scan of B in parallel, then performs a constant-time combine step, and then finally computes final-scan of B and C in parallel. If we have at least two cores and N is sufficiently large, a parallel prefix sum that uses three chunks can therefore be computed in about two thirds of the time of the sequential implementation. And parallel_prefix can of course execute with more than three chunks to take advantage of more cores.

Figure 2-14 shows an implementation of the simple partial sum example using a TBB parallel_scan. The range is the interval [1, N), the identity value is 0, and the combine function returns the sum of its two arguments. The scan body returns the partial sum for all of the values in its subrange, added to the initial sum it receives. However, only when its is_final_scan argument is true does it assign the prefix results to the running_sum array.

Figure 2-15 shows a serial implementation of a line of sight problem similar to the one described in Vector Models for Data-Parallel Computing, Guy E. Blelloch (The MIT Press). Given the altitude of a viewing point and the altitudes of points at fixed intervals from the viewing point, the line of sight code determines which points are visible from the viewing point. As shown in Figure 2-15, a point is not visible if any point between it and the viewing point, altitude[0], has a larger angle Ѳ. The serial implementation performs a scan to compute the maximum Ѳ value for all points between a given point and the viewing point. If the given point’s Ѳ value is larger than this maximum angle, then it is a visible point; otherwise, it is not visible.

Figure 2-16 shows a parallel implementation of the line of sight example that uses a TBB parallel_scan. When the algorithm completes, the is_visible array will contain the visibility of each point (true or false). It is important to note that the code in Figure 2-16 needs to compute the maximum angle at each point in order to determine the point’s visibility, but the final output is the visibility of each point, not the maximum angle at each point. Because the max_angle is needed but is not a final result, it is computed in both pre-scan and final-scan mode, but the is_visible values are stored for each point only during final-scan executions.

The parallel_do function has two interfaces, one that accepts a first and last iterator and another that accepts a container. A complete description of the parallel_do interfaces is provided in Appendix B. In this section, we will look at the version that receives a container:

As a simple example, let us start with a std::list of std::pair<int, bool> elements, each of which contains a random integer value and false. For each element, we will calculate whether or not the int value is a prime number; if so, we store true to the bool value. We will assume that we are given functions that populate the container and determine if a number is prime. A serial implementation follows:

We can create a parallel implementation of this loop using a TBB parallel_do as shown in Figure 2-17.

The TBB parallel_do algorithm will safely traverse the container sequentially, while creating tasks to apply the body to each element. Because the container has to be traversed sequentially, a parallel_do is not as scalable as a parallel_for, but as long as the body is relatively large (> 100,000 clock cycles), the traversal overhead will be negligible compared to the parallel executions of the body on the elements.

In addition to handling containers that do not provide random access, the parallel_do also allows us to add additional work items from within the body executions. If bodies are executing in parallel and they add new items, these items can be spawned in parallel too, avoiding the sequential task spawning limitations of parallel_do.

Figure 2-18 provides a serial implementation that calculates whether values are prime numbers, but the values are stored in a tree instead of a list.

We can create a parallel implementation of this tree version using a parallel_do, as shown in Figure 2-19. To highlight the different ways to provide work items, in this implementation we use a container that holds a single tree of values. The parallel_do starts with only a single work item, but two items are added in each body execution, one to process the left subtree and the other to process the right subtree. We use the parallel_do_feeder.add method to add new work items to the iteration space. The class parallel_do_feeder is defined by the TBB library and is passed as the second argument to the body.

The number of available work items increases exponentially as the bodies traverse down the levels of the tree. In Figure 2-19, we add new items through the feeder even before we check if the current element is a prime number, so that the other tasks are spawned as quickly as possible.

We should note that the two uses we considered of parallel_do have the potential to scale for different reasons. The first implementation, without the feeder in Figure 2-17, can show good performance if each body execution has enough work to do to mitigate the overheads of traversing the list sequentially. In the second implementation, with the feeder in Figure 2-19, we start with only a single work item, but the number of available work items grows quickly as the bodies execute and add new items.

The second generic parallel algorithm in TBB used to handle complex loops is parallel_pipeline. A pipeline is a linear sequence of filters that transform items as they pass through them. Pipelines are often used to process data that stream into an application such as video or audio frames, or financial data. In Chapter 3, we will discuss the Flow Graph interfaces that let us build more complex graphs that include fan-in and fan-out to and from filters.

Figure 2-24 shows a small example loop that reads in arrays of characters, transforms the characters by changing all of the lowercase characters to uppercase and all of the uppercase characters to lowercase, and then writes the results in order to an output file.

The operations have to be done in order on each buffer, but we can overlap the execution of different filters applied to different buffers. Figure 2-25(a) shows this example as a pipeline, where the “write buffer” operates on bufferi, while in parallel the “process” filter operates on bufferi+1 and the “get buffer” filter reads in bufferi+2.

As illustrated in Figure 2-25(b), in the steady state, each filter is busy, and their executions are overlapped. However, as shown in Figure 2-25(c), unbalanced filters decrease speedup. The performance of a pipeline of serial filters is limited by the slowest serial stage.

The TBB library supports both serial and parallel filters. A parallel filter can be applied in parallel to different items in order to increase the throughput of the filter. Figure 2-26(a) shows the “case change” example, with the middle/process filter executing in parallel on two items. Figure 2-26(b) illustrates that if the middle filter takes twice as long as the other filters to complete on any given item, then assigning two threads to this filter will allow it to match the throughput of the other filters.

A complete description of the parallel_pipeline interfaces is provided in Appendix B. The interface of parallel_pipeline we use in this section is shown as follows:

The second argument to parallel_pipeline is filter_chain, a series of filters created by concatenating filters that are created using the make_filter function:

The template arguments T and U specify the input and output types of the filter. The mode argument can be serial_in_order, serial_out_of_order, or parallel. And the f argument is the body of the filter. Figure 2-27 shows the implementation of the case change example using a TBB parallel_pipeline. A more complete description of the parallel_pipeline interfaces is provided in Appendix B.

We can note that the first filter, since its input type is void, receives a special argument of type tbb::flow_control. We use this argument to signal when the first filter in a pipeline is no longer going to generate new items. For example, in the first filter in Figure 2-27, we call stop() when the pointer returned by getCaseString() is null.

In this implementation, the first and last filters are created using the serial_in_order mode. This specifies that both filters should run on only one item at a time and that the last filter should execute the items in the same order that the first filter generated them in. A serial_out_of_order filter is allowed to execute the items in any order. The middle filter is passed parallel as its mode, allowing it to execute on different items in parallel. The modes supported by parallel_pipeline are described in more detail in Appendix B.