Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors

because the amount of computations en-

capsulated in tasks are usually varied.

Furthermore, parallel and distributed

architectures have evolved into various

types such as distributed-memory mul-

ticomputers

[Hwang 1993];

shared-memory multiprocessors (SMMs)

[Hwang 1993]; clusters of symmetric

multiprocessors (SMPs) [Hwang 1993];

and networks of workstations (NOWs)

[Hwang 1993]. Therefore, their more de-

tailed architectural characteristics must

be taken into account. For example, in-

tertask communication in the form of

message-passing or shared-memory ac-

cess inevitably incurs a non-negligible

amount of latency. Moreover, a conten-

tion-free communication and full con-

nectivity of processors cannot be as-

sumed for a DMM, a SMP or a NOW.

(DMMs)

ACM Computing Surveys, Vol. 31, No. 4, December 1999

Thus, scheduling algorithms relying on

such assumptions are apt to have re-

stricted applicability in real environ-

ments.

Multiprocessor scheduling has been

an active research area and, therefore,

many different assumptions and termi-

nology are independently suggested.

Unfortunately, some of the terms and

assumptions are neither clearly stated

nor consistently used by most of the

researchers. As a result, it is difficult to

appreciate the merits of various sched-

uling algorithms and quantitatively

evaluate their performance. To avoid

this problem, we first introduce the di-

rected acyclic graph (DAG) model of a

parallel program, and then proceed to

describe the multiprocessor model. This

is followed by a discussion about the

NP-completeness of variants of the DAG

scheduling problem. Some basic tech-

niques used in scheduling are intro-

duced. Then we describe a taxonomy of

DAG scheduling algorithms and use it

to classify several reported algorithms.

The problem of scheduling a set of

tasks to a set of processors can be di-

vided into two categories: job scheduling

and scheduling and mapping (see Fig-

ure 1(a)). In the former category, inde-

pendent jobs are to be scheduled among

the processors of a distributed comput-

ing system to optimize overall system

performance [Bozoki and Richard 1970;

Chen and Lai 1988a; Cheng et al. 1986].

In contrast, the scheduling and map-

ping problem requires the allocation of

multiple interacting tasks of a single

parallel program in order to minimize

the completion time on the parallel com-

puter system [Adam et al. 1974; Ahmad

et al. 1996; Bashir et al. 1983; Casavant

and Kuhl 1988; Coffman 1976; Veltman

et al. 1990]. While job scheduling re-

quires dynamic

run-time scheduling

that is not a priori decidable, the sched-

uling and mapping problem can be ad-

dressed in both static [El-Rewini et al.

1995; 1994; Gerasoulis and Yang 1992;

Hochbaum and Shmoys 1987; 1988;

Khan et al. 1994; McCreary et al. 1994;

Shirazi et al. 1990] as well as dynamic

Static Scheduling for Task Graph Allocation

•

409

Figure 1.

graph; (c) a task precedence graph.

(a) A simplified taxonomy of the approaches to the scheduling problem; (b) a task interaction

contexts [Ahmad and Ghafoor 1991;

Norman and Thanisch 1993]. When the

characteristics of the parallel program,

including its task execution times, task

dependencies, task communications and

synchronization are known a priori,

scheduling can be accomplished off-line

during compile-time. On the contrary,

dynamic scheduling in the absence of a

priori information is done on-the-fly ac-

cording to the state of the system.

Two distinct models of the parallel

program have been considered exten-

sively in the context of static schedul-

ing: the task interaction graph (TIG)

model and the task precedence graph

(TPG) model (see Figure 1(b) and Figure

1(c)).

The task interaction graph model, in

which vertices represent parallel pro-

cesses and edges denote the interpro-

cess interaction [Bokhari 1981], is usu-

ally used in static scheduling of loosely

coupled communicating processes (since

all tasks are considered as simulta-

neously and independently executable,

there is no temporal execution depen-

dency) to a distributed system. For ex-

ample, a TIG is commonly used to model

the

(FEM)

