Scribd
Upload
6 views30 pages

Chapter 5-Part Two

Uploaded by

Habiba Elezaby
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
6 views30 pages

Chapter 5-Part Two

Uploaded by

Habiba Elezaby
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Chapter Five Scheduling and Task Allocation Reference: ADVANCED COMPUTER ARCHITECTURE AND PARALLEL PROCESSING Hesham El-Rewini, Southern Methodist University Mostafa Abd-El-Barr, Kuwait University Published by A JOHN WILEY & SONS, INC Chapter -10 in the book COMMUNICATION MODELS The Gantt Chart It shows the precedence relations between tasks are, but doesn’t reflect the communication delay. Program Completion Time Components: ° Computing Time and Communication Delay. Program Completion Time = Execution Time + Total Communication Delay The Execution Time; determines from the Gantt chart as the maximum finishing time (schedule length)of any task. Total Communication Delay = Total Number of Messages * Communication Delay per Message. COMMUNICATION MODELS- Cont.. _ © Total number of messages can be obtained according to two models as follows. _ Model A: © Total number of messages is defined as the number of node pairs (u, v) such that (u, v) EE and proc(u)# proc(v). Model B: © Total number of messages is defined as the number of processor-task pairs (P, v) such that processor P does not compute task v but computes at least one immediate successor task of v. Example: __e Suppose each of the five tasks takes one unit of execution time on either PI or P2,and task a sends messages to tasks b, c,d, and e using one unit time. Assuming Model A and B: (:) Tasks a, b,and d are allocated to processor PI while tasks ¢ and e assigned to P2. Using Model A: (s) () (i) () © Total Number of Messages= |(a,c), (a,e)|=2 te ar n e Program Compilation Time= 3+2=5 Using Model B: ¢ Total Number of Messages=|(P2, a)|=1 e Program Compilation Time= 3+1=4 j 0) (a) task graph; (b) allocation (Models A & B) Completion Time From The Gantt Chart ° The existence of an I/O processor implies that a processing element can execute a task and communicate with another processing element at the same time. ¢ Tasks can schedule for execution in the communication holes in a Gantt chart. e The program completion time can be determined directly from Gantt chart as follows: Program Completion Time = Schedule Length ¢ The communication delay should be considered in the Gantt chart according to Model C. Model C e A task can assign to a processor for execution while this Processor performs communication. e Communication delay between two tasks allocated to the same processor is negligible. e Communication delay between two communicating tasks allocated to two different processors is a function of: Message size, the route, and communication speed Example: e Suppose each of the five tasks takes one unit of execution time on either PI or P2, and task @ sends messages to tasks b, c,d, and e using one unit time. _ Using Model C: e Assuming communication delay between two communicating tasks allocated to two different processors is one unit of time. Task Graph; Sleek ° Task b is assigned to the same processor PI, © no delay. Task d can start on P2 after arriving message from a after one unit of time. ° Therefore ‘Schedule(Model C) Communication e Program Completion Time = schedule length = 4 units of time Scheduling DAGs With Communication Communication cost is considered in the Scheduling Algorithms Two algorithms will explain to schedule © In-forests/Out-forests, and ° Interval orders. In these two cases, we assume the following: ° A task graph consisting of n tasks; A target machine made of m processors; The execution time of each task is one unit of time; Communication according to Model C; ° The communication delay between two communicating tasks scheduled on two different processors is one unit of time; The communication delay between two communicating tasks scheduled on the same processor equals zero; The goal is to find an optimal schedule that minimizes the total execution time. Scheduling In-Forests/Out-Forests on Two Processors [Link] __ It was introduced by El-Rewini and Ali (1994). | —_ ¢ The time complexity of the algorithm is @(n?+n _ © Authors introduces Augment Task Graph; ° By adding new precedence relations to the task graph in order to compensate for communication ° Scheduling the augmented task graph without considering communication is equivalent to scheduling the original task graph with communication. Some Definitions: e Node Depth; the length of the longest path from any node with depth zero to that node. A node with no predecessors has a depth of zero. i.e., depth(u)= I+ max(depth(v)),V v € predecessors(u);and depth(u)= 0 V u, predecessors(u)= 0 ° Operation Swapall (f, x,y); effect of this function is to swap all task pairs scheduled on processors i and j in schedule f at time tl, V tl, tl> t. Where x and y are two tasks in f scheduled to start at fon processors iand /. Scheduling In-Forests/Out-Forests on Two Processors (Cont..) _ Algorithm: |. Given an in-forest G = (V, A), identify sets of siblings: $1, $2, . where Si is the set of all nodes in V with a common child (Si). 2. ALC A. 3. For every set Si (a) Pick node u € Si with the maximum depth seiko (b) Al €AI - (v, child(Si)) Vv € Siandv#u TREE Graph (c) AL € Al U (v, u) VV E Siandv #u. 4. Obtain the schedule f by applying Algorithm on the augmented in- forest f = (V Al). 5. For every set Si in the original in-forest G if node u (with maximum depth) scheduled in f in time slot immediately before child(Si) but on a different processor, then apply operation swapall (f, child(Si), x), where x is task scheduled in time slot immediately after u on same processor. Scheduling In-Forests/Out-Forests on Two Processors (Cont..) _ Example |- Identify the sets of siblings with a common child: Four sets as follows: SI = { a, b}, S2= {c, d}, $3 = {e, f}, $4 = {g, h} “ Q ® OO OO © @ ‘S) CG) 2- Node with maximum depth from each set is picked: * Since a and b in SI and e and f in $3 have same depth (Zero), we select b from SI and f from $2 randomly. * Nodes ¢ (depth e=2), and g (depth g=3)are the ones that have maximum depth in $2 and $4 , respectively. These selected nodes are shaded in Figure * Node i (depth i= 5) (max. no. of predecessor nodes) A Scheduling In-Forests/Out-Forests on Two Processors (Cont..) _ 3- The augmented task graph (F) is constructed: ped as shown in Figure (C) with Task Priority in Figure (D). (b) * Scheduling in-forests without law considering communication is applied /) to augmented task graph (C). Figures (D) and (E) show task priorities and optimal schedule when communication is ignored. * Schedule shown in Figure (E) is not correct when communication is considered because communicating tasks b and ¢ are allocated to different ince on @ processors but there is no delay left asm pom Tm POP for communication according to eta] |"oTol mh © 3 1 Model C. : , , as slot 7 [byl 4 | * Operation swapall is applied to fix this es slit Me svt problem. Figure (F) shows the final ffs afb : h optimal schedule on two processors ert! te : sia a [3 5 when communication is considered. i to 6Li 6 Scheduling Interval Orders with Communication _ Itis introduced by Ali and El-Rewini (1995) Scheduling algorithm with considering execution time is the same for all tasks and is identical to communication delay. © The time complexity of the algorithm is @(e + 2m) where Mis the number of tasks, @ is the number of arcs in the interval order, and mis the number of processors. Definitions: start-time(v,i,f) The earliest time at which task v can start execution on processor Pi in schedule f. task(i,t,f) The task scheduled on processor Pi at time t in schedule f. If there is no task scheduled on processor Pi at time t in schedule f, then task(i,t,f) returns the empty task @. Note that the priority of the empty task is less than the priority of any other task. Scheduling Interval Orders with Communication Algorithm _ [Link] number of all successors of each node is used as each node's priority. 2. Nodes with the highest priority are scheduled first. 3. Each task v is assigned to processor Pi with the earliest start time. 4. If start-time(v,i,f) = start-time(v,j,f), | < i, j => m, task v is assigned to processor Pi if task(i, start-time(v,i,f)-1, f) has the smaller priority (smaller number of successors). Example Consider schedule an interval order with communication according to Model C on three _ processors. Algorithm Steps: ~ © Number of successors for each node obtained and used as priority. © Tasks d, ¢,and b scheduled to start at time 0 on delay between e and its predecessors d and ¢ that scheduled on different processors (PI and P2). 0 Gantt Chart processors PI , P2 ,and P3 , respectively. TaskGraph_ Sleek ' , ode Numberot Til © Task @ can start execution at time | on any of the Ne® tees three processors. But according to algorithm it : - len Pe allocated to processor P3 after task b with the “aE ’ smallest priority. Where task b has priority 6X). PL P2 ———— 30 using P1, P2 ==) = 40 usin P1 only Total Excution Time. mo] x

You might also like