Performance Comparison of HEFT, Lookahead, CEFT and PEFT Scheduling Algorithms for Heterogeneous Computing Systems

Abstract

Efficient scheduling algorithms play an essential part in heterogeneous computing systems to achieve high performance. The problem of producing an optimal schedule for the precedence-constrained tasks is recognized to be an NP-complete problem. To work out this problem, the researchers have already been proposed various scheduling algorithms in the literature. This paper discusses four well-known list scheduling algorithms such as HEFT, Lookahead, CEFT and PEFT for heterogeneous computing systems and performs experiments for randomly created application graphs and the application graphs generated from real-world problem for instance molecular dynamic code. The performance of algorithms are evaluated and compared on different scheduling parameters such as scheduling length ratio, efficiency, etc.