Lecture for Chapter 5.2 (Fall 13)

Martha Garcia
 Goals
of Static Process Scheduling
 Types of Static Process Scheduling
 Future Research
 References
 Given a set or partially ordered tasks, define a
mapping of processes to processors before the
execution of the processes.
 Cost model:CPU cost and communication cost,
both should be specified in prior
 Minimize the overall finish time on a nonpreemptive(can not be interrupted)
multiprocessor system (of identical processors)
-Except for some very restricted cases,
scheduling to optimize the makespand are
-Heuristic solutions are usually proposed.
Two Types :
 Precedence
Process Model
 Communication Process Model
 Precedence
Process Model :
Program is represented by a DAG(Directed
Acyclic Graph). Direct edges represent the
precedence relationship.
The longest execution path in the DAG often
used to compare the performance of a
heuristic algorithm.
[Chow and Johnson 1997]
Communication overhead for A(P1) and
E(P3)= 4 * 2 = 8
Execution time
Communication overhead for
one message
No. of messages
to communicate
Precedence constraints among tasks in a program are
explicitly specified.
Scheduling goal: minimize the makespan time
[Chow and Johnson 1997]
 List Scheduling (LS): Communication overhead is
not considered. Using a simple greedy heuristic:
No processor remains idle if there are some tasks
available that it could process.
Extended List Scheduling (ELS): the actual
scheduling results of LS with communication
Earliest Task First scheduling (ETF): the earliest
schedulable task (with communication delay
considered) is scheduled first.
[Chow and Johnson 1997]
Makespan Calculation for LS, ELS, and ETF
[Chow and Johnson 1997]
Communication Process Model
There are no precedence constrains among processes
modeled by a undirected graph G, node represent
processes and weight on the edge is the amount of
communication messages between two connected
Process execution cost might be specified some times to
handle more general cases.
Scheduling goal: maximize the resource utilization
[Chow and Johnson 1997]
 the
problem is to find an optimal assignment
of m process to P processors with respect to
the target function:
 P:
a set of processors. ej(pi): computation
cost of execution process pi in processor Pj.
 ci,j(pi,pj): communication overhead between
processes pi and pj.
 Assume a uniform communicating speed
between processors.
[Chow and Johnson 1997]
This is referred as Module Allocation problem. It is
NP-complete except for a few cases:
For P=2, Stone suggested an polynomial time solution
using Ford-Fulkerson’s maximum flow algorithm.
Known results: The mapping problem for an
arbitrary number of processors is NPcomplete.
[Chow and Johnson 1997]
Stone’s two-processor model to achieve
minimum total execution and communication
 Partition the graph by drawing a line cutting through some
Result in two disjoint graphs, one for each process
Set of removed edges  cut set
 Cost of cut set  sum of weights of the edges
 Total inter-process communication cost between
Of course, the cost of cut sets is 0 if all processes are
assigned to the same node
 Computation constraints (no more k, distribute
 Maximum flow and minimum cut in a commodity-flow
 Find the maximum flow from source to destination
[Chow and Johnson 1997]
Maximum Flow Algorithm in Solving the
Scheduling Problem
[Chow and Johnson 1997]
Minimum-Cost Cut
Only the cuts that separate A and B
are feasible
[Chow and Johnson 1997]
Future Research :
Use AI techniques for Static Scheduling :
Genetic Algorithm
References :
Design Optimization of Time – and Cost – Constrained Fault – Tolerant Distributed
Embedded Systems.- Viacheslav Izosimov, Paul Pop. Petru Eles, Zebo Peng
A Static Task Scheduling Framework for Independent Tasks Accelerated using a
Shared Graphics Processing Unit.- Teng Li, Vikram K.Narayana, Tarek El-Ghazawi,
IEEE 2011
MAPPLE chip: a processing element for a static scheduling centric
multiprocessor.- Kenta Yasufuku, Riku Ogawa, Keisure Iwai, Hideharu Amanu, IEEE
 Thank

similar documents