1 + ε approximation clock rate assignment for periodic real-time tasks on a voltage-scaling processor

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

1 + ε approximation clock rate assignment for periodic real-time tasks on a voltage-scaling processor

Full text

Pdf (156 KB)

Source

International Conference On Embedded Software archive
Proceedings of the 5th ACM international conference on Embedded software table of contents

Jersey City, NJ, USA

SESSION: Clocks and energy table of contents

Pages: 247 - 250

Year of Publication: 2005

ISBN:1-59593-091-4

Authors

Jian-Jia Chen	National Taiwan University, Taiwan
Tei-Wei Kuo	National Taiwan University, Taiwan
Chi-Sheng Shih	National Taiwan University, Taiwan

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/1086228.1086273 What is a DOI?

ABSTRACT

Energy-efficient scheduling is an effective way to balance the system performance and the energy consumption. We design a polynomial-time (1+ε)-approximation algorithm to minimize the energy consumption for periodic real-time tasks over such processors, where ε is the tolerable error given by users (1 ≥ ε > 0). It provides trade-offs between the user's tolerable error and the runtime complexity including the time complexity and the memory space complexity. System engineers could trade performance with implementation constraints.

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	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
	2	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]
	3	Jane W. S. W. Liu, Real-Time Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2000
	4	Pedro Mejia-Alvarez , Eugene Levner , Daniel Mossé, Adaptive scheduling server for power-aware real-time tasks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.284-306, May 2004 [doi>10.1145/993396.993400]
	5	B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic task scheduling for hard-real-time systems. Real-time Systems Journal, July 1989.
	6	Intel-Xscale Microarchitecture. http://developer.intel.com/design/intelxscale/benchmarks.htm.
	7	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 6

	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
	Jian-Jia Chen , Tei-Wei Kuo, Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Xiliang Zhong , Cheng-Zhong Xu, System-wide energy minimization for real-time tasks: lower bound and approximation, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Sushu Zhang , Karam S. Chatha , Goran Konjevod, Approximation algorithms for power minimization of earliest deadline first and rate monotonic schedules, Proceedings of the 2007 international symposium on Low power electronics and design, August 27-29, 2007, Portland, OR, USA
	Xiliang Zhong , Cheng-Zhong Xu, System-wide energy minimization for real-time tasks: Lower bound and approximation, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.3, p.1-24, April 2008
	Hui Liu , Zili Shao , Meng Wang , Junzhao Du , Chun Jason Xue , Zhiping Jia, Combining Coarse-Grained Software Pipelining with DVS for Scheduling Real-Time Periodic Dependent Tasks on Multi-Core Embedded Systems, Journal of Signal Processing Systems, v.57 n.2, p.249-262, November 2009