Capacitance computations in a multilayered dielectric medium usingclosed-form spatial Green's functions

An efficient method to compute the 2-D and 3-D capacitance matrices of multiconductor interconnects in a multilayered dielectric medium is presented. The method is based on an integral equation approach and assumes the quasi-static condition. It is applicable to conductors of arbitrary polygonal shape embedded in a multilayered dielectric medium with possible ground planes on the top or bottom of the dielectric layers. The computation time required to evaluate the space-domain Green's function for the multilayered medium, which involves an infinite summation, has been greatly reduced by obtaining a closed-form expression, which is derived by approximating the Green's function using a finite number of images in the spectral domain. Then the corresponding space-domain Green's functions are obtained using the proper closed-form integrations. In both 2-D and 3-D cases, the unknown surface charge density is represented by pulse basis functions, and the delta testing function (point matching) is used to solve the integral equation. The elements of the resulting matrix are computed using the closed-form formulation, avoiding any numerical integration. The presented method is compared with other published results and showed good agreement. Finally, the equivalent microstrip crossover capacitance is computed to illustrate the use of a combination of 2-D and 3-D Green's functions     

Fast and accurate quasi-three-dimensional capacitance determinationof multilayer VLSI interconnects

A new fast and accurate capacitance determination methodology for intricate multilayer VLSI interconnects is presented. Since a multilayer interconnect structure is too complicated to be directly tractable, it is simplified by investigating charge distributions within the system. The quasi-three-dimensional (3-D) capacitances of the structure are then determined by combining a set of solid-ground-based two-dimensional (2-D) capacitances and shielding effects that can be independently calculated from the simplified structure. The shielding effects due to the neighboring lines of a line can be analytically determined from the given layout dimensions. The solid-ground-based 2-D capacitances can also be quickly computed from the simplified structure. Thus, the proposed capacitance determination methodology is much more cost-efficient than conventional 3-D-based methods. It is shown that the calculated quasi-3-D capacitances have excellent agreement with 3-D field-solver-based results within 5% error     

小波多分辨率分析改进互连结构电容提取

本文将点匹配矢量法矩阵视作类似离散图像信号的一组数字信号矢量,进行小波多分辨率分解对该矩阵进行拟对角化压缩,克服了以往小小基直接展开的矩量法在求解二维与三维电在问题时的困难。文章例子的计算结果说明了这种方法在将矩量法得到的满矩阵变换为稀疏矩阵时具有的效率。电容参数提取的效率也由于矩阵的稀疏化得到了提高。文中的数据值结果与文献及ＦＡＳＴＣＡＰ软件的结果吻合。     

A hybrid BEM/WTM approach for analysis of the EM scattering fromlarge open-ended cavities

An effective hybrid boundary-element method (BEM) and wavelet-transform method (WTM) is proposed to analyze electromagnetic scattering from three-dimensional (3-D) open-ended cavities with arbitrary shapes. This hybrid technique formulates the original cavity problems by a magnetic field integral equation. The BEM is employed to establish the mapping between the original complex integral surface and the unit square. The WTM is used to reduce the density of the moment matrix. Since a surface integral equation has to be solved, the WTM requires a two-dimensional (2-D) wavelet basis to implement the numerical computation. The previous fast iterative algorithm for 2-D wavelets has been extended for efficiently constructing various 2-D wavelet basis functions by a tensorial product from two one-dimensional (1-D) regular multiresolution analyses. Unlike the conventional method of moments, the proposed hybrid technique can always obtain sparse moment matrix equations, which can be efficiently solved by sparse solvers. As the level scales for numerical discretization of cavities increase, larger compression rates can be obtained, which makes it possible for the hybrid BEM/WTM technique to efficiently solve scattering from large open-ended cavities with complex terminations. Numerical results are presented to demonstrate the merits of the proposed method     

A statistical approach to derive an electrical port model of capacitively coupled interconnects

This paper considers the derivation of an electrical model at the input/output ports of a generic system of nonparallel interconnects that can be employed to simulate cross talk and delay effects through a conventional SPICE-like simulator. Only capacitive coupling effects are considered. The equivalent model of the interconnects system is determined through an iterative procedure based on the contemporary adoption of the floating random walk method that estimates the grounding and coupling capacitances per unit length and the Picard-Carson procedure that determines the entries of the transmission-matrix (T-matrix) representation at the electrical ports. It is shown that the entries of the T matrix can be efficiently computed through Monte Carlo integration.     

A wavelet-based multiresolution regularized least squaresreconstruction approach for optical tomography

The authors present a wavelet-based multigrid approach to solve the perturbation equation encountered in optical tomography. With this scheme, the unknown image, the data, as well as the weight matrix are all represented by wavelet expansions, thus yielding a multiresolution representation of the original perturbation equation in the wavelet domain. This transformed equation is then solved using a multigrid scheme, by which an increasing portion of wavelet coefficients of the unknown image are solved in successive approximations. One can also quickly identify regions of interest (ROI's) from a coarse level reconstruction and restrict the reconstruction in the following fine resolutions to those regions. At each resolution level a regularized least squares solution is obtained using the conjugate gradient descent method. This approach has been applied to continuous wave data calculated based on the diffusion approximation of several two-dimensional (2-D) test media. Compared to a previously reported one grid algorithm, the multigrid method requires substantially shorter computation time under the same reconstruction quality criterion     

SET logic driving capability and its enhancement in 3-D integrated SET–CMOS circuit

The driving capability of a single-electron transistor (SET) circuit is sensitive to the load and interconnects. We discuss about improving the performance of a SET logic in hybrid SET–CMOS circuit by parameter variation and circuit architecture along with its simulation results. With an intention of studying the SET logic drivability in a SET-only circuit, we examined a circuit composed of 2¹³ SET inverters with its interconnect effect in a 3-D CMOS IC. The schematic of the simulation is based on fabrication model of this large circuit along with interlayer and coupling capacitances of its metallization. The simulation results for delay, bandwidth and power validate the efficiency of a SET circuit.     

区域分裂法在提取多层介质中多导体三维复杂互连结构电磁参数中的应用

本文首次将区域分裂法（ＤＤＭ）用于多层介质中多导体三维复杂互连结构的电磁参数的提取，可以快速、准确地提取复杂互连结构的静态电容矩阵。由于区域分裂法能肥大问题化为若干独立的小问题，不仅可以缩小计算规划，而且可以在该算法框架下灵活地组合各种三维互连结构，具有很强的灵活性，再充分利用集成电路结构分层的特点，对各个小问题采用最恰当的计算方法，从而可大大减少整体设计所需的时间和存储空间。文中给出的计算结果Ａ     

Capacitance extraction for electrostatic multiconductor problems byon-surface MEI

In this paper, on-surface measured equation of invariance (OSMEI) method is implemented for capacitance extraction of electrostatic multiconductor interconnect problems. OSMEI uses the same mesh as that in method of moments (MoM), but generates highly sparse matrices rather than a full matrix. In comparison with “standard” MEI which contains a few finite difference (FD) or finite element (FE) mesh layers, the number of unknowns and the computation memory can be saved. For each OSMEI equation in the multiconductor interconnects, a given node on a given conductor is forced into coupling with the few adjacent nodes on conductor itself and the few sampled nodes on other conductors. Thus, the system sparse matrices can be generated. The convergent behavior of the capacitance with the number of the nodes in the OSMEI equations has been widely investigated, Numerical examples of the capacitance extraction for two-dimensional (2-D) and three-dimensional (3-D) multiconductor interconnects show that the computing errors are within 24%. The OSMEI method may become a powerful technique for the more complex interconnect problems     

A novel dimension-reduction technique for the capacitanceextraction of 3-D VLSI interconnects

In this paper, a new capacitance extraction method called the dimension-reduction technique (DRT) is presented for three-dimensional (3-D) very large-scale integration (VLSI) interconnects. The DRT converts a complex 3-D problem into a series of cascading simple two-dimensional (2-D) problems. Each 2-D problem is solved separately, thus we can choose the most efficient method according to the arrangement of conductors. We have used the DRT to extract the capacitance matrix of multilayered and multiconductor crossovers, bends, vias with signal lines, and open-end. The results are in close agreement with those of Ansoft's SPICELINK and the Massachusetts Institute of Technology's (MIT) FastCap, but the computing time and memory size used by the DRT are several (even ten) times less than those used by SPICELINK and FastCap     

基于边界元法的二维VLSI版图电容提取

提出了一种用边界元法计算ＶＬＳＩ版图电容的方法，通过求解二维拉普拉斯方程，直接得到版图中各种类型的电容的值。该方法提取数据准确简单，占用内存少，计算效率高，且有较高的精度。用该方法对几种典型的ＶＬＳＩ版图电容进行提取，均取得较好的结果。     

A comprehensive 2-D inductance modeling approach for VLSI interconnects: frequency-dependent extraction and compact circuit model synthesis

Although three-dimensional (3-D) partial inductance modeling costs have decreased with stable, sparse approximations of the inductance matrix and its inverse, 3-D models are still intractable when applied to full chip timing or crosstalk analysis. The 3-D partial inductance matrix (or its inverse) is too large to be extracted or simulated when power-grid cross-sections are made wide to capture proximity effect and wires are discretized finely to capture skin effect. Fortunately, 3-D inductance models are unnecessary in VLSI interconnect analysis. Because return currents follow interconnect wires, long interconnect wires can be accurately modeled as two-dimensional (2-D) transmission lines and frequency-dependent loop impedances extracted using 2-D methods . Furthermore, this frequency dependence can be approximated with compact circuit models for both uncoupled and coupled lines. Three-dimensional inductance models are only necessary to handle worst case effects such as simultaneous switching in the end regions. This paper begins by explaining and defending the 2-D modeling approach. It then extends the extraction algorithm to efficiently include distant return paths. Finally, a novel synthesis technique is described that approximates the frequency-dependent series impedance of VLSI interconnects with compact circuit models suitable for timing and noise analysis.     

On the use of spatio-temporal multiresolution analysis in method ofmoments solutions of transient electromagnetic scattering

A novel method of moments approach to the solution of time-domain integral-equation formulation of electromagnetic scattering problems is presented. The method is based on a spatio-temporal multiresolution analysis. This analysis facilitates a basis from which a small number of expansion functions is selected via an iterative procedure and utilized to model the unknown current distribution. In contrast to marching-on-in-time sequential procedures, the proposed method models the unknown current simultaneously at all the time steps within the time frame of interest. This new method is applied to a one-dimensional (1-D) problem of electromagnetic plane wave interaction with a dielectric slab. A comparison of the computed results with results based on the analytic solution demonstrates that the method is capable of attaining accurate results while achieving substantial reduction in computation time and resources     

区域分裂法及其在三维散射中的应用

基于区域分裂（ＤＤＭ）和频域有限差分（ＦＤＦＤ）提出了一种分析三维散射问题的精确高效算法。用区域分裂法可以把原问题分解成若干子问题,可以大大缩小稀疏矩阵的规模,使得求解大尺寸三维散射问题成为可能。文中首先在小尺寸下计算了三维立体柱的散射特性,并和没有进行区域分裂时的ＦＤＦＤ法进行了对比,验证了本算法的正确性;然后又计算了尺寸比较大的三维矩形柱的散射特性,验证了它的高效性。     

A sparse-matrix/canonical grid method for analyzing densely packedinterconnects

In this paper, a fast numerical method called the sparse-matrix/canonical-grid (SM/CG) method is employed to analyze densely packed microstrip interconnects that involve a large number of unknowns. The mixed-potential integral equation is solved by using the method of moments in the spatial domain. The closed-form expressions of the spatial Green's functions of microstrip structures are obtained from the combination of the fast Hankel transform and the matrix pencil method. The Rao-Wilton-Glisson triangular basis functions are used to convert the integral equation into a matrix equation. The matrix equation is then solved by using the SM/CG method, in which the far-interaction portion of the matrix-vector multiplication in the iterative solution is performed by the fast Fourier transforms (FFTs). This is achieved by the Taylor series expansions of the spatial Green's functions about the uniformly spaced canonical grid points overlaying the triangular discretization. Numerical examples are presented to illustrate the accuracy and efficiency of the proposed method. The SM/CG method has computational complexity of O(NlogN). Furthermore, being FFT-based facilitates the implementation for parallel computation     

Three-dimensional biorthogonal multiresolution time-domain method and its application to electromagnetic scattering problems

A three-dimensional (3-D) multiresolution time-domain (MRTD) analysis is presented based on a biorthogonal-wavelet expansion, with application to electromagnetic-scattering problems. We employ the Cohen-Daubechies-Feauveau (CDF) biorthogonal wavelet basis, characterized by the maximum number of vanishing moments for a given support. We utilize wavelets and scaling functions of compact support, yielding update equations involving a small number of proximate field components. A detailed analysis is presented on algorithm implementation, with example numerical results compared to data computed via the conventional finite-difference time-domain (FDTD) method. It is demonstrated that for 3-D scattering problems the CDF-based MRTD often provides significant computational savings (in computer memory and run time) relative to FDTD, while retaining numerical accuracy.     

Three-dimensional modeling from two-dimensional video

This paper presents the surface-based factorization method to recover three-dimensional (3-D) structure, i.e., the 3-D shape and 3-D motion, of a rigid object from a two-dimensional (2-D) video sequence. The main ingredients of our approach are as follows: 1) we describe the unknown shape of the 3-D rigid object by polynomial patches; 2) projections of these patches in the image plane move according to parametric 2-D motion models; 3) we recover the parameters describing the 3-D shape and 3-D motion from the 2-D motion parameters by factorizing a matrix that is rank 1 in a noiseless situation. Our method is simultaneously an extension and a simplification of the original factorization method of Tomasi and Kanade (1992). We track regions where the 2-D motion in the image plane is described by a single set of parameters, avoiding the need to track a large number of pointwise features, in general, a difficult task. Then our method estimates the parameters describing the 3-D structure by factoring a rank 1 matrix, not rank 3 as in Tomasi and Kanade. This allows the use of fast iterative algorithms to compute the 3-D structure that best fits the data. Experimental results with real-life video sequences illustrate the good performance of our approach     

