From nowick@cs.columbia.edu Wed Nov 30 01:21:24 1994
Date: Tue, 29 Nov 94 20:15:40 EST
From: Steven Nowick
To: asynchronous-private@cs.columbia.edu
Subject: ["Alex Yu. Kondratyev" : Re: Question
concerning delay hazards]
Cc: nowick@cs.columbia.edu
Content-Length: 5129
X-Lines: 116
Status: RO
Date: Fri, 25 Nov 1994 14:26:01 +0900
From: "Alex Yu. Kondratyev"
>From: Luciano Lavagno
>In fact, I would claim that most of the available synthesis methods work in
>I/O mode.
>From: Ken Stevens
>Unfortunately there is no known methodology for synthesizing
>sum-of-products circuits free of delay hazards (using unbounded delays).
>From: jeroen@es.ele.tue.nl (Jeroen Rutten)
>A lot of these methods however make severe assumptions in the
>implementation phase. They merge gates into complex ones and declare them
>atomic, or they suffer from an overhead penalty of at least 100 % because they
>use dual-rail encoding.
>My question was intended to find out if there exist methods assuming
>Input-Output mode which use conventional two-level logic /
>multi-level logic and which can take into account delay hazards.
>From: Steven Nowick
>When considering delay hazards in I/O mode circuits, it is important
>to consider the circuit model. An SI or quasi-DI circuit should be
>robust regardless of gate delays. However, in bounded-delay designs
>meant to operate in I/O mode (Lavagno's earlier work, Myers' work,
>etc.), delay hazards can cause incorrect operation -- correct me
>if I am wrong, Luciano/Chris.
Two issues are probably mixed together here:
(1) Delay hazards, which cause short pulses on the primary outputs because some
of the internal signal transitions left unacknowledged and input
transitions are two close together (for more precise definition, see, e.g.,
Luciano's book, p. 67). In the theory of speed-independent circuits
delay hazards are relevant to the "term take-overs".
and
(2) delay faults, that faults in the circuit operations due to the fact that
delay assumptions are not valid for the circuit after fabrication.
Steve Nowick probably has in mind that delay Faults might be dangerous for
the bounded-delay techniques. However, they might be as well dangerous
for the SI/QDI if wire delays (isocronic forks) are out of relational bounds
and for FM models (if assuptions about the environment are wrong).
As far as we can see Luciano's technique allows to produce circuits which
are free of delay hazards under the bounded wire delay model and also allows
to use "conventional" two-level/multi-level logic (hazard-free preserving
transformations.
We also know at least two relatively realistic
techniques that suggest methods to solve this problem
for the unbounded gate delay model. Both based on simple gates
rather than complex gates.
1. One is the method suggested by Peter Beerel (Stanford univ.) in
which each signal of State Graph is implemented by C-latch with S
and R' inputs. Functions for S and R' are implemented in SOP and
are extracted in traditional way from the original SG. To avoid
hazards in combinational circuits for R' and S if more than one
cube are driving the change of the signal on the output of the
latch the switching of these cubes has to be acknowledged (for this
the additional inputs are introduced in signal networks for another
signals). This procedure is not always possible and sometimes it is
needed to introduce additional signals to make the original
networks for R and S simpler. For more details see:
\bibitem{beer92b}
P.~A. Beerel and T.~H. Meng.
\newblock Automatic gate-level synthesis of speed-independent circuits.
\newblock In {\em Proceedings of the International Conference on Computer-Aided
Design}, November 1992.
2. Another method was suggested by us. The very similar architecture
was used: SOP implementation for R and S functions with the output
RS- or C-latch. The main difference is that the formal Monotonous
Cover (MC) condition for
the SOP implementation of R and S to be hazard-free requires that
only one cube (AND-gate in SOP) can drive the output of latch to
change the value. If this condition is ensured in original STG or
SG (there is an efficient way of checking it) then there are no
hazards (delay hazards included)
in implementation of signal networks (i.e., they will be
hazard-free under the unbounded delay model). If the
MC condition is violated then by adding
extra signals it is always possible to reduce the original
specification to the specification which meets the MC condition.
There are two ways to do it:
1. by the reduction to the satisfiability problem (see Kondratyev, A.;
Kishinevsky, M.; Lin, B.; Vanbekbergen, P.;
Yakovlev, A.
Basic Gate Implementation of Speed-Independent Circuits. In Proc
31th Design Automation Conference, June 6--10, 1994, p.56-62)
2. by the equivalent transformations on the STG level (the set of the
effective transformations was suggested in technical report:
Kondratyev A., Kishinevsky M., Yakovlev A. "Monotonous cover
transformations for si-implementation of asynchronous circuits". The
technical report can be taken by ftp to u-aizu.ac.jp,
cd doc/Tech-Report/1994, file 94-2-002.ps.Z.)
Hope this info will help.
Alex Kondratyev
Michael Kishinevsky