[Bokhari 1979]. The objective of sched-

uling is to minimize parallel program

completion time by properly mapping

the tasks to the processors. This re-

quires balancing the computation load

uniformly among the processors while

element method

finite

ACM Computing Surveys, Vol. 31, No. 4, December 1999

410

•

Y.-K. Kwok and I. Ahmad

simultaneously keeping communication

costs as low as possible. The research in

this area was pioneered by Bokhari

[1979] and Stone [1977]: Stone [1977]

applied network-flow algorithms

to

solve the assignment problem, whereas

Bokhari [1981] described the mapping

problem as being equivalent to graph

assignment,

quadratic

isomorphism,

and sparse matrix bandwidth reduction

problems.

The task precedence graph model (or

simply the DAG) in which the nodes

represent the tasks and the directed

edges represent the execution depen-

dencies as well as the amount of com-

munication, is commonly used in static

scheduling of a parallel program with

tightly coupled tasks on multiproces-

sors. For example, in the task prece-

dence graph shown in Figure 1(c), task

n 4 cannot commence execution before

tasks n 1 and n 2 finish execution and

gathers all

the communication data

from n 2 and n 3. The scheduling objec-

tive is to minimize the program comple-

tion time (or maximize the speed-up,

defined as the time required for sequen-

tial execution divided by the time re-

quired for parallel execution). For most

parallel applications, a task precedence

graph can model the program more ac-

curately because it captures the tempo-

ral dependencies among tasks. This is

the model we use in this paper.

As mentioned above, earlier static

scheduling research made simplifying

assumptions about the architecture of

the parallel program and the parallel

machine, such as uniform node weights,

zero edge weights, and the availability

of an unlimited number of processors.

However, even with some of these as-

sumptions, the scheduling problem has

been proven to be NP-complete except

for a few restricted cases [Garey and

Johnson 1979]. Indeed, the problem is

NP-complete even in two simple cases:

tasks with uniform

(1)

weights to an arbitrary number of pro-

cessors [Ullman 1975] and (2) schedul-

ing tasks with weights equal to one or

scheduling

ACM Computing Surveys, Vol. 31, No. 4, December 1999

algorithms.

two units to two processors [Ullman

1975]. There are only three special

cases for which there exists optimal

These

polynomial-time

cases are (1) scheduling tree-structured

task graphs with uniform computation

costs on an arbitrary number of proces-

sors [Hu 1961]; (2) scheduling arbitrary

task graphs with uniform computation

costs on two processors [Coffman and

Graham 1972]; and (3) scheduling an

interval-ordered task graph [Fishburn

1985] with uniform node weights to an

arbitrary number of processors [Papad-

imitriou and Yannakakis 1979]. How-

ever, even in these cases, communica-

tion among

the parallel

program is assumed to take zero time

[Coffman 1976]. Given these observa-

tions, the general scheduling problem

cannot be solved in polynomial-time un-

less P 5 NP.

tasks

of

Due to the intractability of the gen-

eral scheduling problem, two distinct

approaches have been taken: sacrificing

efficiency for the sake of optimality and

sacrificing optimality for the sake of

efficiency. To obtain optimal solutions

under relaxed constraints, state-space

search and dynamic programming tech-

niques have been suggested. However,

these techniques are not useful because

most of them are designed to work un-

der restricted environments and most

importantly they incur an exponential

time in the worst case. In view of the

ineffectiveness of optimal techniques,

many heuristics have been suggested to

tackle the problem under more prag-

matic situations. While these heuristics

are shown to be effective in experimen-

tal studies, they usually cannot gener-

ate optimal solutions, and there is no

guarantee about their performance in

the heuristics are

general. Most of

based on a list scheduling approach

[Coffman 1976], which is explained be-

low.

2. THE DAG SCHEDULING PROBLEM

The objective of DAG scheduling is to

minimize the overall program finish-

Static Scheduling for Task Graph Allocation

•

411

time by proper allocation of the tasks to

the processors and arrangement of exe-

cution sequencing of the tasks. Schedul-

