Network flow-based power optimization under timing constraints in MSV-driven floorplanning

ABSTRACT

Power consumption has become a crucial problem in modern circuit design. Multiple Supply Voltage (MSV) design is introduced to provide higher flexibility in controlling the power and performance tradeoff. One important requirement of MSV design is that timing constraints of the circuit must be satisfied after voltage assignment of the cells. In this paper, we will show that the voltage assignment task on a given netlist can be formulated as a convex cost dual network flow problem and can be solved optimally in polynomial time using a cost-scaling algorithm when the delay choices of each module are continuous in the real or integer domain. We can make use of this approach to obtain a feasible voltage assignment solution in the general cases with power consumption approximating the minimum one. Furthermore, we will propose a framework to optimize power consumption and physical layout of a circuit simultaneously during the floorplanning stage, by embedding this cost-scaling solver into a simulated annealing based floorplanner. This is effective in practice due to the short running time of the solver. We compared our approach with the latest work [9] on the same problem, and the experimental results show that, using our framework, significant improvement on power saving (18% less power cost on average) can be achieved in much less running time (7X faster on average) for all the test cases, which confirms the effectiveness of our approach.

REFERENCES

• 1: Ravindra K. Ahuja , Dorit S. Hochbaum , James B. Orlin, Solving the Convex Cost Integer Dual Network Flow Problem, Management Science, v.49 n.7, p.950-964, July 2003 [doi>10.1287/mnsc.49.7.950.16384]
• 2: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 3: Royce L. S. Ching , Evangeline F. Y. Young , Kevin C. K. Leung , Chris Chu, Post-placement voltage island generation, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233632]
• 4: Andrew V. Goldberg, An efficient implementation of a scaling minimum-cost flow algorithm, Journal of Algorithms, v.22 n.1, p.1-29, Jan. 1997 [doi>10.1006/jagm.1995.0805]
• 5: A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.7-18, January 1987, New York, New York, United States [doi>10.1145/28395.28397]
• 6: Jingcao Hu , Youngsoo Shin , Nagu Dhanwada , Radu Marculescu, Architecting voltage islands in core-based system-on-a-chip designs, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013283]
• 7: W.-L. Hung , G. M. Link , Yuan Xie , N. Vijaykrishnan , N. Dhanwad , J. Conner, Temperature-Aware Voltage Islands Architecting in System-on-Chip Design, Proceedings of the 2005 International Conference on Computer Design, p.689-696, October 02-05, 2005 [doi>10.1109/ICCD.2005.103]
• 8: David E. Lackey , Paul S. Zuchowski , Thomas R. Bednar , Douglas W. Stout , Scott W. Gould , John M. Cohn, Managing power and performance for System-on-Chip designs using Voltage Islands, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.195-202, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774601]
• 9: Wan-Ping Lee , Hung-Yi Liu , Yao-Wen Chang, Voltage island aware floorplanning for power and timing optimization, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233579]
• 10: Wan-Ping Lee , Hung-Yi Liu , Yao-Wen Chang, An ILP algorithm for post-floorplanning voltage-island generation considering power-network planning, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 11: Bin Liu , Yici Cai , Qiang Zhou , Xianlong Hong, Power driven placement with layout aware supply voltage assignment for voltage island generation in Dual-Vdd designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118437]
• 12: Qiang Ma , Evangeline F. Y. Young, Voltage island-driven floorplanning, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 13: Wai-Kei Mak , Jr-Wei Chen, Voltage Island Generation under Performance Requirement for SoC Designs, Proceedings of the 2007 conference on Asia South Pacific design automation, p.798-803, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.358087]
• 14: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 15: Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan [doi>10.1145/370155.370523]
• 16: Kimiyoshi Usami , Mark Horowitz, Clustered voltage scaling technique for low-power design, Proceedings of the 1995 international symposium on Low power design, p.3-8, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224083]
• 17: Huaizhi Wu , I-Min Liu , M. D. F. Wong , Yusu Wang, Post-placement voltage island generation under performance requirement, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.309-316, November 06-10, 2005, San Jose, CA
• 18: Huaizhi Wu , Martin D. F. Wong , I-Min Liu, Timing-constrained and voltage-island-aware voltage assignment, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147023]