Efficient Local Search for DAG Scheduling.
AbstractScheduling DAGs to multiprocessors is one of the key issues in high-performance computing. Most realistic scheduling algorithms are heuristic and heuristic algorithms often have room for improvement. The quality of a scheduling algorithm can be effectively improved by a local search. In this paper, we present a fast local search algorithm based on topological ordering. This is a compaction algorithm that can effectively reduce the schedule length produced by any DAG scheduling algorithm. Thus, it can improve the quality of existing DAG scheduling algorithms. This algorithm can quickly determine the optimal search direction. Thus, it is of low complexity and extremely fast.
Introduction
Scheduling computations onto processors is one of the crucial components of a parallel processing
environment. They can be performed at compile-time or runtime. Scheduling performed
at compile-time is called static scheduling; scheduling performed at runtime is called dynamic
scheduling. The
exibility inherent in dynamic scheduling allows adaptation to unforeseen appli-
cations' requirements at runtime. However, load balancing suers from run-time overhead due to
load information transfer among processors, load balancing decision-making process, and communication
delay due to task relocation. Furthermore, most runtime scheduling algorithms utilize
neither the characteristics information of application problems, nor global load information for
load balancing decision. The major advantage of static scheduling is that the overhead of the
scheduling process is incurred at compile time, resulting in a more e-cient execution time environment
compared to dynamic scheduling. Static scheduling can utilize the knowledge of problem
characteristics to reach a well-balanced load.
We consider static scheduling algorithms that schedule an edge-weighted directed acyclic graph
(DAG), also called task graph or macro-data
ow graph, to a set of homogeneous processors to
minimize the completion time. Since the static scheduling problem is NP-complete in its general
forms [6], and optimal solutions are known in restricted cases [3, 5, 7], there has been considerable
research eort in this area, resulting in many heuristic algorithms [19, 24, 4, 25, 20, 2, 14]. In this
paper, instead of suggesting a new scheduling algorithm, we present an algorithm that can improve
the scheduling quality of the existing scheduling algorithms by using a fast local search technique.
This algorithm, called TASK (Topological Assignment and Scheduling Kernel), systematically
minimizes a given schedule in a topological order. In each move, the dynamic cost of a node is
used to quickly determine the search direction. It can eectively reduce the length of a given
schedule.
This paper is organized as follows. In the next section, we review DAG scheduling algorithms.
In Section 3, the local search technique is described. The random local search algorithm is
discussed in Section 4. In Section 5, we propose a new local search algorithm, TASK. Performance
data and comparisons are presented in Section 6. Finally, Section 7 concludes this paper.
Scheduling
A directed acyclic graph (DAG) consists of a set of nodes fn 1
connected by a set of
edges, each of which is denoted by e i;j . Each node represents a task, and the weight of node n i ,
w(n i ), is the execution time of the task. Each edge represents a message transferred from one
node to another node, and the weight of edge e i;j , w(e i;j ) is equal to the transmission time of
the message. The communication-to-computation ratio (CCR) of a parallel program is dened as
its average communication cost divided by its average computation cost on a given system. In a
DAG, a node that does not have any parent is called an entry node, whereas a node that does not
have any child is called an exit node. A node cannot start execution before it gathers all of the
messages from its parent nodes. In static scheduling, the number of nodes, the number of edges,
the node weight, and the edge weight are assumed to be known before program execution. The
weight between two nodes assigned to the same processing element (PE) is assumed to be zero.
The objective in static scheduling is to assign nodes of a DAG to PEs such that the schedule
length or makespan is minimized without violating the precedence constraints. There are many
approaches that can be employed in static scheduling. In the classical approach [13], also called
list scheduling, the basic idea is to make a priority list of nodes, and then assign these nodes
one by one to PEs. In the scheduling process, the node with the highest priority is chosen for
scheduling. The PE that allows the earliest start time is selected to accommodate this node.
Most of the reported scheduling algorithms are based on this concept of employing variations in
the priority assignment methods, such as HLF (Highest level First), LP (Longest Path), LPT
(Longest Processing Time) and CP (Critical Path) [1, 24, 15]. In the following we review some
of contemporary static scheduling algorithms, including MCP, DSC, DLS, and CPN methods.
The Modied Critical Path (MCP) algorithm is based on the as-late-as-possible (ALAP) time
of a node [24]. The ALAP time is dened as critical is the
length of the critical path, and level(n i ) is the length of the longest path from node n i to an exit
node, including node n i [5]. The MCP algorithm was designed to schedule a DAG on a bounded
number of PEs. It sorts the node list in the increasing ALAP order. The rst node in the list
is scheduled to the PE that allows the earliest start time, considering idle time slots. Then the
node is deleted from the list and this operation repeats until the list is empty.
The Dominant Sequence Clustering (DSC) algorithm is designed based on an attribute for a
task graph called the dominant sequence (DS) [25]. A DS is dened for a partially scheduled task
graph as the path with the maximum sum of communication costs and computation costs in the
graph. Nodes on the DS are considered to be relatively more important than others. The ready
nodes with the highest priority will be scheduled rst. Then the priorities of the child nodes of
the scheduled node will be updated and this operation repeats until all nodes are scheduled. The
dynamic cost is used to quickly determine the critical path length. This idea has been incorporated
into our TASK algorithm to reduce its complexity.
The Dynamic Level Scheduling (DLS) algorithm determines node priorities by assigning an
attribute called dynamic level (DL) to each node at every scheduling step [20]. DL is the dierence
between the static level and message ready time. DLS computes DL for each ready node on all
available processors. Suppose DL(n i ; J) is the largest among all pairs of ready nodes and available
processors. Schedule n i to processor J . Repeat this process until all nodes are scheduled.
Recently, a new algorithm has been proposed by using the Critical Path Node (CPN) [16].
This algorithm is based on the CPN-dominate priority. If the next CPN is a ready node, it is
put in the CPN-dominate list. For a non-ready CPN, its parent node n y with the smallest ALAP
time is put in the list if all the parents of n y are already in the list; otherwise, all the ancestor
nodes of n y are recursively included in the list before the CPN node is in the list. The rst node
in the list is scheduled to the PE that allows the earliest start time. Then the scheduled node
is removed from the list and this operation repeats until the list is empty. The CPN-dominate
algorithm utilizes the two important properties of DAG: the critical path and topological order.
It potentially generates a good schedule.
Although these algorithms produce relatively good schedules, they are usually not optimal.
Sometimes, the generated schedule is far from optimal. In this paper, we propose a fast local
search algorithm, TASK, to improve the quality of schedules generated by an initial scheduling
algorithm.
Local search was one of the early techniques for combinatorial optimization. It has been applied
to solve NP-hard optimization problems [12]. The principle of local search is to rene a given
initial solution point in the solution space by searching through the neighborhood of the solution
point. Recently a number of e-cient heuristics for local search, i.e., con
ict minimization [8, 21],
random selection/assignment [22, 23], and pre- and partial selection/assignment [22, 23], have
been developed.
There are several signicant local search solutions to the scheduling problems. The SAT1
algorithm was the rst local search algorithm developed for the satisability problem during the
later '80s [8, 9, 10, 11]. This scheduling problem is well-known as a Max-Satisability problem.
A local search solution to the SAT problem was applied to solve several large-scale industrial
scheduling problems.
Two basic strategies have been used in a local search. The rst one is a random search, in
which the local search direction is randomly selected. If the initial solution point is improved,
it moves to the rened solution point. Otherwise, another search direction is randomly selected.
The random strategy is simple and eective for some problems, such as the n-queens problem [21].
However, it may not be e-cient for other problems such as the microword length minimization [18]
and DAG scheduling problem.
The second strategy utilizes certain criteria to nd a search direction that will most likely
lead to a better solution point. In the microword length minimization [18], a compatibility class
is considered only when moving some nodes from the class may reduce the cost function. This
strategy eectively reduces the search space by guiding the search toward a more promising
direction. The local search algorithm presented in this paper uses this strategy. With carefully
selected criteria, a local search for DAG scheduling becomes very e-cient and the scheduling
quality can be improved signicantly.
4 Random Local Search Algorithm
A number of local search algorithms for scheduling have been presented [16, 17]. A random local
search algorithm for DAG scheduling, named FAST, was given in [16] (see Figure 1). In this
algorithm, a node is randomly picked and then moved to a randomly selected PE. If the schedule
length is reduced, the move is accepted. Otherwise, the node is moved back to its original PE.
Each move, successful or not, takes O(e) time to compute the schedule length, where e is the
number of edges in the graph. To reduce its complexity, a constant MAXSTEP is dened to
limit the number of steps so that only MAXSTEP nodes are inspected. The time taken for
the algorithm is proportional to eMAXSTEP . MAXSTEP is set to be 64 [16]. Moreover,
randomly selected nodes and PEs may not be able to signicantly reduce the length of a given
schedule. Even if the MAXSTEP is equal to the number of nodes, leading to a complexity of
O(en), the random search algorithm still cannot provide a satisfactory performance.
do f
pick a node n i randomly
pick a PE P randomly
move n i to PE P
if schedule length does not improve
move n i back to its original PE
while (searchstep++ < MAXSTEP )

