An Evaluation of Heuristics for Scheduling Meta-Tasks on Heterogeneous Computing Systems
Scheduling is one of the core steps to efficiently exploit the capabilities of heterogeneous computing systems. In heterogeneous computing environment several applications require numerous resources for execution which are not often available for them, thus presence of a scheduling system to allocate resources to input jobs is vital. The problem of optimally mapping (defined as matching and scheduling) tasks onto the machines of a heterogeneous computing environment have been shown, in general, to be NP-complete, requiring the development of heuristic techniques. Selecting the best heuristic to use in a given environment, however, remains a difficult problem. Different criteria can be used for evaluating the efficiency of scheduling algorithms, the most important of which are makespan, flowtime, execution time and system utilization.