Scheduling algorithms in Heterogeneous Computing Systems ≈ Anum masood Lecturer, COMSATS Institute of Information Technology, Pakistan PhD Student selee SJTu. China
Scheduling Algorithms in Heterogeneous Computing Systems Anum Masood Lecturer, COMSATS Institute of Information Technology, Pakistan. PhD Student, SEIEE, SJTU, China
Algorithm for Task and Edge Scheduling it Heterogeneous Computing Systems
Algorithm for Task and Edge Scheduling in Heterogeneous Computing Systems 2
Outline ≈ Introduction s Motivation ≈Prob| em statement ≈Re| ated work o Heterogeneous Edge and Task Scheduling algorithm
Outline Introduction Motivation Problem Statement Related Work Heterogeneous Edge and Task Scheduling Algorithm 3
Introduction o Computing systems from cell-phones to supercomputers,are becoming heterogeneous in terms of processing capa bility as well as data transfer Scietuilet
Introduction Computing systems from cell-phones to supercomputers, are becoming heterogeneous, in terms of processing capability as well as data transfer. 4
Introduction(cont o Heterogeneous computing system are widely used to solve complex scientific engineering or business oriented problems o Heterogeneous computing platforms can be found in every domain of computing o Scalable computing, meta computing, Peer-to-Peer(P2P)computing, volunteer computing, Grid computing and Cloud Computing. Distributed Volunteer Computing(DvC) CLOUD COMPUTING Internet (s 200 TFLOPS)
Introduction (cont...) Heterogeneous computing system are widely used to solve complex scientific, engineering or business oriented problems. Heterogeneous computing platforms can be found in every domain of computing Scalable computing, meta computing, Peer-to-Peer (P2P) computing, volunteer computing, Grid computing and Cloud Computing. 5
Introduction(cont o Heterogeneous parallel computing systems are required for higher power efficiency and computation throughput o Effective use of these heterogeneous computing systems requires knowledge about efficient scheduling in these systems such that the maximum utilization of these systems is possible
Introduction (cont...) Heterogeneous parallel computing systems are required for higher power efficiency and computation throughput. Effective use of these heterogeneous computing systems requires knowledge about efficient scheduling in these systems such that the maximum utilization of these systems is possible. 6
Introduction(cont Parallel program is a collection of communicating tasks o Task assignment problem for balancing computational load among the processors and reducing the overhead of communication between them o Requires distribution of tasks onto p processors to achieve computational load balance and appropriate scheduling of graph application to minimize the overhead of communication o Scheduling problem: Two types of algorithms developed o Heuristic algorithms and Physical optimization algorithms
Introduction (cont...) Parallel program is a collection of communicating tasks Task assignment problem for balancing computational load among the processors and reducing the overhead of communication between them. Requires distribution of tasks onto p processors to achieve computational load balance and appropriate scheduling of graph application to minimize the overhead of communication. Scheduling problem: Two types of algorithms developed Heuristic algorithms and Physical optimization algorithms 7
Motivation o Numerous task scheduling heuristics were proposed on the assumptions such as tasks are s Independent o No communication delay 9 Communication links are homogeneous o These assumptions are unrealistic. The communication links are mostly heterogeneous therefore an algorithm was required which considers the heterogeneity of the links and communication delay
Motivation Numerous task scheduling heuristics were proposed on the assumptions such as tasks are: Independent No communication delay Communication links are homogeneous These assumptions are unrealistic. The communication links are mostly heterogeneous therefore an algorithm was required which considers the heterogeneity of the links and communication delay. 8
Motivation(cont o Heterogeneity was considered not just in terms of nodes and processor but also in terms of: o Edges between dependent nodes o Links interconnecting the processors
Motivation (cont...) Heterogeneity was considered not just in terms of nodes and processor but also in terms of : Edges between dependent nodes Links interconnecting the processors 9
Problem statement o Directed weighted graph G comprises of a set of vertices VGwhich represents the computational nodes and a set of edges Eg shows the data-dependency o Each vertex E Vg has a weight Wy() o Each edge eii e egrepresents the communication between the two vertices i and j o Each vertex ix E VGis mapped on the compute node Vr o Each edge eii e eg is mapped on sequence of links edge liiE E o Each compute node has the different processing speed, denoted by the set of valueS C(VT) o Each link has the different bandwidth, denoted by set of values L(Er). Links lz∈ L have varying bandwidth b∈B
Problem Statement Directed weighted graph 𝐺comprises of a set of vertices 𝑉𝐺which represents the computational nodes and a set of edges 𝐸𝐺 showsthe data-dependency Each vertex 𝑖 ∈ 𝑉𝐺 has a weight 𝑤𝑉(𝑖) Each edge 𝑒𝑖𝑗 ∈ 𝐸𝐺represents the communication between the two vertices 𝑖 and 𝑗 Each vertex 𝑖𝑥 ∈ 𝑉𝐺is mapped on the compute node 𝑝𝑥 ∈ 𝑉𝑇 Each edge 𝑒𝑖𝑗 ∈ 𝐸𝐺 is mapped on sequence of links edge 𝑙𝑖𝑗 ∈ 𝐸𝑇. Each compute node has the different processing speed, denoted by the set of values 𝐶(𝑉𝑇). Each link has the different bandwidth, denoted by set of values 𝐿(𝐸𝑇). Links 𝑙𝑖 ∈ 𝐿 have varying bandwidth 𝑏𝑖 ∈ 𝐵. 10
