MTL Annual Research Report 2011

Figure 1: A sample layout containing 85 nets (represented by different colours) and 14 dielectric layers (removed from image for clarity). Image courtesy of Intel Corporation.

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 significant 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, finite element method, and boundary element method ^[1] , while the best-known discretization-free algorithms are 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] to combine the advantages of both discretization-based and discretization-free methods.

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, and the Markov Transition Matrix (MTM) for each block is computed. Then, the capacitance of the full layout is extracted by simulating the Markov Chain using 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 does not require the assembly or the 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 min 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.