Article

A solenoidal basis method for efficient inductance extraction

Authors:

Hemant Mahawar,

Weiping ShiAuthors Info & Claims

DAC '02: Proceedings of the 39th annual Design Automation Conference

Pages 751 - 756

https://doi.org/10.1145/513918.514107

Published: 10 June 2002 Publication History

Abstract

The ability to compute the parasitic inductance of the interconnect is critical to the timing verification of modern VLSI circuits. A challenging aspect of inductance extraction is the solution of large, dense, complex linear systems of equations via iterative methods. Accelerating the convergence of the iterative method through preconditioning is made difficult due to the non-availability of the system matrix. This paper presents a novel algorithm to solve these linear systems by restricting current to a discrete solenoidal subspace in which Kirchoff's law is obeyed, and solving a reduced system via an iterative method such as GMRES. A preconditioner based on the Green's function is used to achieve near-optimal convergence rates in several cases. Experiments on a number of benchmark problems illustrate the advantages of the proposed method over FastHenry.

References

[1]

J. Barnes and P. Hut. A hierarchical O(n log n) force calculation algorithm. Nature, Vol. 324, 1986.

[2]

L. Daniel, A. Sangiovanni-Vincentelli, and J. White. Techniques for including dielectrics when extracting passive low-order models of high speed interconnect. ICCAD 01.

Digital Library

[3]

K. Gala, et. al. % V. Zolotov, R. Panda, B. Young, J. Wang and D. Blaauw, On chip inductance modeling and analysis. DAC 2000.

Digital Library

[4]

L. Greengard. The Rapid Evaluation of Potential Fields in Particle Systems. The MIT Press, Cambridge, Massachusetts, 1988.

[5]

Z. He, M. Celik and L. Pileggi. SPIE: Sparse partial inductance extraction. DAC 1997.

Digital Library

[6]

M. Kamon. Fast Parasitic Extraction and Simulation of Three-dimensional Interconnect via Quasistatic Analysis. PhD thesis, EE & CS Dept., MIT, 1998.

Digital Library

[7]

M. Kamon and J. R. Philips. Preconditioning techniques for constrained vector potential integral equations, with application to 3-D magnetoquasistatic analysis of electronic packages. In Proceedings of the Colorado Conference on Iterative Methods, Breckenridge, Colorado, 1994.

[8]

M. Kamon, M. J. Tsuk, and J. White. FASTHENRY: A multipole-accelerated 3D inductance extraction program. IEEE Trans. MTT, Vol. 42:1750--1758, 1994.

[9]

B. Krauter and S. Mehrotra. Layout based frequency dependent inductance and resistance extraction for on-chip interconnect timing analysis. DAC 1998.

Digital Library

[10]

B. Krauter and L. T. Pileggi. Generating sparse partial inductance matrices with guaranteed stability. ICCAD 95.

Digital Library

[11]

M. Liu, T. Yu and W. W.-M. Dai. Fast 3D inductance extraction in lossy multi-layer substrate. ICCAD 01.

Digital Library

[12]

V. Rokhlin. Rapid solution of integral equations of classical potential theory. Journal of Computational Physics, Vol. 60:187--207, 1985.

[13]

A. E. Ruehli. Inductance calculation in a complex integrated circuit environment. IBM J. Res. Dev., Sept. 1972.

Digital Library

[14]

Y. Saad. Iterative methods for sparse linear systems. PWS publishing company, 1996.

Digital Library

[15]

K. L. Shepard and Y. Zhang. Return-limited inductances: A practical approach to on-chip inductance extraction. IEEE Trans. CAD, 19(4):425--436, 2000.

Digital Library

Cited By

Yi YWenzel RSarin VShi W(2009)Inductance extraction for interconnects in the presence of nonlinear magnetic materialsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.201886928:7(1106-1110)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2018869
Mahawar HSarin V(2006)Parallel algorithms for inductance extraction of VLSI circuitsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1899013(80-80)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1899013
Mahawar HSarin VGrama A(2004)Parallel performance of hierarchical multipole algorithms for inductance extractionProceedings of the 11th international conference on High Performance Computing10.1007/978-3-540-30474-6_48(450-461)Online publication date: 19-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30474-6_48
Show More Cited By

Index Terms

A solenoidal basis method for efficient inductance extraction
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Hardware validation
    1. Functional verification
      1. Simulation and emulation

Recommendations

Preconditioned Iterative Solvers for Inductance Extraction of VLSI Circuits

Parasitic extraction techniques are used to estimate signal delay in VLSI circuits. Inductance extraction is a critical component of the parasitic extraction process that involves estimation of on-chip inductive effects with high accuracy. The problem ...
Fast Inductance Extraction of Large VLSI Circuits
IPDPS '02: Proceedings of the 16th International Symposium on Parallel and Distributed Processing

Accurate estimation of signal delay is critical to the design and verification of VLSI circuits. At very high frequencies, signal delay in circuits with small feature sizes is dominated by the parasitic inductance and capacitance of the interconnect. ...
Sparse transformations and preconditioners for hierarchical 3-D capacitance extraction with multiple dielectrics
DAC '04: Proceedings of the 41st annual Design Automation Conference

Capacitance extraction is an important problem that has been extensively studied. This paper presents a significant improvement for the fast multipole accelerated boundary element method. We first introduce an algebraic transformation to convert the n x ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '02: Proceedings of the 39th annual Design Automation Conference

June 2002

956 pages

ISBN:1581134614

DOI:10.1145/513918

General Chair:
Bryan Ackland
Agere Systems, Inc., Holmdel, NJ

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC02

Sponsor:

SIGDA

DAC02: 39th Design Automation Conference

June 10 - 14, 2002

Louisiana, New Orleans, USA

Acceptance Rates

DAC '02 Paper Acceptance Rate 147 of 491 submissions, 30%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
14
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yi YWenzel RSarin VShi W(2009)Inductance extraction for interconnects in the presence of nonlinear magnetic materialsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.201886928:7(1106-1110)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2018869
Mahawar HSarin V(2006)Parallel algorithms for inductance extraction of VLSI circuitsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1899013(80-80)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1899013
Mahawar HSarin VGrama A(2004)Parallel performance of hierarchical multipole algorithms for inductance extractionProceedings of the 11th international conference on High Performance Computing10.1007/978-3-540-30474-6_48(450-461)Online publication date: 19-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30474-6_48
Yan SLiu JShi WYasuura H(2003)Improving boundary element methods for parasitic extractionProceedings of the 2003 Asia and South Pacific Design Automation Conference10.1145/1119772.1119823(261-267)Online publication date: 21-Jan-2003
https://dl.acm.org/doi/10.1145/1119772.1119823
Mahawar HSarin V(2003)Parallel iterative methods for dense linear systems in inductance extractionParallel Computing10.1016/S0167-8191(03)00100-529:9(1219-1235)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1016/S0167-8191%2803%2900100-5

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten