On Runtime Parallel Scheduling for Processor Load Balancing.
AbstractParallel scheduling is a new approach for load balancing. In parallel scheduling, all processors cooperate to schedule work. Parallel scheduling is able to accurately balance the load by using global load information at compile-time or runtime. It provides high-quality load balancing. This paper presents an overview of the parallel scheduling technique. Scheduling algorithms for tree, hypercube, and mesh networks are presented. These algorithms can fully balance the load and maximize locality at runtime. Communication costs are significantly reduced compared to other existing algorithms.
Introduction
Static scheduling balances the workload before runtime and can be applied to problems with a
predictable structure, which are called static problems. Dynamic scheduling performs scheduling
activities concurrently at runtime, which applies to problems with an unpredictable structure,
which are called dynamic problems. Static scheduling utilizes the knowledge of problem characteristics
to reach a well-balanced load [1, 2, 3, 4]. However, it is not able to balance the load for
dynamic problems. In addition, the requirement of large memory space to store the task graph
restricts the scalability of static scheduling. Dynamic scheduling is a general approach suitable
for a wide range of applications [5, 6, 7]. It can adjust load distribution based on runtime system
load information. However, most runtime scheduling algorithms utilize neither the characteristics
information of application problems, nor the global load information for load balancing decisions.
System stability usually sacrifices both quality and quickness of load balancing.
Parallel scheduling is a promising technique for processor load balancing. In parallel schedul-
ing, all processors cooperate to schedule work. Parallel scheduling utilizes global load information
and is able to accurately balance the load. It provides high-quality, scalable load balancing. Some
parallel scheduling algorithms have been introduced in [8, 9, 10, 11].
Parallel scheduling can be applied to static problems. Most existing scheduling algorithms
for static problems running on a single processor are not scalable to massively parallel computers
because storing the task graph requires large memory space. To speed up scheduling and to
relax the demand of memory space, static scheduling can be parallelized. Kwok and Ahmad have
developed a parallel algorithm [12]. Wu has parallelized the MCP algorithm [13].
Parallel scheduling can also be applied to dynamic problems. When parallel scheduling is
applied at runtime, it becomes an incremental collective scheduling. It is applied whenever the
load becomes unbalanced. All processors collectively schedule the workload. Such a system has
been described in [11]. It starts with a system phase which schedules initial tasks; it is followed
by a user computation phase to execute the scheduled tasks and possibly to generate new tasks.
In the next system phase, the old tasks that have not been executed will be scheduled together
with the newly generated tasks. In each system phase, a parallel scheduling algorithm is applied
to balance the load.
In this paper, we discuss the parallel scheduling methodology. This paper is devoted particularly
to a kind of scheduling that only schedules ready jobs or tasks. That is, the objects to be
scheduled are a set of jobs or tasks that are ready to execute. Scheduling algorithms for tree,
hypercube, and mesh networks will be presented. These algorithms are primarily designed for dynamic
problems with randomly arrived or dynamically generated jobs or tasks. These algorithms
can fully balance the load, maximize locality, and significantly reduce communication overhead
compared to other existing algorithms.
This paper is organized as follows. In section 2, we discuss the optimal scheduling problem.
The parallel scheduling algorithms for tree, hypercube, and mesh topologies are presented in
section 3. The properties of these algorithms are described in section 4 and performance is
presented in section 5. Previous works are discussed in section 6, while section 7 concludes the
paper.
2. The Optimal Scheduling Problem
The objective of scheduling is to schedule works so that each processor has the same work
load. Thus, we need to estimate the task execution time. The estimation can be application-
specific, leading to a less general approach. Sometimes, such an estimation is difficult to obtain.
Due to these difficulties, each task is presumed to require equal execution time, and the objective
of the algorithm becomes to schedule tasks so that each processor has the same number of
tasks. Inaccuracy caused by grain-size variation can be corrected in the next system phase. An
algorithm with estimated time of tasks could improve load balancing to some extent. However,
since the algorithm is more complex, the scheduling overhead increases which may overwrite this
benefit [11].
The scheduling problem can be described as follows. In a parallel system, N computing nodes
are connected by a given topology. Each node i has w i tasks when parallel scheduling is applied.
A scheduling algorithm is to redistribute tasks so that the number of tasks in each node is equal.
Assume the sum of w i of all nodes can be evenly divided by N . The average number of tasks
w avg is calculated by
Each node should have w avg tasks after executing the scheduling algorithm. When w
the node must determine where to send the tasks.
In a communication step, many communications can be performed simultaneously. The time
spent on the load balancing activity depends on the number of communication steps and the
time taken for each step. For a parallel scheduling algorithm that utilizes global information,
the number of communication steps can be of the order of log N , where N is the number of
processors [14]. The average time of each communication step depends on both the total number
of tasks migrated and their traveling distances. The objective function is to minimize the number
of task-hops: X
where e k is the number of tasks transmitted through the edge k. In general, this problem can be
converted to the minimum-cost maximum-flow problem [15] as follows. Each edge is treated as a
bidirectional arc and given a tuple (capacity; cost), where capacity is the capacity of the edge and
cost is the cost of the edge. Set edges in the processor network.
Then add a source node s with an edge (s; i) to each node i if w i ? w avg and a sink node t with
an edge (j; t) from each node j if w cost
capacity cost minimum-cost maximum-flow algorithm yields a
solution to the problem. Figure 1 shows a load distribution in an eight-node hypercube network.
The graph constructed for Figure 1 is given in Figure 2, where w 8. The minimum cost
algorithm [15] generates a solution as shown in Figure 3.
The complexity of the minimum cost algorithm is O(N 2 v), where N is the number of nodes
and v is the desired flow value [15]. The complexity of its corresponding parallel algorithm on N
nodes is at least O(Nv). This high complexity is not realistic for runtime scheduling. For certain
topology, such as trees, the complexity can be reduced to O(log N) on N nodes. For a topology
other than trees, we need to find a heuristic algorithm.
3. Parallel Scheduling Algorithms
In this section, we present parallel scheduling algorithms for the tree, hypercube, and mesh
topologies. The common feature of these algorithms is that the total number of tasks is obtained by
Figure

