Energy Efficient Task Assignment with Guaranteed Probability Satisfying Timing Constraints for Embedded Systems
Top Cited Papers
- 1 October 2013
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 25 (8), 2043-2052
- https://doi.org/10.1109/tpds.2013.251
Abstract
The trade-off between system performance and energy efficiency (service time) is critical for battery-based embedded systems. Most of the previous work focuses on saving energy in a deterministic way by taking the average or worst scenario into account. However, such deterministic approaches usually are inappropriate in modeling energy consumption because of uncertainties in conditional instructions on processors and time-varying external environments (e.g., fluctuant network bandwidth and different user inputs). By adopting a probabilistic approach, this paper proposes a model and a set of algorithms to address the Processor and Voltage Assignment with Probability (PVAP) problem of data-dependent aperiodic tasks in real-time embedded systems, ensuring that all the tasks can be done under the time constraint with a guaranteed probability. We adopt a task DAG (Directed Acyclic Graph) to model the PVAP problem. We first use a processor scheduling algorithm to map the task DAG onto a set of voltage-variable processors, and then use our dynamic programming algorithm to assign a proper voltage to each task. Finally, to escape from local optima, a local search with restarts searches the optimal solution from candidate solutions by updating the objective function, until the stop criteria are reached or a time bound is elapsed. The experimental results demonstrate that for probability 1.0, our approach yields slightly better results than the well-known algorithms like ASAP/ALAP (As Soon As Possible/As Late As Possible) and ILP (Integer Linear Programming) with/without DVS (Dynamic Voltage Scaling). However, for probabilities 0.8 and 0.9, our approach significantly outperforms those algorithms (maximum improvement of 50.3 percent).Keywords
This publication has 31 references indexed in Scilit:
- Parallel and distributed local search in COMETComputers & Operations Research, 2009
- IntroductionPublished by Springer Science and Business Media LLC ,2009
- Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systemsACM Transactions on Design Automation of Electronic Systems, 2009
- Energy-Constrained Scheduling of DAGs on Multi-core ProcessorsCommunications in Computer and Information Science, 2009
- Combining Coarse-Grained Software Pipelining with DVS for Scheduling Real-Time Periodic Dependent Tasks on Multi-Core Embedded SystemsJournal of Signal Processing Systems, 2008
- Voltage Assignment with Guaranteed Probability Satisfying Timing Constraint for Real-time Multiproceesor DSPJournal of Signal Processing Systems, 2007
- Local search with annealing-like restarts to solve the VRPTWEuropean Journal of Operational Research, 2003
- Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systemsIEEE Transactions on Parallel and Distributed Systems, 2003
- Energy characterization of embedded real-time operating systemsACM SIGARCH Computer Architecture News, 2001
- Probabilistic loop scheduling for applications with uncertain execution timeInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2000