LDBS: a duplication based scheduling algorithm for heterogeneous computing systems

Finding an optimal solution to the problem of scheduling an application modeled by a directed acyclic graph (DAG) onto a set of heterogeneous machines is known to be an NP-hard problem. In this study, we present a duplication based scheduling algorithm, namely the levelized duplication based scheduling (LDBS) algorithm, which solves this problem efficiently. The primary goal of LDBS is to minimize the schedule length of applications. LDBS can accommodate different duplication heuristics, thanks to its modular design. Specifically, we have designed two different duplication heuristics with different time complexities. The simulation studies confirm that LDBS is a very competitive scheduling algorithm in terms of minimizing the schedule length of applications.

1. Introduction

A heterogeneous computing (HC) system is a suite of geographically distributed machines interconnected by a high-speed network, thereby promising high-speed processing of computationally intensive applications with diverse computing needs. It is envisioned that such a computing system will enable users around the globe to execute their applications on the most suitable computing resources. In order to take advantage of a HC system, an application is first split into coarse-grained communicating tasks, which are represented by a directed acyclic graph (DAG), and then, a scheduling algorithm is used to assign the tasks of the application to machines. Since both the performance of a particular application and the utilization of system resources heavily depend on how applications are scheduled, deploying an efficient scheduling algorithm is crucial. However, finding an optimal solution to the problem of scheduling a directed acyclic graph onto a HC system is not trivial and the problem is NP-hard [3].