當量產電路顯示出大量的製程變異迫使先進製程面臨了比以往更嚴厲的挑戰，因此製程變異的考量對於保證高參數時序良率更顯重要。而在IC設計階段中，快速估計安插緩衝器後之連線延遲可輔助在區塊擺置或公域繞線時進行更精準且快速的線路擺放及時序分析。在這篇論文中，我們推導出具製程變異及緩衝器安插障礙影響考量之連線延遲估算其一次近似標準式。我們的經驗顯示：一個現存不具製程變異考量的方法若採用最壞情況（平均值加3倍標準差）作延遲估計，結果會顯得過份悲觀並因此導致不必要的設計反轉。實驗結果也顯示我們的估計方法平均誤差為4%，卻能比一個目前最先進的實際安插緩衝器方法快達149倍。

Advanced process technologies impose more significant challenges especially when manufactured circuits exhibit substantial process variations. Consideration of process variations becomes critical to ensure high parametric timing yield. During the design stage, fast estimation of the achievable buffered delay can navigate more accurate and efficient wire planning and timing analysis in floorplanning or global routing. In this thesis, we derived approximated first-order canonical forms for buffered delay estimation which considers the effect of process variations and the presence of buffer blockages. We empirically show that an existing deterministic delay estimation using 3-sigma values will be over-pessimistic and thus result in unnecessary design rollback. The experimental results also show that our method can estimate buffered delay with 4% average error but achieve up to 149 times speedup when compared to a state-of-the-art statistical buffer insertion method.

Abstract (in Chinese) iv
Abstract v
Contents vi
List of Figures vii
List of Tables viii

Chapter 1. Introduction 1
Chapter 2. Preliminaries 4
A. Delay Model 4
B. Process Variation Modeling 4
C. Problem Formulation 5
D. Useful Properties in Statistics 5
Chapter 3. Methodology 7
A. Deterministic Buffered Delay Estimation (DBDE) 7
B. Statistical Buffered Delay Estimaton (SBDE) 12
Chapter 4. Experimental Results 17
Chapter 5. Conclusion 22

Appendix A. Detailed Derivation of the First and Second Momments 23
Appendix B. Individual Experimental Results of Randomly Generated Nets 24
References 32

[1] P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick, “Repeater scaling and its impact on CAD,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, no. 4, pp. 451-463, Apr. 2004.
[2] C. J. Alpert, J. Hu, S. S. Sapatnekar, and C. N. Sze, “Accurate estimation of global buffer delay within a floorplan,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 6, pp. 1140-1146, Jun. 2006.
[3] R. H. J. M. Otten, “Global wires harmful?” in Proc. Intl. Symp. on Physical Design, pp. 104-109, 1998.
[4] L. P. P. P. van Ginneken, “Buffer placement in distributed RC-Tree network for minimal Elmore delay,” in Proc. Intl. Symp. on Circuits and Systems, pp. 865-868, 1990.
[5] C. Visweswariah, “Death, taxes and failing chips,” in Proc. Design Automation Conf., pp. 343-347, 2003.
[6] H. Chang, and S. Sapatnekar, “Statistical timing analysis considering spatial correlations using a single PERT-like traversal,” in Proc. Intl. Conf. on Computer-Aided Design, pp. 621-625, 2003.
[7] C. Visweswariah, K. Ravindran, K. Kalafala, S. G. Walker, and S. Narayan, “Frist-order incremental block-based statistical timing analysis,” in Proc. Design Automation Conf., pp. 331-336, 2004.
[8] M. R. Guthaus, N. Venkateswaran, C. Visweswariah, and V. Zolotov, “Gate sizing using incremental parameterized statistical timing analysis,” in Proc. Intl. Conf. on Computer-Aided Design, pp. 1029-1036, 2005.
[9] M. Mani, A. Devgan, and M. Orshansky, “An efficient algorithm for statistical minimization of total power under timing yield constraints,” in Proc. Design Automation Conf., pp. 309-314, 2005.
[10] V. Khandelwal, A. Davoodi, A. Nanarati, and A. Srivastava, “A probabilistic approach to buffer insertion,” in Proc. Intl. Conf. on Computer-Aided Design, pp. 560-567, 2003.
[11] L. He, A. B. Kahng, K. Tam, and J. Xiong, “Simultaneous buffer insertion and wire sizing considering systematic CMP variation and random Leff variation,” in Proc. Intl. Symp. on Physical Design, pp. 78-85, 2005.
[12] A. Davoodi, and A. Srivastava, “Variability-driven buffer insertion considering correlations,” in Proc. Intl. Conf. on Computer Design, pp. 425-430, 2005.
[13] L. Deng, and M. D. F. Wong, “Buffer insertion under process variations for delay minimization,” in Proc. Intl. Conf. on Computer-Aided Design, pp. 317-321, 2005.
[14] J. Xiung, K. Tam, and L. He, “Buffer insertion considering process variation,” in Proc. Conf. on Design Automation and Test in Europe, pp. 970-975, 2005.
[15] J. Xiung, and L. He, “Fast buffer insertion considering process variations,” in Proc. Intl. Symp. on Physical Design, pp. 128-135, 2006.
[16] L. Zhang, W. Chen, Y. Hu, J. A. Gubner, and C. C.-P. Chen, “Correlation-preserved non-Gaussian statistical timing analysis with quadratic timing model,” in Proc. Design Automation Conf., pp. 83-88, 2005.
[17] J. Jess, “DFM in synthesis,” research report, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY 10598, Dec. 2001.
[18] J. A. G. Jess, K. Kalafala, S. R. Naidu, R. H. J. M. Otten, and C. Visweswariah, “Statistical timing for parametric yield prediction of digital integrated circuits,” in Proc. Design Automation Conf., pp. 932-937, 2003.
[19] E. Kreyszig, Advanced engineering mathematics, 8th edition, Peter Janzow, 1999.
[20] M. Cain, “The moment-generating function of the minimum of bivariate normal random variables,” in The American Statistician, vol. 48, May 1994.
[21] C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar, and A. J. Sullivan, “Buffered Steiner trees for difficult instances,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 1, pp. 3-14, Jan. 2002.