Platform synthesis and partitioning of real-time tasks for energy efficiency

Energy-efficient and power-aware designs have played important roles in modern computing systems to reduce the power bills for server systems or prolong the lifetime of embedded devices. Moreover, systems with multiple heterogeneous processing units have been widely adopted to enhance the computing capability or reduce the power consumption. This work explores how to synthesize a heterogeneous multiprocessor platform or select processing units with the partitioning of real-time tasks so that the energy consumption is minimized. Given a set of processing unit types, characterized by the power consumption for maintaining activeness and executing jobs, this paper proposes an efficient and effective algorithm to allocate processing units with energy-efficient task partitioning. When the constraint on the numbers of allocated processing units is not specified, we show that the algorithm is with a (1+lnn)(1+lnn)-approximation factor, in worst cases, for processing unit types with a variety of power consumption models, where n   is the number of tasks. The approximation factor is asymptotically optimal for polynomial-time approximation algorithms unless P=NPP=NP. Moreover, we also present how to deal with specified maximal numbers of allocated processing units to minimize the energy consumption. Simulation results show that the proposed algorithm is effective for energy consumption minimization.