Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors

Full text

Pdf (213 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 38th annual Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 828 - 833

Year of Publication: 2001

ISBN:1-58113-297-2

Authors

Gang Quan	Department of Computer Science & Engineering, University of Notre Dame, Notre Dame, IN
Xiaobo Hu	Department of Computer Science & Engineering, University of Notre Dame, Notre Dame, IN

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 29, Citation Count: 65

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/378239.379074 What is a DOI?

ABSTRACT

Energy consumption has become an increasingly important consideration in designing many real-time embedded systems. Variable voltage processors, if used properly, can dramatically reduce such system energy consumption. In this paper, we present a technique to determine voltage settings for a variable voltage processor that utilizes a fixed priority assignment to schedule jobs. Our approach also produces the minimum constant voltage needed to feasibly schedule the entire job set. Our algorithms lead to significant energy saving compared with previously presented approaches.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alan Burns , Ken Tindell , Andy Wellings, Effective Analysis for Engineering Real-Time Fixed Priority Schedulers, IEEE Transactions on Software Engineering, v.21 n.5, p.475-480, May 1995 [doi>10.1109/32.387477]
	2	V. Gutnik and A. Chandrakasan. An efficient controller for variable supply-voltage low power processing. Symposium on VLSI Circuits, pages 158-159, 1996.
	3	Inki Hong , Darko Kirovski , Gang Qu , Miodrag Potkonjak , Mani B. Srivastava, Power optimization of variable voltage core-based systems, Proceedings of the 35th annual conference on Design automation, p.176-181, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277088]
	4	Inki Hong , Miodrag Potkonjak , Mani B. Srivastava, On-line scheduling of hard real-time tasks on variable voltage processor, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.653-656, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289105]
	5	I. Hong , G. Qu , M. Potkonjak , M. B. Srivastava, Synthesis Techniques for Low-Power Hard Real-Time Systems on Variable Voltage Processors, Proceedings of the IEEE Real-Time Systems Symposium, p.178, December 02-04, 1998
	6	Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
	7	C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
	8	Jane W. S. W. Liu, Real-Time Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2000
	9	W. Namgoong, M. Yu, and T. Meng. A high-efficiency variable-voltage cmos dynamic dc-dc switching regulator. IEEE Internation Solid-State Circuits Conference, pages 380-381, 1997.
	10	Namyun Kim , Minsoo Ryu , Seongsoo Hong , M. Saksena , Chong-Ho Choi , Heonshik Shin, Visual assessment of a real-time system design: a case study on a CNC controller, Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), p.300, December 04-06, 1996
	11	G. Quan and X. Hu. Energy Efficient Scheduling for Real-Time Systems on Variable Voltage Processors. Technical Report TR01-3, Dept. of Compu. Sci. & Eng., Univ. of Notre Dame, 2001.
	12	Youngsoo Shin , Kiyoung Choi, Power conscious fixed priority scheduling for hard real-time systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.134-139, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309901]
	13	Youngsoo Shin , Kiyoung Choi , Takayasu Sakurai, Power optimization of real-time embedded systems on variable speed processors, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	14	F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995

