Dynamic power management of complex systems using generalized stochastic Petri nets

ABSTRACT

In this paper, we introduce a new technique for modeling and solving the dynamic power management (DPM) problem for systems with complex behavioral characteristics such as concurrency, synchronization, mutual exclusion and conflict. We model a power-managed distributed computing system as a controllable Generalized Stochastic Petri Net (GSPN) with cost. The obtained GSPN model is automatically converted to an equivalent continuous-time Markov decision process. Given the delay constraints, the optimal power management policy for system components as well as the optimal dispatch policy for requests are calculated by solving a linear programming problem based on the Markov decision process. Experimental results show that the proposed technique can achieve more than 20% power saving compared to other existing DPM techniques.

REFERENCES

• 1: Anantha P. Chandrakasan , Robert W. Brodersen, Low Power Digital CMOS Design, Kluwer Academic Publishers, Norwell, MA, 1995
• 2: M. Horowitz, T. Indermaur, and R. Gonzalez, "Low-Power Digital Design", IEEE Symposium on Low Power Electronics, pp.8-11, 1994.
• 3: A. Chandrakasan , V. Gutnik , T. Xanthopoulos, Data driven signal processing: an approach for energy efficient computing, Proceedings of the 1996 international symposium on Low power electronics and design, p.347-352, August 12-14, 1996, Monterey, California, United States
• 4: Massoud Pedram , Jan M. Rabaey, Power Aware Design Methodologies, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: Luca Benini , Giovanni de Micheli, Dynamic Power Management: Design Techniques and CAD Tools, Kluwer Academic Publishers, Norwell, MA, 1998
• 6: Mani B. Srivastava , Anantha P. Chandrakasan , R. W. Brodersen, Predictive system shutdown and other architectural techniques for energy efficient programmable computation, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.1, p.42-55, March 1996 [doi>10.1109/92.486080]
• 7: Chi-Hong Hwang , Allen C.-H. Wu, A predictive system shutdown method for energy saving of event-driven computation, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.28-32, November 09-13, 1997, San Jose, California, United States
• 8: G. A. Paleologo , L. Benini , A. Bogliolo , G. De Micheli, Policy optimization for dynamic power management, Proceedings of the 35th annual conference on Design automation, p.182-187, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277094]
• 9: 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]
• 10: Qinru Qiu , Qing Wu , Massoud Pedram, Stochastic modeling of a power-managed system: construction and optimization, Proceedings of the 1999 international symposium on Low power electronics and design, p.194-199, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313923]
• 11: Luca Benini , Alessandro Bogliolo , Stefano Cavallucci , Bruno Riccó, Monitoring system activity for OS-directed dynamic power management, Proceedings of the 1998 international symposium on Low power electronics and design, p.185-190, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280887]
• 12: Eui-Young Chung , Luca Benini , Alessandro Bogiolo , Giovanni De Micheli, Dynamic power management for non-stationary service requests, Proceedings of the conference on Design, automation and test in Europe, p.18-es, January 1999, Munich, Germany [doi>10.1145/307418.307456]
• 13: Luca Benini , Robin Hodgson , Polly Siegel, System-level power estimation and optimization, Proceedings of the 1998 international symposium on Low power electronics and design, p.173-178, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280881]
• 14: U. Narayan Bhat, "Elements Of Applied Stochastic Processes", John Wiley & Sons, Inc. 1984
• 15: B. Miller, "Finite State Continuous Time Markov Decision Processes With an Finite Planning Horizon." SlAM J. Control, Vol. 5, No. 2, pp. 266-281, 1968.
• 16: B. Miller, "Finite State Continuous Time Markov Decision Processes With an Infinite Planning Horizon". J. Of Mathematical Analysis and Applications, No. 22, pp. 552-569, 1968.
• 17: R.A.Howard, Dynamic Programming and Markov Processes, Wiley, New York, 1960
• 18: D. P. Heyman, M. J. Sobel, Stochastic Models in Operations Research, McGraw-Hill Book Company, 1982
• 19: Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor S. Trivedi, Queueing networks and Markov chains: modeling and performance evaluation with computer science applications, Wiley-Interscience, New York, NY, 1998
• 20: L. Kleinrock, Queueing Systems. Volume I: Theory, Wiley- Interscience, New York, 1981.
• 21: J. F. Shapiro, Mathematical Programming: Structures and Algorithms, John Wiley & Sons, Inc, 1979.
• 22: D. Kartson , G. Balbo , S. Donatelli , G. Franceschinis , Giuseppe Conte, Modelling with Generalized Stochastic Petri Nets, John Wiley & Sons, Inc., New York, NY, 1994
• 23: UltraSAN User's Manual, Version 3.0, Center for Reliable and high- Performance Computing, Coordinated Science Laboratory, University of Illinois.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Petri nets

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Design, Performance, Theory