Energy management for battery-powered embedded systems

ABSTRACT

Portable embedded computing systems require energy autonomy. This is achieved by batteries serving as a dedicated energy source. The requirement of portability places severe restrictions on size and weight, which in turn limits the amount of energy that is continuously available to maintain system operability. For these reasons, efficient energy utilization has become one of the key challenges to the designer of battery-powered embedded computing systems.In this paper, we first present a novel analytical battery model, which can be used for the battery lifetime estimation. The high quality of the proposed model is demonstrated with measurements and simulations. Using this battery model, we introduce a new "battery-aware" cost function, which will be used for optimizing the lifetime of the battery. This cost function generalizes the traditional minimization metric, namely the energy consumption of the system. We formulate the problem of battery-aware task scheduling on a single processor with multiple voltages. Then, we prove several important mathematical properties of the cost function. Based on these properties, we propose several algorithms for task ordering and voltage assignment, including optimal idle period insertion to exercise charge recovery.This paper presents the first effort toward a formal treatment of battery-aware task scheduling and voltage scaling, based on an accurate analytical model of the battery behavior.

REFERENCES

• 1: Arora, P., Doyle, M., Gozdz, A., White, R., and Newman, J. 2000. Comparison between computer simulations and experimental data for high-rate discharges of plastic lithium-ion batteries. J. Power Sources 88.
• 2: Bard, A. and Faulkner, L. 1980. Electrochemical Methods. Wiley, New York.
• 3: Bellman, R. 1961. A Brief Introduction to Theta Functions. Holt, Rinehart and Winston, New York.
• 4: L. Benini , G. Castelli , A. Macii , E. Macii , M. Poncino , R. Scarsi, A discrete-time battery model for high-level power estimation, Proceedings of the conference on Design, automation and test in Europe, p.35-41, March 27-30, 2000, Paris, France [doi>10.1145/343647.343694]
• 5: Luca Benini , Giuliano Castelli , Alberto Macii , Riccardo Scarsi, Battery-Driven Dynamic Power Management, IEEE Design & Test, v.18 n.2, p.53-60, March 2001 [doi>10.1109/54.914621]
• 6: Botte, G., Subramanian, V., and White, R. 2000. Mathematical modeling of secondary lithium batteries. Electrochimica Acta 45.
• 7: Robert W. Brodersen, Energy Efficient Microprocessor Design, Kluwer Academic Publishers, Norwell, MA, 2001
• 8: Chowdhury, P. and Chakrabarti, C. 2002. Battery-aware task scheduling for a system-on-a-chip using voltage/clock scaling. In Proceedings of Work. Signal Processing Systems.
• 9: Doyle, M., Fuller, T., and Newman, J. 1993. Modeling of galvanostatic charge and discharge of the lithium/polymer/insertion cell. J. Electrochem. Soc. 140, 6.
• 10: Doyle, M. and Newman, J. 1995. Modeling the performance of rechargeable lithium-based cells: Design correlations for limiting cases. J. Power Sources 54.
• 11: Dudzinski, K. and Walukiewicz, S. 1987. Exact methods for the knapsack problem and its generalizations. European J. Oper. Research 28.
• 12: Fuller, T., Doyle, M., and Newman, J. 1994. Simulation and optimization of the dual lithium ion insertion cell. J. Electrochem. Soc. 141, 1.
• 13: Gold, S. 1997. A pspice macromodel for lithium-ion batteries. In Proc. Battery Conference.
• 14: Leslie A. Hall , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.142-151, January 28-30, 1996, Atlanta, Georgia, United States
• 15: William R. Hamburgen , Deborah A. Wallach , Marc A. Viredaz , Lawrence S. Brakmo , Carl A. Waldspurger , Joel F. Bartlett , Timothy Mann , Keith I. Farkas, Itsy: Stretching the Bounds of Mobile Computing, Computer, v.34 n.4, p.28-36, April 2001 [doi>10.1109/2.917534]
• 16: Intel. 2002. http://developer.intel.com/communications/app_processors.htm.
• 17: 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]
• 18: Lawler, E. 1978. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. 2.
• 19: Linden, D. 1995. Handbook of Batteries. McGraw-Hill, New York.
• 20: Jinfeng Liu , Pai H. Chou , Nader Bagherzadeh , Fadi Kurdahi, Power-aware scheduling under timing constraints for mission-critical embedded systems, Proceedings of the 38th conference on Design automation, p.840-845, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379076]
• 21: Jiong Luo , Niraj K. Jha, Battery-aware static scheduling for distributed real-time embedded systems, Proceedings of the 38th conference on Design automation, p.444-449, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378553]
• 22: 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 [doi>10.1145/383082.383168]
• 23: Mooney III, V. and De Micheli, G. 2000. Hardware/software co-design of run-time schedulers for real-time systems. J. Design Automation Embed. Systems.
• 24: Takanori Okuma , Hiroto Yasuura , Tohru Ishihara, Software Energy Reduction Techniques for Variable-Voltage Processors, IEEE Design & Test, v.18 n.2, p.31-41, March 2001 [doi>10.1109/54.914613]
• 25: Debashis Panigrahi , Sujit Dey , Ramesh Rao , Kanishka Lahiri , Carla Chiasserini , Anand Raghunathan, Battery Life Estimation of Mobile Embedded Systems, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.57, January 03-07, 2001
• 26: Massoud Pedram , Qing Wu, Design considerations for battery-powered electronics, Proceedings of the 36th ACM/IEEE conference on Design automation, p.861-866, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310089]
• 27: Pering, T. and Brodersen, R. 1998. Energy efficient voltage scheduling for real-time operating systems. In Proceedings of Real-Time Technology and Applications.
• 28: Trevor Pering , Tom Burd , Robert Brodersen, The simulation and evaluation of dynamic voltage scaling algorithms, Proceedings of the 1998 international symposium on Low power electronics and design, p.76-81, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280790]
• 29: 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
• 30: 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]
• 31: Daler Rakhmatov , Sarma Vrudhula , Chaitali Chakrabarti, Battery-conscious task sequencing for portable devices including voltage/clock scaling, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513967]
• 32: Daler Rakhmatov , Sarma Vrudhula , Deborah A. Wallach, Battery lifetime prediction for energy-aware computing, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566449]
• 33: Roberts, G. and Kaufman, H. 1966. Table of Laplace Transforms. Saunders, Philadelphia.
• 34: Dongkun Shin , Jihong Kim , Seongsoo Lee, Intra-Task Voltage Scheduling for Low-Energy, Hard Real-Time Applications, IEEE Design & Test, v.18 n.2, p.20-30, March 2001 [doi>10.1109/54.914596]
• 35: 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
• 36: Sidney, J. 1975. Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Research 23.
• 37: Tajana Simunic , Luca Benini , Andrea Acquaviva , Peter Glynn , Giovanni De Micheli, Dynamic voltage scaling and power management for portable systems, Proceedings of the 38th conference on Design automation, p.524-529, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379016]
• 38: Amit Sinha , Anantha P. Chandrakasan, Energy efficient real-time scheduling, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 39: Smith, W. 1956. Various optimizers for single-stage production. Naval Research Log. Quart. 3.
• 40: Weiser, M., Welch, B., Demers, A., and Shenker, S. 1994. Scheduling for reduced CPU energy. In Proceedings of OS Design and Implementation.
• 41: 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:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Performance

Keywords:
Battery, low-power design, modeling, scheduling, voltage scaling