|
Description:
|
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 . |