Scheduling heuristics for heterogeneous processors

Scheduling computation tasks oil processors is a key issue for high-performance computing, Although a large number of scheduling heuristics have been presented in the literature, most of them target only homogeneous resources. We survey five heuristics aiming at scheduling directed acyclic weighted task graphs on a bounded number of heterogeneous processors: the Best Imaginary Level (BIL), tile Generalized Dynamic Level (GDL), the Critical-Path-on-a-Processor (CPOP), the Heterogeneous Earliest Finish Time (HEFT) and the Partial Completion Time (PCT) algorithms. We also introduce a new low-complexity heuristic, which we call tire Iso-Level Heterogeneous Allocation (ILHA) algorithm. We compare the performances of these six heuristics using four classical testbeds.