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 ...