A hierarchical floating random walk algorithm for fabric-aware 3D capacitance extraction

Markov processes;boundary-elements methods;capacitance;integrated circuit layout;3D capacitance extraction;Markov transition matrices;boundary element method;hierarchical domain decomposition;hierarchical floating random walk algorithm;integrated circuit layout;parasitic extraction;size 22 nm

El-Moselhy, Tarek Ali ; Elfadel, Ibrahim M. ; Daniel, Luca

Institute of Electrical and Electronics Engineers

Others  :  http://dspace.mit.edu/openaccess-disseminate/1721.1/59352

美国|英语

来源: MIT Theses in DSpace@MIT

【 摘 要 】

With the adoption of ultra regular fabric paradigms for controlling design printability at the 22 nm node and beyond, there is an emerging need for a layout-driven, pattern-based parasitic extraction of alternative fabric layouts. In this paper, we propose a hierarchical floating random walk (HFRW) algorithm for computing the 3D capacitances of a large number of topologically different layout configurations that are all composed of the same layout motifs. Our algorithm is not a standard hierarchical domain decomposition extension of the well established floating random walk technique, but rather a novel algorithm that employs Markov Transition Matrices. Specifically, unlike the fast-multipole boundary element method and hierarchical domain decomposition (which use a far-field approximation to gain computational efficiency), our proposed algorithm is exact and does not rely on any tradeoff between accuracy and computational efficiency. Instead, it relies on a tradeoff between memory and computational efficiency. Since floating random walk type of algorithms have generally minimal memory requirements, such a tradeoff does not result in any practical limitations. The main practical advantage of the proposed algorithm is its ability to handle a set of layout configurations in a complexity that is basically independent of the set size. For instance, in a large 3D layout example, the capacitance calculation of 120 different configurations made of similar motifs is accomplished in the time required to solve independently just 2 configurations, i.e. a 60x speedup.