Figure

1: A random local search algorithm, FAST.
The FAST algorithm has been modied in [17], which is shown in Figure 2. The major
improvement is that it uses a nested loop for a probabilistic jump. The total number of search steps
is MAXSTEPMAXCOUNT . MARGIN is used to reduce the number of steps. MAXSTEP
is set to 8, MAXCOUNT to 64, and MARGIN to 2 [17]. A parallel version of the FAST
algorithm is named FASTEST. A speedup from 11.93 to 14.45 on 16 PEs has been obtained for
FASTEST [17].
5 Local Search with Topological Ordering for Scheduling
We propose a fast local search algorithm utilizing topological ordering for eective DAG schedul-
ing. The algorithm is called TASK (Topological Assignment and Scheduling Kernel). In this
algorithm, the nodes in the DAG are inspected in a topological order. In this order, it is not
required to visit every edge to determine whether the schedule length is reduced. The time spent
on each move can be drastically reduced so that inspecting every node in a large graph becomes
feasible. Also, in this order, we can compact the given schedule systematically.
For a given graph, in order to describe the TASK algorithm succinctly, several terms are
repeat
do f
pick a node n i randomly
pick a PE P randomly
move n i to PE P
if schedule length does not improve
move n i back to its original PE and increment counter;
otherwise set counter to 0;
while (searchstep++ < MAXSTEP and counter < MARGIN);
Schedule length of schedule S */
endif
Randomly pick a node from the critical path and
move it to another processor;
until (searchcount++ > MAXCOUNT);

