Sushu Zhang
ABSTRACT
We address power minimization of earliest deadline first and rate monotonic schedules by voltage and frequency scaling. We prove that the problems are NP-hard, and present (1+∈) fully polynomial time approximation techniques that generate solutions which are guaranteed to be within a specified quality bound (QB= ∈) (say within 1% of the optimal). We demonstrate that our techniques can match optimal solutions when QB is set at 1%, out perform existing approaches [1] even when QB is set at 10%, generate solutions that are quite close to optimal (< 5%) even when QB is set at higher values (25%), and execute in a fraction of a second (with QB > 5%) for large 100 node task sets.
- N. K. Jha. Low power system scheduling and synthesis. In Proceedings of ICCAD, 2001. Google Scholar
Digital Library
- L. Benini and G. De Micheli. A survey of design techniques for system-level dynamic power management. IEEE Transactions on VLSI Systems, 2000. Google ScholarDigital Library
- C.L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in hard-real-time environment. Journal of ACM, 20(1), January 1973. Google ScholarDigital Library
- P. Mejia-Alvarez, E. Levner, and D. Mosse. Adaptive scheduling server for power aware real-time tasks. ACM TECS, 3(2):284--306, May 2004. Google ScholarDigital Library
- F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In IEEE Annual Foundations of Comp. Sci., 1995. Google ScholarDigital Library
- T. Ishihara and H. Yasuura. Voltage scheduling problem for dynamic variable voltage processors. In Proceedings of ISLPED, 1998. Google ScholarDigital Library
- Y. Shin, K. Choi, and T. Sakura. Power opimization of real-time embedded systems on variable speed processors. In Proceedings of ICCAD, 2000. Google ScholarDigital Library
- P. Pillai and K. G. Shin. Real-time dynamic voltage scaling for low-power embedded operating systems. In Proceedings of ACM Symposium on Operating Systems Principles, 2001. Google ScholarDigital Library
- H. Aydin, R. Melhem, D. Mosse, and P. M. Alvarez. Dynamic and aggressive scheduling techniques for power aware real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, 2001. Google ScholarDigital Library
- L. Yan, J. Luo, and N. K. Jha. Combined dynamic voltage scaling and adaptive body biasing for heterogeneous distributed real-time embedded systems. In Proceedings of ICCAD, 2003. Google ScholarDigital Library
- S. Irani, S. Shukla, and R. Gupta. Algorithms for power savings. In Proceedings of the 14th Symposium on Discrete Algorithms, 2003. Google ScholarDigital Library
- R. Jejurikar, C. Pereira, and R. Guptar. Leakage aware dynamic voltage scaling for real-time embedded systems. In Proceedings of DAC, 2004. Google ScholarDigital Library
- Y. Shin, K. Choi, and T. Sakura. Dynamic voltage and frequency scaling under a precise energy model considering variable and fixed components of the system power dissipation. In Proceedings of ICCAD, 2004. Google ScholarDigital Library
- B. Mochocki, X. S. Hu, and G. Quan. A unified approach to variable scheduling for nonideal dvs processors. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 23(9), September 2004. Google ScholarDigital Library
- F. Xie, M. Martonosi, and S. Malik. Bounds on power savings using runtime dynamic voltage scaling: An exact algorithm and a linear-time heuristic approximation. In Proceedings of ISLPED, 2005. Google ScholarDigital Library
- J. Chen, T. Kuo, and C. Shih. (1+∈) approximation clock rate assignment for periodic real-time tasks on a voltag-scaling processor. In Proceedings of EMSOFT, 2005. Google ScholarDigital Library
- X. Zhong and C. Xu. System-wide energy minimization for real-time tasks: Lower bound and approximation. In Proceedings of ICCAD, 2006. Google ScholarDigital Library
- P. Yang and F. Catthoor. Pareto-optimization-based run-time task scheduling for embedded systems. In Proceedings of CODES+ISSS, 2003. Google ScholarDigital Library
- W. Kim, J. Kim, and S. L. Min. A dynamic voltage scaling algorithm for dynamic-priority hard real-time systems using slack time analysis. In Proceedings of DATE, 2002. Google ScholarDigital Library
- C. M. Krishna and Y. H. Lee. Voltage-clock-scaling adaptive scheduling techniques for low power in hard real-time systems. IEEE Transactions on Computers, 52(12), December 2003. Google ScholarDigital Library
- Y. Zhu and F. Mueller. Feedback edf scheduling exploiting dynamic voltage scaling. In Proceedings of RTAS, 2004. Google ScholarDigital Library
- J. Zhuo and C. Chakrabarti. System-level energy-efficient dynamic task scheduling. In Proceedings of DAC, 2005. Google ScholarDigital Library
- B. Mochocki, X. S. Hu, and G. Quan. Practical on-line dvs scheduling for fixed-priority real-time systems. In Proceedings of RTAS, 2005. Google ScholarDigital Library
- V. Swaminathan and K. Chakrabarty. Network flow techniques for dynamic voltage scaling in hard real-time systems. IEEE Trans. on CAD of Integrated Circuits and Systems, 2004. Google ScholarDigital Library
- Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001. Google ScholarDigital Library
- H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer-Verlag, 2004.Google ScholarCross Ref
- A. K. Chandra, D. S. Hirschberg, and C. K. Wong. Approximation algorithms for some generalized knapsack problems. Theoretical Computer Science, (3):293--304, 1976.Google Scholar
- E. L. Lawler. Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, (4):339--356, 1979.Google Scholar
- K. Niyogi and D. Marculescu. Speed and voltage selection for gals systems based on voltage/frequency islands. In Proceedings of ASPDAC, 2005. Google ScholarDigital Library
- A. Sinha and A. P. Chandrakasan. Jouletrack-a web based tool for software energy profiling. In Proceedings of DAC, 2001. Google ScholarDigital Library
Index Terms
- Approximation algorithms for power minimization of earliest deadline first and rate monotonic schedules
Recommendations
Rate monotonic vs. EDF: judgment day
Since the first results published in 1973 by Liu and Layland on the Rate Monotonic (RM) and Earliest Deadline First (EDF) algorithms, a lot of progress has been made in the schedulability analysis of periodic task sets. Unfortunately, many ...
Job vs. portioned partitioning for the earliest deadline first semi-partitioned scheduling
In this paper, we focus on the semi-partitioned scheduling of sporadic tasks with constrained deadlines and identical processors. We study two cases of semi-partitioning: (i) the case where the worst case execution time (WCET) of a job can be portioned, ...
Buffer minimization in earliest-deadline first scheduling of dataflow graphs
LCTES '13Symbolic schedulability analysis of dataflow graphs is the process of synthesizing the timing parameters (i.e. periods, phases, and deadlines) of actors so that the task system is schedulable and achieves a high throughput when using a specific ...
Comments