PERFORMANCE ANALYSIS OF HEFT TASK SCHEDULING FOR HETEROGENEOUS COMPUTING

Abstract

There has been a recent increase of interest in heterogeneous computing systems, due partly to the fact that a single parallel architecture may not be adequate for exploiting all of the programs available parallelism. In some cases, heterogeneous systems have been shown to produce higher performance for lower cost than single large machine. There are so many scheduling algorithms developed for homogeneous system but few for heterogeneous computing. The main objective of scheduling is to reduce the overall completion time (i.e. schedule length) of a parallel application by properly allocating the tasks to the processors. The aim of this dissertation is to analyses the performance of HEFT scheduling algorithm and modify HEFT algorithm for better performance and compare both algorithms for different weighted directed acyclic graphs (DAG). A simulation framework was developed in C++ on which both algorithms were implemented and the simulation results for performance thus obtained are presented. Algorithms are used for bounded number of fully connected heterogeneous processors network. The performance parameters used for comparison of algorithms, which are schedule length, speedup factor and, efficiency. The results substantiate the fact that for high value of CCR HEFT performance is not good. So, HEFT algorithm is modified. Modified HEFT algorithm performs better as compare to HEFT for higher value of CCR