Title :
Parallel algorithms for inductance extraction of VLSI circuits
Author :
Mahawar, Hemant ; Sarin, Vivek
Author_Institution :
Dept. of Comput. Sci., Texas A&M Univ., College Station, TX, USA
Abstract :
Inductance extraction involves estimating the mutual inductance in a VLSI circuit. Due to increasing clock speed and diminishing feature sizes of modern VLSI circuits, the effects of inductance are increasingly felt during the testing and verification stages. Hence, there is a need for fast and accurate inductance extraction software. A generalized approach for inductance extraction requires the solution of a dense complex symmetric linear system that models mutual inductive effects among circuit elements. Iterative methods are used to solve the system without explicit computation of the matrix itself. Fast hierarchical techniques are used to compute approximate matrix-vector products with the dense system matrix. This work presents an overview of a new parallel software package for inductance extraction of large VLSI circuits. The technique uses a combination of the solenoidal basis method and effective preconditioning schemes to solve the linear system. Fast multipole method (FMM) is used to compute approximate matrix-vector products with the inductance matrix. By formulating the pre-conditioner as a dense matrix similar to the coefficient matrix, we are able to use FMM for the preconditioning step as well. A two-tier parallelization scheme allows an efficient parallel implementation using both OpenMP and MPI directives simultaneously. The experiments conducted on various multiprocessor machines demonstrate the portability and parallel performance of the software.
Keywords :
VLSI; electronic engineering computing; inductance; iterative methods; matrix algebra; message passing; open systems; parallel algorithms; parallel programming; MPI; OpenMP; VLSI circuit; dense system matrix; fast multipole method; inductance extraction; iterative method; matrix-vector product; multiprocessor machines; parallel algorithm; parallel software package; solenoidal basis method; symmetric linear system; Circuit testing; Clocks; Inductance; Iterative methods; Linear systems; Parallel algorithms; Software packages; Software performance; Symmetric matrices; Very large scale integration;
Conference_Titel :
Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International
Print_ISBN :
1-4244-0054-6
DOI :
10.1109/IPDPS.2006.1639316