A Markov chain based hierarchical algorithm for fabric-aware capacitance extraction

Tarek El-Moselhy, Ibrahim Abe M. Elfadel, Luca Daniel

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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.

Original languageBritish English
Article number5671505
Pages (from-to)818-827
Number of pages10
JournalIEEE Transactions on Advanced Packaging
Issue number4
StatePublished - Nov 2010


  • Integrated circuit interconnections
  • interconnected systems
  • large scale integration
  • Markov processes
  • Monte Carlo methods
  • parameter extraction
  • parasitic capacitance


Dive into the research topics of 'A Markov chain based hierarchical algorithm for fabric-aware capacitance extraction'. Together they form a unique fingerprint.

Cite this