平行計算應用於汲取複雜結構金屬之互連電容

Parallel Computing for Complex-Structured Metal-Dielectric Interconnected Capacitance Extraction

黃朝鍵(Chao-Jian Huang)

指導教授 ： 張建成

國立臺灣大學/工學院/應用力學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201803118

摘要

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

關鍵字

隨機漫步 ； 互連寄生電容 ； 停留介面法 ； 格林函數數值特徵化 ； 平行計算 ； MPI

並列摘要

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.

並列關鍵字

Random walk ； Interconnected parasitic capacitance ； stay at interface method ； Green’s function numerical characterization ； parallel computing ； message passing interface

參考文獻

[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.