臺灣博碩士論文加值系統

本研究目的為利用隨機漫步法發展一快速、準確且能計算二維及三維含有斜邊金屬與多層介電質互連電容的新隨機演算法。其中本研究是以方形隨機漫步法為基礎，並結合Chang,C.C研究團隊獨創的停留介面法(始於Lin,Y.B碩士論文)、Coz文獻中：在介面上時，往介面兩側漫步之機率及單層介電質方形隨機漫步以及Yu文獻中的多層介面格林函數數值特徵化，以處理含有斜邊導體及多層介電質結構之問題。而在電場計算方面同樣採用Chang,C.C研究團隊獨創的口字型積分法，將電位值利用解析的方式來求取電場，其具有高精準度的特色。
斜邊金屬導體的研究資料在文獻中十分少見，在本論文中，我們擴展和改進了所有上述算法，以計算具有斜邊之金屬和多層電介質的互連的電容。本文中拓展以及改進之處有以下幾點：
(i) 在取樣點布置方面，為因應因斜邊所造成的狹縫問題，因此採用沿著導體布置取樣點的方式。在導體邊上時，取樣點會與導體邊相互平行；而在導體轉角處時，則以頂點為圓心，取樣點以極座標的方式布置。如此高斯面才可完全包覆導體。 (ii) 由於隨機漫步時之最大正方形需與最接近之導體或介面相切，因此正方形通常需要做旋轉。因此本研究提出一新方法以計算正方形旋轉且有一界面通過正方形中心之機率分布。 (iii) 由於導體轉角處之取樣點是以極座標方式布置，因此無法使用原先之口字型積分法計算由取樣點構成的網格的中心點電場，因此導體轉角處之取樣點網格之中心點電場改以有限差分的方法計算。 (iv) 本研究也採用Cubic Spline的方法以提升演算法計算之速度。
除了開發適用於計算斜邊金屬導體的演算法之外，我們更是對斜邊結構計算時之取樣點間距、重複計算次數、取樣點與導體之距離以及最大步長限制…等參數做詳細的分析以及探討。
(1)由結果顯示，取樣點間距是決定電容值計算結果精準度最重要的參數，取樣點間距越小，電位值分布的情況就能計算的越詳細，藉此以提高電容計算的精準度。
(2) 重複計算次數則是決定電位值計算結果的準確度的重要參數。重複計算次數越高，電位值結果越準確，但在達到一定次數之後結果便會收。
(3) 依照高斯定律，高斯面之大小並不會影響電容的計算結果，但由於演算法的特性，其計算結果誤差會隨著取樣點與導體之距離增大而增加。
(4) 最大步長限制對於電容計算結果並沒有明確的正面或負面的影響，但對於演算法計算時間卻有著很大的影響，當最大步長限制到達一定大小時，計算時間便會劇烈增加。
(5) 本研究利用Cubic Spline內插法，將少數精準計算點之結果做內插，以達到減少取樣點計算量。其中一般導體都可以利用此方法將計算量減少到原本的1/8並且保有1%左右的誤差大小。
(6) 最後比較二維以及三維的模擬結果，其中二維電容值計算結果需要較高的重複計算次數才會收斂，三維則反之。
總結而論，本研究之演算法在計算二維及三維多層介電質-斜邊導體結構之計算結果已經有十分不錯的精準度，而未來則需增加薄膜計算的功能、程式碼的優化以及平行化等…加速計算的演算法，使本研究之演算法能更加完善。

The study is aimed to develop a new fast and accurate stochastic algorithm for extracting the electric capacitance of-non-rectangular metal-dielectric interconnect. The elements of the new stochastic solver for rectangular interconnects comprise (i) a known block algorithm for the Laplace equation without and with interface (Coz et al.), (Yu et al.) combined with (ii) a pausing algorithm at the Interface between dielectrics to definitely capture the effect of the interface (Chang et al.), and (iii) a new boundary treatment (Chang et al.) based on a Green’s function formulation (Yu et al.). In particular, a special technique of integration using the sampling potentials on the corner points of a boundary square is developed to calculate the electric field near a conductor with high precision. The total charge of each conductor is thus determined, and then all the self- and mutual capacitances of the interconnect can be evaluated.

