Low power task scheduling and mapping for applications with conditional branches on heterogeneous multi-processor system

Many real time applications demonstrate uncertain workload that varies during runtime. One of the major influences of the workload fluctuation is the selection of conditional branches which activate or deactivate a set of instructions belonging to a task. In this work, we capture the workload dynamics using Conditional Task Graph (CTG) and propose a set of algorithms for the optimization of task mapping, task ordering and dynamic voltage/frequency scaling of CTGs running on a heterogeneous multi-core system. Our mapping algorithm balances the latency and the energy dissipation among heterogeneous cores in order to maximize the slack time without significant energy increase. Our scheduling algorithm considers the statistical information of the workload to minimize the mean power consumption of the application while maintaining a hard deadline constraint. The proposed DVFS algorithm has pseudo linear complexity and achieves comparable energy reduction as the solutions found by mathematical programming. Due to its capability of slack reclaiming, our DVFS technique is less sensitive to the slight change in hardware or workload and works more robustly than the conventional DVFS techniques.