African Journal of
Mathematics and Computer Science Research

  • Abbreviation: Afr. J. Math. Comput. Sci. Res.
  • Language: English
  • ISSN: 2006-9731
  • DOI: 10.5897/AJMCSR
  • Start Year: 2008
  • Published Articles: 262

Full Length Research Paper

A new algorithm for static task scheduling for heterogeneous distributed computing systems

Nirmeen A. Bahnasawy1*, Magdy A. Koutb1, Mervat Mosa1 and Fatma Omara2
  1Faculty of Engineering, Menoufia University, Egypt. 2Faculty of Computers and Science, Cairo University, Egypt.  
Email: [email protected]

  •  Accepted: 11 April 2011
  •  Published: 30 June 2011

Abstract

 

Effective task scheduling is essential for obtaining high performance in heterogeneous distributed computing systems (HeDCSs). However, finding an effective task scheduling in HeDCSs should take into consideration the heterogeneity of processors and inter-processor communication over head, which results from non-trivial data movement between tasks scheduled on different processors. In this paper, a new high performance task scheduling algorithm called sorted nodes in leveled DAG division (SNLDD) is presented for HeDCSs considering a bounded number of processors. The main concept of the proposed algorithm is to divide the Directed Acyclic Graph DAG into levels and tasks in each level are sorted in descending order according to their computation size. A new attribute has been introduced and used to efficiently select tasks for scheduling in HeDCSs. This selection of tasks enables the proposed SNLDD algorithm to generate high-quality task schedule in a heterogeneous computing environment. To evaluate the performance of the proposed SNLDD algorithm, a comparison study has been done between it and the longest dynamic critical path (LDCP) algorithm which is considered the most efficient algorithm. According to the comparative results, it is found that the performance of the proposed algorithm provides better performance than the LDCP algorithm in terms of speedup, efficiency, complexity, and quality.

 

Key words: Task scheduling, directed acyclic graph, heuristics, parallel processing, heterogeneous distributed computing systems.