Intel Threading Building Blocks

How Task Scheduling Works

The scheduler evaluates a task graph. The graph is a directed graph in which nodes are tasks, and each points to its parent, which is either NULL for the root task or another task that is waiting for it to complete. The task::parent() method gives you read-only access to the parent pointer.

Each task has a refcount that counts the number of tasks that have it as a parent. Each task also has a depth, which is usually one more than the depth of its parent. Figure 9-3 shows a task graph for the Fibonacci example shown earlier in Example 9-2 and Example 9-3.

In the figure, the tasks with nonzero reference counts (A, B, and C) wait for their child tasks. The leaf tasks are running or are ready to run.

The scheduler runs tasks in a way that tends to minimize both memory demands and cross-thread communication. To achieve this, a balance must be reached between depth-first and breadth-first execution. Assuming that the tree is finite, depth-first is best for sequential execution for the following reasons:

Strike when the cache is hot

The deepest tasks are the most recently created tasks and, therefore, the hottest in the cache. Also, if they can complete, task C can continue executing; although it’s not the hottest in the cache, it’s still warmer than the older tasks above it.

Minimize space

Executing a shallow task in breadth-first fashion unfolds the tree under it and makes all those tasks take up space while they wait for threads. This creates a potentially exponential ...