Figure

2: The modied FAST algorithm.
dened as follows:
largest sum of communication and computation costs at the top level of node
i.e., from an entry node to n i , excluding its own weight w(n i ) [26].
largest sum of communication and computation costs at the bottom level of node
i.e., from n i to an exit node [26].
- The critical path, CP, is the longest path in a DAG. The length of the critical path of a DAG
is
is the node set of the graph.
The TASK algorithm is applied to a previously scheduled DAG. In this case, a scheduled DAG
is constructed, which contains scheduling and execution order information [25]. To enforce the
execution order in each PE, some pseudo edges (with zero weights) are inserted to incorporate
the initial schedule into the graph. The above denitions of tlevel, blevel, and the critical path
are still applied to the scheduled DAG. Then we dene more terms:
been scheduled on PE pe(n i ).
be the predecessor node that has been scheduled immediately before node n i on PE
pe(n i ). If node n i is the rst node scheduled on the PE, p(n i ) is null.
be the successor node that has been scheduled immediately after node n i on PE pe(n i ).
If node n i is the last node scheduled on the PE, s(n i ) is null.
procedure TASK (DAG Schedule)
begin
initialization */
Construct a scheduled DAG;
for node i := 0 to n 1 do
longest path in DAG;
/* search */
while there are nodes in DAG to be scheduled do
begin
pick a node with Max L(n i );
for each PE k
obtain L k (n i ) by moving n i to PE k;
t := pick a PE with Min L k , where
/* if no improvement */
let node n i stay at PE pe(n i );
/* if there are improvements */
else begin
move node n i from PE pe(n i ) to PE t;
modify pseudo edges in DAG;
propagate tlevel of n i to its children;
mark n i as being scheduled;

Figure

