SCHEDULING DAGs WITHOUT CONSIDERING COMMUNICATION

SCHEDULING DAGs WITHOUT CONSIDERING
COMMUNICATION
Prepared by:
Afrah Salman
Noor Kadhim
Zeena Mohammed

SCHEDULING DAGs WITHOUT CONSIDERING
COMMUNICATION
• There are three polynomial algorithms:
1) Scheduling In-Forests/Out-Forests Task Graphs
2) Scheduling Interval Ordered Tasks
3) Two-Processor Scheduling

Requirements of the algorithms
• In the three cases, we assume the following:
• A task graph consists of n tasks;
• A target machine is made of m processors;
• The execution time of each task is one unit of
time;
• Communication between any pair of tasks is zero;
• The goal is to find an optimal schedule that
minimizes the total execution time.

Scheduling In-Forests/Out-Forests Task Graphs
Algorithm 1
1. The level of each node in the task graph is
calculated as given above, and used
as each node’s priority.
2. Whenever a processor becomes available,
assign it the unexecuted ready task
with the highest priority.

Scheduling Interval Ordered Tasks
Algorithm 2
1. The number of all successors of each node is
used as each node’s priority.
2. Whenever a processor becomes available,
assign it the unexecuted ready task
with the highest priority.

Two-Processor Scheduling
Algorithm 3
1. Assign 1 to one of the terminal tasks.
2. Let labels 1, 2, . . . , j 2 1 have been assigned. Let S be
the set of unassigned tasks with no unlabeled successors.
We next select an element of S to be assigned label j. For
each node x in S define l(x) as follows: Let L(y1), L(y2), . . .
, L(yk) be the labels already assigned to the immediate
successors of x. Then l(x) is the decreasing sequence of
integers formed by ordering the set fL(y1), L(y2), . . . ,
L(yk)g. Let x be an element of S such that for all x0 in S,
l(x) l(x0) (lexicographically). Assign j to x (L(x) ¼ j).
3. Use L(v) as the priority of task v and ties are broken
arbitrarily.
4. Whenever a processor becomes available, assign it
the unexecuted ready task with the highest priority. Ties
are broken arbitrarily.

SCHEDULING DAGs WITHOUT CONSIDERING COMMUNICATION

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to SCHEDULING DAGs WITHOUT CONSIDERING COMMUNICATION

Similar to SCHEDULING DAGs WITHOUT CONSIDERING COMMUNICATION (20)

More from University of Technology - Iraq

More from University of Technology - Iraq (19)

Recently uploaded

Recently uploaded (20)

SCHEDULING DAGs WITHOUT CONSIDERING COMMUNICATION