{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/71502"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/71502","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"A hierarchical Markov chain based solver for very-large-scale capacitance extraction","abstract":"This thesis presents two hierarchical algorithms, FastMarkov and FD-MTM, for computing the capacitance of very-large-scale layout with non-uniform media. Fast- Markov is Boundary Element Method based and FD-MTM is Finite Difference based. In our algorithms, the layout is first partitioned into small blocks and the capacitance matrix of each block is solved using standard deterministic methods, BEM for Fast- Markov and FDM for FD-MTM. We connect the blocks by enforcing the boundary condition on the interfaces, forming a Markov Chain containing the capacitive characteristic of the layout. Capacitance of the full layout is then extracted with the random walk method. By employing the \"divide and conquer\" strategy, our algorithm does not need to assemble or solve a linear system of equations at the level of the full layout and thus eliminates the memory problem. We also propose a modification to the FastMarkov algorithm (FastMarkov with boundary fix) to address the block interface issue when using the finite difference method. We implemented FastMarkov with boundary fix in C++ and parallelized the solver with Message Passing Interface. Compared with standard FD capacitance solver, our solver is able to achieve a speedup almost linear to the number of blocks the layout is partitioned into. On top of it, FastMarkov is easily parallelizable because the computation of the capacitance matrix of one block is independent of other blocks and one path of random walk is independent of other paths. Results and comparisons are presented for parallel plates example and for a large Intel example.","abstract_html":"This thesis presents two hierarchical algorithms, FastMarkov and FD-MTM, for computing the capacitance of very-large-scale layout with non-uniform media. Fast- Markov is Boundary Element Method based and FD-MTM is Finite Difference based. In our algorithms, the layout is first partitioned into small blocks and the capacitance matrix of each block is solved using standard deterministic methods, BEM for Fast- Markov and FDM for FD-MTM. We connect the blocks by enforcing the boundary condition on the interfaces, forming a Markov Chain containing the capacitive characteristic of the layout. Capacitance of the full layout is then extracted with the random walk method. By employing the "divide and conquer" strategy, our algorithm does not need to assemble or solve a linear system of equations at the level of the full layout and thus eliminates the memory problem. We also propose a modification to the FastMarkov algorithm (FastMarkov with boundary fix) to address the block interface issue when using the finite difference method. We implemented FastMarkov with boundary fix in C++ and parallelized the solver with Message Passing Interface. Compared with standard FD capacitance solver, our solver is able to achieve a speedup almost linear to the number of blocks the layout is partitioned into. On top of it, FastMarkov is easily parallelizable because the computation of the capacitance matrix of one block is independent of other blocks and one path of random walk is independent of other paths. Results and comparisons are presented for parallel plates example and for a large Intel example.","abstract_has_math":false,"creators":["Zhao, Yan, Ph. D. Massachusetts Institute of Technology"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Luca Daniel."],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-07-22T22:20:58Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/71502","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Luca Daniel."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Zhao, Yan, Ph. D. Massachusetts Institute of Technology"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2012-07-02T15:48:26Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2012-07-02T15:48:26Z"]},{"key":"dc:date.issued","label":"Date","values":["2012"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/71502"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 79-80)."]},{"key":"dc:description.abstract","label":"Abstract","values":["This thesis presents two hierarchical algorithms, FastMarkov and FD-MTM, for computing the capacitance of very-large-scale layout with non-uniform media. Fast- Markov is Boundary Element Method based and FD-MTM is Finite Difference based. In our algorithms, the layout is first partitioned into small blocks and the capacitance matrix of each block is solved using standard deterministic methods, BEM for Fast- Markov and FDM for FD-MTM. We connect the blocks by enforcing the boundary condition on the interfaces, forming a Markov Chain containing the capacitive characteristic of the layout. Capacitance of the full layout is then extracted with the random walk method. By employing the \"divide and conquer\" strategy, our algorithm does not need to assemble or solve a linear system of equations at the level of the full layout and thus eliminates the memory problem. We also propose a modification to the FastMarkov algorithm (FastMarkov with boundary fix) to address the block interface issue when using the finite difference method. We implemented FastMarkov with boundary fix in C++ and parallelized the solver with Message Passing Interface. Compared with standard FD capacitance solver, our solver is able to achieve a speedup almost linear to the number of blocks the layout is partitioned into. On top of it, FastMarkov is easily parallelizable because the computation of the capacitance matrix of one block is independent of other blocks and one path of random walk is independent of other paths. Results and comparisons are presented for parallel plates example and for a large Intel example."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["A hierarchical Markov chain based solver for very-large-scale capacitance extraction"]}]}],"canonical_facts":{"dc:contributor.advisor":["Luca Daniel."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Zhao, Yan, Ph. D. Massachusetts Institute of Technology"],"dc:date.accessioned":["2012-07-02T15:48:26Z"],"dc:date.available":["2012-07-02T15:48:26Z"],"dc:date.issued":["2012"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 79-80)."],"dc:description.abstract":["This thesis presents two hierarchical algorithms, FastMarkov and FD-MTM, for computing the capacitance of very-large-scale layout with non-uniform media. Fast- Markov is Boundary Element Method based and FD-MTM is Finite Difference based. In our algorithms, the layout is first partitioned into small blocks and the capacitance matrix of each block is solved using standard deterministic methods, BEM for Fast- Markov and FDM for FD-MTM. We connect the blocks by enforcing the boundary condition on the interfaces, forming a Markov Chain containing the capacitive characteristic of the layout. Capacitance of the full layout is then extracted with the random walk method. By employing the \"divide and conquer\" strategy, our algorithm does not need to assemble or solve a linear system of equations at the level of the full layout and thus eliminates the memory problem. We also propose a modification to the FastMarkov algorithm (FastMarkov with boundary fix) to address the block interface issue when using the finite difference method. We implemented FastMarkov with boundary fix in C++ and parallelized the solver with Message Passing Interface. Compared with standard FD capacitance solver, our solver is able to achieve a speedup almost linear to the number of blocks the layout is partitioned into. On top of it, FastMarkov is easily parallelizable because the computation of the capacitance matrix of one block is independent of other blocks and one path of random walk is independent of other paths. Results and comparisons are presented for parallel plates example and for a large Intel example."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/71502"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["A hierarchical Markov chain based solver for very-large-scale capacitance extraction"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:58Z"}