TY - JOUR
T1 - A Markov chain based hierarchical algorithm for fabric-aware capacitance extraction
AU - El-Moselhy, Tarek
AU - Elfadel, Ibrahim Abe M.
AU - Daniel, Luca
N1 - Funding Information:
Manuscript received January 19, 2010; revised October 27, 2010; accepted October 28, 2010. Date of publication December 17, 2010; date of current version January 07, 2011. This work was supported by Mentor Graphics, AMD, IBM, the Semiconductor Corporations and the Interconnect Focus Center, one of five research centers funded under the Focus Center Research Program, a DARPA and Semiconductor Research Corporation program. This work was recommended for publication by Associate Editor D. Jiao upon evaluation of the reviewers comments.
PY - 2010/11
Y1 - 2010/11
N2 - In this paper, we propose a hierarchical algorithm to compute the 3-D capacitances of a large number of topologically different layout configurations that are all assembled from the same basic layout motifs. Our algorithm uses the boundary element method in order to compute a Markov transition matrix (MTM) for each motif. The individual motifs are connected together by building a large Markov chain. Such Markov chain can be simulated extremely efficiently using Monte Carlo simulations (e.g., random walks). The main practical advantage of the proposed algorithm is its ability to extract the capacitance of a large number of layout configurations in a complexity that is basically independent of the number of configurations. For instance, in a large 3-D layout example, the capacitance calculation of 1000 different configurations assembled from the same motifs is accomplished in the time required to solve independently two configurations, i.e., a 500 × speedup.
AB - In this paper, we propose a hierarchical algorithm to compute the 3-D capacitances of a large number of topologically different layout configurations that are all assembled from the same basic layout motifs. Our algorithm uses the boundary element method in order to compute a Markov transition matrix (MTM) for each motif. The individual motifs are connected together by building a large Markov chain. Such Markov chain can be simulated extremely efficiently using Monte Carlo simulations (e.g., random walks). The main practical advantage of the proposed algorithm is its ability to extract the capacitance of a large number of layout configurations in a complexity that is basically independent of the number of configurations. For instance, in a large 3-D layout example, the capacitance calculation of 1000 different configurations assembled from the same motifs is accomplished in the time required to solve independently two configurations, i.e., a 500 × speedup.
KW - Integrated circuit interconnections
KW - interconnected systems
KW - large scale integration
KW - Markov processes
KW - Monte Carlo methods
KW - parameter extraction
KW - parasitic capacitance
UR - http://www.scopus.com/inward/record.url?scp=78651334149&partnerID=8YFLogxK
U2 - 10.1109/TADVP.2010.2091504
DO - 10.1109/TADVP.2010.2091504
M3 - Article
AN - SCOPUS:78651334149
SN - 1521-3323
VL - 33
SP - 818
EP - 827
JO - IEEE Transactions on Advanced Packaging
JF - IEEE Transactions on Advanced Packaging
IS - 4
M1 - 5671505
ER -