Energy efficient task partitioning and real-time scheduling on heterogeneous multiprocessor platforms with QoS requirements

We address the problem of partitioning a set of independent, periodic, real-time tasks over a fixed set of heterogeneous processors while minimizing the energy consumption of the computing platform subject to a guaranteed quality of service requirement. This problem is NP-hard and we present a fully polynomial time approximation scheme for this problem. The main contribution of our work is in tackling the problem in a completely discrete, and possibly arbitrarily structured, setting. In other words, each processor has a discrete set of speed choices. Each task has a computation time that is dependent on the processor that is chosen to execute the task and on the speed at which that processor is operated. Further, the energy consumption of the system is dependent on the decisions regarding task allocation and speed settings.

► We devise a new model for energy expenditure that alleviates previous impractical assumptions.
► We tackle task allocation on unrelated machines to minimize energy consumption and meet a desired QoS score.
► We develop an FPTAS for solving the problem above given it is NP-hard.
► We prove theoretical bounds on the quality of the solution returned by our algorithm relative to the optimal.
► We design an efficient heuristic for solving the problem above, equipped with simulations to compare it to our FPTAS.