There are few references in the literature to the current issue for oblique metal-dielectric interconnect. In this thesis, we extend and/or improve all the above algorithms/techniques to calculate the capacitances of interconnects that have oblique shapes of metal and multi-layers of dielectrics. The features of the extension and improvements are several: (i) At the sampling point arrangement, the sampling points are distributed parallel to the side of the conductor and distribute in the form of the polar coordinate by taking the vertex as the center of circle when the sampling points are close to the corner of the conductor. (ii) Because of the reason that the block of the random walk must be parallel to the nearest conductor or interface, so the blocks usually needs to be rotated. Here we develop a new way to calculate the probability distribution of the block when the block is rotated and the interface is passing through the block. (iii) Because the sampling points distribute in the form of the polar coordinate by taking the vertex as the center of circle when the sampling points are close to the corner of the conductor, we use Finite difference method to calculate the electric field of the corner of the conductor. (iv) We also use Cubic Spline to reduce the amount of calculation and accelerate the simulation.

We also do a detailed analysis and discussion of the parameters such as : Sampling point spacing, The number of repetition calculations, The distance between the sampling point and the conductor, and The restriction of maximum step size.
(1) The results show that the sampling point spacing is the most important parameter to determine the accuracy of the ‘capacitance calculation’. The smaller the sampling point spacing we used, the more detailed the description of the potential energy distribution is, and we can improve the accuracy of the capacitance calculation.
(2) The number of iterations is an important parameter to determine the accuracy of the potential energy’ calculation results. The higher the number of iterations, the more accurate the potential value is, but the results will converge when the number of iterations reach a certain number of times.
(3) According to Gaussian law, the size of the Gaussian surface does not affect the calculation results of capacitance. However, due to the characteristics of the algorithm, the error of calculation result will increase with the increased of the distance between the sampling point and the conductor.
(4) The restriction of maximum step size has no positive or negative effect on the capacitance calculation result, but has a significant effect on the computational time of the algorithm. When the size of maximum step reaches a certain size, the computational time of the algorithm will increase dramatically.
(5) This study also uses Cubic Spline interpolation, which uses a few results with high precision, to do the interpolation to reduce the amount of calculation. In general, the amount of calculation can be reduced to 1/8 and keep the error about 1%.
(6) We also compare the result of the two-dimensional and the result of the three-dimensional. The result of the two-dimensional capacitance calculation requires a higher number of iterations to converge, and the results of three-dimensional does not.
In summary, the result of problems, containing oblique edge conductors and multi-dielectric in 2D and 3D, calculated by the algorithm of this study have a good accuracy. To make the algorithm more perfect, we have to add to function of thin film computing, code optimization and parallel operation, which can accelerate the calculation of the algorithm, in the future.

目錄
口試委員會審定書
誌謝 1
中文摘要 2
英文摘要 4
圖目錄 9
表目錄 14
第一章緒論 17
1.1 前言 17
1.2 文獻回顧 18
1.3 研究目的 22
1.4 全文概敘 23
第二章理論背景與方法 24
2.1 電容矩陣 24
2.2 隨機漫步法 26
2.2.1 隨機漫步法求解寄生電容 26
2.2.2 停留介面法 27
2.2.3.1 多層介面格林函數數值特徵化(最大正方形無旋轉) 29
2.2.3.2 多層介面格林函數數值特徵化(最大正方形旋轉) 34
2.3 取樣點布置(高斯面) 37
2.4 二維電場口字型積分 40
2.5 三維電場口字型積分 45
2.6 轉角處電場計算 52
2.7 電容計算 53
第三章二維模擬結果與討論 54
3.1 電容計算結果 54
3.1.1 雙導體單層介電質 56
3.1.2 雙導體雙層介電質 59
3.1.3 雙導體三層介電質 62
3.1.4 雙導體四層介電質 65
3.1.5 四導體單層介電質 68
3.1.6 四導體四層介電質 75
3.2 重複計算次數對電位值的影響 82
3.3 最大步長對於計算結果之影響 85
3.4 轉角處取樣點數的多寡對於精準度的影響 93
3.5 Cubic Spline 96
3.6 複雜結構之模擬與計算結果 115
第四章三維模擬結果與討論 117
4.1 電容之模擬結果 117
4.1.1 雙導體單層介電質 118
4.1.2 雙導體四層介電質 121
4.2 電位值與重複計算次數之分析 124
4.3 二維與三維計算結果之比較 128
4.4 複雜結構之模擬結果 130
第五章結論與未來展望 132
5.1 結論 132
5.2 未來展望 134
參考文獻 135

