Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-05-07
2003-02-25
Thomas, Tom (Department: 2811)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06526542
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to an asynchronous circuit with completion detection, and a system and method for designing the same. More specifically, the present invention is directed to conversion of a Boolean logic circuit to an asynchronous circuit, optimizing the completeness detection aspects of the circuit, and a system and method for designing the same.
2. Discussion of Background Information
Asynchronous circuits have been proposed that are intended to operate without a clock. One asynchronous logic paradigm is disclosed in U.S. Pat. No. 5,305,463 (“the '463 logic system”), issued Apr. 19, 1994, which is incorporated herein by reference in its entirety. Several data representations are discussed, but in one representation a signal may assume a DATA value or a NULL value. A DATA value, for example, might be a numeric value ZERO or ONE, or a logic value TRUE or FALSE, or another meaning not related to binary or Boolean logic representations.
In such a representation, a signal may take the form of two signal lines, with a first signal line designated to mean ZERO or FALSE, and the second signal line designated to mean ONE or TRUE. Each line may assume one of two states: “ASSERTED” or “NULL.” The meaning of the pair of signal lines is determined by the states of the lines. The pair of lines together represents a single binary variable (such as a single bit of binary data) and have four possible states: (1) ASSERTED, ASSERTED, (2) ASSERTED, NULL, (3) NULL, ASSERTED, and (4) NULL, NULL.
The first state (ASSERTED/ASSERTED) is not permitted. The second state (NULL/ASSERTED) represents/signifies meaningful data of a value ZERO or FALSE. The third state (ASSERTED/NULL) represents/signifies meaningful data of value ONE or TRUE. The fourth state (NULL/NULL) can be thought of as indicating that the variable is in a NULL state and has not assumed a meaningful value.
This representation is known as a multi-rail representation of mutually exclusive assertion groups for asynchronous circuits. Dual-rail representation (i.e., two signal lines with three states: NULL, DATA ZERO and DATA ONE) is a specific subset of multi-rail representation. As used herein, DATA collectively refers to DATA ZERO and DATA ONE states for a dual rail representation (and for any other DATA X states for multi-rail lines with three or more signal lines).
Asynchronous circuits designed consistent with the above require some type of indication that the computations are completed. A circuit is “indicating” if each signal transition “a”, on an input or internal signal in the circuit, is a cause of a transition “b”, on an output signal, that could not occur without “a”. If an asynchronous circuit is not “indicating,” then additional circuitry may be necessary to ensure correct asynchronous operation. Delay Insensitive Minterm Synthesis (DIMS) is a method that uses C-elements as the basis of such additional “completeness” circuitry. A drawback of DIMS is that it requires a great deal of space and logic elements, with a correspondingly high cost. Further, since the functional aspects of the underlying circuit and the completion aspects are intertwined, it is difficult to reduce or optimize the completion aspects of the circuit without adversely affecting the functionality of the circuit.
At present, while the overwhelming majority of circuit designers can design circuits using Boolean logic, only a small number of designers exist who can design asynchronous circuits that operate using multi-rail signals. While there are certain available methodologies for converting a Boolean expression into an asynchronous circuit (such as DIMS), these methodologies result in large circuits with correspondingly high design and production costs.
SUMMARY OF THE INVENTION
The present invention addresses the drawbacks of the prior art.
According to an embodiment of the invention, a design methodology is provided for converting a Boolean logic circuit into an asynchronous circuit.
According to another embodiment of the invention, a design methodology is provided for adding and optimizing completeness detection in an asynchronous circuit.
According to an embodiment of the invention, a method for designing a multi-rail asynchronous circuit is provided. The method includes providing a circuit having n circuit paths, defining a plurality of nodes, each node having an n-rail signal output and at least one n-rail signal input, each rail of the n-rail signal input being connected to a different one of the plurality of circuit paths, and adding completeness detection to each of the plurality of nodes, completion detection for a downstream one of the plurality of nodes being at least partially based on completion detection from an upstream one of the plurality of nodes. Signals propagate along the plurality of data paths independent of the completeness detection.
According to another embodiment of the invention, a method is provided for designing a multi-rail asynchronous circuit that operates using n-rail signals, the circuit including at least one primary input, at least one primary output, and at least one intermediate output. The method includes providing a circuit having n circuit paths, defining a plurality of nodes, each node having at least one n-rail signal output and at least one n-rail signal input, each of the n circuit paths providing a rail of the n-rail signal input, adding completeness detection to at least those nodes that generate intermediate outputs, completion detection for a downstream one of the plurality of nodes being at least partially based on completion detection from an upstream one of the plurality of nodes; and optimizing the completeness detection. The circuit is capable of propagating signals along the plurality of circuit paths independent of the completeness detection.
According to yet another embodiment of the invention, a method is provided for designing a dual-rail asynchronous circuit from a Boolean expression. The method includes converting the Boolean expression into a corresponding first plurality of circuits along a first data path, converting each of the plurality of circuits into an unate circuit, providing a dual circuit along a second data path, each of the dual circuits being the dual of a corresponding unate circuit, each of the unate circuits and the corresponding one of the dual circuits defining a node, and adding completeness detection circuitry for at least each intermediate output between the nodes such that completion detection of at least one downstream node is based at least partially on completion detection of at least one upstream node. The completeness detection circuitry does not affect propagation of signals through the nodes.
According to still another embodiment of the invention, a method is provided for adding completeness to an n-rail asynchronous circuit including a plurality of nodes. The method includes assigning to a completion tree at least all primary inputs to the plurality of nodes and intermediate outputs between any of the plurality of nodes, optimizing the completion tree, comprising at least one of removing duplicate completion detection of any signal, testing whether the plurality of nodes is indicating for any primary input, testing whether the plurality of nodes is indicating for any intermediate output, removing completion detection circuitry that proves unnecessary in response to a result of the optimizing, and designing the circuit based on a result of the removing.
According to still yet another embodiment of the invention, a method is provided for adding completion to an n-rail circuit including a plurality of nodes, each node including n rail circuits that define an n-rail output, the n-rail circuit having k primary inputs. The method includes, for each node, providing circuit logic that can obtain a completion signal for each input to the node, providing circuit logic that can issue a data signal representing the presence of DATA on the n rails of the n-rail output, and inputting the output of the
Steptoe & Johnson
Theseus Logic Inc.
Thomas Tom
Vu Hung Kim
LandOfFree
Multi-rail asynchronous flow with completion detection and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-rail asynchronous flow with completion detection and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-rail asynchronous flow with completion detection and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3178717