Intel Threading Building Blocks

Recursive Chain Reaction

The scheduler works best with tree-structured task graphs, because that is where the strategy of breadth-first theft and depth-first work applies very well. Also, tree-structured task graphs allow fast creation of many tasks. For example, if a master task tries to create n children directly, it will take O(n) steps. But with tree-structured forking, it takes only O(log n) steps because some of the tasks created can go on to create subtasks.

Often, domains are not obviously tree-structured, but you can easily map them to trees. For example, parallel_for works over an iteration space such as a sequence of integers. The template function parallel_for uses that definition to recursively map the iteration space onto a binary tree.