A Probability-Based Parasitic Extraction Algorithm for Global-Routed VLSI Designs

CHEN Jiarui; WU Zhaoyi; YOU Yongjie; CHEN Yilu; LIN Zhifeng

doi:10.11999/JEIT250458

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

CHEN Jiarui, WU Zhaoyi, YOU Yongjie, CHEN Yilu, LIN Zhifeng. A Probability-Based Parasitic Extraction Algorithm for Global-Routed VLSI Designs[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250458

Citation:

CHEN Jiarui, WU Zhaoyi, YOU Yongjie, CHEN Yilu, LIN Zhifeng. A Probability-Based Parasitic Extraction Algorithm for Global-Routed VLSI Designs[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250458

Citation:

PDF( 1688 KB)

A Probability-Based Parasitic Extraction Algorithm for Global-Routed VLSI Designs

doi: 10.11999/JEIT250458 cstr: 32379.14.JEIT250458

1.
College of Computer and Data Science, Fuzhou University, Fuzhou 350108, China
2.
Shanghai LEDA Technology Co., Ltd., Shanghai 201203, China
3.
School of Computer and Information Engineering, Xiamen University of Technology, Xiamen 361024, China
4.
Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China

Funds: The Natural Science Foundation of Fujian Province (2024J01363), The National Key Research and Development Program of China (2021YFA1003602)

Received Date: 2025-05-26
Rev Recd Date: 2025-09-14

Available Online: 2025-09-16

Abstract

Abstract

Objective Parasitic extraction is a critical stage in the VLSI design flow, as it determines the parasitic parameters of interconnect wires, directly affecting delay evaluation, timing analysis, and performance verification. With the increasing complexity of modern designs, accurate estimation of parasitic parameters has become a central challenge in routing. Developing a fast and accurate extraction algorithm is therefore essential to enable high-performance routing solutions. Methods Pattern matching is a widely used technique for full-layout parasitic extraction. Given an interconnect layout, the method divides it into small sections and determines the parasitics of each section with a pre-built pattern library. However, with billions of transistors placed on a single chip, the continuous growth of design complexity makes full-layout parasitic extraction increasingly challenging. Inspired by pattern matching, this paper presents a probability-based parasitic extraction algorithm tailored for modern VLSI designs. The proposed method consists of two main stages: (1) layout analysis and (2) parasitic extraction. Given a global-routed netlist and technology files containing pre-characterized parasitic values, layout analysis captures coupling segment information and generates a probability-based look-up table for efficient wire-spacing computation. Parasitic extraction then constructs the RC tree for each net and produces accurate interconnect parasitic parameters using the spacing information derived from layout analysis. For layout analysis, a partitioning strategy is employed to identify coupling segments that are parallel to and overlap with the target wire segment. In practice, coupling segments far from the target wire exert negligible effects on parasitics; therefore, the chip layout is divided into regions to improve identification efficiency. During parasitic extraction, coupling segments in both the same layer and in abutting layers are considered. If the target wire fully traverses the grids in an adjacent layer, all segments in those grids are treated as cross segments; otherwise, only partially overlapping segments are included. Once the coupling segments are determined, wire spacing must be calculated. In parasitic extraction, spacing represents the distance between a wire and its nearest neighbor. Because of the vast number of wires in modern circuits, computing exact spacing for every wire is prohibitively expensive. To address this, a probability-based average spacing model is proposed. In multilayer circuit designs, extraction also requires accurate reconstruction of routing information from layout data. In the standard Design Exchange Format (DEF), routing topology is represented by wires and vias. To handle this efficiently, a construction algorithm is developed to build connected RC trees from distributed wires and vias. Leveraging the probability-based wire-spacing model together with the technology files, the algorithm extracts parasitic parameters while accounting for coupling effects. The technology file “.captbl” provides interconnect parasitic tables indexed by wire width and spacing, with widths varying across different metal layers due to process constraints. Interpolation methods are first applied to obtain the unit resistance as a function of wire spacing and width. Wire resistance is then modeled by multiplying this unit resistance by wire length. Similarly, capacitance is extracted using interpolation, with additional coupling effects between neighboring layers captured through a grid-based recognition strategy that identifies the number of cross segments. Relative coupling capacitance is then determined accordingly. Results and Discussions Experiments were conducted on twelve industrial designs to evaluate the proposed extraction algorithm. The results demonstrate that the method achieves high parasitic accuracy while being 21.6% faster than the commercial tool Innovus. The average capacitance error is 1.15% with a standard deviation of 3.09%, and the average resistance error is 0.08% with a standard deviation of 2.63%. Notably, for all twelve circuits, the standard deviation of both capacitance and resistance errors remains below 5%. These findings confirm that the proposed algorithm provides both accuracy and efficiency for full-chip parasitic extraction, offering a practical foundation for developing high-performance routing algorithms. Conclusions This paper presents a probability-based parasitic extractor for addressing full-chip extraction challenges. A partitioning strategy with grid-based data representation is developed to capture coupling segments efficiently. Based on these segments, a probability-driven mathematical model is proposed to calculate wire spacing, with a pre-computed look-up table accelerating the computation. An efficient construction algorithm is further presented to build connected RC trees from distributed wires and vias, followed by a coupling-aware RC extraction method to produce accurate interconnect parasitics. Experimental evaluation on twelve industrial benchmarks demonstrates strong correlation between the extracted parasitics and those obtained from the commercial tool Innovus.
- Very large scale integration,
- Parasitic extraction,
- Timing analysis,
- Global routing

FullText(HTML)

References(21)

References

[1]	SHI Hanyu and HE Qing. VLSI parasitic capacitance extraction based on pattern matching using modified machine learning methods[C]. The 10th International Conference on Computer and Communications (ICCC), Chengdu, China, 2024: 92–99. doi: 10.1109/ICCC62609.2024.10942273.
[2]	LIU Lihao, YANG Fan, SHANG Li, et al. GNN-cap: Chip-scale interconnect capacitance extraction using graph neural network[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024, 43(4): 1206–1217. doi: 10.1109/TCAD.2023.3331942.
[3]	PATIDAR S and BODADE R M. Evaluation trends and development in integrated circuit parasitic extraction[C]. 2024 IEEE International Students' Conference on Electrical, Electronics and Computer Science (SCEECS), Bhopal, India, 2024: 1–7. doi: 10.1109/SCEECS61402.2024.10482256.
[4]	ZEMANIAN A H. A finite-difference procedure for the exterior problem inherent in capacitance computations for VLSI interconnections[J]. IEEE Transactions on Electron Devices, 1988, 35(7): 985–992. doi: 10.1109/16.3355.
[5]	SUMANT P S and CANGELLARIS A C. Algebraic multigrid Laplace solver for the extraction of capacitances of conductors in multi-layer dielectrics[J]. International Journal of Numerical Modelling: Electronic Networks, Devices and Fields, 2007, 20(5): 253–269. doi: 10.1002/jnm.650.
[6]	YU Wenjian, SHEN Shan, YANG Dingcheng, et al. Deep learning inspired capacitance extraction techniques[C]. The 30th Asia and South Pacific Design Automation Conference, Tokyo, Japan, 2025: 106–112. doi: 10.1145/3658617.3703148.
[7]	WU Shengkun, XIE Biwei, and LI Xingquan. An adaptive partition strategy of Galerkin boundary element method for capacitance extraction[C]. The 28th Asia and South Pacific Design Automation Conference, Tokyo, Japan, 2023: 541–546. doi: 10.1145/3566097.3567903.
[8]	YU Wenjian, WANG Zeyi, and GU Jiangchun. Fast capacitance extraction of actual 3-D VLSI interconnects using quasi-multiple medium accelerated BEM[J]. IEEE Transactions on Microwave Theory and Techniques, 2003, 51(1): 109–119. doi: 10.1109/TMTT.2002.806923.
[9]	CHAI Wenwen, JIAO Dan, and KOH C K. A direct integral-equation solver of linear complexity for large-scale 3D capacitance and impedance extraction[C]. The 46th Annual Design Automation Conference, San Francisco, USA, 2009: 752–757. doi: 10.1145/1629911.1630107.
[10]	SHI Weiping, LIU Jianguo, KAKANI N, et al. A fast hierarchical algorithm for 3-D capacitance extraction[C]. The 35th Annual Design Automation Conference, San Francisco, USA, 1998: 212–217. doi: 10.1145/277044.277101.
[11]	YANG Ming and YU Wenjian. Floating random walk capacitance solver tackling conformal dielectric with on-the-ﬂy sampling on eight-octant transition cubes[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 4935–4943. doi: 10.1109/TCAD.2020.2968544.
[12]	YU Wenjian, ZHANG Bolong, ZHANG Chao, et al. Utilizing macromodels in ﬂoating random walk based capacitance extraction[C]. 2016 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2016: 1225–1230.
[13]	XU Jiahao, ZHANG Yibin, GAO Shenghan, et al. A 2-D multi-dielectric capacitance solver based on floating random walk method[C]. 2023 China Semiconductor Technology International Conference (CSTIC), Shanghai, China, 2023: 1–3. doi: 10.1109/CSTIC58779.2023.10219380.
[14]	WEI Xin, YAN Changhao, ZHOU Hai, et al. An efficient FPGA-based ﬂoating random walk solver for capacitance extraction using SDAccel[C]. 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1040–1045. doi: 1 0.23919/DATE.2019.8714992.
[15]	YU Wenjian, XU Zhezhao, LI Bo, et al. Floating random walk-based capacitance simulation considering general ﬂoating metals[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(8): 1711–1715. doi: 10.1109/TCAD.2017.2782770.
[16]	ARORA N D, RAOL K V, SCHUMANN R, et al. Modeling and extraction of interconnect capacitances for multilayer VLSI circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996, 15(1): 58–67. doi: 10.1109/43.486272.
[17]	SAKURAI T and TAMARU K. Simple formulas for two- and three-dimensional capacitances[J]. IEEE Transactions on Electron Devices, 1983, 30(2): 183–185. doi: 10.1109/T-ED.1983.21093.
[18]	CHOUDHURY U and SANGIOVANNI-VINCENTELLI A L. Automatic generation of analytical models for interconnect capacitances[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995, 14(4): 470–480. doi: 10.1109/43.372374.
[19]	LI Zhixing and SHI Weiping. Layout capacitance extraction using automatic pre-characterization and machine learning[C]. 2020 21st International Symposium on Quality Electronic Design, Santa Clara, USA, 2020: 457–464. doi: 10.1109/ISQED48828.2020.9136970.
[20]	YANG Dingcheng, LI Haoyuan, YU Wenjian, et al. CNN-cap: Effective convolutional neural network-based capacitance models for interconnect capacitance extraction[J]. ACM Transactions on Design Automation of Electronic Systems, 2023, 28(4): 56. doi: 10.1145/3564931.
[21]	ABOUELYAZID M S, HAMMOUDA S, and ISMAIL Y. Accuracy-based hybrid parasitic capacitance extraction using rule-based, neural-networks, and field-solver methods[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(12): 5681–5694. doi: 10.1109/TCAD.2022.3161199.