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.
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
,
where
()
is the length of the longest path from an in-degree 0 (out-degree 0) task to
.
DSC initializes
for every free task and inserts them into a free task list. Next,
is computed for each task. The free task
with the highest priority is processed first. If
cannot be reduced by merging it with a predecessor's cluster, then
will be assigned to a new processor. Next, DSC updates the priorities of
's
successors, and inserts any newly free successors into the free list. The
process is repeated until all tasks are scheduled.
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)