ing is done in such a manner that the

precedence constraints among the pro-

gram tasks are preserved. The overall

finish-time of a parallel program is com-

monly called the schedule length or

makespan. Some variations to this goal

have been suggested. For example,

some researchers proposed algorithms

to minimize the mean flow-time or

mean finish-time, which is the average

of the finish-times of all the program

tasks [Bruno et al. 1974; Leung and

Young 1989]. The significance of the

mean finish-time criterion is that mini-

mizing it in the final schedule leads to

the reduction of the mean number of

unfinished tasks at each point in the

schedule. Some other algorithms try to

reduce the setup costs of the parallel

processors [Sumichrast 1987]. We focus

on algorithms that minimize the sched-

ule length.

2.1 The DAG Model

A parallel program can be represented

by a directed acyclic graph (DAG) G 5

~V, E!, where V is a set of v nodes and

E is a set of e directed edges. A node in

the DAG represents a task which in

turn is a set of instructions which must

be executed sequentially without pre-

emption in the same processor. The

weight of a node n i is called the compu-

tation cost and is denoted by w~n i!. The

edges in the DAG, each of which is

denoted by ~n i, n j!, correspond to the

communication messages and prece-

dence constraints among the nodes. The

weight of an edge is called the commu-

nication cost of the edge and is denoted

by c~n i, n j!. The source node of an edge

is called the parent node while the sink

node is called the child node. A node

with no parent is called an entry node

and a node with no child is called an

exit node. The communication-to-com-

putation-ratio (CCR) of a parallel pro-

gram is defined as its average edge

weight divided by its average node

weight. Hereafter, we use the terms

node and task interchangeably. We

summarize in Table I the notation used

throughout the paper.

The precedence constraints of a DAG

dictate that a node cannot start execu-

tion before it gathers all of the messages

from its parent nodes. The communica-

tion cost between two tasks assigned to

the same processor is assumed to be

zero. If node n i

is scheduled to some

processor, then ST~n i! and FT~n i! de-

note the start-time and finish-time of

n i, respectively. After all the nodes have

been scheduled, the schedule length is

defined as max i$FT~n i!% across all pro-

cessors. The goal of scheduling is to

minimize max i$FT~n i!%.

The node and edge weights are usu-

ally obtained by estimation at compile-

time [Ahmad et al. 1997; Chu et al.

1984; Ha and Lee 1991; Cosnard and

Loi 1995; Wu and Gajski 1990]. Genera-

tion of the generic DAG model and some

of the variations are described below.

2.2 Generation of a DAG

A parallel program can be modeled by a

DAG. Although program loops cannot be

explicitly represented by the DAG

model, the parallelism in data-flow com-

putations in loops can be exploited to

subdivide the loops into a number of

tasks by the loop-unraveling technique

[Beck et al. 1990; Lee and Feng 1991].

The idea is that all iterations of the loop

are started or fired together, and opera-

tions in various iterations can execute

when their input data are ready for

access. In addition, for a large class of

data-flow computation problems and

many numerical algorithms (such as

matrix multiplication), there are very

few, if any, conditional branches or in-

determinism in the program. Thus, the

DAG model can be used to accurately

represent these applications so that the

scheduling techniques can be applied.

Furthermore, in many numerical appli-

ACM Computing Surveys, Vol. 31, No. 4, December 1999

412

•

Y.-K. Kwok and I. Ahmad

Symbol

n i

w~n i!

~n i, n j!

c~n i, n j!

v

e

p

CP

CP

CPN

IBN

OBN

sl

b-level

t-level

ASAP

ALAP

T s~n i!

DAT~n i, P!

ST~n i, P!

FT~n i, P!

VIP~n i!

Pivot 2PE

Proc~n i!

L ij

CCR

SL

UNC

BNP

TDB

APN

Table I. Notation

Definition

The node number of a node in

the parallel program task graph

The computation cost of node n i

An edge from node n i to n j

The communication cost of the

directed edge from node n i to n j

