臺灣博碩士論文加值系統

在IC製程步入奈米等級的今日，金屬導線間的寄生電容效應不可忽視，故本研究目的在於發展一快速、準確且能夠計算二維及三維複雜結構之金屬互連電容的隨機演算法。本研究發展之演算法為以方形隨機漫步為基礎，並結合了Chang,C.C研究團隊獨創的停留介面法(始於Lin,Y,B碩士論文)，以及Coz文獻中對於介面上漫步之機率的探討和Yu文獻中提出多層介面格林函數特徵化的方法用以處理多層介電質問題。在電場的計算上同樣使用了Chang,C.C研究團隊獨創的口字型積分法，利用解析的方式求取電場值，故具有高精準度的特色。
由於隨機漫步法始源於蒙地卡羅法，其隨機亂數獨立特性適合發展平行計算，故本研究將探討平行計算應用於寄生電容隨機算法的平行效益與誤差值的分析。
本研究在進行平行處理時，需考量取樣點的數目與漫步重複次數，在二維的計算上，由於取樣點數較少，大部份模擬時間皆花在隨機漫步的過程中，故將隨機漫步次數均分至各處理器即有良好平行效果，而在三維的計算中，由於取樣點數遠大於二維，故在電場積分的過程也得納入考慮，因此在三維處理上，有別於二維，需將大量佈置在高斯邊界上的取樣點做平行處理，而最終也獲得不錯的平行效益。並在具備八核心處理器的機器上實作，結果顯示，二維平行計算比循序版本快了7.7倍，三維則是快了7.1倍。

As IC processing enters into nano scaled, parasitic capacitance between the metal wires can not be ignored. Therefore, the purpose of this study is to develop a fast and accurate stochastic solver for extracting 2D and 3D multi metal-dielectric interconnect capacitances. The development of the algorithm in this study is based on the squared-shaped random walk, combing Stop at Interface method proposed by Chang,C.C. et al (originated from Lin,Y,B’s master thesis), the approach of the chance of walking on the interface from document Coz, and the method of numerical characterization of Green’s function method proposed in document Yu to solve the problem of multi-dielectric. The calculation of electric field also applies Chang, C.C research team’s square integral, using analytical solution to obtain electric field, hence the feature of high accuracy.
Due to the random walk originated from Monte Carlo , its independent feature
of the random number is fitting to develop parallel computing, therefore this study will be discussing the efficiency of the application of parallel computing to the solver for interconnect capacitances and analysis of its difference.
Results show when doing parallel computing in this study, it is required to take the number of sampling point and the repeated counts of random walk under consideration. On the calculation of 2D case, owing to less sampling point, most simulation time is spent in the process of random walk, therefore, equally splitting the number of times of random walk to each processor will result in fine parallel effect. As for the calculation of 3D case, because the number of sampling points is remotely greater than 2D case, the large amount of sampling point arranged on Gaussian boundary should be doing parallel computing, to finally result in fine parallel benefits also. According to the experiments on an 8-core CPU machine, results show that two-dimensional parallel computing version is faster than serial-computing version by 7.7 times, while three-dimensional parallel computing version is faster by 7.1 times.

致謝 i
中文摘要 ii
Abstract iii
目錄 v
圖目錄 viii
表目錄 xii
第一章 緒論 1
1.1前言 1
1.2文獻回顧 2
1.3研究目的 6
1.4全文概述 6
第二章 隨機漫步基礎理論 8
2.1隨機漫步基本概念 8
2.2隨機漫步概念證明 9
2.2.1準確度證明 9
2.2.2隨機性證明 11
2.2.3調和函數與唯一性原則 12
2.3布朗運動：近似連續的隨機步進方法 13
2.4布朗運動：定義與特性 15
第三章 理論背景與方法 16
3.1電容矩陣 16
3.2隨機漫步法 19
3.2.1 隨機漫步求解寄生電容 19
3.2.2 停留介面法 19
3.2.3 多層介面格林函數數值特徵化(方形無旋轉) 21
3.2.4 多層介面格林函數數值特徵化(方形旋轉) 26
3.3二維口字型積分 27
3.4三維電場口字型積分 33
3.5轉角電場計算 41
第四章 平行計算 45
4.1平行計算基本概念 45
4.2平行系統架構 46
4.2.1費林分類法 46
4.2.2共享式與分散式記憶體 47
4.3硬體與軟體 49
4.4 MPI平行函式庫 50
4.5平行演算法 51
4.6平行效率分析 53
第五章 二維模擬結果與討論 55
5.1 二維電容計算結果 55
5.1.1 雙導體單層介電質 56
5.1.2 雙導體雙層介電質 61
5.1.3 雙導體四層介電質 66
5.1.4 四導體四層介電質 71
5.2 模擬參數對電位值的影響 79
第六章 三維模擬結果與討論 80
6.1三維電容計算結果 80
6.1.1 雙導體雙層介電質 81
6.1.2 雙導體三層介電質 87
6.1.3 雙導體四層介電質 93
6.1.4 四導體四層介電質 99
6.2不同切割法之比較 105
第七章 結論與未來展望 107
7.1 結論 107
7.2 未來展望 107
參考文獻 109

