Scheduling Algorithms | Algorithms & Applications Group
Scheduling Algorithms


supported by NSF, DOE
Olga Pearce, Marvin Adams, Nancy Amato
Project Alumni: Ping An


Task Scheduling | Scheduling Algorithms | STAPL Scheduler | ASCI Scheduler

Unfortunately, standard task scheduling is NP-complete, even for the unit task size and unit communication cost. However, various heuristic methods have been proposed that obtain suboptimal solutions (schedules) in polynomial time.


Wave Front Method (WFM)

The wave fronts of the graph are determined according to the level of the vertices in a breadth-first-search traversal of the DAG. The vertices in each wave front are independent from each other, and are all assigned to different processors. Following is an example of applying Wave Front Method.



Critical Path Merge (CPM)

A critical path in a DAG is a maximum weight root to leaf path (the path weight is the summation of all vertex and edge weights on the path). CPM computes the critical path, clusters all tasks in it, assigns them to the same processor, and removes them from the graph. This process is iterated until all tasks are scheduled.



Heavy Edge Merge (HEM)

Heavy Edge Merge works by iteratively clustering vertices (tasks) along edges with non-increasing weights. During an initialization stage, the edges are sorted in non-increasing order by edge weight, one task is assigned to each (virtual) processor, and the makespan of this assignment is computed. Then, all edges are processed in sorted order. For each edge, the makespan resulting from merging the tasks associated with the endpoints (perhaps clusters themselves) is computed. If the makespan increases, then the merge is not performed.



Dominant Sequence Clustering (DSC)

DSC works by iteratively identifying, and scheduling, so-called dominant sequence tasks which are defined as follows. An unscheduled task is called free if all of its predecessors are already scheduled. A dominant sequence task is the highest priority free task. The priority of a task is defined as $p(t_x) = top(t_x) + bot(t_x)$, where $top(t_x)$ ($bot(t_x)$) is the length of the longest path from an in-degree 0 (out-degree 0) task to $t_x$. DSC initializes $top()=0$ for every free task and inserts them into a free task list. Next, $bot()$ is computed for each task. The free task $t_x$ with the highest priority is processed first. If $top(t_x)$ cannot be reduced by merging it with a predecessor's cluster, then $t_x$ will be assigned to a new processor. Next, DSC updates the priorities of $t_x$'s successors, and inserts any newly free successors into the free list. The process is repeated until all tasks are scheduled.







Related Projects

Task Scheduling
STAPL Scheduler
ASCI Scheduler


Papers

Load Balancing Techniques for Scalable Parallelization of Sampling-Based Motion Planning Algorithms, Adam Fidel, Sam Ade Jacobs, Shishir Sharma, Lawrence Rauchwerger, Nancy M. Amato, Technical Report, TR13-002 , Parasol Laboratory, Department of Computer Science, Texas A&M University, Mar 2013.
Technical Report(pdf, abstract)

Task Scheduling and Parallel Mesh-Sweeps in Transport Computations, Nancy M. Amato, Ping An, Technical Report, TR00-009, Department of Computer Science and Engineering, Texas A&M University, Jan 2000.
Technical Report(ps, pdf)