Postplacement voltage assignment under performance constraints

ABSTRACT

Multi-Vdd is an effective method to reduce both leakage and dynamic power. A key challenge in a multi-Vdd design is to control the complexity of the power-supply system and limit the demand for level shifters. This can be tackled by grouping cells of different supply voltages into a small number of voltage islands. Recently, an elegant algorithm was proposed for generating voltage islands that balance the power-versus-design-cost tradeoff under performance requirement, according to the placement proximity of the critical cells. One prerequisite of this algorithm is an initial voltage assignment at the standard-cell level that meets timing. In this article, we present a novel method to produce quality voltage assignment which not only meets timing but also forms good proximity of the critical cells to provide a smooth input to the aforementioned voltage island generation. Our algorithm is based on effective delay budgeting and efficient computation of physical proximity by Voronoi diagram. Our extensive experiments on real industrial designs show that our algorithm leads to 25%--75% improvement in the voltage island generation in terms of the number of voltage islands generated, with computation time only linear to design size.

REFERENCES

• 1: Synopsys. 2003. Liberty user guide, version 2003.12. Synopsys, Inc.
• 2: S. Ghiasi , E. Bozorgzadeh , S. Choudhuri , M. Sarrafzadeh, A unified theory of timing budget management, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.653-659, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382657]
• 3: Cadence. 2005. Cadence software manual: SoC Encounter GPS. http://www.cadence.com/products/digital_ic/soc_encounter/index.aspx.
• 4: Yici Cai , Bin Liu , Jin Shi , Qiang Zhou , Xianlong Hong, Power Delivery Aware Floorplanning for Voltage Island Designs, Proceedings of the 8th International Symposium on Quality Electronic Design, p.350-355, March 26-28, 2007 [doi>10.1109/ISQED.2007.121]
• 5: Cai, Y., Liu, B., Zhou, Q., and Hong, X. 2005. A thermal aware floorplanning algorithm supporting voltage islands for low power SoC design. In Proceedings of the PATMOS, 257--266.
• 6: Chunhong Chen , Ankur Srivastava , Majid Sarrafzadeh, On gate level power optimization using dual-supply voltages, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.5, p.616-629, October 2001 [doi>10.1109/92.953496]
• 7: 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]
• 8: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 9: Dwyer, R. A. 1987. A faster divide-and-conquer algorithm for constructing Delaunay triangulations. Algorithmica 2, 2, 137--151.
• 10: Fortune, S. 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 2, 153--174.
• 11: Gerousis, V. 2003. Modeling challenges for 90 nm and below. http://www.us.design-reuse.com/articles/article6326.html.
• 12: Green, P. and Sibson, R. 1978. Computing dirichlet tessellations in the plane. Computing Journal 21, 2, 168--173.
• 13: Guibas, L., Knuth, D., and Sharir, M. 1992. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7, 1, 381--413.
• 14: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 15: 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]
• 16: 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]
• 17: 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]
• 18: 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]
• 19: Hung-Yi Liu , Wan-Ping Lee , Yao-Wen Chang, A provably good approximation algorithm for power optimization using multiple supply voltages, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278698]
• 20: Nair, R., Berman, C. L., Hauge, P. S., and Yoffa, E. J. 1989. Generation of performance constraints for layout. IEEE Trans. Comput.-Aided Des. 8, 8, 860--874.
• 21: Ruchir Puri , Leon Stok , John Cohn , David Kung , David Pan , Dennis Sylvester , Ashish Srivastava , Sarvesh Kulkarni, Pushing ASIC performance in a power envelope, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776032]
• 22: 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]
• 23: 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
• 24: Wu, H., Wong, M. D., Liu, I.-M., and Wang, Y. 2007. Placement proximity based voltage island grouping under timing requirement. IEEE Trans. Comput.-Aided Des. 26, 7, 1256--1269.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design

Keywords:
Low power, Voronoi diagram, timing, voltage assignment