Number of nodes in the task

graph

Number of nodes in the task

graph

Number of edges in the task

graph

The number of processors or

processing elements (PEs) in

the target system

A critical path of the task graph

Critical Path Node

In-Branch Node

Out-Branch Node

Static level of a node

Bottom level of a node

Top level of a node

As soon as possible start time

of a node

As late as possible start time of

a node

The actual start time of a node n i

The possible data available

time of n i on target processor P

The start time of node n i on

target processor P

The finish time of node n i on

target processor P

The parent node of n i that

sends the data arrive last

The target processor from

which nodes are migrated

The processor accommodating

node n i

The communication link

between PE i and PE j

Communication-to-computation

Ratio

Schedule Length

Unbounded Number of Clusters

scheduling algorithms

Bounded Number of Processors

scheduling algorithms

Task Duplication Based

scheduling algorithms

Arbitrary Processors Network

scheduling algorithms

cations, such as Gaussian elimination

or fast Fourier transform (FFT), the

loop bounds are known during compile-

ACM Computing Surveys, Vol. 31, No. 4, December 1999

time. As such, one or more iterations of

a loop can be deterministically encapsu-

lated in a task and, consequently, be

represented by a node in a DAG.

The node- and edge-weights are usu-

ally obtained by estimation using profil-

ing information of operations such as

numerical operations, memory access

operations, and message-passing primi-

tives [Jiang et al. 1990]. The granular-

ity of tasks usually is specified by the

programmers [Ahmad et al. 1997]. Nev-

ertheless, the final granularity of the

scheduled parallel program is to be re-

fined by using a scheduling algorithm,

which clusters the communication-in-

tensive tasks to a single processor [Ah-

mad et al. 1997; Yang and Gerasoulis

1992].

2.3 Variations in the DAG Model

There are a number of variations in the

generic DAG model described above.

The more important variations are: pre-

emptive scheduling vs. nonpreemptive

scheduling, parallel tasks vs. non-paral-

lel tasks, and DAG with conditional

branches vs. DAG without conditional

branches.

et

al.

Preemptive Scheduling vs. Nonpre-

In preemptive

emptive Scheduling:

scheduling, the execution of a task may

be interrupted so that the unfinished

portion of the task can be re-allocated to

a different processor [Chen and Lai

1988b; Gonzales and Sahni 1978; Hor-

vath

1977; Rayward-Smith

1987a]. On the contrary, algorithms as-

suming nonpreemptive scheduling must

allow a task to execute until completion

on a single processor. From a theoreti-

cal perspective, a preemptive schedul-

ing approach allows more flexibility for

the scheduler so that a higher utiliza-

tion of processors may result. Indeed, a

preemptive scheduling problem is com-

monly reckoned as “easier” than its non-

preemptive counterpart in that there

are cases in which polynomial time so-

lutions exist for the former while the

latter is proved to be NP-complete [Coff-

man and Graham 1972; Gonzalez, Jr.

Static Scheduling for Task Graph Allocation

•

413

1977]. However, in practice, interrupt-

ing a task and transferring it to another

processor can lead to significant pro-

cessing overhead and communication

delays. In addition, a preemptive sched-

uler itself is usually more complicated

since it has to consider when to split a

task and where to insert the necessary

communication induced by the splitting.

We concentrate on the nonpreemptive

approaches.

independent parallel

Parallel Tasks vs. Nonparallel Tasks:

A parallel task is a task that requires

more than one processor at the same

time for its execution [Wang and Cheng

1991]. Blazewicz et al. [1986; 1984] in-

vestigated the problem of scheduling a

tasks to

set of

identical processors under preemptive

and nonpreemptive scheduling assump-

tions. Du and Leung [1989] also ex-

plored the same problem but with one

more flexibility: a task can be scheduled

to no more than a certain predefined

maximum number of processors. How-

ever, in Blazewicz et al. ’s approach, a

task must be scheduled to a fixed pre-

defined number of processors. Wang

and Cheng [1991] further extended the

model to allow precedence constraints

