How Task Scheduler Works
- The scheduler runs tasks in a way that tries to achieve several targets simultaneously:
- Enable as many threads as possible, by creating enough job, to achieve actual parallelism
- Preserve data locality to make a single thread execution more efficient
- Minimize both memory demands and cross-thread communication to reduce an overhead
- Strike when the cache is hot. The deepest tasks are the most recently created tasks and therefore are the hottest in the cache. Also, if they can be completed, tasks that depend on it can continue executing, and though not the hottest in a cache, they are still warmer than the older tasks deeper in the dequeue.
- Minimize space. Execution of the shallowest task leads to the breadth-first unfolding of a graph. It creates an exponential number of nodes that co-exist simultaneously. In contrast, depth-first execution creates the same number of nodes, but only a linear number can exists at the same time, since it creates a stack of other ready tasks.
- Get the task returned by the previous one, if any.
- Take a task from the bottom of its deque, if any.
- Steal a task from the top of another randomly chosen deque. If the selected deque is empty, the thread tries again to execute this rule until it succeeds.