International Journal of Information and Communication Technology Research

International Journal of Information and Communication Technology Research>> Call for Papers(CFP)>>Volume 7, Number 9, September 2017

International Journal of Information and Communication Technology Research


A New Algorithm for Static Task Scheduling For Heterogeneous Distributed Computing Systems

Full Text Pdf Pdf
Author Nirmeen A. Bahnasawy, Fatma Omara, Magdy A. Koutb, Mervat Mosa
On Pages 10-19
Volume No. 1
Issue No. 1
Issue Date May 01, 2011
Publishing Date May 01, 2011
Keywords Task scheduling; directed acyclic graph; heuristics; parallel processing; heterogeneous distributed computing systems



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 with 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 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. 

Seperator
    Journal of Information and Communication Technology | Journal of Science and Technology |     
Copyrights
2010 IRPN Publishers