MTL Annual Research Report 2012

FastMarkov: A Markov–Chain-based Hierarchical Solver for Large-scale Capacitance Extraction

Standard full-chip capacitance extraction algorithms rely for computational efficiency on 2D scanning and table lookup algorithms. These algorithms trade off accuracy for computational efficiency and result in large error in the extracted capacitance of complex layouts. It is therefore desirable to use accurate field solvers for full-chip extraction, which in general can be divided into two types: discretization-based and discretization-free. Discretization-based methods include the finite difference methods, the finite element methods and the boundary element methods ^[1] . The most well-known discretization-free algorithm is the floating random walk method and its variants. It is widely accepted that discretization-based methods are very efficient for small and medium-size structures and that discretization-free methods are more efficient for very large structures. Recently, our group has proposed a Markov Chain-based hierarchical algorithm ^[2] combining the advantages of both discretization-based and discretization-free methods.

Figure 1: An example of a layout that can be analysed by our solver and containing 85 nets (represented by different colours) and 14 dielectric layers (removed from image for clarity). Image courtesy of Intel Corporation.

In this project we further refine our algorithm and implement it in C++ for very large-scale capacitance extraction. A layout is first partitioned into smaller blocks. The Markov Transition Matrix (MTM) for each block is computed, and then the capacitance of the full layout is extracted by simulating the Markov Chain with random walk methods. Our algorithm is efficient because the computation of an MTM is derived from the capacitance matrix associated with each block. Such a matrix is computed using the Finite Difference Method, which can handle highly inhomogeneous structures including different dielectrics and metal fills. In addition, our algorithm requires neither assembly nor solution of any linear system of equations at the level of the full layout. Consequently, the algorithm requires very modest computational time and memory to compute the capacitance matrix of the full- chip to field solver accuracy. In addition, our algorithm lends itself to efficient parallelization because both the computation of MTMs and the computation of random walks are embarrassingly parallelizable. The accuracy, efficiency, and almost linear scalability of the algorithm are being tested on FastMarkov – our C++ implemented, MPI-parallelized solver, which can handle large-scale, geometrically complex, industry provided examples (such as the one shown in Figure 1) in 45 minutes using 4-core parallelization. We have so far also verified that around 95% of computation time is spent on MTM computation, which can be reduced significantly by larger number parallelization.

1. K. Nabors and J. White, “Fastcap: a multipole accelerated 3-d capacitance extraction program,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, no. 11, pp. 1447-1459, Nov. 1991. [↩]
2. T. El-Moselhy, I. Elfadel, and L. Daniel, “A hierarchical floating random walk algorithm for fabric-aware 3d capacitance extraction,” in IEEE/ACM International Conference on Computer-Aided Design, 2009. [↩]