1: A load distribution in a 3-dimensional hypercube.
s
All other edges
have

Figure

2: Graph for optimal scheduling problem (Figure 1).

Figure

3: An optimal solution of Figure 1.
a parallel reduction operation so that the average number of tasks per node can be calculated [14].
A node will not send its tasks to other nodes unless the number of tasks exceeds the average.
Therefore, only necessary tasks are migrated.
Before discussing individual algorithms for different topologies, we give a generic algorithm
which is shown in Figure 4. The first step collects global information by using a sum reduction [14].
In step 2, the average number of tasks per node is calculated. If the number of tasks cannot be
evenly divided by the number of nodes, the remaining R tasks are evenly distributed to the first
R nodes so that they have one more task than the others. The values of w avg and R are available
to each node. In step 3, each node calculates its quota so that each node knows if it is overloaded
or underloaded. The quotas for some subsets of nodes are also computed here for a particular
topology. In step 4, tasks are exchanged to meet the quotas with minimum communication.
Different algorithms are designed for different topologies.
Let w i be the number of tasks in node i.
1. Global Information Collection: Perform the sum reduction of w i to compute T and
other information, where T is the total number of tasks.
2. Average Load Calculation: w
3. Quota Calculation: Each node computes its quota q i
w avg otherwise
The quotas for some subsets of nodes are also computed.
4. Task Exchange: Each overloaded node determines where to send its excess tasks.

Figure

4: The Generic Parallel Scheduling Algorithm.
In the following subsections, we present three parallel scheduling algorithms: the Tree Walking
Algorithm (TWA), the Cube Walking Algorithm (CWA), and the Mesh Walking Algorithm
(MWA). The tree algorithm is an optimal algorithm in terms of the number of task-hops. The
hypercube and mesh algorithms are heuristic algorithms.
3.1 Tree Walking Algorithm
When the network topology is a tree, the complexity of optimal scheduling can be reduced.
The Tree Walking Algorithm (TWA) is shown in Figure 5, which is essentially the same as the one
presented in [11]. In step 1, when the total number of tasks is counted with a parallel reduction
operation, each node records the number of tasks in its subtree and its children's subtrees (if
any). In step 2, the root calculates the average number of tasks per node and then broadcasts
the number to every node. In step 3, each subtree rooted at node i calculates its quota Q i that
indicates how many tasks are to be scheduled to the subtree. Q i can be calculated directly as
follows:
where
Each node keeps records of Q i and Q j , where node j is node i's child (if any). In step 4, the
workload is exchanged so that at the end of the system phase each node has the same number of
tasks as its quota.
Tree Walking Algorithm (TWA)
Assign each node an order i according to the preorder traversal; and n i , the number of nodes of its
subtree, where is the total number of nodes in the system. Node i
has its parent node p i and also has a child vector c i;0 ; c i;1 ; ::::; c i;m i \Gamma1 to give its m i children's node
numbers.
1. Global Information Collection: Perform a sum reduction of w
2. Average Load Calculation:
3. Quota Calculation: The quota of each node q i is computed:
Also, the quota for each subtree is computed:
4. Task Exchange: Each node computes
4.1) For node i with j L
receive tasks from node p i .
4.2) For node i and
receive tasks from node c i;j .
4.3) For node i with j L
i tasks to node p i .
4.4) For node i and
i;j tasks to node c i;j .

Figure

