A Linear-Time Eigenvalue Solver for Finite-Element-Based Analysis of Large-Scale Wave Propagation Problems in On-Chip Interconnect Structures

摘要

The analysis and design of next-generation VLSI circuits using accurate electromagnetics-based models result in numerical problems of very large scale. 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. In [1], a 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 procedure is rigorous, and entails no approximation. The size of the system matrix constructed by this method, M, is the number of unknowns in a 2D seed residing on either the x-y or y-z plane (y is the stack growth direction). Taking a test-chip interconnect as an example, M is 6678 while N is 10.1 million. With a larger example, M is 222k while N is 336 million. While the M parameter model was successfully constructed in [1], the solution of the associated modeling problem with O(M) complexity still remains open. The computational bottleneck is the solution of a generalized eigenvalue problem. Efficient algorithms such as ARPACK [2] still require O(M{sup}2) 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.