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