Power optimization for conditional task graphs in DVS enabled multiprocessor systems

In this paper, we focus on power optimization of real-time applications with conditional execution running on a dynamic voltage scaling (DVS) enabled multiprocessor system. The targeted system consists of heterogeneous processing elements with non-negligible inter-processor communication delay and energy. Given a conditional task graph (CTG), we have developed novel online and offline algorithms that perform simultaneous task mapping and ordering followed by task stretching. Both algorithms minimize the mathematical expectation of energy dissipation of non-deterministic applications by considering the probabilistic distribution of branch selection. Compared with existing CTG scheduling algorithms, our online and offline scheduling algorithms reduce energy by 28% and 39% in average, respectively.