A linear-time eigenvalue solver for finite-element-based analysis of large-scale wave propagation problems in on-chip interconnect structures
In this paper the analysis and design of next-generation VLSI circuits using accurate electromagnetics-based models result in numerical problems of very large scale is presented. Typically, the solution of a problem with N parameters requires at least O(N) computation. With next generation VLSI circuits, however, even O(N) is prohibitively high since N is very large. The method that partially addresses this issue was developed for full-wave modeling of large-scale interconnect structures. In this method, a number of seeds (a seed has a unique cross section) are first recognized from an interconnect structure. In each seed, the original wave propagation problem is represented as a generalized eigenvalue problem. The complexity of solving 3D interconnects of O(N) is then overcome by seeking the solution of a few 2D seeds, which is then post-processed to obtain the solution of the original 3D problem through the development of an on-chip mode-matching technique. The computational bottleneck is the solution of a generalized eigenvalue problem. Efficient algorithms such as ARPACK  still require O(M2) storage and operations due to a dense matrix-vector multiplication. We present an algorithm that provides a solution to the generalized eigenvalue problem with O(M) complexity, thus paving the way for the full-wave simulation of next generation VLSI circuits.
Eigenvalues and eigenfunctions, finite element analysis, integrated circuit interconnections, Matrix algebra, VLSI
Date of this Version
2008 IEEE Antennas and Propagation Society International Symposium and USNC/URSI National Radio Science Meeting (2008) 4 pp.-4 pp.;
Publisher retains content copyright.