Battery-aware static scheduling for distributed real-time embedded systems

ABSTRACT

This paper addresses battery-aware static scheduling in battery-powered distributed real-time embedded systems. As suggested by previous work, reducing the discharge current level and shaping its distribution are essential for extending the battery lifespan. We propose two battery-aware static scheduling schemes. The first one optimizes the discharge power profile in order to maximize the utilization of the battery capacity. The second one targets distributed systems composed of voltage-scalable processing elements (PEs). It performs variable-voltage scheduling via efficient slack time re-allocation, which helps reduce the average discharge power consumption as well as flatten the discharge power profile. Both schemes guarantee the hard real-time constraints and precedence relationships in the real-time distributed embedded system specification. Based on previous work, we develop a battery lifespan evaluation metric which is aware of the shape of the discharge power profile. Our experimental results show that the battery lifespan can be increased by up to 29% by optimizing the discharge power file alone. Our variable-voltage scheme increases the battery lifespan by up to 76% over the non-voltage-scalable scheme and by up to 56% over the variable-voltage scheme without slack-time re-allocation.

REFERENCES

• 1: C. F. Chiasserini , R. R. Rao, Pulsed battery discharge in communication devices, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.88-95, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313488]
• 2: Thomas L. Martin , Daniel P. Siewiorek, Balancing batteries, power, and performance: system issues in cpu speed-setting for mobile computing, 1999
• 3: http://www.batteryeng.com/lithium_ion_fs.htm
• 4: H. D. Linden, Handbook of Batteries, 2 nd ed., McGraw-Hill, New York, 1995.
• 5: 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]
• 6: Tajana Simunic , Luca Benini , Giovanni De Micheli, Energy-efficient design of battery-powered embedded systems, Proceedings of the 1999 international symposium on Low power electronics and design, p.212-217, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313928]
• 7: Qinru Qiu , Massoud Pedram, Dynamic power management based on continuous-time Markov decision processes, Proceedings of the 36th ACM/IEEE conference on Design automation, p.555-561, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309997]
• 8: Eui-Young Chung , Luca Benini , Giovanni De Micheli, Dynamic power management using adaptive learning tree, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.274-279, November 07-11, 1999, San Jose, California, United States
• 9: I. Hong, D. Kirovski, G. Qu, M. Potkonjak, and M. B. Srivastava, "Power optimization of variable-voltage core-based systems," IEEE Trans. Computer-Aided Design, vol. 18, no. 12, pp. 1702-1714, Dec. 1999.
• 10: 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]
• 11: Jiong Luo , Niraj K. Jha, Power-conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: 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]
• 13: Robert P. Dick , David L. Rhodes , Wayne Wolf, TGFF: task graphs for free, Proceedings of the 6th international workshop on Hardware/software codesign, p.97-101, March 15-18, 1998, Seattle, Washington, United States
• 14: http://www.transmeta.com/
• 15: E. L. Lawler and C. U. Martel, "Scheduling periodically occurring tasks on multiple processors," Information Processing Letters, vol. 7, pp. 9-12, Feb. 1981.
• 16: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 17: W. Ye , N. Vijaykrishnan , M. Kandemir , M. J. Irwin, The design and use of simplepower: a cycle-accurate energy estimation tool, Proceedings of the 37th conference on Design automation, p.340-345, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337436]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Experimentation, Measurement, Performance, Theory