{"id":809,"date":"2010-06-28T10:30:56","date_gmt":"2010-06-28T14:30:56","guid":{"rendered":"https:\/\/wpmu2.mit.local\/?p=809"},"modified":"2010-06-29T15:13:07","modified_gmt":"2010-06-29T19:13:07","slug":"a-random-walk-based-hierarchical-algorithm-for-fabric-aware-interconnect-extraction","status":"publish","type":"post","link":"https:\/\/wpmu2.mit.local\/a-random-walk-based-hierarchical-algorithm-for-fabric-aware-interconnect-extraction\/","title":{"rendered":"A Random-walk-based Hierarchical Algorithm for Fabric-aware Interconnect Extraction"},"content":{"rendered":"
\"Figure<\/a>

Figure 1: Five layer configurations. Each layer has a different dielectric constant. Different configurations are constructed by different orderings of the five layers. Each configuration is composed of 209 conductors. <\/p><\/div>\n

With the adoption of restricted design rules (RDR) and ultra-regular fabric paradigms for controlling design printability at the 22nm node and beyond, there is an emerging need for a layout-driven, pattern-based parasitic extraction of alternative fabric layouts. Such paradigms impose two requirements of micro- and macro-regularity on the layouts. \u201cMicro-\u201d regularity is achieved by restricting shape edges to lie on a restricted design grid that also imposes stringent directionality on shape orientation. \u201cMacro-\u201d regularity is achieved by using a very restricted set of litho-friendly logic cells. Such regularities have motivated using a relatively small number of optimized (litho-friendly and robust) layouts as building blocks to construct any arbitrary structure. These building blocks will be referred to subsequently as \u201cmotifs.\u201d A designer typically examines different arrangements of the \u201cmotifs\u201d in order to choose the \u201coptimal\u201d (in terms of printability, area, and electrical performance) design. Consequently, from an extraction point of view, there is a need to develop tools that are aware of topological variations.<\/p>\n

\"Figure<\/a>

Figure 2: Markov Transition Probability associated with one of the layers.<\/p><\/div>\n

In this project, we propose a hierarchical floating random walk (HFRW) [1<\/a>]<\/sup> [2<\/a>]<\/sup> 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 [3<\/a>]<\/sup> [4<\/a>]<\/sup> but rather a novel algorithm that employs Markov Transition Matrices (MTMs). Specifically, we first compute for each motif an MTM, representing the probability of making a transition from any point on the motif boundary to any point on the motif boundary or on a surface of the conductors inside the motifs. Then the capacitance of the different layout configurations is extracted by using the pre-computed motif MTM to form a large Markov Chain, and finally by simulating such a chain using random walks. The complexity of our algorithm is primarily related to the computation of the motif MTM. Such computation needs to be performed once for each motif, independent of the number of configurations. On the other hand, the complexity of simulating the Markov Chains (computing the configuration) is almost negligible. Consequently, the main practical advantage of the proposed algorithm is its ability to compute the capacitance of 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 60\u00d7 speedup.<\/p>\n

\r\nReferences
  1. T. El-Moselhy, I. M. Elfadel and L. Daniel, \u201cA hierarchical floating random walk algorithm for fabric-aware 3D capacitance extraction,\u201d Proceedings of the 2009 IEEE\/ACM International Conference on Computer Aided Design<\/em>, November 2009. [↩<\/a>]<\/li>
  2. T. El-Moselhy, I. M. Elfadel, and L. Daniel, \u201cA Markov Chain Based Hierarchical Algorithm for Fabric-Aware Capacitance Extraction,\u201d accepted for publication in Transaction on Advanced Packaging<\/em>. [↩<\/a>]<\/li>
  3. R. B. Iverson and Y. L. Le Coz, “A Stochastic Algorithm for High Speed capacitance Extraction in Integrated Circuits,” Solid-State Electronics, Vol. 35, No. 7, pp. 1005–1012, 1992. [↩<\/a>]<\/li>
  4. T. El-Moselhy, I. M. Elfadel , and L. Daniel, \u201cA capacitance solver for incremental variation-aware extraction,\u201d Proceedings of the 2008 IEEE\/ACM International Conference on Computer-Aided Design, November 2008<\/a> [↩<\/a>]<\/li><\/ol><\/div>","protected":false},"excerpt":{"rendered":"

    With the adoption of restricted design rules (RDR) and ultra-regular fabric paradigms for controlling design printability at the 22nm node…<\/p>\n<\/div>","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[26],"tags":[4071,48,4070,4069],"_links":{"self":[{"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/posts\/809"}],"collection":[{"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/comments?post=809"}],"version-history":[{"count":3,"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/posts\/809\/revisions"}],"predecessor-version":[{"id":1037,"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/posts\/809\/revisions\/1037"}],"wp:attachment":[{"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/media?parent=809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/categories?post=809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wpmu2.mit.local\/wp-json\/wp\/v2\/tags?post=809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}