5: The Tree Walking Algorithm
Lemma 1: After execution of TWA, the number of tasks in each node is equal to its quota.
Proof: Assume node j is a child of node i such that c
j in node j is equal to \Gammaj R
i;l
in node i. Thus, if j L
receive jj L
tasks from node i. Similarly, j R
i;l in node i is
equal to \Gammaj L
j in node j. Thus, if j R
receive jj R
tasks from node j. Therefore,
after execution of TWA, the number of tasks in node i is
j is child of i
j is child of i
Because
j is child of i
j is child of i
j is child of i
steps 1 and 2 spend 2m communication steps, where m is the depth of the
tree. The communication steps in step 4 is the distance from a leaf node to another leaf node,
which is at most 2m. Therefore, the total number of communication steps of this algorithm is
at most 4m. With a balanced tree, and the number of communication steps of this
parallel algorithm on N nodes is O(logN ).
Example 1:
An example is shown in Figure 6. The nodes in the tree are numbered by preorder traversal.
At the beginning of scheduling, each node has w i tasks ready to be scheduled. Values of W i are
calculated in step 1. The root calculates the value of w avg and R:
Then, each node calculates the value of Q i in step 3. The values of w
are shown as follows:
Figure

Example for the Tree Walking Algorithm.
The numbers of tasks to be exchanged between nodes are shown in Figure 6. At the end of
scheduling, nodes 0-4 have five tasks each, and nodes 5-8 have four tasks each.
3.2 Cube Walking Algorithm
In this subsection, we study two algorithms designed for the hypercube topology: the DEM
algorithm [8, 9] and the proposed Cube Walking Algorithm (CWA).
In DEM, small domains are balanced first and then combined to form larger domains until
ultimately the entire system is balanced. The "integer version" of DEM is described in Figure 7.
All node pairs in the first dimension whose addresses differ in only the least significant bit balance
the load between themselves. Next, all node pairs in the second dimension balance the load
between themselves, and so forth, until each node has balanced its load with each of its neighbors.
The number of communication steps of the DEM algorithm is 3d, where d is the number of
dimensions [16].
DEM
node i exchanges with node j the current values of w i and w j , where
if (w tasks to node j
if (w tasks from node j
update the value w i

Figure

7: The DEM algorithm.
Example 2:
The DEM algorithm is illustrated in Figure 8. The load distribution before execution of the
(a)
(b)
(c)
(d)

Figure

8: An example for the DEM algorithm.
DEM algorithm is shown in Figure 8(a). In the first step, nodes exchange load information and
balance the load in dimension 0 as shown in Figure 8(b). Then, the load is balanced in dimension 1
as shown in Figure 8(c). After load balancing in dimension 2 (Figure 8(d)), the final result is
shown in Figure 8(e). The load is not fully balanced, because only integer numbers of tasks can
be transmitted between nodes. There are a total of 33 task-hops, whereas the optimal scheduling
shown in Figure 3 has only 21 task-hops.
After execution of the DEM algorithm, the load difference
by d, the dimension of the hypercube [17]. Figure 9 shows an example where
4-dimensional hypercube.

Figure

9: An example which shows that the number of tasks differs by 4 resulting from DEM.
The DEM algorithm is simple and of low complexity. At each load balancing step, only node
pairs exchange their load information. No global information is collected. Without global load
information, it is impossible for a node to make a correct decision about how many tasks should
be sent. Node pairs attempt to average their number of tasks anyway. A node may send excessive
tasks to its neighbor. DEM is unable to fully balance the load and to minimize the communication
cost.
A good heuristic algorithm can be designed by utilizing global load information. Here we
present a new parallel scheduling algorithm for the hypercube topology. The algorithm, called
Cube Walking Algorithm (CWA), is shown in Figure 10. Let w 0
i be the number of tasks in node i
before the algorithm is applied. The first step collects the system load information by exchanging
values of w k
i to obtain the values of w k+1
i . Each node records a w vector, where w k
i is the total
number of tasks in its k-dimensional subcube. Here, the k-dimensional subcube of node i is
defined as all nodes whose numbers have the same (d \Gamma k)-bit prefix as node i. The value of
i in each node is equal to the total number of tasks in the entire cube. In step 2, each node
calculates the average number of tasks per node. A quota vector q is calculated in step 3 so that
each node knows if its k-dimensional subcubes are overloaded or underloaded. The vector q can
be computed directly as follows:
where
where - is the bitwise AND and - the bitwise OR. The ffi vector is the difference of w and q,
which stand for the number of tasks to be sent to or received from other subcubes.
Cube Walking Algorithm (CWA)
Assume the cube dimension is d, the number of nodes is
Let \Phi denote the bitwise exclusive OR and - the bitwise AND.
1. Global Information Collection:
Perform sum reductions. Each node computes its w vector,
2. Average Load Calculation:
3. Quota Calculation: Each node computes its vectors q k
4. Task Exchange: For do
4.1) For node i with
compute the number of tasks to be sent out
For
tasks as well as its ' vector to node i \Phi 2 k . Update its own w and ffi vectors for each
4.2) For node i with
receive tasks as well as the ' vector from node i \Phi 2 k . Update its
own w and ffi vectors for each dimension

