A parallel low-rank multilevel matrix compression algorithm for parasitic extraction of electrically large structures

ABSTRACT

Simulation of distributed electromagnetic effects of electrically large structures is no longer a luxury but a necessity in the accurate prediction of modern day circuit performance. In this regard, integral equation based methods have steadily gained in popularity but suffer from the time and memory bottlenecks arising from the resultant dense matrix. Fast linear complexity solvers have been introduced in the past but with the growing complexity of circuit layouts parallel implementations are the only viable options in addressing practical circuit layouts. In this paper, we present a parallel implementation of the low-rank compression based fast solver with linear cost reduction capacity with respect to the number of processors. The main problems in parallelizing a hierarchical algorithm are discussed and the advantages of the implemented scheme are highlighted. The new solver enables the simulation of full-chip problems consisting of millions of unknowns with acceptable accuracy and modest time and memory requirements.

REFERENCES

• 1: R. Coifman, V. Rokhlin and S. Wandzura, "The fast multipole method for the wave equation: a pedestrian prescription", IEEE Trans. Antennas Propagat. Mag., vol. 35, pp. 7--12, June 1993.
• 2: L.J. Jiang and W.C. Chew, "Modified fast inhomogeneous plane wave algorithm from low frequency to microwave frequency", IEEE Antennas and Propag. Soc. Int. Symp., vol. 2 , pp. 22--27, June 2003.
• 3: E. Bleszynski, M. Bleszynski and T. Jaroszewicz, "AIM: Adaptive Integral Method for Solving large-scale electromagnetic scattering and radiation problems", Radio Science, vol. 31, pp. 1225--1251, Sept-Oct 1996.
• 4: N. Yuan, T.S. Yeo, X.C. Nie and L.W. Li, "A Fast Analysis of Scattering and Radiation of Large Microstrip Antenna Arrays", IEEE Trans. on Antennas and Propagation, vol. 51, pp. 2218--2226, Sep 2003.
• 5: Z. Zhu, B. Song and J. White, "Algorithms in FastImp: a fast and wide-band impedance extraction program for complicated 3-D geometries", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, pp. 981 -- 998, July 2005
• 6: Sharad Kapur , David E. Long, IES3: a fast integral equation solver for efficient 3-dimensional extraction, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.448-455, November 09-13, 1997, San Jose, California, United States
• 7: D.Gope and V.Jandhyala, "Oct-Tree Based Multilevel Low-Rank Decomposition Algorithm for Rapid 3D Parasitic Extraction", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol-23, pp. 1575 -- 1580, Nov. 2004.

INDEX TERMS

General Terms:
Algorithms, Design, Performance

Keywords:
MPI, compression, parallel, parasitics