⬇ Download Markdown  ·  ⬇ Download LaTeX  ·  ⬇ original  ·  view original

An FFT-Accelerated Inductance Extractor for Voxelized Structures

Abdulkadir C. Yucel and Hakan Bagci Division of Computer, Electrical and Mathematical Science and Engineering King Abdullah University of Science and

Technology (KAUST) Thuwal 23955-6900, Saudi Arabia [email protected]

[email protected] Ioannis P. Georgakis and Athanasios G.

Polimeridis Center for Computational Data-Intensive

Science and Engineering Skolkovo Institute of Science and

Technology Moscow 143026, Russia [email protected]

[email protected] Abstract—A fast Fourier transform (FFT)-accelerated integral equation solver for efficiently and accurately extracting inductance of structures discretized by voxels is described. This new solver called VoxHenry, unlike its predecessor FastHenry, can accurately account for the current flow around corners of structures using a carefully selected set of basis functions. VoxHenry solves the matrix system obtained upon discretization of the volume integral and current continuity equations iteratively. Matrix-vector multiplications required by the iterative solver are carried out using FFTs and the number of iterations is reduced using a sparse preconditioner. The accuracy and efficiency of VoxHenry are demonstrated via its application to inductance extraction of a circular coil.

Keywords—Fast Fourier transform, inductance extraction, interconnects.

I. I NTRODUCTION

The design of high-speed integrated circuits calls for efficient and accurate inductance extractors to produce circuit representations that can be used for signal timing, signal integrity, and cross-talk analyses. Inductance extractors that have been developed so far require structures to be discretized with volume filaments [1], tetrahedrons [2], or surface elements [3]. That said, there is a need for inductance extractors capable of working on structures discretized with voxels. Such an extractor would be extremely easy to incorporate into voxel-based virtual fabrication environments and suitable for modeling the structures during unit process steps of iterative design explorations. Additionally, its acceleration using fast Fourier transform (FFT) techniques [4]- [9] is straightforward.

In this work, an FFT-accelerated inductance extractor, named VoxHenry, is developed for solving a coupled system of volume integral and current continuity equations on voxelized structures. This new inductance extractor is more accurate and efficient than its predecessor FastHenry [1] thanks to algorithmic developments listed next. (i) VoxHenry expands the current density in terms of piecewise constant and linear basis functions permitting its accurate representation around corners. (ii) During the iterative solution of the matrix system obtained upon discretization, VoxHenry uses FFTs to expedite

I. P. Georgakis, A. G. Polimeridis, and J. White were supported by a grant

from Skoltech as part of the Skoltech-MIT Next Generation Program.

Jacob K. White Department of Electrical Engineering

and Computer Science Massachusetts Institute of Technology

Cambridge, MA 02139, USA

[email protected] the matrix-vector multiplications. (iii) The number of iterations is reduced using a sparse preconditioner. Numerical results demonstrating the accuracy, efficiency, applicability of VoxHenry are provided.

II. F ORMULATION

Let V represent the volume of a non-magnetic structure with conductivity σ , which resides in an unbounded background medium with permittivity ε 0 and permeability µ 0 . The structure is excited by source(s) operated at frequency ω . The structure is discretized by K t voxels of size ∆ d , K t = K x × K y × K z , where K x , K y , and K z are the numbers of voxels along x , y , and z directions; ∆ d is selected to be equal to or less than the skin depth at ω . Let K denote the number of non-empty voxels (with non-zero σ ), each of which has one node on each of its six surfaces; let M denote the total number of these nodes.

VoxHenry solves the coupled system of volume integral and current continuity equations:

( ) 0 ( ) ( ) , { , } 4 V j dv V µ ω φ σ π ′ ′ ′ + = −∇ ∈ ′ − ∫ J r J r r r r r r (1) ( ) 0 ∇ ⋅ = J r , (2)

where J ( r ) and φ ( r ) represent the current density and scalar potential. To solve (1) and (2), J ( r ) is expanded in terms of divergence-free basis functions as:

( ) ( ) 5 1 1 K i i k k k i I = = ≈ ∑∑ J r b r (3)

where I k i is the unknown current coefficient,

() () () 1 2 3 ˆ ˆ ˆ , , k k k = = = br x br y br z , ( ) ( ) ( ) ( ) 4 1 ˆ ˆ k k k d x x y y − =∆ − − − b r x y ,

(4)

( ) ( ) ( ) ( ) k k k d x x y y =∆ − − − b r x y , ( ) ( ) ( ) ( ) ( ) 5 1 ˆ ˆ ˆ 2 k k k k d x x y y z z − =∆ − + − − − b r x y z ,

th (6) and ( x k , y k , z k ) are the coordinates of center of k voxel. Substituting (3) into (1), testing the resulting equation with b l j , j = 1,  ,5 , and enforcing (2) (in the form of normal current density continuity) across the voxel surfaces, yield a linear system of equations with dimensions (5 K + M ) × (5 K + M ) :

