A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction
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 matri...
| Hlavní autoři: | , , |
|---|---|
| Další autoři: | |
| Médium: | Článek |
| Jazyk: | en_US |
| Vydáno: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| On-line přístup: | http://hdl.handle.net/1721.1/68998 https://orcid.org/0000-0002-5880-3151 |
| _version_ | 1826216583264993280 |
|---|---|
| author | El-Moselhy, Tarek Ali Elfadel, Ibrahim M. Daniel, Luca |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics El-Moselhy, Tarek Ali Elfadel, Ibrahim M. Daniel, Luca |
| author_sort | El-Moselhy, Tarek Ali |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:49:34Z |
| format | Article |
| id | mit-1721.1/68998 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:49:34Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/689982022-09-29T21:46:58Z A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction El-Moselhy, Tarek Ali Elfadel, Ibrahim M. Daniel, Luca Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Daniel, Luca El-Moselhy, Tarek Ali Elfadel, Ibrahim M. Daniel, Luca 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. Mentor Graphics (Firm) Advanced Micro Devices (Firm) International Business Machines Corporation Semiconductor Research Corporation Interconnect Focus Center (United States. Defense Advanced Research Projects Agency and Semiconductor Research Corporation) 2012-02-01T20:15:24Z 2012-02-01T20:15:24Z 2011-01 2010-10 Article http://purl.org/eprint/type/JournalArticle 1521-3323 1557-9980 http://hdl.handle.net/1721.1/68998 El-Moselhy, T, I M Elfadel, and L Daniel. “A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction.” IEEE Transactions on Advanced Packaging 33.4 (2010): 818-827. Web. 1 Feb. 2012. © 2011 Institute of Electrical and Electronics Engineers https://orcid.org/0000-0002-5880-3151 en_US http://dx.doi.org/10.1109/tadvp.2010.2091504 IEEE Transactions on Advanced Packaging Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | El-Moselhy, Tarek Ali Elfadel, Ibrahim M. Daniel, Luca A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction |
| title | A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction |
| title_full | A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction |
| title_fullStr | A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction |
| title_full_unstemmed | A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction |
| title_short | A Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction |
| title_sort | markov chain based hierarchical algorithm for fabric aware capacitance extraction |
| url | http://hdl.handle.net/1721.1/68998 https://orcid.org/0000-0002-5880-3151 |
| work_keys_str_mv | AT elmoselhytarekali amarkovchainbasedhierarchicalalgorithmforfabricawarecapacitanceextraction AT elfadelibrahimm amarkovchainbasedhierarchicalalgorithmforfabricawarecapacitanceextraction AT danielluca amarkovchainbasedhierarchicalalgorithmforfabricawarecapacitanceextraction AT elmoselhytarekali markovchainbasedhierarchicalalgorithmforfabricawarecapacitanceextraction AT elfadelibrahimm markovchainbasedhierarchicalalgorithmforfabricawarecapacitanceextraction AT danielluca markovchainbasedhierarchicalalgorithmforfabricawarecapacitanceextraction |