Browse Prior Art Database

Parallel Waveform Relaxation Analysis of Circuits with Global Feedback

IP.com Disclosure Number: IPCOM000103682D
Original Publication Date: 1993-Jan-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 3 page(s) / 135K

Publishing Venue

IBM

Related People

Johnson, TA: AUTHOR [+2]

Abstract

Disclosed is a new waveform relaxation based circuit simulation technique developed specifically for implementation in a parallel processing environment that provides greater parallelism and faster convergence for circuits with global feedback loops than is achievable with other published methods.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Parallel Waveform Relaxation Analysis of Circuits with Global Feedback

       Disclosed is a new waveform relaxation based circuit
simulation technique developed specifically for implementation in a
parallel processing environment that provides greater parallelism and
faster convergence for circuits  with global feedback loops than is
achievable with other published methods.

      The primary challenge facing any implementation of parallel
waveform relaxation (WR) is to consistently achieve high processor
utilization and parallel efficiency.  The efficiency of waveform
relaxation circuit analysis strongly depends on the ability to
partition a large circuit into many smaller subcircuits which are
weakly coupled to each other.  Circuits which partition into weakly
coupled subcircuits can always be solved much faster using waveform
relaxation than conventional methods.  However, the presence of
global feedback loops introduces strong coupling which restricts
subcircuit partitioning.

      In conventional sequential WR algorithms, feedback loops may be
broken or absorbed inside of a subcircuit.  The broken feedback loops
force portions of a circuit to be solved at each iteration with at
least some input waveforms not precisely known for the current
iteration.  This generally will result in more waveform iterations
than is the case in the absence of such broken loops, since some of
the feedback waveforms are in error.  Most Gauss-Seidel (G-S)
algorithms apply a basic scheduling technique where the WR relaxation
sweep spans all non-converged subcircuits.  The subcircuits are
scheduled according to an ordering which is determined by the signal
flow.  Hence, signals may be propagated which are in error, causing
unnecessary iterations.  The impact of this is more severe in early
iterations, where few, if any, of the subcircuits are dormant.  The
G-S level of each subcircuit, which is assigned by a levelling
algorithm, is important since errors in early stages impact all
subcircuits connected at later levels.

      Feedback loops which are absorbed in a subcircuit maintain
strict G-S ordering but they often create large subcircuits.  This
has a negative impact on load balancing, matrix size and multi-rate
properties of the WR algorithm.

      The above observations as well as extensive experimentations
lead us to the following approach.  Note that all feedback loops are
assumed to be automatically identified by the partitioner.
1.  Break all feedback loops, independent of size.
2.  Break each feedback loop between subcircuits in an attempt to
balance workload among the processors.  It was determined in [1] that
the...