Saturday, 4 June 2011

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

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



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.

Download Link:


  1. This comment has been removed by the author.

  2. This new algorithm for a static scheduling system will be very important and essential for getting a very high performance in computing system.This HeDCSs should be taken more advantage of using it because it is very useful for task scheduling.which are the best writing services in internet reviews

  3. hope that this new scheduling algo is better than its previous version which is fine but have nothing special on it Writing research essays

  4. Future residents present Bartley MRT Circle Line will be able to walk. Such a short drive to the city area as well as orchard Wallet passbee Media and bugis area, with entertainment for your loved ones and family will come to a stone's throw away.

  5. purchase Tabs, download the Khan academy and start to flip the classroom because both the rich and poor are suffering from poor education.Pest Control