Name
Title | ||
|---|---|---|
A hierarchical floating random walk algorithm for fabric-aware 3D capacitance extraction |
Abstract | ||
|---|---|---|
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 60Ã speedup. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1687399.1687539 | San Jose, CA |
Keywords | Field | DocType |
hierarchical domain decomposition,topologically different layout configuration,layout motif,hierarchical floating random walk,layout example,capacitance extraction,computational efficiency,novel algorithm,layout configuration,proposed algorithm,alternative fabric layout,data mining,algorithm design and analysis,random walk,high level synthesis,integrated circuit layout,parasitic extraction,capacitance,markov processes,domain decomposition,layout,boundary element method,conductors | Integrated circuit layout,Algorithm design,Markov process,Random walk,Computer science,High-level synthesis,Markov chain,Electronic engineering,Domain decomposition methods,Speedup | Conference |
ISSN | ISBN | Citations |
1092-3152 E-ISBN : 978-1-60558-800-1 | 978-1-60558-800-1 | 10 |
PageRank | References | Authors |
0.90 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tarek A. El-Moselhy | 1 | 91 | 9.34 |
| Ibrahim M. Elfadel | 2 | 242 | 44.16 |
| Luca Daniel | 3 | 497 | 50.96 |