Figure

10: The Cube Walking Algorithm.
In step 4, task exchanges are conducted among each dimension. We start with the cube of
dimension d \Gamma 1. Recursively, we partition a cube of dimension k into two subcubes of dimension
\Gamma1). Each node n(i) is paired with the corresponding node n(i) in the other subcube.
In this particular step, we only exchange tasks between n(i) and n(i) 0 , where
And, we send tasks only in one direction - from the overloaded subcube to the other. In this way,
an overloaded node does not necessarily commit itself to send tasks out since it may postpone the
action. The decision is made globally within the subcube by calculating a ' vector for every node
in the overloaded subcube. The calculation of ' is a local operation without any communication.
The value of ffi of n 0 can be calculated by
The fl vector records the
number of tasks reserved for subcubes of lower dimensions. The following lemma shows that at
the end of the algorithm, each node has the same number of tasks as its quota.
Lemma 2: After execution of CWA, the number of tasks in each node is equal to its quota.
Proof: To show after iteration 0 the number of tasks in each node is equal to its quota q 0
need to show that after iteration k, each k-dimensional subcube has q k
tasks. Then, the subcube
with
needs to send ffi k
i tasks to the other subcube with
Because tasks are sent in
one direction, the number of tasks sent from the overloaded subcube to the underloaded subcube
must be equal to ffi k
. That is,
It can be proven by showing that
There are three cases when assigning the value of ':
Case 1: when
i , we have
Hence,
Case 2: when ' j+1
since
since
Hence,
Case 3: when
since
since
Hence,
In this algorithm, step 1 spends 2d communication steps for exchanging load information,
where d is the dimension of the cube. Step 4 spends d communication steps for load balancing.
Therefore, the total number of communication steps of this algorithm is 3d.
Example 3:
A running example of CWA is shown in Figure 11. At the beginning of scheduling, each node
has w 0
tasks ready to be scheduled. Values of w k
are calculated at step 1. The values of w avg
and R are as follows:
Then, each node calculates the values of q k
i at step 3. Because every node has the same
quota vector:
At step 4, when 2, the subcube f0,1,2,3g is the overloaded one. The values of w k
are as follows:
Node d0 d1 d2
Thus, node 0 sends six tasks to node 4, and node 1 sends three tasks to node 5. Now, the
loads between subcubes f0, 1, 2, 3g and f4, 5, 6, 7g have been balanced. Each subcube has
tasks.
subcubes f0,1g and f4,5g are overloaded. The values of w k
are
as follows:
Node d0 d1
Thus, node 0 sends five tasks to node 2, and node 5 sends two tasks to node 7. The loads
between subcubes f0, 1g, f2, 3g, f4, 5g, and f6, 7g have been balanced. Each subcube has
tasks.
are overloaded. Their values of w k
are as
follows:
(a)
(b)
(c)

Figure

