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

Load Balancing Versus Task Stealing

Task stealing is terrible because it can result in a relatively large synchronization cost. But more importantly, it can move all the data in cache from one core to another. You should minimize the number of tasks stolen. Therefore, there are two levels of work distribution in the example:

  • Balancing the amount of work within each domain task

  • Task stealing of domain tasks

The work in each domain of data decomposition by a spatial data structure, such as a k-d tree, can be balanced by selecting an algorithm available in the data structure research. But because the work does not have to be perfectly balanced, and rarely is, it is good to create more domain tasks than physical threads. In the example, we demonstrate that Threading Building Blocks can be used to steal domain tasks from one thread to another when the first thread has less work to do in its normal domain.

The example shows that on average, m tasks are stolen. As long as m << n, the data decomposition is sufficiently efficient.

In addition, in the current k-d tree traversal, we assume that the k-d tree is roughly spatially balanced. But objects can move in space from one quadrant to another without moving in the k-d tree. Thus, the tree can become an incorrect k-d tree over time. Moving objects to their proper place in the k-d tree takes extra time and may not be necessary for threading efficiency. In some games, it may be necessary to keep the k-d tree correct for other purposes. So in the ...

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