CITED BY 65

	Vishnu Swaminathan , Krishnendu Chakrabarty, Pruning-based energy-optimal device scheduling for hard real-time systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado
	Ravindra Jejurikar , Rajesh Gupta, Energy aware task scheduling with task synchronization for embedded real time systems, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France
	Ali Manzak , Chaitali Chakrabarti, Variable voltage task scheduling algorithms for minimizing energy, Proceedings of the 2001 international symposium on Low power electronics and design, p.279-282, August 2001, Huntington Beach, California, United States
	Peng Yang , Paul Marchal , Chun Wong , Stefaan Himpe , Francky Catthoor , Patrick David , Johan Vounckx , Rudy Lauwereins, Managing dynamic concurrent tasks in embedded real-time multimedia systems, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan
	Dexin Li , Qiang Xie , Pai H. Chou, Scalable modeling and optimization of mode transitions based on decoupled power management architecture, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Yann-Hang Lee , Yoonmee Doh , C. M. Krishna, EDF scheduling using two-mode voltage-clock-scaling for hard real-time systems, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA
	Han-Saem Yun , Jihong Kim, On energy-optimal voltage scheduling for fixed-priority hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.393-430, August 2003
	Han-Saem Yun , Jihong Kim, On energy-optimal voltage scheduling for fixed-priority hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.393-430, August 2003
	Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Bren Mochocki , Xiaobo Sharon Hu , Gang Quan, A realistic variable voltage scheduling model for real-time applications, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.726-731, November 10-14, 2002, San Jose, California
	Ali Manzak , Chaitali Chakrabarti, Variable voltage task scheduling algorithms for minimizing energy/power, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.2, p.270-276, April 2003
	Sunghyun Lee , Kiyoung Choi , Sungjoo Yoo, An intra-task dynamic voltage scaling method for SoC design with hierarchical FSM and synchronous dataflow model, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA
	Peng Yang , Francky Catthoor, Pareto-optimization-based run-time task scheduling for embedded systems, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA
	Daler Rakhmatov , Sarma Vrudhula, Energy management for battery-powered embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.277-324, August 2003
	Ramana Rao Kompella , Alex C. Snoeren, Practical lazy scheduling in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	Ying Zhang , Krishnendu Chakrabarty, Dynamic adaptation for fault tolerance and power management in embedded real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.336-360, May 2004
	Marcus T. Schmitz , Bashir M. Al-Hashimi , Petru Eles, Iterative schedule optimization for voltage scalable distributed embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.182-217, February 2004
	Gang Qu, What is the limit of energy saving by dynamic voltage scaling?, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Vishnu Swaminathan , Krishnendu Chakrabarty, Pruning-based, energy-optimal, deterministic I/O device scheduling for hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.141-167, February 2005
	Ying Zhang , Robert Dick , Krishnendu Chakrabarty, Energy-aware deterministic fault tolerance in distributed real-time embedded systems, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Chaeseok Im , Soonhoi Ha , Huiseok Kim, Dynamic voltage scheduling with buffers in low-power multimedia applications, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.4, p.686-705, November 2004
	Niraj K. Jha, Low power system scheduling and synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Cristiano Pereira , Rajesh Gupta , Paleologos Spanos , Mani Srivastava, A power-aware API for embedded and portable systems, Power aware computing, Kluwer Academic Publishers, Norwell, MA, 2002
	Shaoxiong Hua , Gang Qu, Energy-efficient dual-voltage soft real-time system with (m,k)-firm deadline guarantee, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA
	D. Verkest , P. Yang , C. Wong , P. Marchal, Optimisation problems for dynamic concurrent task-based systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Yumin Zhang , Xiaobo Sharon Hu , Danny Z. Chen, Task scheduling and voltage selection for energy minimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.211-230, February 2005
	T. K. Tan , A. Raghunathan , N. K. Jha, Energy macromodeling of embedded operating systems, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.231-254, February 2005
	Jianli Zhuo , Chaitali Chakrabarti, System-level energy-efficient dynamic task scheduling, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	A. Goel , C. M. Krishna , I. Koren, Energy aware kernel for hard real-time systems, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA
	Vincent W. Freeh , David K. Lowenthal, Using multiple energy gears in MPI programs on a power-scalable cluster, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
	Shaoxiong Hua , Gang Qu , Shuvra S. Bhattacharyya, Energy reduction techniques for multimedia applications with tolerance to deadline misses, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Rony Ghattas , Alexander G. Dean, Energy management for commodity short-bit-width microcontrollers, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA
	Bruno Gaujal , Nicolas Navet , Cormac Walsh, Shortest-path algorithms for real-time scheduling of FIFO tasks with minimal energy use, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.907-933, November 2005
	Rabi N. Mahapatra , Wei Zhao, An Energy-Efficient Slack Distribution Technique for Multimode Distributed Real-Time Embedded Systems, IEEE Transactions on Parallel and Distributed Systems, v.16 n.7, p.650-662, July 2005
	Yumin Zhang , Xiaobo Sharon Hu , Danny Z. Chen, Energy minimization of real-time tasks on variable voltage processors with transition energy overhead, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Shaoxiong Hua , Gang Qu, Voltage setup problem for embedded systems with multiple voltages, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.7, p.869-872, July 2005
	Van R. Culver , Sunil P. Khatri, A dynamic voltage scaling algorithm for energy reduction in hard real-time systems, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	C. Brandolese , W. Fornaciari , F. Salice , L. Pomante , R. Zafalon, DPM at OS level: low-power scheduling policies, Proceedings of the 5th WSEAS International Conference on Circuits, Systems, Electronics, Control & Signal Processing, p.100-105, November 01-03, 2006, Dallas, Texas
	Jianli Zhuo , Chaitali Chakrabarti , Naehyuck Chang , Sarma Vrudhula, Extending the lifetime of fuel cell based hybrid systems, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Jian-Jia Chen , Tei-Wei Kuo, Procrastination for leakage-aware rate-monotonic scheduling on a dynamic voltage scaling processor, ACM SIGPLAN Notices, v.41 n.7, July 2006
	Shaoxiong Hua , Gang Qu , Shuvra S. Bhattacharyya, Probabilistic design of multimedia embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.3, p.15-es, July 2007
	Krishnan Srinivasan , Karam S. Chatha, Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraints, Integration, the VLSI Journal, v.40 n.3, p.326-354, April, 2007
	Jianli Zhuo , Chaitali Chakrabarti , Naehyuck Chang, Energy management of DVS-DPM enabled embedded systems powered by fuel cell-battery hybrid source, Proceedings of the 2007 international symposium on Low power electronics and design, August 27-29, 2007, Portland, OR, USA
	Tongquan Wei , Piyush Mishra , Kaijie Wu , Han Liang, Online task-scheduling for fault-tolerant low-energy real-time systems, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Sungpack Hong , Sungjoo Yoo , Hoonsang Jin , Kyu-Myung Choi , Jeong-Taek Kong , Soo-Kwan Eo, Runtime distribution-aware dynamic voltage scaling, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Bren Mochocki , Xiaobo Sharon Hu , Gang Quan, Transition-overhead-aware voltage scheduling for fixed-priority real-time systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.2, p.11-es, April 2007
	Jinfeng Liu , P. H. Chou, Optimizing mode transition sequences in idle intervals for component-level and system-level energy minimization, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.21-28, November 07-11, 2004
	Yoonmee Doh , Daeyoung Kim , Yann-Hang Lee , C. M. Krishna, Bounded energy allocation and scheduling for real-time Embedded Systems, Journal of Embedded Computing, v.1 n.1, p.101-117, January 2005
	Vishnu Swaminathan , Krishnendu Chakrabarty, Generalized Network Flow Techniques for Dynamic Voltage Scaling in Hard Real-Time Systems, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.21, November 09-13, 2003
	Ying Zhang , Krishnendu Chakrabarty , Vishnu Swaminathan, Energy-Aware Fault Tolerance in Fixed-Priority Real-Time Embedded Systems, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.209, November 09-13, 2003
	Dong Wu , Bashir M. Al-Hashimi , Petru Eles, Scheduling and Mapping of Conditional Task Graphs for the Synthesis of Low Power Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10090, March 03-07, 2003
	Ying Zhang , Krishnendu Chakrabarty, Energy-Aware Adaptive Checkpointing in Embedded Real-Time Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10918, March 03-07, 2003
	Gang Quan , Xiaobo Sharon Hu, Energy efficient DVS schedule for fixed-priority real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.29-es, September 2007
	Jianli Zhuo , Chaitali Chakrabarti, Energy-efficient dynamic task scheduling algorithms for DVS systems, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.2, p.1-25, February 2008
	Jiong Luo , Niraj K. Jha, Static and Dynamic Variable Voltage Scheduling Algorithms for Real-Time Heterogeneous Distributed Embedded Systems, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.719, January 07-11, 2002
	Dexin Li , Pai H. Chou , Nader Bagherzadeh, Mode Selection and Mode-Dependency Modeling for Power-Aware Embedded Systems, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.697, January 07-11, 2002
	Ying Zhang , Krishnendu Chakrabarty, Task Feasibility Analysis and Dynamic Voltage Scaling in Fault-Tolerant Real-Time Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.21170, February 16-20, 2004
	Bruno Gaujal , Nicolas Navet, Dynamic voltage scaling under EDF revisited, Real-Time Systems, v.37 n.1, p.77-97, October 2007
	Ravindra Jejurikar , Rajesh Gupta, Optimized Slowdown in Real-Time Task Systems, IEEE Transactions on Computers, v.55 n.12, p.1588-1598, December 2006
	Rodrigo M. Santos , Jorge Santos , Javier D. Orozco, Power saving and fault-tolerance in real-time critical embedded systems, Journal of Systems Architecture: the EUROMICRO Journal, v.55 n.2, p.90-101, February, 2009
	Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, ACM Transactions on Algorithms (TALG), v.3 n.4, p.41-es, November 2007
	Sheayun Lee , Insik Shin , Woonseok Kim , Insup Lee , Sang Lyul Min, A design framework for real-time embedded systems with code size and energy constraints, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.2, p.1-27, February 2008
	Xiliang Zhong , Cheng-Zhong Xu, Energy-Aware Modeling and Scheduling for Dynamic Voltage Scaling with Statistical Real-Time Guarantee, IEEE Transactions on Computers, v.56 n.3, p.358-372, March 2007
	Ayse Kivilcim Coskun , Tajana Šimunic Rosing , Keith A. Whisnant , Kenny C. Gross, Static and dynamic temperature-aware scheduling for multiprocessor SoCs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.9, p.1127-1140, September 2008