among tasks. They devised a list sched-

uling approach to construct a schedule

based on the earliest completion time

(ECT) heuristic. We concentrate on

scheduling DAGs with

nonparallel

tasks.

DAG with Conditional Branches vs.

DAG without Conditional Branches:

Towsley [1986] addressed the problem

of scheduling a DAG with probabilistic

branches and loops to heterogeneous

distributed systems. Each edge in the

DAG is associated with a nonzero prob-

ability that the child will be executed

immediately after the parent. He intro-

duced two algorithms based on the

shortest path method for determining

the optimal assignments of tasks to pro-

cessors. El-Rewini and Ali [1995] also

investigated the problem of scheduling

DAGs with conditional branches. Simi-

lar to Towsley’s approach, they also

used a two-step method to construct a

the

final schedule. However, unlike Tows-

ley’s model, they modeled a parallel pro-

gram by using two DAGs: a branch

graph and a precedence graph. This

model differentiates

conditional

branching and the precedence relations

among the parallel program tasks. The

objective of the first step of the algo-

rithm is to reduce the amount of inde-

terminism in the DAG by capturing the

similarity of different instances of the

precedence graph. After this preprocess-

ing step, a reduced branch graph and a

reduced precedence graph are gener-

ated. In the second step, all the differ-

ent instances of the precedence graph

are generated according to the reduced

branch graph, and the corresponding

schedules

determined. Finally,

these schedules are merged to produce a

unified final schedule [El-Rewini and

Ali 1995]. Since modeling branching

and looping in DAGs is an inherently

difficult problem, little work has been

reported in this area. We concentrate on

DAGs without conditional branching in

this research.

are

2.4 The Multiprocessor Model

In DAG scheduling, the target system is

assumed to be a network of processing

elements (PEs), each of which is com-

posed of a processor and a local memory

unit so that the PEs do not share mem-

ory and communication relies solely on

message-passing. The processors may

be heterogeneous or homogeneous. Het-

erogeneity of processors means the pro-

cessors have different speeds or process-

ing capabilities. However, we assume

every module of a parallel program can

be executed on any processor even

though the completion times on differ-

ent processors may be different. The

PEs are connected by an interconnec-

tion network with a certain topology.

The topology may be fully connected or

of a particular structure such as a hy-

percube or mesh.

ACM Computing Surveys, Vol. 31, No. 4, December 1999

414

•

Y.-K. Kwok and I. Ahmad

Table II. Summary of Optimal Scheduling Under Various Simplified Situations

Researcher(s)

Complexity

p

Hu [1961]

Coffman and Graham

[1972]

Sethi [1976]

Papadimitrious and

Yannakakis [1979]

Ali and El-Rewini

[1993]

Papadimitrious and

Yannakakis [1979]

Garey and Johnson

[1979]

Ullman [1975]

Ullman [1975]

O~v!

O~v 2!

O~va~v! 1 e!

O~ve!

O~ev!

NP-complete

—

2

2

—

—

—

w~n i!

Uniform

Uniform

Uniform

Uniform

Uniform

(5c)

—

Structure

c~n i, n j!

Free-tree

—

NIL

NIL

—

NIL

Interval-ordered NIL

Interval-ordered Uniform

(5c)

Interval-ordered NIL

Open

Fixed, .2

Uniform

NP-complete

NP-complete

—

Fixed, .1

Uniform

51 or 2

—

—

—

NIL

NIL

NIL

3. NP-COMPLETENESS OF THE DAG

SCHEDULING PROBLEM

The DAG scheduling problem is in gen-

eral an NP-complete problem [Garey

and Johnson 1979], and algorithms for

optimally scheduling a DAG in polyno-

mial-time are known only for three sim-

ple cases [Coffman 1976]. The first case

is to schedule a uniform node-weight

free-tree to an arbitrary number of pro-

cessors. Hu [1961] proposed a linear-

time algorithm to solve the problem.

The second case is to schedule an arbi-

trarily structured DAG with uniform

