RWCap: A Floating Random Walk Solver for 3-D Capacitance Extraction of Very-Large-Scale Integration Interconnects
Authors:
Top Cited Papers
- 14 February 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 32 (3) , 353-366
Abstract
A floating random walk (FRW) solver, called RWCap, is presented for the capacitance extraction of very-large-scale integration (VLSI) interconnects. An approach, including the numerical characterization of the cross-interface transition probability and weight value, is proposed to accelerate the extraction of structures with multiple dielectric layers. A comprehensive variance reduction scheme based on the importance sampling and stratified sampling is proposed to improve the convergence rate of the FRW algorithm. Finally, the space management technique using an octree data structure and the parallel computing technique are presented to further improve the efficiency. Numerical experiments are carried out with the test cases generated under the 180 and 45-nm process technologies. They demonstrate that the proposed multidielectric FRW algorithm achieves up to 160× speedup over the FRW algorithm using spherical transition domains to cross dielectric interface, with very small memory overhead. The variance reduction techniques further bring 3× or more speedup without memory overhead and the loss of accuracy. The RWCap also outperforms other existing FRW algorithm and fast boundary element method solvers in terms of computational time or scalability. The experiments on an 8-core CPU machine show that the parallel RWCap is over 6× faster than its serial-computing version.Keywords
This publication has 20 references indexed in Scilit:
- A hierarchical floating random walk algorithm for fabric-aware 3D capacitance extraction2009
- A capacitance solver for incremental variation-aware extraction2008
- A statistical method for fast and accurate capacitance extraction in the presence of floating dummy fills2006
- Efficient 3-D extraction of interconnect capacitance considering floating metal fills with boundary element methodIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005
- Sparse transformations and preconditioners for 3-D capacitance extractionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005
- Variance reduction in Monte Carlo capacitance extraction2005
- Enhanced QMM-BEM Solver for Three-Dimensional Multiple-Dielectric Capacitance Extraction Within the Finite DomainIEEE Transactions on Microwave Theory and Techniques, 2004
- A floating random-walk algorithm for extracting electrical capacitanceMathematics and Computers in Simulation, 2001
- A statistical algorithm for 3D capacitance extractionIEEE Microwave and Guided Wave Letters, 2000
- Performance of random-walk capacitance extractors for IC interconnects: A numerical studySolid-State Electronics, 1998