Loading [MathJax]/extensions/MathMenu.js
RWCap: A Floating Random Walk Solver for 3-D Capacitance Extraction of Very-Large-Scale Integration Interconnects | IEEE Journals & Magazine | IEEE Xplore

RWCap: A Floating Random Walk Solver for 3-D Capacitance Extraction of Very-Large-Scale Integration Interconnects


Abstract:

A floating random walk (FRW) solver, called RWCap, is presented for the capacitance extraction of very-large-scale integration (VLSI) interconnects. An approach, includin...Show More

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.
Page(s): 353 - 366
Date of Publication: 14 February 2013

ISSN Information:


I. Introduction

Under the nanometer process technology, accurate extraction of interconnect capacitance with 3-D field-solver algorithm becomes increasingly important for high-performance integrated circuit (IC) design. The field-solver algorithm for capacitance extraction can be classified into two categories: 1) the conventional deterministic algorithms based on boundary element method (BEM) [1]–[6], finite element method (FEM) [7], [8], etc., and 2) the floating random walk (FRW) algorithm with stochastic nature [9]–[20]. The deterministic algorithms are fast and accurate, but not suitable for large-scale structures due to the large demand of computational time and the bottleneck of memory usage.

References

References is not available for this document.