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. K. Agarwal, D. Sylvester, D. Blaauw, F. Liu, S. Nassif, and S. Vrudhula. Variational delay metrics for interconnect timing analysis. In DAC, pages 381--384, 2004.
2. C. J. Alpert and A. Devgan. Wire segmenting for improved buffer insertion. In DAC, pages 588--593, 1997.
3. C. J. Alpert, M. Hrkic, and S. T. Quay. A fast algorithm for identifying good buffer insertion candidate locations. In ISPD, pages 47--52, 2004.
4. H. B. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley, 1990.
5. H. Chang and S. S. Sapatnekar. Statistical timing analysis considering spatial correlations using a single pert-like traversal. In ICCAD, pages 621--625, 2003.
6. R. Chen and H. Zhou. A flexible data structure for efficient buffer insertion. In ICCD, pages 216--221, 2004.
7. R. Chen and H. Zhou. Efficient algorithms for buffer insertion in general circuits based on network flow. In ICCAD, pages 322--326, 2005.
8. R. Chen and H. Zhou. Fast buffer insertion for yield optimization under process variations. In ASP-DAG, 2007.
9. K. Chopra, S. Shah, A. Srivastava, D. Blaauw, and D. Sylvester. Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation. In ICCAD, pages 1023--1028, 2005.
10. A. Davoodi and A. Srivastava. Variability-driven buffer insertion considering correlations. In ICCD, 2005.
11. L. Deng and M. D. Wong. Buffer insertion under process variations for delay minimization. In ICCAD, pages 317--321, 2005.
12. M. Guthaus, N. Venkateswaran, C. Visweswariah, and Z. Zolotov. Gate sizing using incremental parameterized statistical timing analysis. In ICCAD, pages 1029--1036, 2005.
13. L. He, A. Kahng, K. H. Tam, and J. Xiong. Simultaneous buffer insertion and wire sizing considering systematic CMP variation and random Leff variation. In ISPD, pages 78--85, 2005.
14. S. Hu, C. J. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi, and C. N. Sze. Fast algorithms for slew constrained minimum cost buffering. In DAC, pages 308--313, 2006.
15. F. Huebbers, A. Dasdan, and Y. Ismail. Computation of accurate interconnect process parameter values for performance corners under process variations. In DAC, pages 797--800, 2006.
16. C. Kashyap, C. Alpert, F. Liu, and A. Devgan. Closed form expressions for extending step delay and slew metrics to ramp inputs. In ISPD, pages 24--31, 2003.
17. V. Khandelwal, A. Davoodi, A. Nanavati, and A. Srivastava. A probabilistic approach to buffer insertion. In ICCAD, pages 560--567, 2003.
18. W. J. Krzanowski. Principles of Multivariate Analysis. Oxford University Press, 2000.
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. P. J. Osler. Placement driven synthesis case studies on two sets of two chips: Hierarchical and flat. In ISPD, pages 190--197, 2004.
21. Y. Peng and X. Liu. Low-power repeater insertion with both delay and slew rate constraints. In DAC, pages 303--307, 2006.
22. P. Saxena, N. Menezes, P. Cocchini, and Desmond A. Kirkpatrick. The scaling challenge: Can correct-by-construction design help? In ISPD, pages 51--58, 2003.
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. W. Shi, Z. Li, and C. J. Alpert. Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost. In Proc. Asia and South Pacific Design Automation Conference, pages 609--614, 2004.
25. D. Sinha, N. Shenoy, and H. Zhou. Statistical gate sizing for timing yield optimization. In ICCAD, pages 1037--1041, 2005.
26. C. N. Sze, C. J. Alpert, J. Hu, and W. Shi. Path based buffer insertion. In DAC, pages 509--514, 2005.
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, and S. Narayan. First-order incremental block-based statistical timing analysis. In DAC, pages 331--336, 2004.
29. M. Waghmode, Z. Li, and W. Shi. Buffer insertion in large circuits with constructive solution search techniques. In DAC, pages 296--301, 2006.
30. J. Xiong and L. He. Fast buffer insertion considering process variations. In ISPD, 2006.
31. J. Xiong, K. Tam, and L. He. Buffer insertion considering process variation. In DATE, 2005.
32. H. Zhou, D. F. Wong, I-Min Liu, and A. Aziz. Simultaneous routing and buffer insertion with restrictions on buffer locations. DAC, 1999.

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Engineering

• Hardware

  • Electronic design automation

    • Physical design (EDA)