An Energy Minimization Approach for Periodic Tasks with Data Dependencies in Heterogeneous Systems

Abstract

Heterogeneous systems offer high instruction throughput and cost advantages but face dual challenges of energy efficiency and task scheduling, especially for periodic tasks with data dependencies—such as signal processing and process control—which require precise execution and careful handling of continuous sampling, data transmission, and processing. The Directed Acyclic Graph (DAGs) are commonly used to capture data dependencies among tasks, where nodes and directed edges represent tasks and data dependencies, respectively. This paper focuses on the non-preemptive scheduling problem of such tasks on heterogeneous platforms for time-critical applications, aiming to minimize energy consumption while guaranteeing worst-case deadline constraints. Clearly, this is an NP-hard problem, making it difficult to obtain an optimal solution in polynomial time. Although Dynamic Voltage and Frequency Scaling (DVFS) is a widely used energy-saving technique, its practical effectiveness is limited by potential transient faults, reduced processor lifespan, and overheads caused by switching. First, this paper analyzes priority constraints within DAGs and simplifies the structure by removing unnecessary dependencies to improve execution efficiency. Then, it reduces energy consumption through two sequential approaches: task scheduling optimization and processor frequency adjustment. Accordingly, two energy-efficient algorithms are proposed: the Time and Energy Balanced Scheduling (TEBS) algorithm and the DVFS-Weakly Dependent Energy Saving (DWDES) algorithm. The former reduces makespan and energy consumption purely through scheduling strategies without considering DVFS, while the latter adjusts processor frequencies based on TEBS to further minimize energy use, allowing DVFS only during application switching. Experimental results show that the proposed algorithms achieve significant energy savings compared to state-of-the-art methods while satisfying deadline constraints. Specifically, taking the classic IPPTS algorithm’s energy consumption as the baseline, TEBS and DWDES achieve energy savings of 15.58% and 46.31%, respectively.