Problem Statement(cont.) o Given tasks should be mapped onto the processors only when the data is completely transferred from the parent tasks. the processor selected should execute the task faster than other processors o Task with more child nodes and longer execution time must be considered while selecting the processor for a given task. o the total execution time of the tasks should be minimum with minimum communication delay
Problem Statement (cont...) Given tasks should be mapped onto the processors only when the data is completely transferred from the parent tasks. The processor selected should execute the task faster than other processors. Task with more child nodes and longer execution time must be considered while selecting the processor for a given task. The total execution time of the tasks should be minimum with minimum communication delay. 11
List Scheduling o List scheduling algorithms are proposed for finding the optimal schedule in heterogeneous computing systems o List scheduling heuristics comprise of two main steps s Task prioritization phase o Processor selection phase o there are two additional phases i.e. Edge prioritization Phase and Link selection phase
List Scheduling List scheduling algorithms are proposed for finding the optimal schedule in heterogeneous computing systems List scheduling heuristics comprise of two main steps: Task Prioritization Phase Processor Selection Phase There are two additional phases i.e., Edge Prioritization Phase and Link Selection Phase 12
Related Work e Good performance algorithms o HEFT(Heterogeneous Earliest Finish Time o Task priority is computed corresponding to the exit task by traversing the dag upwards using a recursive procedure o Known as Upward rank o Processor selection is made on minimum earliest finish time Uses insertion based policy s CPOP(Critical Path On a Processor) o Upward as well as downward rank o Critical tasks are assigned to the critical processor o PETS(Performance Effective task scheduling o Divides the communication cost of a task into data transfer and data receiving costs o Upward rank calculation using computation and communication costs
Good performance algorithms HEFT (Heterogeneous Earliest Finish Time） Task priority is computed corresponding to the exit task by traversing the DAG upwards using a recursive procedure Known as Upward rank Processor selection is made on minimum earliest finish time Uses insertion based policy CPOP (Critical Path On a Processor) Upward as well as downward rank Critical tasks are assigned to the Critical processor PETS (Performance Effective task scheduling) Divides the communication cost of a task into Data Transfer and Data Receiving costs Upward rank calculation using computation and communication costs Related Work 13
Task Scheduling(cont 1896 Computational Cost of Nodes C(VT) 176 e411 15 DAG Input Graph (45) 8 Communication Cost of Edges((ET) (i=3)∈V wv(3)=(10+12+19)/3 13.667 b1 2 GB/s Edge:e(35)∈Eo b2 4 GB/s We(e(3,5)=27 L3 b3 6 GB/s Bandwidth of Links (B)
Task Scheduling (cont...) Nodes P1 P2 P3 1 12 16 11 2 13 19 18 3 10 12 19 4 13 9 16 5 12 14 10 12 1 2 3 4 5 9 11 23 27 13 Computational Cost of Nodes 𝐶(𝑉𝑇) DAG Input Graph 14 Edges 𝑒𝑖 L1 L2 L3 𝑒(1, 𝟐) 𝑒2 12 17 6 𝑒(1, 𝟑) 𝑒3 9 11 15 𝑒(1, 𝟒) 𝑒4 11 13 15 𝑒(𝟐,𝟓) 𝑒8 23 18 9 𝑒(𝟑.𝟓) 𝑒9 27 20 21 𝑒(𝟒.𝟓) 𝑒11 13 10 8 Link 𝑏𝑖 Bandwidth L1 𝑏1 2 GB/s L2 𝑏2 4 GB/s L3 𝑏3 6 GB/s Communication Cost of Edges (𝐿(𝐸𝑇)) Bandwidth of Links (𝐵) Vertex: (𝑖 = 3) ∈ 𝑉𝐺 𝑤𝑉 3 = (10 + 12 + 19) /3 = 13.667 Edge: 𝑒(3,5) ∈ 𝐸𝐺 𝑊𝑒 (𝑒(3,5) ) = 27
Example
𝑃 1 𝑃 2 𝑃 3 𝐿 1 𝐿 2 𝐿 3 55 50 45 40 35 30 25 20 155 100 𝑛 1 ( 0 , 9 ) 15 Example :