圖目錄
圖1 Coz與Iverson隨機漫步示意圖[1] 19
圖2 Jere圓形隨機漫步示意圖[2] 19
圖3 C.C. Chang圓形隨機漫步示意圖[5] 21
圖4 電場積分示意圖[5] 21
圖5 多層介電質機率分布示意圖[8] 21
圖6計算流程結構示意圖 26
圖7基礎隨機漫步示意圖 29
圖8停留介面法示意圖 29
圖9有限差分示意圖[7] 30
圖10中心點與周圍八點示意圖 32
圖11二維最大正方形機率分布示意圖 33
圖12三維最大正方形機率分布示意圖 34
圖13停留介面最大正方形旋轉示意圖 34
圖14最大正方形旋轉後之機率分布示意圖 36
圖15電位值與電場位置示意圖 37
圖16取樣點分佈示意圖 38
圖17 三維取樣點分布示意圖 39
圖18拉普拉斯方程式定義域及邊界示意圖 40
圖19定義域座標平移示意圖 42
圖20 雙導體單一介電質結構 56
圖21 導體1之電位值分布 58
圖22 導體2之電位值分布 58
圖23 雙導體雙層介電質結構 59
圖24 導體1之電位值分布 61
圖25 導體2之電位值分布 61
圖26 雙導體三層介電質結構 62
圖27 導體1之電位值分布 64
圖28 導體2之電位值分布 64
圖29 雙導體四層介電質結構 65
圖30 導體1之電位值分布 67
圖31 導體2之電位值分布 67
圖32 四導體單層介電質結構 68
圖33 導體1之電位值分布 71
圖34 導體2之電位值分布 72
圖35 導體3之電位值分布 73
圖36 導體4之電位值分布 74
圖37 四導體四層電介質結構 75
圖38 導體1之電位值分布 78
圖39 導體2之電位值分布 79
圖40 導體3之電位值分布 80
圖41 導體4之電位值分布 81
圖42 取樣點間距0.0005；重複計算次數1000之電位值分佈 83
圖43 取樣點間距0.0005；重複計算次數1萬次之電位值分佈 83
圖44 取樣點間距0.0005；重複計算次數10萬次之電位值分佈 84
圖45 取樣點間距0.0005；重複計算次數20萬次之電位值分佈 84
圖46 結構3.1.1之最大步長限制與誤差 87
圖47 結構3.1.2之最大步長限制與誤差 88
圖48 結構3.1.4之最大步長限制與誤差 89
圖49 結構3.1.1不同取樣點間距配合不同重複計算次數下最大步長限制與計算時間之關係 90
圖50 結構3.1.2不同取樣點間距配合不同重複計算次數下最大步長限制與計算時間之關係 91
圖51 結構3.1.4不同取樣點間距配合不同重複計算次數下最大步長限制與計算時間之關係 92
圖52 結構3.1.1之取樣點與導體之距離對誤差的影響結果取樣點間距0.001 重複計算次數100k 94
圖53 結構3.1.2之取樣點與導體之距離對誤差的影響結果取樣點間距0.001 重複計算次數100k 94
圖54 結構3.1.3之取樣點與導體之距離對誤差的影響結果取樣點間距0.001 重複計算次數100k 95
圖55 結構3.1.4之取樣點與導體之距離對誤差的影響結果取樣點間距0.001 重複計算次數100k 95
圖56 結構3.1.1示意圖 97
圖57 結構3.1.4示意圖 97
圖58 結構3.1.1；取樣點數為1/2；M1C1之電位值 99
圖59 結構3.1.1；取樣點數為1/4；M1C1之電位值 99
圖60 結構3.1.1；取樣點數為1/8；M1C1之電位值 100
圖61 結構3.1.1；取樣點數為1/16；M1C1之電位值 100
圖62 結構3.1.1；取樣點數為1/20；M1C1之電位值 101
圖63 結構3.1.1；取樣點數為1/2；M1C2之電位值 101
圖64 結構3.1.1；取樣點數為1/4；M1C2之電位值 102
圖65 結構3.1.1；取樣點數為1/8；M1C2之電位值 102
圖66 結構3.1.1；取樣點數為1/16；M1C2之電位值 103
圖67 結構3.1.1；取樣點數為1/20；M1C2之電位值 103
圖68 結構3.1.1；取樣點數為1/2；M1C3之電位值 104
圖69 結構3.1.1；取樣點數為1/4；M1C3之電位值 104
圖70 結構3.1.1；取樣點數為1/8；M1C3之電位值 105
圖71 結構3.1.1；取樣點數為1/16；M1C3之電位值 105
圖72 結構3.1.1；取樣點數為1/20；M1C3之電位值 106
圖73 結構3.1.1之Cubic Spline取樣點數量與誤差之關係 106
圖74 結構3.1.4；取樣點數為1/2；M1C1之電位值 107
圖75 結構3.1.4；取樣點數為1/4；M1C1之電位值 107
圖76 結構3.1.4；取樣點數為1/8；M1C1之電位值 108
圖77 結構3.1.4；取樣點數為1/16；M1C1之電位值 108
圖78 結構3.1.4；取樣點數為1/20；M1C1之電位值 109
圖79 結構3.1.4；取樣點數為1/2；M1C2之電位值 109
圖80 結構3.1.4；取樣點數為1/4；M1C2之電位值 110
圖81 結構3.1.4；取樣點數為1/8；M1C2之電位值 110
圖82 結構3.1.4；取樣點數為1/16；M1C2之電位值 111
圖83 結構3.1.4；取樣點數為1/20；M1C2之電位值 111
圖84 結構3.1.4；取樣點數為1/2；M1C3之電位值 112
圖85 結構3.1.4；取樣點數為1/4；M1C3之電位值 112
圖86 結構3.1.4；取樣點數為1/8；M1C3之電位值 113
圖87 結構3.1.4；取樣點數為1/16；M1C3之電位值 113
圖88 結構3.1.4；取樣點數為1/20；M1C3之電位值 114
圖89 結構3.1.4之Cubic Spline取樣點數量與誤差之關係 114
圖90 複雜結構構型示意圖 115
圖91 導體3之電位值分布 116
圖92 三維雙導體單層介電質結構切面；延伸長度為1 118
圖93 導體1之電位值分佈 120
圖94 三維雙導體四層介電質結構切面；延伸長度為1 121
圖95 導體1之電位值分佈 123
圖96 導體1在取樣點間距0.001 重複計算次數100下之電位值分布 125
圖97 導體1在取樣點間距0.001 重複計算次數500下之電位值分布 126
圖98 導體1在取樣點間距0.001 重複計算次數1000下之電位值分布 127
圖99 分析重複計算次數之結構 128
圖100 二維之電位值分佈重複計算次數：10萬 129
圖101 三維之電位值分佈重複計算次數：1000 129
圖102 複雜結構構型示意圖 130
圖103 複雜結構構型示意圖 130
圖104 平板導體之電位值分布 131