Automatic construction of multiple-object three-dimensional statistical shape models: application to cardiac modeling

A novel method is introduced for the generation of landmarks for three-dimensional (3-D) shapes and the construction of the corresponding 3-D statistical shape models. Automatic landmarking of a set of manual segmentations from a class of shapes is achieved by 1) construction of an atlas of the class, 2) automatic extraction of the landmarks from the atlas, and 3) subsequent propagation of these landmarks to each example shape via a volumetric nonrigid registration technique using multiresolution B-spline deformations. This approach presents some advantages over previously published methods: it can treat multiple-part structures and requires less restrictive assumptions on the structure's topology. In this paper, we address the problem of building a 3-D statistical shape model of the left and right ventricle of the heart from 3-D magnetic resonance images. The average accuracy in landmark propagation is shown to be below 2.2 mm. This application demonstrates the robustness and accuracy of the method in the presence of large shape variability and multiple objects.     

Three-dimensional surface reconstruction using optical flow formedical imaging

The recovery of a three-dimensional (3-D) model from a sequence of two-dimensional (2-D) images is very useful in medical image analysis. Image sequences obtained from the relative motion between the object and the camera or the scanner contain more 3-D information than a single image. Methods to visualize the computed tomograms can be divided into two approaches: the surface rendering approach and the volume rendering approach. In this paper, a new surface rendering method using optical flow is proposed. Optical flow is the apparent motion in the image plane produced by the projection of real 3-D motion onto the 2-D image. The 3-D motion of an object can be recovered from the optical-flow field using additional constraints. By extracting the surface information from 3-D motion, it is possible to obtain an accurate 3-D model of the object. Both synthetic and real image sequences have been used to illustrate the feasibility of the proposed method. The experimental results suggest that the proposed method is suitable for the reconstruction of 3-D models from ultrasound medical images as well as other computed tomograms     

Measurements and extractions of parasitic capacitances in ULSI layouts

This paper deals with the extraction of parasitic capacitances of interconnects in submicron layouts. It is well known that, in integrated circuits, the signal delay due to interconnects is comparable to that of gates. This aspect becomes particularly important, for example, during the design of clock trees in high-speed applications. In general, capacitance extraction is carried out with software tools but they should be validated on a set of geometrical structures, which have been accurately characterized and that are representative of the circuit layouts. Experimental characterization of these structures and their set up in a golden set of measures is still a challenging task. In this paper, we first describe some experimental approaches to measure capacitances of structures from the golden set and in particular we identify a high accuracy transducer based on pass-gate transistors. We then propose a software implementation of the floating random walk algorithm that solves the drawbacks in the extraction of capacitances of interconnects in a nonhomogeneous medium as an industrial layout. Finally, experimental and simulation results are presented, validating the adopted approach.