This section explains useful programming techniques for scheduling tasks.
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( steps. But with tree-structured forking, it takes only
O(log 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.
spawn_and_wait_for_all method is a convenient way to wait for child tasks, but it incurs some inefficiency if a thread becomes idle. The idle thread attempts to keep busy by stealing tasks from other threads. The scheduler limits possible victim tasks to those deeper than the waiting task. This limit modifies the policy that the shallowest task should be chosen. The limit restrains memory demands in worst-case scenarios.
A way around the constraint is for the parent not to wait, but simply to spawn both children and return. The children are allocated not as children of the parent, but as children of the parent’s ...