Performance-Effective DAG Scheduling for Heterogeneous Distributed Systems

Publications

Performance-Effective DAG Scheduling for Heterogeneous Distributed Systems

Year : 2022

Publisher : Association for Computing Machinery

Source Title : ACM International Conference Proceeding Series

Document Type :

Abstract

The problem of scheduling Directed Acyclic Graphs (DAGs) in order to minimize schedule length (also known as makespan), is known to be a challenging as well as computationally hard problem. Therefore, researchers have endeavored towards the design of various heuristic solution generation techniques both for homogeneous as well as heterogeneous computing platforms. Traditionally, list scheduling heuristics are known to generate efficient schedules within reasonable time complexities. In this research work, we first focus on a makespan minimizing DAG scheduler for heterogeneous distributed systems. Secondly, we also formulated a problem, which is an extension of the first work, by considering a real-time application on a heterogeneous platform. We proposed an algorithm, named PRESTO that aims to minimize a generic penalty function while satisfying the resource, precedence and timing constraints. This generic penalty function can suitably tune to various optimization problems in different application domains.