Approximation algorithm for the temperature-aware scheduling problem

ABSTRACT

The paper addresses the problem of performance optimization for a set of periodic tasks with discrete voltage/frequency states under thermal constraints. We prove that the problem is NP-hard, and present a pseudo-polynomial optimal algorithm and a fully polynomial time approximation technique (FPTAS) for the problem. The FPTAS technique is able to generate solutions in polynomial time that are guaranteed to be within a designer specified quality bound (QB) (say within 1% of the optimal). We evaluate our techniques by experimentation with multimedia and synthetic benchmarks mapped on the 70nm CMOS technology processor. The experimental results demonstrate our techniques are able to match optimal solutions when QB is set at 5%, can generate solutions that are quite close to optimal (< 5%) even when QB is set at higher values (50%), and executes in few seconds (with QB > 25%) for large task sets with 120 nodes (while the optimal solution takes several hundred seconds). We also analyze the effect of different thermal parameters, such as the initial temperature, the final temperature and the thermal resistance.

REFERENCES

• 1: M. J. Ellsworth. Chip power density and module cooling technology projection for the current decade. In Proc. of ITHERM, 2004.
• 2: Semiconductor research corporation packing thrust strategic needs. http://www.src.org/fr/S200504packaging_needs.pdf, 2005.
• 3: Shekhar Borkar , Tanay Karnik , Siva Narendra , Jim Tschanz , Ali Keshavarzi , Vivek De, Parameter variations and impact on circuits and microarchitecture, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775920]
• 4: M. N. Touzelbaev. Thermal challenges for future microprocessors. Presentation at Semicon, 2005.
• 5: David Brooks , Margaret Martonosi, Dynamic Thermal Management for High-Performance Microprocessors, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.171, January 20-24, 2001
• 6: Michael Huang , Jose Renau , Seung-Moon Yoo , Josep Torrellas, A framework for dynamic energy efficiency and temperature management, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.202-213, December 2000, Monterey, California, United States [doi>10.1145/360128.360149]
• 7: Kevin Skadron , Tarek Abdelzaher , Mircea R. Stan, Control-Theoretic Techniques and Thermal-RC Modeling for Accurate and Localized Dynamic Thermal Management, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.17, February 02-06, 2002
• 8: Kevin Skadron, Hybrid Architectural Dynamic Thermal Management, Proceedings of the conference on Design, automation and test in Europe, p.10010, February 16-20, 2004
• 9: R. McGowen, Adaptive designs for power and thermal optimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.118-121, November 06-10, 2005, San Jose, CA
• 10: Jayanth Srinivasan , Sarita V. Adve, Predictive dynamic thermal management for multimedia applications, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782831]
• 11: Wonbok Lee , Kimish Patel , Massoud Pedram, Dynamic thermal management for MPEG-2 decoding, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165647]
• 12: N. Bansal and K. Pruhs. Speed scaling to manage temperature. In Proc. of STACS, pages 460--471, 2005.
• 13: Yongpan Liu , Huazhong Yang , Robert P. Dick , Hui Wang , Li Shang, Thermal vs Energy Optimization for DVFS-Enabled Processors in Embedded Systems, Proceedings of the 8th International Symposium on Quality Electronic Design, p.204-209, March 26-28, 2007 [doi>10.1109/ISQED.2007.158]
• 14: L. Yuan, S. Leventhal, and G. Qu. Temperature-aware leakage minimization technique for real-time systems. UMIACS Technical Report, University of Maryland, UMIACS-TR-2006-02, 2006.
• 15: Ravishankar Rao , Sarma Vrudhula , Chaitali Chakrabarti , Naehyuck Chang, An optimal analytical solution for processor speed control with thermal constraints, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165643]
• 16: Intel Corporation. Intel pentium d processor, intel pentium processor extreme edition, intel pentium 4 processor and intel core2#8482; duo extreme processor x6800 - thermal and mechanical design guidelines. 2007.
• 17: 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]
• 18: 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]
• 19: 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
• 20: Kevin Skadron , Mircea R. Stan , Wei Huang , Sivakumar Velusamy , Karthik Sankaranarayanan , David Tarjan, Temperature-aware microarchitecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 21: Fen Xie , Margaret Martonosi , Sharad Malik, Bounds on power savings using runtime dynamic voltage scaling: an exact algorithm and a linear-time heuristic approximation, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA [doi>10.1145/1077603.1077670]
• 22: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 23: D. H. Lorenz and D. Raz. A simple efficient approximation scheme for the restricted shortest path problem. Operations Research Letters, 28:213--219, 2001.
• 24: Guoliang Xue , Arunabha Sen , Weiyi Zhang , Jian Tang , Krishnaiya Thulasiraman, Finding a path subject to many additive QoS constraints, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.201-211, February 2007 [doi>10.1109/TNET.2006.890089]
• 25: R. Viswanath et al. Thermal performance challenges from silicon to systems. Intel Corporation, Tech. Rep., 2000.
• 26: Mediabench at:. http://euler.slu.edu/fritts/mediabench/.
• 27: SimpleScalar. http://www.simplescalar.com/.