Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-12-23
2001-05-01
Teska, Kevin J. (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06226774
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the automation of asynchronous circuit designs, and more specifically to the generation and implementation of hazard-free asynchronous circuit designs.
2. Background of the Invention
Races and Hazards in Asynchronous Circuits
Problems specific to the design of asynchronous control circuits are races and hazards. In general, a race-free asynchronous circuit is a circuit that will always respond as specified given enough time. That is, if the inputs of the circuit are frozen, and the outputs are observed after all internal switchings have occurred, then the specified output values are always observed. Race-freeness is a necessary condition for a correct asynchronous circuit.
A hazard-free asynchronous circuit is a circuit in which the specified output values are continuously observed and no unexpected values are intermittently observed. This is, if the inputs of the circuit are frozen, the specified output values are continuously observed. Hazard-freeness is also a necessary condition for a correct asynchronous circuit.
Modeling Asynchronous Circuits
Because time is not used to pace the operation of an asynchronous circuit, the specification and correct implementation of an asynchronous circuit design is quite complex. Events, signal transitions, or alternative indicia are generally used as pacers in models where implicit clocks are not part of the semantics.
Signal transition graphs (STGs) are used as a formal basis for the automatic synthesis of asynchronous designs. State graphs (SGs) represent a general model where low level circuit details become more evident. SGs are a generally accepted low level form of representation with well defined semantics that capture every possible event occurrence. Because of the simplicity behind the SG semantics, SGs provide a strong basis to formalize asynchronous circuit properties and to derive clear links between the SG representation and its implementation (i.e., in a circuit design). As is conventionally known in the art, an STG can be transformed into an SG (see, e.g., T. A. Chu, “Synthesis of self-timed VLSI circuits from graph-theoretic specifications”, Ph.D. thesis, MIT, June 1987, hereinafter Chu Thesis).
Informally, an SG has the following basic properties:
1) Any two consecutive states always differ by one and only one bit.
2) The time it takes to make a state transition is any finite non-zero time.
3) A state transition represents an input or an output event.
4) An event is simply a (0 to 1) or a (1 to 0) signal change. SGs are more formally defined in Appendix A.
FIGS. 1
a
through
1
d
show a typical asynchronous circuit design path. First, a high-level description of the asynchronous process in the form of a timing diagram is given. In the example of
FIG. 1
a
, a handshaking status generator timing diagram is shown with inputs signals a and c, and output signal b. In
FIG. 1
b
, an STG is generated from the timing diagram in
FIG. 1
a
. In
FIG. 1
c
(
1
), an SG is conventionally generated from the STG in
FIG. 1
b
(or directly from the timing diagram in
1
a
). Each state transition of the SG captures one possible event occurrence. The SG can be mechanically generated from the STG. In the example of
FIG. 1
c
(
1
), a code conflict occurs at state 001 (explained below) and is resolved by adding a signal as shown in
FIG. 1
c
(
2
). A hazard-free circuit can then be derived from the SG as shown in
FIG. 1
d.
Implementation of Models
To implement an SG (e.g., in a circuit), the states of an SG are interpreted as the states of the domain of a Boolean function that implements an output signal. The output signal can be implemented using pure logic or latches.
Logic can be derived for each output signal in an SG by considering at each state the next state value of the output signal, which is called the implied value. For example, an SG for an asynchronous process with input signals a and b, and output signals c and d is shown in
FIG. 2
a
. At state s
—
3, the implied value of d is ONE. At state s
—
9, the implied value of d is ZERO.
FIG. 2
b
is a Karnaugh map with the implied values for signal d. “DON'T CARES” are assigned to the unreachable states (i.e., 1100, 0011)—these are states that are not specified in the SG. Thus, from the Karnaugh map, signal d can be represented logically as d=ab+b(
c)+ad. The logic representation can be conventionally implemented in a logic circuit.
Another way to implement signal d is to use an asynchronous flip-flop or so-called C-element. The flip-flop has a SET input, a RESET input, and an output, OUT. The flip-flop implements the output signal. As a flip-flop is a memory, it suffices to only generate the logic to either set or reset it. The output signal is implemented with two auxiliary Boolean functions where one is used to set the flip-flop to generate d+(SET) and the other is used to reset the flip-flop to produce d−(RESET). These auxiliary Boolean functions are called SET and RESET functions or solutions. The implementation of the output signal corresponds to the implementation of the SET and RESET functions. The Boolean functions SET and RESET are generally expressed in sum-of-product (SOP) format.
FIG. 2
c
is an example Karnaugh map of a flip-flop-based solution to the SG in
FIG. 2
a
. For the SET Boolean function, it suffices to consider the implied value for output signal d as ONE only at states s
—
3 and s
—
6. It is only at these states that d+ must be fired. At all other states where the implied value of d is ONE, a DON'T CARE is assigned. This assignment corresponds to the fact that after d+ is produced, the flip-flop will keep d at ONE in place of the logic. A ZERO is assigned to all states where the implied value of d is ZERO and DON'T CARES to all unreachable states. The RESET Boolean function is similarly derived to fire d−. The SET and RESET functions are then implemented in logic to drive the asynchronous flip-flop to implement the signal d as figuratively shown in
FIG. 2
c.
For the flip-flop-based solution, a number of states that were assigned a ONE in the pure logic derivation are now assigned DON'T CARES. A flip-flop has the effect of producing additional DON'T CARE states other than the unreachable states. In a pure logic derivation, DON'T CARE states correspond to the unreachable states (or non-specified states) in an SG. In a flip-flop-based derivation, DON'T CARE states correspond to the unreachable state set plus all states where a signal is stable. Thus, flip-flop-based solutions are preferred because of the availability of a larger DON'T CARE set.
Unfortunately, simply deriving the logic or flip-flop-based solutions from SGs as described does not guarantee that the derived circuit is correct. Races and hazards must be eliminated.
Prior Art Failures
One approach is to use complex gates to implement a hazard-free solution. However, the use of complex gates gives rise to new practical problems. As a complex gate is primarily a parallel-serial transistor network, as the complexity of the network grows, so does the number of serial N or P transistors. This significantly slows down in the response of the complex gate. In practice, only integration of simple two-level logic e.g., AND-NORs or OR-NANDs, are available in complex gates. Even if more complex gates are available, an enormous number of complex gate instances are required to cover any possible configuration. In general, a custom design is required for every race-free SG specified.
An improved solution is to substitute derived complex gates with a logic network composed of basic gates (e.g., NANDs, NORs, ANDs, ORs, negation). An architecture is fixed based on an asynchronous C-element flip-flop, and a simplified logic network is constructed from the complex solution to drive the flip-flop. However, a hazard-free network is only guaranteed for the limited class of race-free distributive SGs (distributivity, as defined below, informally means a res
De Man Hugo
Lin Bill
Sawasaki Milton Hiroki
Ykman-Couvreur Chantal
Garbowski Leigh Marie
IMEC
Knobbe Martens Olsen & Bear LLP
Teska Kevin J.
LandOfFree
System and method for generating a hazard-free asynchronous... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for generating a hazard-free asynchronous..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating a hazard-free asynchronous... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2523533