Contention Aware Energy Efficient Scheduling on Heterogeneous Multiprocessors

Energy efficiency along with enhanced performance are two important goals of scheduling on multiprocessors. This paper proposes a Contention-aware, Energy Efficient, Duplication based Mixed Integer Programming (CEEDMIP) formulation for scheduling task graphs on heterogeneous multiprocessors, interconnected in a distributed system or a network on chip architecture. The effect of duplication is studied with respect to minimizing: the makespan, the total energy for processing tasks and messages on processors and network resources respectively and the tardiness of tasks with respect to their deadlines. Optimizing the use of duplication with MIP provides both energy efficiency and performance by reducing the communication energy consumption and the communication latency. The contention awareness gives a more accurate estimation of the energy consumption. We also propose a corner case that allows the scheduling of a parent task copy after a copy of the child task which may lead to efficient schedules. It has been observed that the proposed MIP with a clustering based heuristic provides scalability and gives 10-30 percent improvement in energy with improved makespan and accuracy when compared with other duplication based energy aware algorithms.