Level-wise earliest finish time based workflow scheduling for heterogeneous computing systems
摘要
To achieve significant improvement in a heterogeneous computing systems environment, it is essential to provide an approach that will execute the task efficiently. The approach is all about scheduling a task of a workflow application to a suitable processor. The tasks are connected with directed edges. These sets of tasks are generally called workflows. The scientific and industrial applications that provide different services in a cloud environment are nothing but workflows. Therefore, the workflow is considered the best representation as it can express a wide range of applications. It is challenging to generate a valid sequence of execution by preserving the precedence constraint. In this paper, an effort has been made to propose an algorithm named Level-Wise Earliest Finish Time (LEFT) for task selection and mapping policies. The algorithm was further extended as Level-wise Earliest Finish Time with Task Duplication (LEFT-D) for better performance. The performance of these algorithms is evaluated against the state-of-the-art list-based scheduling algorithms in terms of generic factors such as makespan, speedup ratio, and efficiency. Further, the performances are analyzed by extensive simulations on different sets of scientific applications such as Montage, Cybershake, Fast Fourier Transformation(FFT), Epigenomics, SIPHT, Ispiral, and the synthetic workflow application data set. The experimental results and analysis show that the proposed algorithms perform considerably better than the existing algorithms such as Heterogeneous Earliest Finish Time (HEFT), Critical-Path-on-a-processor (CPOP), Performance Effective Task Scheduling (PETS), and Predict Earliest Finish Time (PEFT). The work and its effectiveness were also validated by Analysis of Variance (ANOVA).