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 -