Skip to Main Content
Intel Threading Building Blocks
book

Intel Threading Building Blocks

by James Reinders
July 2007
Intermediate to advanced content levelIntermediate to advanced
332 pages
10h 4m
English
O'Reilly Media, Inc.
Content preview from Intel Threading Building Blocks

Quicksort: Visualizing Task Stealing

Although Quicksort is a recursive algorithm, no explicit recursion is needed in Threading Building Blocks. Aside from studying the code for Quicksort, look to this example as an illustration of task stealing and range splitting. Let’s go through how it would work using Threading Building Blocks.

Part of the magic is realizing that when you are splitting a parallel range, you are free to adjust the data in that range before considering it split and handing it off. It is safe to do this because when a range is being split, there is no concurrent use on that particular range.

The Quicksort range shown in Example 11-31 is where the partitioning step is done (using std::swap). Partitioning involves making sure that all the numbers on one side of a pivot are smaller than or equal to the pivot, and the numbers on the other side are larger than or equal to it. Without this step, you would end up with a bunch of sort sections in the array. They appear sorted overall only because of this partitioning. See Example 11-32 for the Quicksort functions.

Tip

Aha! Recursive splitting so that tasks fit available parallelism is very powerful.

Example 11-31. Quicksort range

template<typename RandomAccessIterator, typename Compare> struct quick_sort_range { static const size_t grainsize = 500; const Compare &comp; RandomAccessIterator begin; size_t size; quick_sort_range( RandomAccessIterator begin_, size_t size_, const Compare &comp_ ) : comp(comp_), begin(begin_), size(size_) ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Intel® Xeon Phi™ Coprocessor Architecture and Tools: The Guide for Application Developers

Intel® Xeon Phi™ Coprocessor Architecture and Tools: The Guide for Application Developers

Rezaur Rahman

Publisher Resources

ISBN: 9780596514808Errata Page