Martha Garcia Goals of Static Process Scheduling Types of Static Process Scheduling Future Research References GOALS : 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 NP-Complete -Heuristic solutions are usually proposed. Two Types : Precedence Process Model Communication Process Model Precedence Process Model : I K J - - L 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] Algorithms: 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 consideration. 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 processes. 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 cost Example: Partition the graph by drawing a line cutting through some edges 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 processors Of course, the cost of cut sets is 0 if all processes are assigned to the same node Computation constraints (no more k, distribute evenly…) Example: Maximum flow and minimum cut in a commodity-flow network 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 2003 Thank you!!