Optimality and improvement of dynamic voltage scaling algorithms for multimedia applications

ABSTRACT

The time-varying workload for multimedia applications poses a great challenge for the efficient performance of dynamic voltage scaling (DVS) algorithms. While many DVS algorithms have been proposed for real-time applications, there does not yet exist a systematic method for evaluating the optimality of such DVS algorithms. In this paper, we propose an offline linear programming (LP) method to determine the minimum energy consumption for processing multimedia tasks under stringent delay deadlines. Based on this lower bound, we evaluate the efficiency of various existing DVS algorithms. Furthermore, we modify the LP formulation to construct an online robust sequential linear programming DVS algorithm for real-time multimedia processing. Simulation results from decoding over a wide range of video sequences shows that on average, our online algorithm consumes less than 1% more energy than the optimal lower bound while dropping only 0.1% of all scheduled decoding jobs, while the existing best algorithm consumes roughly 3% more energy at the same miss rate.

REFERENCES

• 1: Luca Benini , Giovanni de Micheli, Dynamic Power Management: Design Techniques and CAD Tools, Kluwer Academic Publishers, Norwell, MA, 1998
• 2: D. Marculescu. On the use of microarchitecture-driven dynamic voltage scaling. Proceedings of the Workshop on Complexity-Effective Design, 2000.
• 3: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: Wanghong Yuan , Klara Nahrstedt , Sarita V. Adve , Douglas L. Jones , Robin H. Kravets, GRACE-1: Cross-Layer Adaptation for Multimedia Quality and Battery Energy, IEEE Transactions on Mobile Computing, v.5 n.7, p.799-815, July 2006 [doi>10.1109/TMC.2006.98]
• 5: Y. Zhu, and F. Mueller. Feedback EDF scheduling exploiting dynamic voltage scaling. Proceedings of the 11th international conference on Computer Architecture, 2004.
• 6: Kihwan Choi , Karthik Dantu , Wei-Chung Cheng , Massoud Pedram, Frame-based dynamic voltage and frequency scaling for a MPEG decoder, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.732-737, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774680]
• 7: Yifan Zhu , Frank Mueller, DVSleak: combining leakage reduction and voltage scaling in feedback EDF scheduling, Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 13-15, 2007, San Diego, California, USA
• 8: B. Foo, and M. van der Schaar. A queuing theoretic approach to processor power adaptation for video decoding systems. IEEE Trans. Signal Process, to appear.
• 9: Ravindra Jejurikar , Cristiano Pereira , Rajesh Gupta, Leakage aware dynamic voltage scaling for real-time embedded systems, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996650]
• 10: Steven M. Martin , Krisztian Flautner , Trevor Mudge , David Blaauw, Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.721-725, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774678]
• 11: Sushu Zhang , Karam S. Chatha, Approximation algorithm for the temperature-aware scheduling problem, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 12: J. Dunning, G. Garcia, J. Lundberg, and E. Nuckolls. An all-digital phase-locked loop with 50-cycle lock time suitable for high-performance microprocessors. IEEE Journal of Solid-State Circuits, Volume 30, Issue 4, Apr 1995 Page(s):412--422.
• 13: A. Adas. Traffic Models in Broadband Networks. IEEE Communications Magazine, Vol. 35, Issue 7, July 1997.
• 14: Z. Cao, B. Foo, L. He, and M. van der Schaar. Optimality and Improvement of Dynamic Voltage Scaling Algorithms for Multimedia Applications. Technical Report UCLA, 08--267, 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Performance

Keywords:
dynamic voltage scaling, multimedia, power management