EECS 298-11: CAD Seminar
Wednesday, March 19, 1997, 5pm
Cory Hall--Hogan Room

	Analysis of Combinational Cycles in Synchronous Circuits

			Tom Shiple
			Synopsys Inc
			Mountain View

We analyze the logical behavior of synchronous circuits, at the gate and
flip-flop level, containing combinational cycles.  A combinational cycle is a
structural cycle containing only logic gates.  Combinational cycles are
sometimes introduced to reduce the area of a circuit or to hold state, or they
can be the unintended consequence of composing circuits in a hierarchical
fashion (e.g., composing Mealy machines). The presence of such cycles can
cause unstable behavior at the outputs of a circuit, but this is not
necessarily always the case.  This work seeks to determine when cycles are
harmless, and when they are not.

In this talk, we introduce three different classes of "well-behaved" circuits.
Informally, we say that a circuit is well-behaved if for every input, the
output stabilizes to a unique value within a bounded amount of time.  For each
class, we discuss the complexity of the corresponding decision problem, and a
procedure to decide the class.  In addition, if a circuit is determined to be
within a given class, then a new circuit can be generated with the same
input/output behavior, but without combinational cycles.  This is an important
utility, as many CAD tools do not accept circuits with combinational cycles.

(Joint work with Gerard Berry, Bob Brayton, Alberto Sangiovanni-Vincentelli,
and Vigyan Singhal.)