Browse Prior Art Database

Parallel Event-Driven Simulation

IP.com Disclosure Number: IPCOM000101455D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 4 page(s) / 159K

Publishing Venue

IBM

Related People

Damiano, RF: AUTHOR [+2]

Abstract

Disclosed is a technique for simulating logic circuits, using parallel processors in order to reduce execution time. This technique is a refinement of the conventional event-driven simulation algorithm, which reduces the number of logic gate evaluations by maintaining a schedule of changes to the values on logic nets, and as each time is reached, calculating only those gates whose input nets have changed value.

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

Parallel Event-Driven Simulation

       Disclosed is a technique for simulating logic circuits,
using parallel processors in order to reduce execution time. This
technique is a refinement of the conventional event-driven simulation
algorithm, which reduces the number of logic gate evaluations by
maintaining a schedule of changes to the values on logic nets, and as
each time is reached, calculating only those gates whose input nets
have changed value.

      This disclosed technique is an example of asynchronous parallel
event-driven simulation, where events at different simulation times
can be evaluated concurrently.  Each gate must compute the effect of
events in the correct time order to avoid incorrect simulation
values.  A later event can only be evaluated before or in parallel
with an earlier event if the events take place at different gates,
and if the earlier event does not cause any new event to be scheduled
at the same gate as, but before, the later event.

      To preserve the order of events at each gate, the disclosed
technique maintains a minimum delay relationship between the various
parts of the model, and only simulates an event X if it is earlier
than the time of any other event Y plus the minimum delay between the
gate of X and the gate of Y.  Minimum delay information is maintained
for a gate only with respect to those gates with which it is directly
connected.  Each gate maintains a "stop" time.  Only events earlier
than this stop time can be evaluated.  The stop time of a gate X is
the minimum delay from Y to X.

      This local approach to advancing simulation time eliminates the
global data structures and calculations involved in a complete
minimum delay table.  However, the lack of global information can be
crippling.  Suppose two gates X and Y are connected to each other in
a feedback loop, with a minimum delay on either connection of 10 time
units.  Suppose at time 100 gate X has an event, while gate Y has
none.  Gate X will tell gate Y, "Safe to proceed to time 110."  Gate
Y will in turn tell gate X, "Safe to proceed to time 120."  The
evaluation of the event may not produce any further events.
Simulation should be able to jump forward to the next event, which
may be very far in the future, but gates X and Y can only allow
each other to advance 10 time units at a time, because neither is
sure if the other doesn't have an event.  We disclose below an
approach to reintroducing global information into the simulation
which eliminates this problem, but without the expense of global
causality tables.

      Another problem with asynchronism is making sure that
simulation proceeds somewhat uniformly across the entire simulation
model.  If gate X feeds gate Y, but gate Y does not feed gate X,
even indirectly, then it is possible for the simulation time of gate
X to proceed arbitrarily far ahead of gate Y.  Simulation at Y might
even halt, with all the processing resources dedicated to...