Algorithm templates are the keys to using Intel Threading Building Blocks. This chapter presents some relatively complex algorithms that build on the foundation laid in Chapter 3, so you should understand Chapter 3 before jumping into this chapter. This chapter covers Threading Building Blocks’ support for the following types of generic parallel algorithms.
Use for an unstructured stream or pile of work. Offers the ability to add additional work to the pile while running.
Use when you have a linear sequence of stages. Specify the maximum number of items that can be in transit. Each stage can be serial or parallel. This uses the cache efficiently because each worker thread takes an item through as many stages as possible, and the algorithm is biased toward finishing old items before tackling new ones.
A comparison sort with an average time complexity not to exceed
O( on a single processor and approaching
O(N) as more processors are used. When worker threads are available,
parallel_sort creates subtasks that may be executed concurrently.