Intel Threading Building Blocks

Chapter 3. Basic Algorithms

This is the key chapter in learning Intel Threading Building Blocks. Here you will come to understand the recursion, task-stealing, and algorithm templates that Threading Building Blocks uniquely combines.

The most visible contribution of Threading Building Blocks is the algorithm templates covered in this chapter and the next chapter. This chapter introduces the simplest loop-oriented algorithms based on recursive ranges, and the next chapter expands on that with more advanced algorithm support. Future chapters offer details that round out features needed to make your use of Threading Building Blocks complete.

Threading Building Blocks offers the following types of generic parallel algorithms, which are covered in this chapter:

Loop parallelization

parallel_for and parallel_reduce

Load-balanced, parallel execution of a fixed number of independent loop iterations

parallel_scan

A template function that computes a prefix computation (also known as a scan) in parallel (y[i]=y [i-1] op x[i])

The validity of the term Building Block is clearer when you see how fully Threading Building Blocks supports nested parallelism to enable you to build larger parallel components from smaller parallel components. A Quicksort example shown in Chapter 11, for instance, was implemented using parallel_for recursively. The recursion is implicit because of Threading Building Blocks’ inherent concept of splitting, as embodied in the parallel iterator.

Tip

When you thoroughly understand ...