Files in this item
Files  Description  Format 

application/pdf 8908850.pdf (5MB)  (no description provided) 
Description
Title:  Parallel Processing Techniques for the Simulation of MOS VLSI Circuits Using Waveform Relaxation 
Author(s):  Smart, David William 
Doctoral Committee Chair(s):  Trick, Timothy N. 
Department / Program:  Electrical Engineering 
Discipline:  Electrical Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Engineering, Electronics and Electrical
Computer Science 
Abstract:  Waveform relaxation algorithms for the simulation of MOS circuits exhibit natural parallelism, arising from the intrinsic partitioning of the circuit into subcircuits which are solved separately during the iterative solution process. Investigated in this thesis is the extent to which the overall run time of a simulation can be reduced by utilizing the natural parallelism of waveform relaxation on parallel processors. Four parallel waveform relaxation algorithms are considered, based on the GaussSeidel and GaussJacobi relaxation methods, in which parallelism is exploited at the individual time point level or at the time window level. The algorithm with the fastest run time depends on the characteristics of the circuit being simulated and on the number of processors used. The GaussJacobi method with time point pipelining is introduced as a highly parallel algorithm which can outperform the other algorithms when the number of processors is large. A theorem is presented comparing the GaussSeidel and GaussJacobi methods, as applied to the solution of a set of linear algebraic equations of the type which occur at each time point in the simulation of MOS circuits. GaussJacobi is shown to be asymptotically faster than GaussSeidel when the number of processors is sufficiently large. Simplified speedup estimates are used in a presimulation selection procedure which selects the fastest of the parallel waveform relaxation algorithms prior to performing the simulation of a given circuit on a given number of processors. More accurate estimates of the potential parallel processing speedups, neglecting overhead, are produced by the PARASITE parallel simulation time estimator, which uses CPU time measurements from a uniprocessor simulation to estimate the parallel run time on any number of processors. PARASITE estimates indicate that speedups of about one order of magnitude are possible for 1000transistor circuits on 32 processors, where the speedup is measured with respect to GaussSeidel waveform relaxation on a single processor. The parallel waveform relaxation algorithms have been implemented in programs which run on an 8processor Alliant FX/8 multiprocessor. Speedups within 11% to 21% of the PARASITE estimates are achieved. 
Issue Date:  1988 
Type:  Text 
Description:  146 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1988. 
URI:  http://hdl.handle.net/2142/69421 
Other Identifier(s):  (UMI)AAI8908850 
Date Available in IDEALS:  20141215 
Date Deposited:  1988 
This item appears in the following Collection(s)

Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois