Ultra-fast and efficient algorithm for energy optimization by gradient-based stochastic voltage and task scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Ultra-fast and efficient algorithm for energy optimization by gradient-based stochastic voltage and task scheduling

Full text

Pdf (616 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 12 , Issue 4 (September 2007) table of contents

Article No. 39

Year of Publication: 2007

ISSN:1084-4309

Authors

Bita Gorjiara	University of California, Irvine, CA, USA
Nader Bagherzadeh	University of California, Irvine, CA, USA
Pai H. Chou	University of California, Irvine, CA, USA and National Tsing Hua University, Taiwan

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 61, Citation Count: 0

Additional Information:

abstract references 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/1278349.1278352 What is a DOI?

ABSTRACT

This paper presents a new technique, called Adaptive Stochastic Gradient Voltage-and-Task Scheduling (ASG-VTS), for power optimization of multicore hard realtime systems. ASG-VTS combines stochastic and energy-gradient techniques to simultaneously solve the slack distribution and task reordering problem. It produces very efficient results with few mode transitions. Our experiments show that ASG-VTS reduces number of mode transitions by 4.8 times compared to traditional energy-gradient-based approaches. Also, our heuristic algorithm can quickly find a solution that is as good as the optimal for a real-life GSM encoder/decoder benchmark. The runtime of ASG-VTS is 150 times and 1034 times faster than energy-gradient based and optimal ILP algorithms, respectively. Since the runtime of ASG-VTS is very low, it is ideal for design space exploration in system-level design tools. We have also developed a web-based interface for ASG-VTS algorithm.

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	Abdi, S., Peng, J., Yu, H., Shin, D., Gerstlauer, A., Doemer, R., and Gajski, D. 2003. System-on-Chip Environment (SCE Version 2.2.0 Beta): Tutorial. Tech. rep. CECS-TR-03-41, CECS, University of California Irvine.
	2	Andrei, A., Schmitz, M., Eles, P., Peng, Z., and Al-Hashimi, B. 2005. Overhead-conscious voltage selection for dynamic and leakage energy reduction of time-constrained systems. IEE Proceedings---Computers and Digital Techniques 152, 1, 28--38.
	3	Alexandru Andrei , Marcus Schmitz , Petru Eles , Zebo Peng , Bashir M. Al-Hashimi, Overhead-Conscious Voltage Selection for Dynamic and Leakage Energy Reduction of Time-Constrained Systems, Proceedings of the conference on Design, automation and test in Europe, p.10518, February 16-20, 2004
	4	Neal K. Bambha , Shuvra S. Bhattacharyya , Jürgen Teich , Eckart Zitzler, Hybrid global/local search strategies for dynamic voltage scaling in embedded multiprocessors, Proceedings of the ninth international symposium on Hardware/software codesign, p.243-248, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371744]
	5	Cai, L., Gerstlauer, A., and Gajski, D. 2003. Retargetable profiling for rapid, early system-level design space exploration. Tech. rep. CECS-TR-04-04, CECS, University of California Irvine. October.
	6	Robert P. Dick , Niraj K. Jha, MOCSYN: multiobjective core-based single-chip system synthesis, Proceedings of the conference on Design, automation and test in Europe, p.55-es, January 1999, Munich, Germany [doi>10.1145/307418.307502]
	7	European Telecommunication Standards Institute (ETSI). 1996. Digital cellular telecommunications system; enhanced full rate (EFR) speech transcoding (GSM 06.60).
	8	Gajski, D. D., Zhu, J., Dömer, R., Gerstlauer, A., and Zhao, S. 2000. SpecC: Specification Language and Methodology. Kluwer Academic Publishers, Boston, MA.
	9	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	10	Gorjiara, B. 2004. http://www.ece.uci.edu/~bgorjiar.
	11	Bita Gorjiara , Nader Bagherzadeh , Pai Chou, An efficient voltage scaling algorithm for complex SoCs with few number of voltage modes, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013326]
	12	Bita Gorji-Ara , Pai Chou , Nader Bagherzadeh , Mehrdad Reshadi , David Jensen, Fast and efficient voltage scheduling by evolutionary slack distribution, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
	13	Flavius Gruian , Krzysztof Kuchcinski, LEneS: task scheduling for low-energy systems using variable supply voltage processors, Proceedings of the 2001 conference on Asia South Pacific design automation, p.449-455, January 2001, Yokohama, Japan [doi>10.1145/370155.370511]
	14	Intel. 2007. Intel XScale microarchitecture. http://developer.intel.com/design/intelxscale.
	15	Ravindra Jejurikar , Rajesh Gupta, Dynamic voltage scaling for systemwide energy minimization in real-time embedded systems, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013261]
	16	Lap-Fai Leung , Chi-Ying Tsui , Wing-Hung Ki, Minimizing energy consumption of multiple-processors-core systems with simultaneous task allocation, scheduling and voltage assignment, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
	17	Jiong Luo , Niraj K. Jha, Power-profile Driven Variable Voltage Sealing for Heterogeneous Distributed Real-time Embedded Systems, Proceedings of the 16th International Conference on VLSI Design, p.369, January 04-08, 2003
	18	Steven M. Martin , Krisztian Flautner , Trevor Mudge , David Blaauw, Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.721-725, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774678]
	19	Marcus T. Schmitz , Bashir M. Al-Hashimi, Considering power variations of DVS processing elements for energy minimisation in distributed systems, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500060]
	20	M. Schmitz , B. Al-Hashimi , P. Eles, Energy-Efficient Mapping and Scheduling for DVS Enabled Distributed Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.514, March 04-08, 2002
	21	Marcus T. Schmitz , Bashir M. Al-Hashimi , Petru Eles, System-Level Design Techniques for Energy-Efficient Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 2004
	22	James C. Spall, Introduction to Stochastic Search and Optimization, John Wiley & Sons, Inc., New York, NY, 2003
	23	von Weymarn, M. 2001. Development of a specification model of the EFR vocoder. Tech. rep. ICS-TR-01-35, University of California Irvine.
	24	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 [doi>10.1145/513918.513966]
	25	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 [doi>10.1145/1119772.1119786]