Stochastic dominant singular vectors method for variation-aware extraction
In this paper we present an efficient algorithm for variation-aware interconnect extraction. The problem we are addressing can be formulated mathematically as the solution of linear systems with matrix coefficients that are dependent on a set of random variables. Our algorithm is based on representi...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72204 https://orcid.org/0000-0002-5880-3151 |
| _version_ | 1826203567664398336 |
|---|---|
| author | El-Moselhy, Tarek Ali Daniel, Luca |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science El-Moselhy, Tarek Ali Daniel, Luca |
| author_sort | El-Moselhy, Tarek Ali |
| collection | MIT |
| description | In this paper we present an efficient algorithm for variation-aware interconnect extraction. The problem we are addressing can be formulated mathematically as the solution of linear systems with matrix coefficients that are dependent on a set of random variables. Our algorithm is based on representing the solution vector as a summation of terms. Each term is a product of an unknown vector in the deterministic space and an unknown direction in the stochastic space. We then formulate a simple nonlinear optimization problem which uncovers sequentially the most relevant directions in the combined deterministic-stochastic space. The complexity of our algorithm scales with the sum (rather than the product) of the sizes of the deterministic and stochastic spaces, hence it is orders of magnitude more efficient than many of the available state of the art techniques. Finally, we validate our algorithm on a variety of onchip and off-chip capacitance and inductance extraction problems, ranging from moderate to very large size, not feasible using any of the available state of the art techniques. |
| first_indexed | 2024-09-23T12:39:06Z |
| format | Article |
| id | mit-1721.1/72204 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:39:06Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/722042022-10-01T10:17:29Z Stochastic dominant singular vectors method for variation-aware extraction El-Moselhy, Tarek Ali Daniel, Luca Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Daniel, Luca El-Moselhy, Tarek Ali Daniel, Luca In this paper we present an efficient algorithm for variation-aware interconnect extraction. The problem we are addressing can be formulated mathematically as the solution of linear systems with matrix coefficients that are dependent on a set of random variables. Our algorithm is based on representing the solution vector as a summation of terms. Each term is a product of an unknown vector in the deterministic space and an unknown direction in the stochastic space. We then formulate a simple nonlinear optimization problem which uncovers sequentially the most relevant directions in the combined deterministic-stochastic space. The complexity of our algorithm scales with the sum (rather than the product) of the sizes of the deterministic and stochastic spaces, hence it is orders of magnitude more efficient than many of the available state of the art techniques. Finally, we validate our algorithm on a variety of onchip and off-chip capacitance and inductance extraction problems, ranging from moderate to very large size, not feasible using any of the available state of the art techniques. Focus Center Research Program. Focus Center for Circuit & System Solutions (C2S2) (Interconnect Focus Center) Mentor Graphics (Firm) International Business Machines Corporation Advanced Micro Devices (Firm) 2012-08-17T20:33:58Z 2012-08-17T20:33:58Z 2010-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0002-5 http://hdl.handle.net/1721.1/72204 Tarek El-Moselhy and Luca Daniel. 2010. Stochastic dominant singular vectors method for variation-aware extraction. In Proceedings of the 47th Design Automation Conference (DAC '10). ACM, New York, NY, USA, 667-672. Copyright © 2010 ACM, Inc. https://orcid.org/0000-0002-5880-3151 en_US http://dx.doi.org/10.1145/1837274.1837444 Proceedings of the 47th Design Automation Conference (DAC '10 ) 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 Association for Computing Machinery (ACM) IEEE |
| spellingShingle | El-Moselhy, Tarek Ali Daniel, Luca Stochastic dominant singular vectors method for variation-aware extraction |
| title | Stochastic dominant singular vectors method for variation-aware extraction |
| title_full | Stochastic dominant singular vectors method for variation-aware extraction |
| title_fullStr | Stochastic dominant singular vectors method for variation-aware extraction |
| title_full_unstemmed | Stochastic dominant singular vectors method for variation-aware extraction |
| title_short | Stochastic dominant singular vectors method for variation-aware extraction |
| title_sort | stochastic dominant singular vectors method for variation aware extraction |
| url | http://hdl.handle.net/1721.1/72204 https://orcid.org/0000-0002-5880-3151 |
| work_keys_str_mv | AT elmoselhytarekali stochasticdominantsingularvectorsmethodforvariationawareextraction AT danielluca stochasticdominantsingularvectorsmethodforvariationawareextraction |