A heterogeneous computing environment is a suite of heterogeneous processors interconnected by high-speed networks, thereby promising high speed processing of computationally intensive applications with diverse computing needs. Scheduling of an application modeled by Directed Acyclic Graph (DAG) is a key issue when aiming at high performance in this kind of environment. The problem is generally addressed in terms of task scheduling, where tasks are the schedulable units of a program. The task scheduling problems have been shown to be NP-complete in general as well as several restricted cases. In this study we present a simple scheduling algorithm based on list scheduling, namely, low complexity Performance Effective Task Scheduling (PETS) algorithm for heterogeneous computing systems with complexity O (e) (p+ log v), which provides effective results for applications represented by DAGs. The analysis and experiments based on both randomly generated graphs and graphs of some real applications show that the PETS algorithm substantially outperforms the existing scheduling algorithms such as Heterogeneous Earliest Finish Time (HEFT), Critical-Path-On a Processor (CPOP) and Levelized Min Time (LMT), in terms of schedule length ratio, speedup, efficiency, running time and frequency of best results. Key words: DAG, task graph, task scheduling, heterogeneous computing system, schedule length, speedup, efficiency A growing emphasis on concurrent processing of jobs has lead to an increased acceptance of heterogeneous computing environments and the availability of a network of processors makes a costeffective utilization of underlying parallelism for applications like weather modeling, image processing, real-time and distributed database systems. A wellknown strategy behind efficient execution of a huge application on a heterogeneous computing environment is to partition it into multiple independent tasks and schedule such tasks over a set of available processors. A task-partitioning algorithm takes care of efficiently dividing an application into tasks of appropriate grain size and an abstract model of such a partitioned application can be represented by a Directed Acyclic Graph (DAG). Each task of a DAG corresponds to a sequence of operations and a directed edge represents the precedence constraints between the tasks. Each task can be executed on a processor and the directed edge shows transfer of relevant data from one processor to another. Task scheduling can be performed at compile-time or at run-time. When the characteristics of an application, which includes execution times of tasks on different processors, the data size of the communication between tasks and the task dependencies, are known a priori, it is represented with a static model. The objective of task scheduling is to map the tasks on the processors and order their execution so that task precedence requirements are satisfied and a minimum overall completion time is obtained. The problem of scheduling of tasks with required precedence relationship, in the most general case, has been proven to be NP-complete [1, 2] for which optimal solutions can be found only after an exhaustive search. Efficient application scheduling is critical for achieving high performance in heterogeneous computing systems. Because of its key importance on performance, the task scheduling problem in general has been extensively studied and various heuristics have been proposed in the literature [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] . These heuristics are classified into a variety of categories such as list scheduling algorithms, clustering algorithms, guided random search methods and task duplication based algorithms. In list scheduling algorithms [4] [5] [6] , an ordered list of tasks is constructed by assigning priority to each task and the tasks are selected for execution based on their priority. List scheduling algorithms are generally preferred since they generate good quality schedules with less complexity. List scheduling algorithms such as Mapping Heuristic (MH) [4] , Levelized Min
HEFT(Heterogeneous Earliest Finish Time) algorithm REF is a two stage method.
Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments
Journal of Computer Science
Computer Science