Browse Prior Art Database

Waveform Relaxation Sub-Circuit Scheduling That Balances Parallel Processor Workload

IP.com Disclosure Number: IPCOM000101249D
Original Publication Date: 1990-Jul-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 91K

Publishing Venue

IBM

Related People

Johnson, TA: AUTHOR

Abstract

Disclosed is a technique to minimize the number of parallel processors needed to analyze a given VLSI circuit using waveform relaxation while balancing the workload between processors. Additionally, inter-processor communication is minimized.

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

Waveform Relaxation Sub-Circuit Scheduling That Balances Parallel Processor Workload

       Disclosed is a technique to minimize the number of
parallel processors needed to analyze a given VLSI circuit using
waveform relaxation while balancing the workload between processors.
Additionally, inter-processor communication is minimized.

      Circuit simulation through waveform relaxation is well suited
for implementation in a parallel processing environment.  However, in
order to balance workload, and maximize processor utilization, it is
necessary to carefully schedule and dispatch sub-circuits to
available processors. Absence of an efficient scheduling technique
can result in non-optimal processor utilization and excessive
inter-processor communication.

      The technique described herein addresses both of these issues.
It should be noted that the subject technique has been developed for
use with a message-passing parallel processing architecture, for
which communication may be a significant factor in performance.
However, the basic technique is applicable to any parallel processing
architecture including shared memory machines.

      It is assumed that the circuit topology to be analyzed has
already been partitioned into strongly-connected components (SCCs),
and a basic scheduling algorithm has been applied that identifies the
earliest level at which input waveforms for each SCC are available.
Inherent to this approach is the assumption that a  Gauss-Seidel
algorithm will be applied to implement waveform relaxation.

      The first step is to create ordered sets of SCCs (threads) that
must be analyzed sequentially.  By building sequential threads, one
guarantees that if the SCCs assigned to each thread are analyzed by
the same processing element, inter-processor communication will be
minimized.  Waveforms needed at each level will be available from
analysis of the SCC that was just analyzed.  There is no way to
eliminate fan- out of signals, but at least one level of fan-out is
accommodated on the same processor that is performing the analysis.

      The next step is to combine the sequential threads into chains
of SCCs to minimize the number of processing elements required and
maximize their utilization.  This is accomp...