Energy-efficient scheduling of tasks with conditional precedence constraints on MPSoCs

In this article, we investigate the problem of energy-efficient scheduling of tasks with conditional precedence constraints on heterogeneous NoC-based MPSoC. We propose a novel offline approach that performs task mapping, scheduling and voltage scaling in an integrated manner. Our approach consists of a scheduling algorithm that constructs a single unified schedule by prioritizing tasks with tight latest finish time bounds. It uses an NLP-based DVFS algorithm to assign continuous frequencies and voltages to tasks and communications, and transforms the assigned frequencies and voltages to tasks and communications to valid discrete frequency and voltage levels using either an ILP or a heuristic-based algorithm. Compared to the state-of-the-art approach designed for the task model with unconditional precedence constraints, our approach using ILP-based algorithm achieves improvements in the range of 9% to 61% and an average improvement of 31%, and our approach using a heuristic-based algorithm achieves improvements in the range of 2% to 46% and an average improvement of 20% in terms of energy reduction. In terms of running time, our approach is approximately 3 times faster than the state-of-the-art approach.