For a set of tasks with dependencies (some tasks may only be begun after some other tasks are completed), topological sorting provides a way to execute tasks sequentially while respecting dependencies.
If the tasks are programs and we have a machine that is capable of executing programs in parallel, then how should we schedule the tasks in order to minimize the total time to complete all tasks? We can use walk relations on acyclic graphs.
A chain in a DAG (Directed Acyclic Graph) is a set of vertices such that any two of them are comparable (when one is reachable from the other). A vertex in a chain that is reachable from all other vertices in the chain is called a maximum element of the chain. A finite chain is said to end at its maximum element.
The time it takes to schedule tasks is at least as large as the number of vertices in any chain (because if we used less time than the size of some chain, then two items from the chain would have to be done at the same step, contradicting the precedence constraints). A largest chain is also known as a critical path.
All tasks can be scheduled in steps, where is the size of the largest chain. This is true for any DAG. A schedule for performing tasks specifies which tasks to do at successive steps. Every task has to be scheduled at some step, and all the tasks have to be completed before task must be scheduled for an earlier step.
A partition of a set is a set of nonempty subsets of called the blocks of the partition, such that every element of is in exactly one block.
For example, one possible partition of the set into three blocks is
A parallel schedule for a DAG is a partition of into blocks , such that when , no vertex in is reachable from any vertex in The block is called the set of elements scheduled at step , and the time of the schedule is the number of blocks. The maximum number of elements scheduled at any step is called the number of processors required by the schedule.
A largest chain ending at an element is called a critical path to . The number of elements less than in the chain is called the depth of . So in any possible parallel schedule, there must be at least depth steps before task can be started. In particular, the minimal elements are precisely the elements with depth .
A minimum time schedule for a finite DAG consists of the sets , where