0 0 T jω   + −     =             V I R L A Φ A . (7) Here, V , 1 2 3 4 5 [ ;;; ; ] = I I II I I , and Φ are the excitation vector and the vectors of u nknown cu rrent a nd pot ential coefficients, r espectively. The e ntries of sp arse matrix m n A , 1, ,5 n K =  , 1, , m M =  , are assign ed a s t he val ue of t h n basis fun ction on t h m no de, multiplie d wit h 1±. The entries o f V are obta ined by summi ng the columns o f T A corresponding to the p ort nod es. Matr ix R consists of K K × diagonal b locks i i l k R with ent ries ( )() 1 , k i i k k V σ − br br , 1, , k K = , wh ere , Ω ⋅ ⋅ d enotes st andard inner pr oduct with support Ω and k V is th e support o f th k vox el. Sim ilarly, matrix L consists of K K × blocks j i l k L with the entries: ( ) ( ) 0 , 4 k l ik j i j l k l V V dv µ π ′ ′ = ′ − ∫ b r L b r r r . (8) Blocks j i L are either zer o or full m atrices. The multip lication of full ma trix j i L with iI , i. e., j j i i = C L I , re quires 2 () OK applicable to voxelized circular coils (without remeshing) due to reasons explained in [11].

filament-based approaches, such as FastHenry, can not model the 3D currents in a circular coil accurately and are not directly operations and is reduced to O ( K t log K t ) using FFTs [4]-[9]:

( )  j = IFFT ∑ i   ji * FFT (  i ) , current distribution at 3 GHz. (9) where   ji = FFT (  ji ) ,  ji is the circulant tensor with the entries computed using (8),  i is a tensor formed by using current coefficients and zero padding,  j is the resultant tensor that provides the entries of C j . Dimensions of all tensors are 2 K x × 2 K y × 2 K z . Note that the multiplications of sparse matrices A and A T with I and Φ , respectively, require only O ( K ) operations. To ensure the rapid convergence of iterative solution of (7), a sparse preconditioner,

1 0 T jω −   + − =    R D A P A , (10)

is applied to matrix-vector multiplications; here D = diag ( L ) .

III. N UMERICAL R ESULT

VoxHenry is used for extracting the inductance of a circular coil with conductivity of 5.8 × 10 7 S/m and loop and tube radii of 150 μm and 5 μm . The coil positioned on the xy plane is excited from a spacing in the lower part of the coil between x = 155 μm and x = 155.5 μm . Discretization parameters 0.5 μm , 5 K = 2969300 and M = 1867 528 . The ∆ d = inductance of the coil is computed at frequencies ranging from 1 Hz to 1 THz and compared to the values provided by an analytical formula [10] [Fig. 1 (a)]. An excellent match between results is observed. In addition, current distribution on the coil at 3GHz is plotted in Fig. 1 (b). For this problem, VoxHenry computes the inductance at one frequency point in 2.93 minutes.

IV. C ONCLUSION

An FFT-accelerated inductance extractor, VoxHenry, and its application to a voxelized circular coil are presented. The R EFERENCES [1] M. Kamon, M. J. Tsuk, and J. K. White, “FASTHENRY: A multipole-

accelerated 3-D inductance extraction program,” IEEE Trans. Microw. Theory Techn., vol. 42, pp. 1750-1758, 1994. [2] K. Jackman and C. J. Fourie, “Tetrahedral modeling method for

inductance extraction of complex 3-D superconducting structures,” IEEE Trans. Appl. Supercond., vol. 26, no. 3, pp. 1-5, April 2016. [3] M. Al-Qedra, J. Aronsson, and V. Okhmatovski, “Surface integral

equation formulation for inductance extraction in 3-D interconnects,” IEEE Microw. Compon. Lett., vol. 20, no. 5, pp. 250-252, May 2010. [4] M. F. Catedra, E. Gago, and L. Nuno, “A numerical scheme to obtain

the RCS of three-dimensional bodies of resonant size using the conjugate gradient method and the fast Fourier transform,” IEEE Trans. Antennas Propagat., vol. 37, pp. 528-537, 1989. [5] A. C. Yucel, L. J. Gomez and E. Michielssen, “Compression of

translation operator tensors in FMM-FFT-accelerated SIE solvers via Tucker decomposition,” IEEE Antennas Wireless Propag. Lett., vol. 16, pp. 2667-2670, 2017. [6] A. G. Polimeridis, J. F. Villena, L. Daniel, and J. K. White, “Stable FFT-

JVIE solvers for fast analysis of highly inhomogeneous dielectric objects,” J. Comp. Phys., vol. 269, pp. 280-296, 2014. [7] A. C. Yucel, “Uncertainty quantification for electromagnetic analysis via

efficient collocation methods,” Ph.D. thesis, University of Michigan, Ann Arbor, 2013. [8] A. C. Yucel, L. J. Gomez, Y. Liu, H. Bagci, and E. Michielssen, “A

FMM-FFT accelerated hybrid volume surface integral equation solver for electromagnetic analysis of re-entry space vehicles,” in CNCUSNC/URSI National Radio Sci. Meet., 2014. [9] A. C. Yucel, Y. Liu, H. Bagci, and E. Michielssen, “An FMM-FFT

accelerated integral equation solver for characterizing electromagnetic wave propagation in mine tunnels and galleries loaded with conductors,” in Proc CNC-USNC/URSI National Radio Sci. Meet., 2014. [10] Radio Instruments and Measurements - Circular C74. Washington, DC:

U.S. Government Printing Office, 1924. [11] A. C. Yucel, I. Georgakis, A. G. Polimeridis, H. Bağcı, and J. White,

“VoxHenry: A fast Fourier transform - accelerated 3D inductance extraction program for voxelized geometries,” IEEE Trans. Microw. Theory Techn., in Press.