[1]Y. L. Coz and R. Iverson, “A stochastic algorithm for high speed capacitance extraction in integrated circuits,” Solid-State Electronics, vol. 35, no. 7, pp. 1005 – 1012,1992.
[2]J. N. Jere and Y. L. L. Coz, “An improved floating-random-walk algorithm for solving the multi-dielectric Dirichlet problem,” IEEE Transactions on Microwave Theory and Techniques, vol. 41, pp. 325–329, Feb 1993.
[3]G. M. Royer, “Monte Carlo Procedure for Theory Problems Potential,” IEEE Transactions on Microwave Theory and Techniques, vol. 19, pp. 813–818, Oct 1971.
[4]R. B. Iverson and Y. L. L. Coz, “A floating random-walk algorithm for extracting electrical capacitance,” Mathematics and Computers in Simulation, vol. 55, no. 1– 3, pp. 59 – 66, 2001. The Second {IMACS} Seminar on Monte Carlo Methods.
[5]Y. B. Lin, “A New Stochastic Solver for Evaluating the Capacitaces of Complex-Structured Metal-Dielectrics,” Master’s thesis, National Taiwan University, 2015.
[6]M. P. Desai, An efficient capacitance extractor using floating random. Indian Insitute of Technology, 1998.
[7]H. Zhuang, W. Yu, G. Hu, Z. Liu, and Z. Ye, “Fast floating random walk algorithm formulti-dielectric capacitance extraction with numerical characterization of Green’s functions,” in 17th Asia and South Pacific Design Automation Conference, pp. 377–382, Jan 2012.
[8]W. Yu and X. Wang, Advanced field-solver techniques for RC extraction of integrated circuits. Springer, 2014.
[9]T. Y. Yang, “A New Stochastic Solver for Multi Metal-Dielectric Interconnect Capacitances Extraction,” Master’s thesis, National Taiwan University, 2016.
[10] J. M. Ren, “A New Stochastic Solver for Complex-Structured Metal-Dielectric Interconnect Capacitances Extraction,” Master’s thesis, National Taiwan University, 2017.
[11]S. H. Kolluru, “Preliminary investigations of a stochastic method to solve electorstatic and electrodynamic problems,” Master’s thesis, University of Massachusetts Amherst, 2008.
[12]J. D. Jackson, Classical electrodynamics. Wiley, 1999.
[13]R. Schlott, “A Monte Carlo method for the Dirichlet problem of dielectric wedges,” IEEE Transactions on Microwave Theory Techniques, vol. 36, pp. 724–730, apr 1988.
[14]Y. L. L. Coz and R. B. Iverson, “A high-speed capacitance extraction algorithm for multi-level VLSI interconnects,” in VLSI Multilevel Interconnection Conference, 1991, Proceedings., Eighth International IEEE, pp. 364–366, Jun 1991.
[15]Y. L. L. Coz and R. B. Iverson, “A high-speed multi-dielectric capacitance-extraction algorithm for MCM interconnects,” in Multi-Chip Module Conference, 1992. MCMC-92, Proceedings 1992 IEEE, pp. 86–89, Mar 1992.
[16]Y. L. Coz, H. Greub, and R. Iverson, “Performance of random-walk capacitance extractors for {IC} interconnects: A numerical study,” Solid-State Electronics, vol. 42, no. 4, pp. 581 – 588, 1998.
[17]R. Singh, FastCap: A Multipole Accelerated 3D Capacitance Extraction Program, pp. 34–47. Wiley-IEEE Press, 2002.
[18]S. H. Batterywala and M. P. Desai, “Variance reduction in Monte Carlo capacitance extraction,” in 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, pp. 85–90, Jan 2005.
[19]M. E. Muller, “Some Continuous Monte Carlo Methods for the Dirichlet Problem,” Ann. Math. Statist., vol. 27, pp. 569–589, 09 1956.
[20]T. A. El-Moselhy, I. M. Elfadel, and L. Daniel, “A hierarchical floating random walk algorithm for fabric-aware 3D capacitance extraction,” in 2009 IEEE/ACM International Conference on Computer-Aided Design - Digest of Technical Papers, pp. 752–758, Nov 2009.
[21]C. Zhang and W. Yu, “Efficient Space Management Techniques for Large-Scale Interconnect Capacitance Extraction With Floating Random Walks,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32,pp. 1633–1637, Oct 2013.
[22]W. Yu, H. Zhuang, C. Zhang, G. Hu, and Z. Liu, “RWCap: A Floating Random Walk Solver for 3-D Capacitance Extraction of Very-Large-Scale Integration Interconnects,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, pp. 353–366, March 2013.
[23]R. Burden and J. Faires, Numerical Analysis. Cengage Learning, 2010.
[24]P. Moin, Fundamentals of Engineering Numerical Analysis. Cambridge University Press, second ed., 2010. Cambridge Books Online.
[25]H. Haus and J. Melcher, Electromagnetic fields and energy. Prentice Hall, 1989.