Browse Prior Art Database

Sub-Circuit Partitioning for Fast Gauss-Seidel Waveform Relaxation Circuit Analysis in a Parallel Processing Environment

IP.com Disclosure Number: IPCOM000113090D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 152K

Publishing Venue

IBM

Related People

Johnson, TA: AUTHOR [+2]

Abstract

Disclosed is a technique to substantially increase the speed of circuit analysis using a Gauss-Seidel waveform relaxation algorithm executing in a parallel processing environment. When operating in a sequential machine environment, a Gauss-Seidel implementation will, in general, out-perform Gauss-Jacobi. The preordering of computations dictated by a Gauss-Seidel implementation results in fewer waveform iterations, and therefore faster solution. However, this ordering of computations inhibits parallelism. This disclosure describes a simple technique that can be applied to a large percentage of circuits to increase the parallelism of a Gauss-Seidel implementation while maintaining the algorithm's fast waveform convergence behavior.

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

Sub-Circuit Partitioning for Fast Gauss-Seidel Waveform Relaxation
Circuit Analysis in a Parallel Processing Environment

      Disclosed is a technique to substantially increase the speed of
circuit analysis using a Gauss-Seidel waveform relaxation algorithm
executing in a parallel processing environment.  When operating in a
sequential machine environment, a Gauss-Seidel implementation will,
in general, out-perform Gauss-Jacobi.  The preordering of
computations dictated by a Gauss-Seidel implementation results in
fewer waveform iterations, and therefore faster solution.  However,
this ordering of computations inhibits parallelism.  This disclosure
describes a simple technique that can be applied to a large
percentage of circuits to increase the parallelism of a Gauss-Seidel
implementation while maintaining the algorithm's fast waveform
convergence behavior.

      Information on signal propagation through a circuit is used by
a Gauss-Seidel algorithm to order the computations.  This ordering
reduces the number of waveform iterations required to solve a
circuit.  The key to proper ordering and fast Gauss-Seidel
convergence is precise knowledge of data flow within a circuit.  When
a circuit includes global feedback, it is often difficult to
correctly determine signal propagation.  Sequential implementations
of Gauss-Seidel algorithms generally characterize feedback loops
according to their estimated delay, and process them differently
depending upon the estimated delay.  Feedback loops that are
characterized as "long" are generally cut.  During each waveform
iteration, the input signals applied to sub-circuits forming such
loops are defined by waveforms solved during the previous waveform
iteration.  Feedback loops characterized as "short" are merged into a
single sub-circuit.  In essence, short feedback loops are removed by
localizing them.  For sequential implementations, this approach works
well.

      It should be realized that broken feedback loops are inherently
a departure from Gauss-Seidel.  Even when Gauss-Seidel is used to
solve the majority of a circuit, broken feedback loops are
essentially an implementation of Gauss-Jacobi.  Broken feedback loops
force portions of a circuit to be solved at each iteration with at
least some input data not precisely known for the current iteration.
In general, this will result in more waveform iterations than one
would expect in the absence of such broken loops.  Merged feedback
loops, on the other hand, maintain strict Gauss-Seidel ordering at
the expense of larger and fewer sub-circuits.  It is possible to
properly choose where to break feedback loops such that parallelism
is increased while the fast convergence properties of Gauss-Seidel
are not further compromised.  Referring to Fig. 1, the feedback loop
shown can be broken at several different places.

      If the loop is broken at "A", the Gauss-Seidel ordering as
shown in Fig. 2 will result.  Breaking the...