Linear time hierarchical capacitance extraction without multipole expansion

S. Balakrishnan; J. H. Park; H. Kim; Yu-Min Lee; C. C.P. Chen

doi:10.1109/ICCD.2001.955010

Linear time hierarchical capacitance extraction without multipole expansion

S. Balakrishnan^*, J. H. Park, H. Kim, Yu-Min Lee, C. C.P. Chen

^*Corresponding author for this work

Department of Electrical and Computer Engineering

Research output: Contribution to conference › Paper › peer-review

2 Scopus citations

Abstract

Recently, hierarchical capacitance extraction algorithms have been shown an efficient and accurate capacitance extraction algorithm. An improved algorithm is also proposed to remove its runtime dependency on the number of conductors by a combination of hierarchical and multipole expansion algorithm. In this paper, we show that with the introduction of hierarchical merging operation and supernode representation, we can achieve linear runtime and accuracy without involving multipole expansion. Experimental results show over 10X runtime improvement and 20X memory saving over the multipole approaches with comparable accuracy and better numerical stability.

Original language	English
Pages	98-103
Number of pages	6
DOIs	https://doi.org/10.1109/ICCD.2001.955010
State	Published - Sep 2001
Event	IEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001) - Austin, TX, United States Duration: 23 Sep 2001 → 26 Sep 2001

Conference

Conference	IEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001)
Country/Territory	United States
City	Austin, TX
Period	23/09/01 → 26/09/01

Access to Document

10.1109/ICCD.2001.955010

Cite this

@conference{c39ce2e03f73449a9ee5a490591b1a97,

title = "Linear time hierarchical capacitance extraction without multipole expansion",

abstract = "Recently, hierarchical capacitance extraction algorithms have been shown an efficient and accurate capacitance extraction algorithm. An improved algorithm is also proposed to remove its runtime dependency on the number of conductors by a combination of hierarchical and multipole expansion algorithm. In this paper, we show that with the introduction of hierarchical merging operation and supernode representation, we can achieve linear runtime and accuracy without involving multipole expansion. Experimental results show over 10X runtime improvement and 20X memory saving over the multipole approaches with comparable accuracy and better numerical stability.",

author = "S. Balakrishnan and Park, {J. H.} and H. Kim and Yu-Min Lee and Chen, {C. C.P.}",

year = "2001",

month = sep,

doi = "10.1109/ICCD.2001.955010",

language = "English",

pages = "98--103",

note = "IEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001) ; Conference date: 23-09-2001 Through 26-09-2001",

}

TY - CONF

T1 - Linear time hierarchical capacitance extraction without multipole expansion

AU - Balakrishnan, S.

AU - Park, J. H.

AU - Kim, H.

AU - Lee, Yu-Min

AU - Chen, C. C.P.

PY - 2001/9

Y1 - 2001/9

N2 - Recently, hierarchical capacitance extraction algorithms have been shown an efficient and accurate capacitance extraction algorithm. An improved algorithm is also proposed to remove its runtime dependency on the number of conductors by a combination of hierarchical and multipole expansion algorithm. In this paper, we show that with the introduction of hierarchical merging operation and supernode representation, we can achieve linear runtime and accuracy without involving multipole expansion. Experimental results show over 10X runtime improvement and 20X memory saving over the multipole approaches with comparable accuracy and better numerical stability.

AB - Recently, hierarchical capacitance extraction algorithms have been shown an efficient and accurate capacitance extraction algorithm. An improved algorithm is also proposed to remove its runtime dependency on the number of conductors by a combination of hierarchical and multipole expansion algorithm. In this paper, we show that with the introduction of hierarchical merging operation and supernode representation, we can achieve linear runtime and accuracy without involving multipole expansion. Experimental results show over 10X runtime improvement and 20X memory saving over the multipole approaches with comparable accuracy and better numerical stability.

UR - http://www.scopus.com/inward/record.url?scp=0035177172&partnerID=8YFLogxK

U2 - 10.1109/ICCD.2001.955010

DO - 10.1109/ICCD.2001.955010

M3 - Paper

AN - SCOPUS:0035177172

SP - 98

EP - 103

T2 - IEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001)

Y2 - 23 September 2001 through 26 September 2001

ER -

Linear time hierarchical capacitance extraction without multipole expansion

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this