11: A running example of CWA.
Node d0
Finally, node 3 sends one task to node 2, node 5 sends two tasks to node 4, and node 6 sends
two tasks to node 7. This results in a balanced load, each node having eight tasks. The total
number of task-hops is 21.
3.3 Mesh Walking Algorithm
A parallel scheduling algorithm for the mesh topology named Mesh Walking Algorithm (MWA)
is shown in Figure 12. First, we scan the partial vector w along every row, and each node i records
a w vector w 0
Each node i (i mod calculates the sum
i;j . A scan operation is performed along these nodes, each of that keeps another
vector
c. The values of w avg and R are calculated at node N \Gamma 1, and
spread to all nodes i (i mod Consequently, these nodes spread the values of w avg ,
i\Gamman 2
along each row. Then, the vectors q 0 and ffi are calculated in each node, as
well as Q 0
i\Gamman 2
. The values of Q
i can be calculated directly by:
where
(i mod
R mod
where
R otherwise
In step 4, the first iteration the load among rows. All nodes calculate the
values of j i;0;L and j i;0;R . If receive jj i;0;L j tasks from row r \Gamma 1. If
receive jj i;0;R j tasks from row i + 1. If j i;0;R ? 0, the submesh from
row 0 to row is overloaded, and j i;0;R tasks need to be sent to row r + 1. Similarly, if
the submesh below row is underloaded, and j i;0;L tasks need to be sent to
row r \Gamma 1. Vector ' is calculated to determine how many tasks at each node need to be sent. The
calculation of j and ' is a local operation without any communication. Variable fl i;j;l indicates
how many tasks are to be reserved for the previous j nodes in the same row, and variable j i;j;l
tells how many tasks remain to be sent out. The values of w and ffi are updated. Iteration 0
Mesh Walking Algorithm (MWA)
Assume a n 1 \Theta n 2 mesh, the number of nodes is
1. Global Information Collection:
Perform scan operations and compute the w vectors:
For
2. Average Load Calculation:
3. Quota Calculation: Compute vectors q k
For
4. Task Exchange: Let
For do
Initialize
4.2) For receive tasks as well as the ' vector from node n l ;
update its own w vector for
4.3) For calculate the number of tasks to be sent out.
For
i;j and j
;l tasks as well as its ' vector to node n l ; update its own w and ffi vectors for

Figure

12: The Mesh Walking Algorithm.
balances the load in each row. The following lemma shows that at the end of the algorithm, each
node has the same number of tasks as its quota.
Lemma 3: After execution of MWA, the number of tasks in each node is equal to its quota.
Proof: In iteration 1,
i;j (2)
When
larger than or equal
to 0,
Because of (1) and (3) v 1
Assume for some
Because of
(1),
is equal to 0, we have
Assume there exists no
i so that ffi 0
Therefore,
From (1) and (2), and fl
Because of (4) and
Because of (3), (6), (7), and (8) j i;v 1
and
From (1) and
Because
;0;R and j
receive jj i;0;L j
tasks from node i receive jj i;0;R j tasks from node i
Therefore, after iteration 1,
The weight w 0
i is updated. In iteration 0, ' Therefore, after iteration 0, the number
of tasks in each row is
In this algorithm, step 1 spends n 2 communication steps to collect load information along
each row and n 1 communication steps to collect load information across rows. Broadcasting
and spreading operations spend communication steps. Step 4 spends at most n 1
communication steps for load balancing. Therefore, the total communication steps of this
algorithm is 3(n 1
Example 4:
A running example of MWA is shown in Figure 13. The total number of tasks is computed
by parallel reduction. The values of w avg and R are calculated:
Because every node has the same q 0
i , which are 8 and 32, respectively. The values
of
are also calculated:
The values of w 0
are listed as follows:
Nodes in the same row have the same values of w 1
which are listed
as follows:
(a)
9 3
(b)
(c)
(d)

Figure

13: A running example of MWA.
In iteration 1, every j i;0;L - 0. Therefore, tasks are sent in one direction for this example.
The values of ffi 0
are listed as follows:
In row 0, node 1 sends three tasks to node 5, and node 3 sends six tasks to node 7. When nodes
in row 1 receive the tasks and ' vectors, they update their ffi . Then, they calculate the ' vectors.
Node 4 sends nine tasks to node 8, and node 7 sends three tasks to node 11. Finally, nodes in
row 2 update their ffi and calculate the ' vectors. Node 8 sends three tasks to node 12, and node
9 sends two tasks to node 13. The task exchange is shown in Figure 13(b). The number of tasks
in each row now is equal to its quota q 1
i , which is 32.
In iteration 0, W 0
i is calculated from updated values of w. The values of Q
are:
The values of j vectors are as follows:
Nodes exchange tasks, as shown in Figure 13(c), according to the values of ' which is equal to
j. This results in a balanced load, and each node has eight tasks. The total number of task-hops
is 48.
4. Properties of the Scheduling Algorithms
In this section, we discuss the scheduling quality, locality, and communication costs of the
TWA, CWA, and MWA algorithms. The next theorem shows that these algorithms are able to
fully balance the load. If the number of tasks can be equally divided by the number of nodes,
then each node will have the equal number of tasks; otherwise, the number of tasks in each node
differs by one.
Theorem 1: The difference in the number of tasks in each node is at most one after execution
of TWA, CWA, or MWA.
Proof: From Lemmas 1, 2, and 3, the number of tasks in each node is equal to its quota after
execution of TWA, CWA, or MWA. Since the quota is either w avg or w avg + 1, the difference in
the number of tasks in each node is at most one. 2
These algorithms also maximize locality. Local tasks are the tasks that are not migrated to
other nodes, and non-local tasks are those that are migrated to other nodes. Maximum locality
implies the maximum number of local tasks and the minimum number of non-local tasks. In
Lemmas 4 and 5 and Theorems 2 and 3, we assume that the number of tasks T is evenly divided
by N , the number of nodes. When T is not evenly divided by N , the algorithms are nearly-optimal.
The following lemma gives the minimum number of non-local tasks.
Lemma 4: To reach a balanced load, the minimum number of non-local tasks is
Proof: Each node where w must receive (w tasks from other nodes for a
balanced load. Therefore, a total of
tasks must be migrated between nodes.The next theorem proves that these three algorithms maximize locality.
Theorem 2: The number of non-local tasks in the TWA, CWA, or MWA algorithm is
Proof: At any time when executing the TWA, CWA, or MWA algorithm, the number of
tasks in each node is not less than min(w; w avg ). In TWA, each node receives tasks before sending
tasks. In CWA or MWA, each node sends tasks only when its weight is larger than w avg and no
more than (w tasks are sent out. Thus, in all nodes at least
tasks are
local. Therefore, the number of non-local tasks is no more than
N \Theta w avg \Gamma
(w
As stated in Lemma 4, these algorithms minimize the number of non-local tasks and maximize
locality. 2
TWA is an optimal scheduling algorithm. The next theorem proves that TWA minimizes the
number of task-hops and communication.
Theorem 3: The TWA algorithm minimizes
the total number of task-hops, and the total
number of communications.
Proof: For an edge k that connects a subtree i and its parent, if
which is the minimum number of tasks to be transmitted from its parent to the subtree. Similarly,
which is the minimum number of tasks to be transmitted from the
subtree to its parent. Therefore,
the total number of task-hops, is minimized.
For each subtree i, if Q i 6= W i , then there is at least one communication between the subtree
and its parent, which is the minimum number of communications. If Q there is no
communication between the subtree and its parent. Therefore, the total number of communications
is minimized. 2
CWA and MWA are heuristic algorithms and in general are not able to minimize the communication
cost. However, for a system with less than or equal to four nodes, the algorithms
minimize the communication cost.
Lemma 5: The CWA and MWA algorithms minimize the communication cost in a system with
two or four nodes.
Proof: The communication cost in a system is minimized if there is no negative cycle [15].
In a system of two nodes, there is no cycle. In a system of four nodes, only a path consisting of
at least three edges can form a negative cycle. With either CWA or MWA, the longest path has
two edges. Therefore, there is no negative cycle. 2
The DEM algorithm does not minimize the communication cost for four nodes because there
may be a path consisting of three edges.
5. Performance Study
TWA is an optimal algorithm. It minimizes communication and maximizes locality while
balancing the load. The optimality of heuristic algorithms, CWA and MWA, needs to be studied
with simulation. For this purpose, we consider a test set of load distributions. In this test set, the
load at each processor is randomly selected, with the mean equal to the specified average number
of tasks. The number of processors varies from 4 to 256. The average number of tasks (average
weight) per processor varies from 2 to 100. The average weight is made to be an integer so that
the load can be fully balanced.
First, we study CWA and compare its performance to DEM. CWA can fully balance the load
but DEM cannot in most cases. Table I shows the percentage of fully-balanced cases of the
DEM algorithm. We run the DEM algorithm with different numbers of processors and different
weights. Each result is from 1,000 test cases. When the number of processors increases, there are
less fully-balanced cases. For 32 processors there are a few cases, and for 64 processors, there is
no fully-balanced case in this test set.
An important measure of a scheduling algorithm is its locality. The CWA algorithm sends
only necessary tasks to other processors so that it maximizes locality. The DEM algorithm results
in unnecessary task migration. Here, we study locality of the DEM algorithm. Because DEM is
not able to fully balance the load for all cases, only the fully-balanced cases are selected. Each
result is the average of the fully-balanced cases in 1,000 test cases. The normalized locality is

Table

I: The Percentage of Fully-Balanced Cases of DEM
Number of Average weight
Processors
4 74.30% 75.30% 75.70% 75.10% 74.50% 74.60%
measured by
where TDEM is the total number of non-local tasks in the DEM algorithm, and TOPT is the
minimum number of non-local tasks. Figure 14 shows the normalized locality on 4, 8, and 16
processors. Because few fully-balanced cases exist on more than 16 processors, they are not
reported here.
0%
5%
10%
15%
20%
30%
40%
Normalized
Locality
Weight
processors
processors
processors

Figure

14: Normalized locality of DEM
Next, we compare the load balancing overhead. DEM is very simple so that the runtime
overhead for load balancing decision is small. However, unnecessary task migration leads to a
large communication overhead. Compared to the time spent on the load balancing decision,
communication time is the dominate factor. CWA, on the other hand, although needing more
time to make an accurate load balancing decision, involves less communication overhead. The
normalized communication cost is measured by
COPT
Normalized
Cost
Weight
DEM
(a) 4 processors
0%
5%
10%
15%
20%
30%
Normalized
Cost
Weight
DEM
(b) 8 processors
0%
5%
10%
15%
20%
30%
40%
45%
50%
Normalized
Cost
Weight
DEM
(c) processors

Figure

15: Normalized communication costs of DEM and CWA
Normalized
Cost
Weight
(a) 64 processors
0%
5%
10%
15%
20%
30%
40%
45%
Normalized
Cost
Weight
(b) 256 processors

Figure

Normalized communication costs of CWA
and
COPT
where CDEM , CCWA , and COPT are the number of task-hops of the DEM, CWA, and optimal
algorithms, respectively. Figure 15 compares the normalized communication costs on 4, 8, and
processors. Each result is the average of the DEM fully-balanced cases in 1,000 test cases.
The number of task-hops of CWA on four processors is the minimum. It can be seen that the
communication costs of DEM are much larger than those of CWA. Figure 16 shows the normalized
communication costs of CWA on 64 and 256 processors. Each data presented here is the average
of 100 different test cases.
The method and assumptions used for performance study of the MWA algorithm are the same
as those for the CWA algorithm. MWA is able to fully balance the load and maximize locality.
However, its communication is not minimized in most cases. The normalized communication cost
of MWA with respect to the optimal algorithm is measured by
where CMWA and COPT are the numbers of task-hops of the MWA and optimal algorithms, re-
spectively. As mentioned in Lemma 3, the number of task-hops of MWA on two or four processors
is the minimum. Figure 17 shows the normalized communication costs on 8 to 256 processors.
The mesh organization is either M \Theta M or M \Theta M=2. Each data presented here is the average
of 100 different test cases. For small meshes, MWA provides a nearly optimal result. The cost
increases with the number of processors.
0%
1%
2%
3%
4%
5%
6%
7%
8%
9%
Normalized
Cost
Weight
processors
processors
processors
(a) 8, 16, and processors
0%
5%
10%
15%
20%
30%
40%
45%
50%
Normalized
Cost
Weight
processors
128 processors
processors
(b) 64, 128, and 256 processors

Figure

17: Normalized communication cost of MWA.
6. Previous Works
Parallel scheduling and static scheduling share some common ideas [1, 2, 3, 4, 18]. Both of
them utilize global information to achieve high quality load balancing. But, parallel scheduling
is different from static scheduling in three aspects. First, the scheduling activity is performed
at runtime. Therefore, it can deal with the dynamic problems. Second, the possible load imbalance
caused by inaccurate grain size estimation can be corrected by the next turn of scheduling.
Third, it eliminates the requirement of large memory space to store task graphs, as scheduling
is conducted in an incremental fashion. It then leads to better scalability for massively parallel
machines and large size applications.
Large research efforts have been directed towards process allocation in distributed systems
[7, 5, 6, 19, 20, 21, 22, 23]. A recent comparison study of dynamic load balancing strategies on
highly parallel computers is given by Willebeek-LeMair and Reeves [16]. Eager et al. compared
the sender-initiated algorithm with the receiver-initiated algorithm [6]. Work with a similar
assumption to ours includes the Gradient Model developed by Lin and Keller [24]. The randomized
allocation algorithms developed by different authors are quite simple and effective [25, 5, 26,
27]. The adaptive contracting within neighborhood (ACWN) [22] and receiver-initiated diffusion
(RID) [16] are other effective algorithms.
Runtime parallel scheduling is similar to dynamic scheduling to a certain degree. Both methods
schedule tasks at runtime instead of compile-time. Their scheduling decisions, in principle, depend
on and adapt to the runtime system information. However, substantial differences make them
appear as two separate categories. First, the system functions and user computation are mixed
together in dynamic scheduling, but there is a clear cutoff between system and user phases in
runtime parallel scheduling, which potentially offers easy management and low overhead. Second,
placement of a task in dynamic scheduling is basically an individual action by a processor based
on partial system information; whereas in parallel scheduling, the scheduling activity is always an
aggregate operation based on global system information.
A category of scheduling sometimes referred to as prescheduling is closely related to the idea
presented in this paper. Prescheduling schedules workload according to the problem input. There-
fore, problems whose load distribution depends on its input and cannot be balanced by static
scheduling can be balanced by prescheduling. Applying prescheduling periodically, the load can
be balanced at runtime. Fox et al. first adapted prescheduling to application problems with geometric
structures [28, 29]. Some other works also deal with this type of problem [30, 31, 32]. The
project PARTI automates prescheduling for nonuniform problems [33]. The dimension exchange
method (DEM) is applied to application problems without geometric structure [9]. It was conceptually
designed for a hypercube system but may be applied to other topologies, such as k-ary
n-cubes [34]. It balances load for independent tasks with an equal grain size. The method has
been extended by Willebeek-LeMair and Reeves [16] so that the algorithm can run incrementally
to correct the unbalanced load caused by varied grain sizes. Nicol has proposed a direct mapping
algorithm which computes the total number of tasks by using sum-reduction [10]. However, it
does not minimize the communication cost, nor eliminate communication conflict. An incremental
scheduling for N-body simulation is presented in [35]. The task graph is rescheduled periodically
to correct the load imbalance. However, its runtime scheduling has not yet been parallelized.
7. Conclusion
Recent research has demonstrated that runtime parallel scheduling can provide a low-overhead
load balancing with global load information. In parallel scheduling, a synchronous approach removes
the stability problem and is able to balance the load quickly and accurately. Parallel
scheduling combines the advantages of static scheduling and dynamic scheduling. All processors
cooperate to collect load information and to exchange workload in parallel. With parallel schedul-
ing, it is possible to obtain high quality load balancing with a fully-balanced load and maximized
locality. Communication costs can be reduced significantly. Three algorithms for tree, hypercube,
and mesh networks have been presented in this paper. It is not difficult to develop an algorithm
for the k-ary n-cube by combining the CWA and MWA algorithms.

Acknowledgments

The author would like to thank Xin He for his helpful discussion.



--R

"Scheduling parallel program tasks onto arbitrary target machines,"
"Hypertool: A programming aid for message-passing systems,"
"PYRROS: Static task scheduling and code generation for message-passing multiprocessors,"
"Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors,"
"Adaptive load sharing in homogeneous distributed systems,"
"A comparison of receiver-initiated and sender-initiated adaptive load sharing,"
"Load distributing for locally distributed sys- tems,"
"Programming a hypercube multicomputer,"
"Dynamic load balancing for distributed memory multiprocessors,"
"Communication efficient global load balancing,"
"Runtime Incremental Parallel Scheduling (RIPS) on distributed memory computers,"
"A parallel approach to multiprocessor scheduling,"
"An efficient parallel scheduling algorithm,"
Vector Models for Data-Parallel Computing
Networks and Matroids.
"Strategies for dynamic load balancing on highly parallel computers,"
"Analysis of a graph coloring based distributed load balancing algorithm,"
"Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors,"
"Simulations of three adaptive, decentralized controlled, job scheduling algorithms,"
"Analysis of three dynamic distributed load-balancing strategies with varying global information requirements,"
"Load sharing in distributed systems,"
"Adaptive dynamic process scheduling on distributed memory parallel computers,"
"Scheduling multithreaded computations by work stealing,"
"The gradient model load balancing method,"
Fine Grain Concurrent Computations.
"A randomized parallel branch-and-bound procedure,"
"Randomized load balancing for tree structured computation,"
Solving Problems on Concurrent Processors
"Parallel hierarchical N-body methods,"
"A low-cost hypercube load balance algorithm,"
"A partitioning strategy for non-uniform problems on multipro- cessors,"
"Dynamic load balancing of a vortex calculation running on multiprocessors,"
"The PARTY parallel run-time system,"
"The generalized dimension exchange method for load balancing in k-ary n-cubes and variants,"
"Experience with graph scheduling for mapping irregular scientific computation,"
--TR

--CTR
Chen Ximing , Lu Xianliang, Runtime incremental concentrated scheduling on NOW(NRICS), ACM SIGOPS Operating Systems Review, v.34 n.2, p.84-96, April, 2000
Hwakyung Rim , Ju-wook Jang , Sungchun Kim, A simple reduction of non-uniformity in dynamic load balancing of quantized loads on hypercube multiprocessors and hiding balancing overheads, Journal of Computer and System Sciences, v.67 n.1, p.1-25, August
Janez Brest , Viljem umer , Milan Ojsterek, Dynamic scheduling on a PC cluster, Proceedings of the 1999 ACM symposium on Applied computing, p.496-500, February 28-March 02, 1999, San Antonio, Texas, United States
Wan Yeon Lee , Sung Je Hong , Jong Kim , Sunggu Lee, Dynamic load balancing for switch-based networks, Journal of Parallel and Distributed Computing, v.63 n.3, p.286-298, March
Hee-Jun Park , Byung Kook Kim, Optimal task scheduling algorithm for cyclic synchronous tasks in general multiprocessor networks, Journal of Parallel and Distributed Computing, v.65 n.3, p.261-274, March 2005
K. Antonis , J. Garofalakis , I. Mourtos , P. Spirakis, A hierarchical adaptive distributed algorithm for load balancing, Journal of Parallel and Distributed Computing, v.64 n.1, p.151-162, January 2004
Arnaud Legrand , Hlne Renard , Yves Robert , Frdric Vivien, Mapping and Load-Balancing Iterative Computations, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.546-558, June 2004
Ching-Jung Liao , Yeh-Ching Chung, Tree-Based Parallel Load-Balancing Methods for Solution-Adaptive Finite Element Graphs on Distributed Memory Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.10 n.4, p.360-370, April 1999
Yeh-Ching Chung , Ching-Jung Liao , Don-Lin Yang, A Prefix Code Matching Parallel Load-Balancing Method for Solution-Adaptive Unstructured Finite Element Graphs on Distributed Memory Multicomputers, The Journal of Supercomputing, v.15 n.1, p.25-49, Jan. 2000
distributed memory computers;trees;runtime parallel scheduling;load balancing;meshes;scheduling algorithms;hypercubes