node-weights to two processors. Coff-

man and Graham [1972] devised a qua-

dratic-time algorithm to solve this prob-

lem. Both Hu’s algorithm and Coffman

et al.’s algorithm are based on node-

labeling methods that produce optimal

scheduling lists

optimal

schedules. Sethi [1976] then improved

the time-complexity of Coffman et al.’s

algorithm to almost linear-time by sug-

gesting a more efficient node-labeling

process. The third case is to schedule an

interval-ordered DAG with uniform

node-weights to an arbitrary number of

processors. Papadimitriou and Yanna-

kakis [1979] designed a linear-time al-

gorithm to tackle the problem. A DAG is

called interval-ordered if every two pre-

cedence-related nodes can be mapped to

two nonoverlapping intervals on the

real number line [Fishburn 1985].

leading to

ACM Computing Surveys, Vol. 31, No. 4, December 1999

In all of the above three cases, com-

munication between tasks is ignored.

Ali and El-Rewini [1993] showed that

interval-ordered DAG with uniform

edge weights, which are equal to the

node weights, can also be optimally

scheduled in polynomial time. These op-

timality results are summarized in Ta-

ble II.

Ullman [1975] showed that schedul-

ing a DAG with unit computation to p

processors

is NP-complete. He also

showed that scheduling a DAG with one

or two unit computation costs to two

processors

[Coffman

is NP-complete

1975; Ullman 1975]. Papadimitriou and

Yannakakis [1979] showed that sched-

uling an interval-ordered DAG with ar-

bitrary computation costs to two proces-

sors is NP-complete. Garey et al. [1983]

showed that scheduling an opposing for-

est with unit computation to p proces-

sors is NP-complete. Finally, Papadimi-

triou and Yannakakis [1990] showed

that scheduling a DAG with unit com-

putation to p processors possibly with

task-duplication is also NP-complete.

4. A TAXONOMY OF DAG SCHEDULING

ALGORITHMS

To outline the variations of scheduling

algorithms and to describe the scope of

our survey, we introduce in Figure 2 a

taxonomy of static parallel scheduling

Static Scheduling for Task Graph Allocation

•

415

[Ahmad et al. 1996; Ahmad et al. 1997].

Note that unlike the taxonomy sug-

gested by Casavant and Kuhl [1988],

which describes the general scheduling

problem (including partitioning and

load balancing issues) in parallel and

distributed systems, the focus of our

taxonomy is on the static scheduling

problem, and therefore is only partial.

The highest level of the taxonomy di-

vides the scheduling problem into two

categories, depending upon whether the

task graph is of an arbitrary structure

or a special structure such as trees.

Earlier algorithms have made simplify-

ing assumptions about the task graph

representing the program and the

model of the parallel processor system

[Coffman 1976; Gonzalez Jr. 1977].

Most of these algorithms assume the

graph to be of a special structure such

forks-join, etc. In general,

as a tree,

however, parallel programs come in a

variety of structures, and as such, many

recent algorithms are designed to tackle

arbitrary graphs. These algorithms can

be further divided into two categories.

Some algorithms assume the computa-

tional costs of all the tasks to be uni-

form. Others assume the computational

costs of tasks to be arbitrary.

Some of the scheduling algorithms

that consider the intertask communica-

tion assume the availability of an un-

limited number of processors, while

some other algorithms assume a limited

number of processors. The former class

of algorithms are called the UNC (un-

bounded number of clusters) scheduling

algorithms

[Kim and Browne 1988;

Kwok and Ahmad 1996; Sarkar 1989;

Wong and Morris 1989; Yang and Gera-

soulis 1994] and the latter the BNP

(bounded number of processors) schedul-

ing algorithms [Adam et al. 1974; Anger

et al. 1990; Kim and Yi 1994; Kwok and

Ahmad 1997; McCreary and Gill 1989;

Palis et al. 1996; Sih and Lee 1993b]. In

both classes of algorithms, the proces-

sors are assumed to be fully connected,

and no attention is paid to link conten-

...