| dc.description.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. | en |
