HETS: Heterogeneous edge and task scheduling algorithm for heterogeneous computing systems

Abstract

Widely used computing systems are heterogeneous in nature, comprising of interconnected resources which differ in computational capability of processing nodes and network bandwidth. Due to this diversity, an efficient heuristic is required to achieve high performance in heterogeneous computing system. In our proposed scheduling algorithm, Heterogeneous Edge and Task Scheduling (HETS), we schedule the communication between the tasks of application graph onto the network links of varying bandwidth, and schedule these tasks of different computation on the network processors after considering the computational capability of the available processors. In HETS, the prioritization is done by calculating the edge priority as well as the node priority. HETS algorithm selects the task after all its incoming edges are scheduled. The proposed algorithm minimizes the communication overhead of the application graph edges and obtains reduced schedule length in terms of the over allexecution time. Performance of the proposed algorithm is studied by varying parameters of the standard task graphs as well as on real world directed acyclic graphs (DAGs) application, such as Cybershake, Gaussian Elimination, and Montage. Extensive simulation results show the effectiveness of HETS algorithm interms of reduced makespan and improved Schedule Length Ratio(SLR) for the given tasks.