Energy-Efficient Real-Time Scheduling of DAG Tasks
Open Access
- 17 September 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 17 (5) , 1-25
Abstract
This work studies energy-aware real-time scheduling of a set of sporadic Directed Acyclic Graph (DAG) tasks with implicit deadlines. While meeting all real-time constraints, we try to identify the best task allocation and execution pattern such that the average power consumption of the whole platform is minimized. To our knowledge, this is the first work that addresses the power consumption issue in scheduling multiple DAG tasks on multi-cores and allows intra-task processor sharing. First, we adapt the decomposition-based framework for federated scheduling and propose an energy-sub-optimal scheduler. Then, we derive an approximation algorithm to identify processors to be merged together for further improvements in energy-efficiency. The effectiveness of the proposed approach is evaluated both theoretically via approximation ratio bounds and also experimentally through simulation study. Experimental results on randomly generated workloads show that our algorithms achieve an energy saving of 60% to 68% compared to existing DAG task schedulers.Keywords
This publication has 29 references indexed in Scilit:
- Mobile 3D mapping for surveying earthwork projects using an Unmanned Aerial Vehicle (UAV) systemAutomation in Construction, 2014
- Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combinationACM Transactions on Embedded Computing Systems, 2014
- Energy Efficient Block-Partitioned Multicore Processors for Parallel ApplicationsJournal of Computer Science and Technology, 2011
- Energy efficient scheduling of parallel tasks on multiprocessor computersThe Journal of Supercomputing, 2010
- Minimizing CPU energy in real-time systems with discrete speed managementACM Transactions on Embedded Computing Systems, 2009
- Energy-efficient policies for embedded clustersACM SIGPLAN Notices, 2005
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completenessTheoretical Computer Science, 2005
- Power-aware scheduling for AND/OR graphs in real-time systemsIEEE Transactions on Parallel and Distributed Systems, 2004
- Greed is good: Approximating independent sets in sparse and bounded-degree graphsAlgorithmica, 1997
- Introduction to Modern Statistical MechanicsPhysics Today, 1988