Research Article Open Access

Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments

E. Ilavarasan1 and P. Thambidurai1
  • 1 ,
Journal of Computer Science
Volume 3 No. 2, 2007, 94-103

DOI: https://doi.org/10.3844/jcssp.2007.94.103

Submitted On: 1 October 2006 Published On: 28 February 2007

How to Cite: Ilavarasan, E. & Thambidurai, P. (2007). Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments . Journal of Computer Science, 3(2), 94-103. https://doi.org/10.3844/jcssp.2007.94.103

Abstract

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.

  • 2,123 Views
  • 3,146 Downloads
  • 81 Citations

Download

Keywords

  • DAG
  • task graph
  • task scheduling
  • heterogeneous computing system
  • schedule length
  • speedup
  • efficiency