Partitioning algorithms for parallel circuit simulation
Yeh, David Ching-kai
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20676
Description
Title
Partitioning algorithms for parallel circuit simulation
Author(s)
Yeh, David Ching-kai
Issue Date
1990
Doctoral Committee Chair(s)
Rao, Vasant B.
Department of Study
Engineering, Electronics and Electrical
Discipline
Engineering, Electronics and Electrical
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Language
eng
Abstract
Circuit simulation is an indispensable tool in the design and analysis of Very Large Scale Integrated (VLSI) circuits. The most widely used circuit simulators rely on direct methods and offer the most accurate, reliable, and technology-independent means of simulating integrated circuits. The simulation process is inherently very computation intensive and, hence, can require a significant portion of the computational resources available for the development of VLSI circuits. With the use of multiprocessor computers becoming more widespread, there exists an opportunity to speed up the simulation by partitioning the circuit so that the computation may be spread among the processors. To accomplish this, the circuit is partitioned into subcircuits using a node tearing method. If the circuit matrix is ordered subcircuit by subcircuit followed by the tearing nodes, then the matrix takes a bordered-block-diagonal form and the LU-factorization of the diagonal blocks may take place in parallel. This thesis defines the important objectives for this partitioning task and presents two algorithms that may be used to meet the partitioning goals. The first algorithm is an iterative improvement algorithm and the second is a network flow algorithm. Partitioning results and speedups are given for a variety of circuits.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