表目錄
表1 電容參考值 56
表2 電容計算結果取樣點間距0.0005 重複計算次數100k 56
表3 電容值誤差表取樣點間距0.0005 重複計算次數100k 56
表4 取樣點間距與重複計算次數對C11誤差影響 57
表5 取樣點間距與重複計算次數對C12誤差影響 57
表6 取樣點間距與重複計算次數對C13誤差的影響 57
表7 電容參考值 59
表8 電容計算結果取樣點間距0.0005 重複計算次數100k 59
表9 電容值誤差表取樣點間距0.0005 重複計算次數100k 59
表10 取樣點間距與重複計算次數對C11誤差影響 60
表11 取樣點間距與重複計算次數對C12誤差影響 60
表12 取樣點間距與重複計算次數對C13誤差影響 60
表13 電容參考值 62
表14 電容計算結果取樣點間距0.0005 重複計算次數100k 62
表15 電容值誤差表取樣點間距0.0005 重複計算次數100k 62
表16 取樣點間距與重複計算次數對C11誤差影響 63
表17 取樣點間距與重複計算次數對C12誤差影響 63
表18 取樣點間距與重複計算次數對C13誤差影響 63
表19 電容參考值 65
表20 電容計算結果取樣點間距0.0005 重複計算次數100k 65
表21 電容值誤差表取樣點間距0.0005 重複計算次數100k 65
表22 取樣點間距與重複計算次數對C11誤差影響 66
表23 取樣點間距與重複計算次數對C12誤差影響 66
表24 取樣點間距與重複計算次數對C13誤差影響 66
表25 電容參考值 68
表26 電容計算結果取樣點間距0.0005 重複計算次數100k 68
表27 電容值誤差表取樣點間距0.0005 重複計算次數100k 68
表28 取樣點間距與重複計算次數對C11誤差影響 69
表29 取樣點間距與重複計算次數對C12誤差影響 69
表30 取樣點間距與重複計算次數對C13誤差影響 69
表31 取樣點間距與重複計算次數對C14誤差影響 70
表32 取樣點間距與重複計算次數對C15誤差影響 70
表33 電容參考值 75
表34 電容計算結果取樣點間距0.0005 重複計算次數100k 75
表35 電容值誤差表取樣點間距0.0005 重複計算次數100k 75
表36 取樣點間距與重複計算次數對C11誤差影響 76
表37 取樣點間距與重複計算次數對C12誤差影響 76
表38 取樣點間距與重複計算次數對C13誤差影響 76
表39 取樣點間距與重複計算次數對C14誤差影響 77
表40 取樣點間距與重複計算次數對C15誤差影響 77
表41 圖90結構之計算電容值 115
表42 電容參考值 118
表43 電容計算結果取樣點間距0.001 重複計算次數1000 118
表44 電容值誤差表取樣點間距0.001 重複計算次數1000 118
表45 取樣點間距與重複計算次數對C11誤差影響 119
表46 取樣點間距與重複計算次數對C12誤差影響 119
表47 取樣點間距與重複計算次數對C13誤差影響 119
表48 電容參考值 121
表49 電容計算結果取樣點間距0.001 重複計算次數1000 121
表50 電容值誤差表取樣點間距0.001 重複計算次數1000 121
表51 取樣點間距與重複計算次數對C11誤差影響 122
表52 取樣點間距與重複計算次數對C12誤差影響 122
表53 取樣點間距與重複計算次數對C13誤差影響 122
表54 二、三維之參數建議 133

[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]M. E. Muller, “Some Continuous Monte Carlo Methods for the Dirichlet Problem,” Ann. Math. Statist., vol. 27, pp. 569–589, 09 1956.
[11]J. D. Jackson, Classical electrodynamics. Wiley, 1999.
[12]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.
[13]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.
[14]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.
[15]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.
[16]R. Singh, FastCap: A Multipole Accelerated 3D Capacitance Extraction Program, pp. 34–47. Wiley-IEEE Press, 2002.
[17]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.
[18]S. H. Kolluru, “Preliminary investigations of a stochastic method to solve electorstatic and electrodynamic problems,” Master’s thesis, University of Massachusetts Amherst, 2008.
[19]T. A. El-Moselhy, I. M. Elfadel, and L. Daniel, “A capacitance solver for incremental variation-aware extraction,” in 2008 IEEE/ACM International Conference on Computer-Aided Design, pp. 662–669, Nov 2008.
[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.