Algorithms for power savings

ABSTRACT

This paper examines two different mechanisms for saving power in battery-operated embedded systems. The first is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s). which indicates the power consumption level given a particular speed. We assume that P(s) and P(s)/s are convex. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its arrival time and before its deadline. Although each problem has been considered separately, this is the first theoretical analysis of systems which can use both mechanisms. We give an off line algorithm which is within a factor of three of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.

REFERENCES

• 1: Luca Benini , Alessandro Bogliolo , Giovanni De Micheli, A survey of design techniques for system-level dynamic power management, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.3, p.299-316, June 2000 [doi>10.1109/92.845896]
• 2: 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
• 3: 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]
• 4: Sandy Irani , Anna R. Karlin, Online computation, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 5: S. Irani , R. Gupta , S. Shukla, Competitive Analysis of Dynamic Power Management Strategies for Systems with Multiple Power Savings States, Proceedings of the conference on Design, automation and test in Europe, p.117, March 04-08, 2002
• 6: S. Irani and S. Shukla and R. Gupta, "Online Strategies for Dynamic Power Management in Systems with Multiple Power Saving States," submitted for publication.
• 7: Anna R. Karlin , Mark S. Manasse , Lyle A. McGeoch , Susan Owicki, Competitive randomized algorithms for non-uniform problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.301-309, January 22-24, 1990, San Francisco, California, United States
• 8: S. Keshav, C. Lund, S. Phillips, N. Reingold, and H. Saran, "An empirical evaluation of virtual circuit holding time policies in ip-over-atm networks," IEEE Journal on Selected Areas in Communications, vol. 13, pp. 1371--1382, 1995.
• 9: Yung-Hsiang Lu , Luca Benini , Giovanni De Micheli, Low-power task scheduling for multiple devices, Proceedings of the eighth international workshop on Hardware/software codesign, p.39-43, May 2000, San Diego, California, United States [doi>10.1145/334012.334020]
• 10: Gang Quan , Xiaobo Hu, Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors, Proceedings of the 38th conference on Design automation, p.828-833, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379074]
• 11: Vijay Raghunathan , Papleologos Spanos , Mani B. Srivastava, Adaptive Power-Fidelity in Energy-Aware Wireless Embedded Systems, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.106, December 03-06, 2001
• 12: Dinesh Ramanathan , Sandy Irani , Rajesh Gupta, Latency effects of system level power management algorithms, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 13: http://www.rockwellscientific.com/hidra/
• 14: Tajana Simunic , Giovanni De Micheli, Energy efficient system design and utilization, 2001
• 15: http://www2.parc.com/spl/projects/cosense/csp/slides/Srivastava.pdf
• 16: 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

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Algorithms, Economics, Theory