Fast min-cost buffer insertion under process variations

ABSTRACT

Process variation has become a critical problem in modern VLSI fabrication. In the presence of process variation, buffer insertion problem under performance constraints becomes more difficult since the solution space expands greatly. We propose efficient dynamic programming approaches to handle the min-cost buffer insertion under process variations. Our approaches handle delay constraints and slew constraints, in trees and in combinational circuits. The experimental results demonstrate that in general, process variations have great impact on slew-constrained buffering, but much less impact on delay-constrained buffering, especially for small nets. Our approaches have less than 9% runtime overhead on average compared with a single pass of deterministic buffering for delay constrained buffering, and get 56% yield improvement and 11.8% buffer area reduction, on average, for slew constrained buffering.

REFERENCES

• 1: Kanak Agarwal , Dennis Sylvester , David Blaauw , Frank Liu , Sani Nassif , Sarma Vrudhula, Variational delay metrics for interconnect timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996675]
• 2: Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
• 3: Charles J. Alpert , Miloš Hrkić , Stephen T. Quay, A fast algorithm for identifying good buffer insertion candidate locations, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981076]
• 4: H. B. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley, 1990.
• 5: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 6: Ruiming Chen , Hai Zhou, A Flexible Data Structure for Efficient Buffer Insertion, Proceedings of the IEEE International Conference on Computer Design, p.216-221, October 11-13, 2004
• 7: Ruiming Chen , Hai Zhou, Efficient algorithms for buffer insertion in general circuits based on network flow, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.322-326, November 06-10, 2005, San Jose, CA
• 8: Ruiming Chen , Hai Zhou, Fast Buffer Insertion for Yield Optimization Under Process Variations, Proceedings of the 2007 conference on Asia South Pacific design automation, p.19-24, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.357786]
• 9: K. Chopra , S. Shah , A. Srivastava , D. Blaauw , D. Sylvester, Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1023-1028, November 06-10, 2005, San Jose, CA
• 10: Azadeh Davoodi , Ankur Srivastava, Variability-Driven Buffer Insertion Considering Correlations, Proceedings of the 2005 International Conference on Computer Design, p.425-430, October 02-05, 2005 [doi>10.1109/ICCD.2005.114]
• 11: Liang Deng , M. D. F. Wong, Buffer insertion under process variations for delay minimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.317-321, November 06-10, 2005, San Jose, CA
• 12: M. R. Guthaus , N. Venkateswarant , C. Visweswariaht , V. Zolotov, Gate sizing using incremental parameterized statistical timing analysis, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1029-1036, November 06-10, 2005, San Jose, CA
• 13: Lei He , Andrew Kahng , King Ho Tam , Jinjun Xiong, Simultaneous buffer insertion and wire sizing considering systematic CMP variation and random leff variation, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055154]
• 14: Shiyan Hu , Charles J. Alpert , Jiang Hu , Shrirang Karandikar , Zhuo Li , Weiping Shi , C. N. Sze, Fast algorithms for slew constrained minimum cost buffering, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146990]
• 15: Frank Huebbers , Ali Dasdan , Yehea Ismail, Computation of accurate interconnect process parameter values for performance corners under process variations, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147110]
• 16: Chandramouli V. Kashyap , Charles J. Alpert , Frank Liu , Anirudh Devgan, Closed form expressions for extending step delay and slew metrics to ramp inputs, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640009]
• 17: Vishal Khandelwal , Azadeh Davoodi , Akash Nanavati , Ankur Srivastava, A Probabilistic Approach to Buffer Insertion, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.560, November 09-13, 2003 [doi>10.1109/ICCAD.2003.16]
• 18: W. J. Krzanowski, Principles of multivariate analysis: a user's perspective, Oxford University Press, Inc., New York, NY, 1988
• 19: J. Lillis, C. K. Cheng, and T. T. Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model. IEEE Journal of Solid-State Circuits, 31:437--447, 1996.
• 20: Peter J. Osler, Placement driven synthesis case studies on two sets of two chips: hierarchical and flat, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981107]
• 21: Yuantao Peng , Xun Liu, Low-power repeater insertion with both delay and slew rate constraints, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146989]
• 22: Prashant Saxena , Noel Menezes , Pasquale Cocchini , Desmond A. Kirkpatrick, The scaling challenge: can correct-by-construction design help?, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640014]
• 23: W. Shi and Z. Li. A fast algorithm for optimal buffer insertion. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 24(6):879--891, 2005.
• 24: Weiping Shi , Zhuo Li , Charles J. Alpert, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 25: D. Sinha , N. V. Shenoy , Hai Zhou, Statistical gate sizing for timing yield optimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1037-1041, November 06-10, 2005, San Jose, CA
• 26: C. N. Sze , Charles J. Alpert , Jiang Hu , Weiping Shi, Path based buffer insertion, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065711]
• 27: L. P. P. P. van Ginneken. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In ISCAS, pages 865--868, 1990.
• 28: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 29: Mandar Waghmode , Zhuo Li , Weiping Shi, Buffer insertion in large circuits with constructive solution search techniques, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146988]
• 30: Jinjun Xiong , Lei He, Fast buffer insertion considering process variations, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123033]
• 31: Jinjun Xiong , Kingho Tam , Lei He, Buffer Insertion Considering Process Variation, Proceedings of the conference on Design, Automation and Test in Europe, p.970-975, March 07-11, 2005 [doi>10.1109/DATE.2005.85]
• 32: Hai Zhou , D. F. Wong , I-Min Liu , Adnan Aziz, Simultaneous routing and buffer insertion with restrictions on buffer locations, Proceedings of the 36th ACM/IEEE conference on Design automation, p.96-99, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309885]

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Performance, Reliability

Keywords:
buffer insertion, statistical optimization, variation