Yan, Shu (2005-12). Efficient numerical methods for capacitance extraction based on boundary element method. Doctoral Dissertation. Thesis uri icon

abstract

  • Fast and accurate solvers for capacitance extraction are needed by the VLSI industry
    in order to achieve good design quality in feasible time. With the development
    of technology, this demand is increasing dramatically. Three-dimensional capacitance
    extraction algorithms are desired due to their high accuracy. However, the present
    3D algorithms are slow and thus their application is limited. In this dissertation, we
    present several novel techniques to significantly speed up capacitance extraction algorithms
    based on boundary element methods (BEM) and to compute the capacitance
    extraction in the presence of floating dummy conductors.
    We propose the PHiCap algorithm, which is based on a hierarchical refinement
    algorithm and the wavelet transform. Unlike traditional algorithms which result in
    dense linear systems, PHiCap converts the coefficient matrix in capacitance extraction
    problems to a sparse linear system. PHiCap solves the sparse linear system iteratively,
    with much faster convergence, using an efficient preconditioning technique. We also
    propose a variant of PHiCap in which the capacitances are solved for directly from a
    very small linear system. This small system is derived from the original large linear
    system by reordering the wavelet basis functions and computing an approximate LU
    factorization. We named the algorithm RedCap. To our knowledge, RedCap is the
    first capacitance extraction algorithm based on BEM that uses a direct method to solve a reduced linear system.
    In the presence of floating dummy conductors, the equivalent capacitances among
    regular conductors are required. For floating dummy conductors, the potential is unknown
    and the total charge is zero. We embed these requirements into the extraction
    linear system. Thus, the equivalent capacitance matrix is solved directly. The number
    of system solves needed is equal to the number of regular conductors.
    Based on a sensitivity analysis, we propose the selective coefficient enhancement
    method for increasing the accuracy of selected coupling or self-capacitances with
    only a small increase in the overall computation time. This method is desirable
    for applications, such as crosstalk and signal integrity analysis, where the coupling
    capacitances between some conductors needs high accuracy. We also propose the
    variable order multipole method which enhances the overall accuracy without raising
    the overall multipole expansion order. Finally, we apply the multigrid method to
    capacitance extraction to solve the linear system faster.
    We present experimental results to show that the techniques are significantly
    more efficient in comparison to existing techniques.

publication date

  • December 2005
  • December 2005