3: TASK: Topological Assignment and Scheduling Kernel, a local search algorithm based
on topological ordering for fast scheduling.
A sketch TASK algorithm is shown in Figure 3 and the detailed description of the TASK
algorithm in Figure 4. One of characteristics of this TASK algorithm is its independence from the
algorithm that was used to generate the initial schedule. A node is labeled as n i , and its current
PE number is pe(n i ). As long as the initial schedule is correct and every node n i has available
application of the local compaction algorithm guarantees that the
new schedule of the graph is better than or equal to the initial one.
The input of the algorithm is a given DAG schedule generated by any heuristic DAG scheduling
algorithm. First, a scheduled DAG is constructed. A pseudo edge may be added with zero
communication time; that is, no data are transferred along the edge. Step 2 computes the value
of blevel of each node in the scheduled DAG and initializes tlevel for entry nodes. All edges are
marked unvisited. The variable next k points to the next node that has not been inspected in PE
k. Initially, none of nodes is inspected so next k points to the rst node in PE k.
In Step 3, a ready node n i with the maximum value L(n selected
for inspection. Ties are broken by tlevel(n i ); for the same tlevel(n i ), ties are broken randomly. A
node is ready when all its parents have been inspected. In this way, the nodes are inspected in a
topological order. Although other topological orders, such as blevel, tlevel, or CPN-dominate can
be used, tlevel + blevel has been shown to be a good indicator for the order of inspection [24, 25].
To inspect node n i , in Step 4, the value L(n re-calculated for
each PE. To conduct the recalculation at PE k, node n i is pretended to be inserted right in front
of next k . Here, tlevel(n i ) can be varied if any of its parent nodes was scheduled to either PE k
or PE pe(n i ). Similarly, blevel(n i ) can be varied if any of its child nodes was initially scheduled
to either PE k or PE pe(n i ). Because the tlevels of its parent nodes are available and the blevels
of its child nodes are unchanged, the value of L(n i ) in every PE can be easily computed. The
values indicate the degree of improvement by a local search. With the new L(n i )'s recalculated
for every PE, node n i is then moved to the PE that allows the minimum value of L(n i ). If node
n i has been moved to PE t, the corresponding pseudo edges are modied in Step 5. The tlevel of
n i is propagated to its children so that when a node becomes ready, its tlevel can be computed.
This process continues until every node is inspected.
The TASK algorithm satises the following properties.
Theorem 1. The critical path length LCP will not increase after each step of the TASK algorithm.
Proof: The L(n i ) of node n i is determined by the longest path that includes n i . Assume
increases as a result of moving node n i . Then, n i and n j must be on the same
path from an entry node to an exit node. Because L(n j ) increases, this path must be the longest
Step 1. Constructing a scheduled DAG:
For each node n i that is not the last node in a PE
exists no e i;j , create a pseudo edge e i;j from n i to n j with w(e i;j
Step 2. Initialization:
For each node n i
compute blevel(n i ) by considering pseudo edges
if it is an entry node, mark n i as ready and initialize tlevel(n i
Mark every e i;j as unvisited
For each PE k
let next k point to the rst node in the PE
Step 3. Selection:
Pick the ready node n i with the highest value of L(n
ties are broken by tlevel(n i ); for the same tlevel(n i ), ties are broken randomly
Step 4. Inspection:
For each PE k, recompute L k (n i ) by assuming n i be moved to PE k and inserted before next k
Find a PE t such that L t (n
Step 5. Compaction:
will stay at PE t */
let next
else /* move node n i from PE
delete edge e l;i if it is a pseudo edge
delete edge e i;m if it is a pseudo edge
if no edge e l;m previously exists
create a pseudo edge e l;m with w(e l;m it as visited
let s(n l
it is a pseudo edge
create a pseudo edge e x;i if no edge e x;i previously exists
create a pseudo edge e i;y if no edge e i;y previously exists
let s(n x
Step 6. Propagation of tlevel
For each child node of node n i , say n
mark edge e i;j as visited
if all incoming edges of n j are marked as visited
mark n j as ready and compute tlevel(n j )
Repeat Steps 3-6 until all nodes are inspected

Figure

4: The detailed description of the TASK algorithm.
path that includes n j and it determines the value of L(n j ). If this path determines the value of
Otherwise, a longer path determines L(n i ) and L(n i ) > L(n j ). In each
not increase and L(n i )  LCP . Thus, L(n j )  LCP . Since the L value of every
node is not larger than LCP , LCP will not increase. 2
If n i is a node on a critical path, reduction of its L(n i ) value implies the reduction of the
critical path length of the entire graph. (It may not immediately reduce the critical path length
in the case of parallel critical paths.) If n i is not a node on a critical path, reducing its L(n i )
value does not reduce the critical path length immediately. However, it increases the possibility
of length reduction in a later step.
In the TASK algorithm, tlevel and blevel values are reused so that the complexity in determining
L is reduced. The following theorems explain how the topological order makes the complexity
reduction possible.
Theorem 2. If the nodes in a DAG are inspected in a topological order and each ready node is
appended to the previous node list in the PE, the blevel of a node is invariant before it is inspected
and the tlevel of a node is invariant after it is inspected.
Proof: If node n i is not inspected, then the topological order implies that all descendants of
are not inspected. Therefore, the blevel of n i is not changed since the blevel of all descendants
of n i are not changed. Once n i is inspected, then the topological order implies that all ancestors
of n x have been inspected. Because a node is always appended to the previous scheduled nodes
in the PE, the tlevel of an inspected node remains unchanged. 2
Following a topological order of node inspection, we can localize the eect of edge zeroing on
the L value of the nodes that have not been inspected. After each move, only the tlevel of currently
inspected node is computed instead of computing tlevels and blevels of all nodes. Therefore, the
time spent on computing L values is signicantly reduced.
Theorem 3. The time complexity of the TASK algorithm is O(e e is the number
of edges, n is the number of nodes, and p is the number of PEs.
Proof: Insertion of pseudo edges in the rst step costs O(n). The second step spends O(e)
time to compute the blevel values. The third step costs O(n) for nding the highest L value. The
main computational cost of the algorithm is in step 4. Computing the L value of each node costs
inspecting every edge connected to n i , where D(n i ) is the degree of node n i . For n
steps, the cost is P
To complete inspection of a node, a target PE must be
selected from all the p PEs, resulting in the cost of O(np). Therefore, the total cost is O(e
The TASK algorithm shares some concepts with the DSC algorithm [25]. The topological
order is used to avoid repeated calculation of the dynamic critical path so that the complexity
can be reduced. The task selection criteria of tlevel+blevel has been used in the MD [24] and
DSC algorithms. It measures the importance of a node for scheduling and is proven as an e-cient
criteria of node selection. The TASK algorithm is dierent from the DSC algorithm in many
aspects. DSC is an algorithm that schedules a DAG onto an unbounded number of clusters,
whereas TASK is a local search algorithm that improves an existing schedule on a bounded
number of processors. Although both DSC and TASK algorithms aim to reduce schedule length,
DSC realizes it by merging clusters, whereas TASK realizes it by moving nodes among processors.
In DSC, the merging of clusters is based on the gain in reduction of edges between a node and
its parents. TASK goes one step further by considering the possible gain in reduction of edges
between the node and its children, which potentially results in a better and more e-cient decision.
In the following, we use an example to illustrate the operation of the TASK algorithm.
Example 1.
Assume the DAG shown in Figure 5 has been scheduled to three PEs by a DAG scheduling
algorithm. The schedule is shown in Figure 6(a), in which three pseudo (dashed) edges have been
added to construct a scheduled DAG: one from node n 6
to node n 8
, one from node n 3
to node
, and one from node n 4
to node n 5
(not shown in Figure 6(a)). The schedule length is 14. The
blevel of each node is computed as shown in Table 1. Tables 2 and 3 trace the tlevel
values for each step. In Table 2, \ p
" indicates the node with the largest L value and is to be
inspected in the current step. In Table 3, \*" indicates the original PE and \ p
" the PE where
the node is moved to.
First, there is only one ready node, n 1
, which is a CP node. Its L value on PE 0 is L 0 (n 1
14. Then the L values on other PEs are computed: L 1 (n 1
shown in Table 3. Thus, node n 1
is moved from PE 0 to PE 2, as shown in

Figure

6(b). The LCP of the DAG is reduced to 12. In iterations 2, 3, and 4, moving nodes
, and n 2
does not reduce any L value. In iteration 5, node n 6
is moved from PE 0 to PE 1
as the L value is reduced from 12 to 11, as shown in Figure 6(c). In the following ve iterations,
nodes
do not move.

Figure

5: A DAG for Example 1.
Time
Time
(a) (b) (c)2next
next
next
next
next
next
nextnext
next

Figure

An example of TASK's operations.

Table

1: The Initial blevel Value of Each Nodes for Example 1
blevel 14 9 9

Table

2: The L Values of Ready Nodes for Selecting a Node To Be Inspected
Iteration

Table

3: The L Values of Node n i on Each PE to Select a PE
Iteration Node PE
9+6 =15 9+4 =13 6+5 =11*
6 Performance study
In this section, we present the performance results of the TASK algorithm and compare the TASK
algorithm to the random local search algorithm, FAST. We performed experiments using synthetic
DAGs as well as real workload generated from the Gaussian elimination program.
We use the same random graph generator in [17]. The synthetic DAGs are randomly generated
graphs consisting of thousands of nodes. These large DAGs are used to test the scalability
and robustness of the local search algorithms. These DAGs were synthetically generated in the
following manner. Given N , the number of nodes in the DAG, we rst randomly generated
the height of the DAG from a uniform distribution with the mean roughly equal to
N . For
each level, we generated a random number of nodes, which were also selected from a uniform
distribution with a mean roughly equal to
N . Then, we randomly connected the nodes from
the higher level to the lower level. The edge weights were also randomly generated. The sizes of
the random DAGs were varied from 1000 to 4000 with an increment of 1000. Three values of the
communication-computation-ratio (CCR) were selected to be 0.1, 1, and 10. The weights of the
nodes and edges were generated randomly so that the average value of CCR corresponded to 0.1,
1, or 10. Performance data are the average over two hundreds graphs.
We evaluated performance of these algorithms in two aspects: the schedule length generated by
the algorithm and the running time of the algorithm. Tables 4 and 5 show the comparison of the
modied FAST algorithm [17] adn the TASK algorithm on 4 PEs and 16 PEs, respectively, where
\CPN" is the CPN-Dominate algorithm, \FAST" the modied FAST algorithm, and \TASK"
the TASK algorithm. The comparison is conducted for dierent sizes and dierent CCRs. The
CPN-Dominate algorithm [16] generates the initial schedules. For the schedule length, the value
in the column \CPN" is the length of the initial schedule; the value in the column \+FAST" is for
initial scheduling plus the random local search algorithm; and the value in the column \+TASK"
is for initial scheduling plus the TASK algorithm. The column \sd" following each schedule value
is its standard deviation. The columns \%" following \+FAST" and \+TASK" are the percentage
of improvement in the initial schedule. The running times of the CPN-Dominate algorithm, the
modied FAST algorithm and the TASK algorithm are also shown in the tables. It can be seen
that TASK is much more eective and faster than FAST. The search order with the L value is
superior to the random search order. In Table 5, for CCR=10 on 16 PEs, the improvement ratio
drops. In this case, the degree of parallelism to exploit is maximized and there is not much to do
with it. The FAST algorithm is about two orders of magnitude slower than TASK, partly because
256. The FASTEST algorithm running on 16 PEs is faster, but
still one order of magnitude slower than TASK.

Table

4: Comparison for Synthetic DAGs with CPN as Initial Scheduling Algorithm (4 PEs)
# of CCR Schedule length Running time (sec)
nodes CPN sd +FAST sd % +TASK sd % CPN FAST TASK
1000
2000

Table

5: Comparison for Synthetic DAGs with CPN as Initial Scheduling Algorithm (16 PEs)
# of CCR Schedule length Running time (sec)
nodes CPN sd +FAST sd % +TASK sd % CPN FAST TASK

Table

Comparison for Synthetic DAGs with DSC as Initial Scheduling Algorithm (4 PEs)
# of CCR Schedule length Running time (sec)
nodes DSC sd +FAST sd % +TASK sd % DSC FAST TASK
1000
28 4.5 2756 28 12.4 0.60 16.1 0.16
2000

Table

7: Comparison for Synthetic DAGs with DSC as Initial Scheduling Algorithm (16 PEs)
# of CCR Schedule length Running time (sec)
nodes DSC sd +FAST sd % +TASK sd % DSC FAST TASK

Tables

6 and 7 show the comparison with DSC [25] as the initial scheduling algorithm. The
cluster merging algorithm shown in [26] maps the clusters to processors. The CPN-Dominate
algorithm generates a better schedule for DAGs with smaller CCR, and DSC is more e-cient
when CCR is large. For smaller CCR, DSC is not very good. Therefore, TASK produces a large
improvement ratio. On the other hand, DSC is particularly suited for large CCR, and TASK is
unable to improve much from its result. In general, less improvement can be obtained by the
TASK algorithm for a better schedule. This is because a good schedule leaves less room for
improvement. The TASK algorithm normally provides uniformly consistent performance. That
is, the schedule produced by TASK does not depend much on the initial schedule.
We also tested the local search algorithms with the DAGs generated from a real application,
Gaussian elimination with partial pivoting. The Gaussian elimination program operates on ma-
trices. The matrix is partitioned by columns. The nest grain size of this column partitioning
scheme is a single column. However, this ne-grain partition generates too many nodes in the
graph. For example, the ne-grain partition of a 1k1k matrix generates a DAG of 525,822 nodes.
To reduce the number of nodes, a medium-grain partition is used. Table 8 lists the number of
nodes in dierent matrix sizes and grain sizes (number of columns). The CCR is between 0.1 and
0.8. These graphs are generated by the Hypertool from an annotated sequential Gaussian elimination
program [24]. The comparisons of the FAST algorithm and the TASK algorithm on dierent
DAGs and dierent number of PEs are shown in Tables 9 and 10, where Table 9 uses CPN as
the initial scheduling algorithm and Table 10 uses DSC as the initial scheduling algorithm. In
general, a cluster algorithm such as DSC performs well when communication of a DAG is heavy.
Therefore, it generates better schedules for Gaussian elimination. TASK performs better than
FAST in most cases and is much faster than FAST.
7 Conclusion and Future Works
A local search is an eective method for solving NP-hard optimization problems. It can be
applied to improve the quality of existing scheduling algorithms. TASK is a low-complexity, high-performance
local search algorithm for static DAG scheduling. It can quickly reduce the schedule
length produced by any DAG scheduling algorithms. By utilizing the topological order, it is much
faster and of much higher quality than the random local search algorithm.
We have demonstrated that TASK was able to reduce drastically the schedule length produced
by some well-known algorithms such as DSC and CPN. In the future work, a comparison with
the best scheduling algorithms such as MCP [24] will be conducted. A preliminary comparison
showed that a small improvement was observed since the MCP produces very good results already.

Table

8: The number of nodes in dierent matrix sizes and grain sizes for Gaussian elimination
Matrix size 1k1k 2k2k
Grain size 64
# of nodes 138 530 2082 8258 530 2082 8258 32898

Table

9: Comparison for Gaussian elimination with CPN as Initial Scheduling Algorithm
Matrix Grain # of Schedule length Running time (sec)
size size PEs CPN +FAST % +TASK % CPN FAST TASK

Table

10: Comparison for Gaussian elimination with DSC as Initial Scheduling Algorithm
Matrix Grain # of Schedule length Running time (sec)
size size PEs DSC +FAST % +TASK % DSC FAST TASK

Acknowledgments

This research was partially supported by NSF Grants CCR-9505300 and CCR-9625784, NSERC
Research Grant OGP0046423, NSERC Strategic Grant MEF0045793, and NSERC Strategic Grant
STR0167029. We would like to thank the anonymous reviewers for their constructive comments.



--R

A comparison of list scheduling for parallel processing systems.
Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors

Scheduling parallel program tasks onto arbitrary target machines.
Task Scheduling in Parallel and Distributed Systems.
Computers and Intractability: A Guide to the Theory of NP-Completeness
Rinnoy Kan.
Parallel algorithms and architectures for very fast search (PhD Thesis).
How to solve Very Large-Scale Satis ability problems

Average time complexities of several local search algorithms for the satis
Local search for satis
Parallel sequencing and assembly line problems.
A comparison of multiprocessor scheduling heuristics.
Grain size determination for parallel processing.

FASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessors
Microword length minimization in microprogrammed controller synthesis.
Partitioning and Scheduling Parallel Programs for Multiprocessors.
A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures



A programming aid for message-passing systems
DSC: Scheduling parallel tasks on an unbounded number of processors.
PYRROS: Static Task Scheduling and Code Generation for Message-passing Multiprocessors
--TR

--CTR
Savina Bansal , Padam Kumar , Kuldip Singh, An Improved Duplication Strategy for Scheduling Precedence Constrained Graphs in Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.533-544, June
multiprocessors;fast local search;complexity;quality;DAG scheduling