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.
Parallel algorithms for streams:
-
parallel_while Use for an unstructured stream or pile of work. Offers the ability to add additional work to the pile while running.
-
pipeline 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.
Parallel sort:
-
parallel_sort A comparison sort with an average time complexity not to exceed
O(on a single processor and approachingnlogn)O(N)as more processors are used. When worker threads are available,parallel_sortcreates subtasks that may be executed concurrently.