Abstract
Embedded systems have limited energy resources. Hence, they should conserve these resources to extend their period of operation. Recently, dynamic frequency scaling (DFS) and dynamic voltage scaling (DVS) have been added to a various embedded processors as a means to increase battery life. A number of scheduling techniques have been developed to exploit DFS and DVS for real-time systems to reduce energy consumption. These techniques exploit idle and slack time of a schedule. Idle time can be consumed by lowering the processor frequency of selected tasks while slack time allows later tasks to execute at lower frequencies with reduced voltage demands.Our work delivers energy savings beyond the level of prior work. We enhance the earliest-deadline first (EDF) scheduling to exploit slack time generated by the invocation of the task at multiple frequency levels within the same invocation. The technique relies strictly on operating system support within the scheduler to implement the approach. Early scaling at a low frequency, determined by a feedback mechanism and facilitated by a slack-passing scheme, capitalizes on high probabilities of a task to finish its execution without utilizing its worst-case execution budget. If a task does not complete at a certain point in time within its low frequency range, the remainder of it continues to execute at a higher frequency. Our experiments demonstrate that the resulting energy savings exceed those of previously published work by up to 33%. In addition, our method only adds a constant complexity at each scheduling point, which has not been achieved by prior work, to the best of our knowledge.
- R. Arnold, F. Mueller, D. B. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. In IEEE Real-Time Systems Symposium, pages 172--181, December 1994]]Google ScholarCross Ref
- N. Audsley, A. Burns, R. Davis, K. Tindell, and A. J. Wellings. Fixed priority pre-emptive scheduling: An historical perspective. J. of Real-Time Systems, 8:173--198, 1995]] Google ScholarDigital Library
- T.P. Baker. Stack-based scheduling of realtime processes. Real-Time Systems, 3(1):67--99, March 1991]] Google ScholarDigital Library
- T.P. Baker and Alan Shaw. The cyclic executive model and Ada. Technical Report 88-04-07, University of Washington, Department of Computer Science, Seattle, Washington, 1988]]Google ScholarCross Ref
- Giorgio C. Buttazzo. Hard Real-Time Computing Systems. Kluwer, 1997]] Google ScholarDigital Library
- H. Chetto and M. Chetto. Some results of the earliest deadline scheduling algorithm. IEEE Transactions on Software Engineering, 15(10):1261--1269, October 1989]] Google ScholarDigital Library
- J. Kim D. Shin and S. Lee. Intra-task voltage scheduling for low-energy hard real-time applications. In IEEE Design and Test of Computers, March 2001]] Google ScholarDigital Library
- R. I. Davis, K. W. Tindell, and A. Burns. Scheduling slack time in fixed priority preemptive systems. In Susan Davidson and Insup Lee, editors, Proceedings of the Real-Time Systems Symposium, pages 222--231, Raleigh-Durham, NC, December 1993. IEEE Computer Society Press]]Google Scholar
- C. Ferdinand, F. Martin, and R. Wilhelm. Applying compiler techiniques to cache behavior prediction. In ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, pages 37--46, June 1997]]Google Scholar
- K. Govil, E. Chan, and H. Wasserman. Comparing algorithms for dynamic speed-setting of a low-power cpu. In 1st Int'l Conference on Mobile Computing and Networking, Nov 1995]] Google ScholarDigital Library
- F. Gruian. Hard real-time scheduling for low energy using stochastic data and dvs processors. In Proceedings of the International Symposium on Low-Power Electronics and Design ISLPED'01, Aug 2001]] Google ScholarDigital Library
- F. Gruian and Kuchcinski. Lenes: task scheduling for low-energy systems using variable voltage processors. In Proceedings of ASP-DAC, 2001]] Google ScholarDigital Library
- D. Grunwald, P. Levis, C. Morrey III, M. Neufeld, and K. Farkas. Policies for dynamic clock scheduling. In Symp. on Operating Systems Design and Implementation, Oct 2000]] Google ScholarDigital Library
- D. Mosse H. Aydin, R. Melhem and P.M. Alvarez. Dynamic and aggressive scheduling techniques for power-aware real-time systems. In Proceedings of 22nd Real-Time Systems Symposium, December 2001]] Google ScholarDigital Library
- M. Harmon, T. P. Baker, and D. B. Whalley. A retargetable technique for predicting execution time. In IEEE Real-Time Systems Symposium, pages 68--77, December 1992]]Google ScholarCross Ref
- C. A. Healy, D. B. Whalley, and M. G. Harmon. Integrating the timing analysis of pipelining and instruction caching. In IEEE Real-Time Systems Symposium, pages 288--297, December 1995]] Google ScholarDigital Library
- I. Hong, M. Potkonjak, and M. Srivastava. On-line scheduling of hard real-time tasks on variable voltage processor. In Int'l Conference on Computer-Aided Design, Nov 1998]] Google ScholarDigital Library
- I. Hong, G. Qu, M. Potkonjak, and M. Srivastava. Synthesis techniques for low-power hard real-time systems on variable voltage processors. In 19th Real-Time Systems Symposium, Dec 1998]] Google ScholarDigital Library
- C. Krishna and Y. Lee. Voltage clock scaling adaptive scheduling techniques for low power in hard real-time systems. In 6th Real-Time Technology and Applications Symposium, May 2000]] Google ScholarDigital Library
- Y. Lee and C. Krishna. Voltage clock scaling for low energy consumption in real-time embedded systems. In 6th Int'l Conf. on Real-Time Computing Systems and Applications, Dec 1999]] Google ScholarDigital Library
- John P. Lehoczky and Sandra Ramos-Thuel. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems. In Robert Werner, editor, Proceedings of the Real-Time Systems Symposium - 1992, pages 110--124, Phoenix, Arizona, USA, December 1992. IEEE Computer Society Press]]Google Scholar
- Y.-T. S. Li, S. Malik, and A. Wolfe. Efficient microarchitecture modeling and path analysis for real-time software. In IEEE Real-Time Systems Symposium, pages 298--397, December 1995]] Google ScholarDigital Library
- Y.-T. S. Li, S. Malik, and A. Wolfe. Efficient microarchitecture modeling and path analysis for real-time software. In IEEE Real-Time Systems Symposium, pages 298--397, December 1995]] Google ScholarDigital Library
- S.-S. Lim, Y. H. Bae, G. T. Jang, B.-D. Rhee, S. L. Min, C. Y. Park, H. Shin, and C. S. Kim. An accurate worst case timing analysis for RISC processors. In IEEE Real-Time Systems Symposium, pages 97--108, December 1994]]Google Scholar
- C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. of the Association for Computing Machinery, 20(1):46--61, January 1973]] Google ScholarDigital Library
- J. Liu. Real-Time Systems. Prentice Hall, 2000]] Google ScholarDigital Library
- J. Lorch and A. J. Smith. Improving dynamic voltage scaling algorithms with pace. In Proceedings of the ACM SIGMETRICS 2001 Conference, June 2001]] Google ScholarDigital Library
- D. Mosse, H. Aydin, B. Childers, and R. Melhem. Compiler-assisted dynamic power-aware scheduling for real-time applications. In Workshop on Compilers and Operating Systems for Low Power, October 2000]]Google Scholar
- F. Mueller. Timing analysis for instruction caches. Real-Time Systems, 18(2/3):209--239, May 2000]] Google ScholarDigital Library
- C. Y. Park. Predicting program execution times by analyzing static and dynamic program paths. Real-Time Systems, 5(1):31--61, March 1993]] Google ScholarDigital Library
- T. Pering, T. Burd, and R. Brodersen. The simulation of dynamic voltage scaling algorithms. In Symp. on Low Power Electronics, 1995]] Google ScholarDigital Library
- Padmanabhan Pillai and Kang~G. Shin. Real-Time dynamic voltage scaling for Low-Power embedded operating systems. In Greg Ganger, editor, Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP-01), volume 35, 5 of ACM SIGOPS Operating Systems Review, pages 89--102, New York, October ~21--24 2001. ACM Press]] Google ScholarDigital Library
- J. Pouwelse, K. Langendoen, and H. Sips. Dynamic voltage scaling on a low-power microprocessor, 2000]]Google Scholar
- P. Puschner and C. Koza. Calculating the maximum execution time of real-time programs. Real-Time Systems, 1(2):159--176, September 1989]] Google ScholarDigital Library
- Lui Sha, Ragunathan Rajkumar, and John~P. Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Computers, 39(9):1175--1185, September 1990]] Google ScholarDigital Library
- Y. Shin, K. Choi, and T. Sakurai. Power optimization of real-time embedded systems on variable speed processors. In Int'l Conf. on Computer-Aided Design, 2000]] Google ScholarDigital Library
- J. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo. Deadline Scheduling for Real-Time Systems. Kluwer, 1998]] Google ScholarDigital Library
- J. Wegener and F. Mueller. A comparison of static analysis and evolutionary testing for the verification of timing constraints. Real-Time Systems, 21(3):241--268, November 2001]] Google ScholarDigital Library
- M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced cpu energy. In 1st Symp. on Operating Systems Design and Implementation, Nov 1994]] Google ScholarDigital Library
- W. Wolf. Smart cameras and embedded computing. seminar presentation, January 2002]] Google ScholarDigital Library
- N. Zhang, A. Burns, and M. Nicholson. Pipelined processors and worst case execution times. Real-Time Systems, 5(4):319--343, October 1993]] Google ScholarDigital Library
Index Terms
- Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints
Recommendations
Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints
LCTES/SCOPES '02: Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systemsEmbedded systems have limited energy resources. Hence, they should conserve these resources to extend their period of operation. Recently, dynamic frequency scaling (DFS) and dynamic voltage scaling (DVS) have been added to a various embedded processors ...
Feedback EDF Scheduling of Real-Time Tasks Exploiting Dynamic Voltage Scaling
Many embedded systems are constrained by limits on power consumption, which are reflected in the design and implementation for conserving their energy utilization. Dynamic voltage scaling (DVS) has become a promising method for embedded systems to ...
Feedback EDF scheduling exploiting hardware-assisted asynchronous dynamic voltage scaling
LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systemsRecent processor support for dynamic frequency and voltage scaling (DVS) allows software to affect power consumption by varying execution frequency and supply voltage on the fly. However, processors generally enter a sleep state while transitioning ...
Comments