Asynchronous controllers effectively control high concurrence of datapath operations for high speed. Signal Transition Graphs (STGs) can effectively represent these concurrent events. However, highly concurrent STGs cause the state explosion problem in asynchronous synthesis tools. Many small but highly concurrent STGs cannot be synthesized to obtain control circuits. Moreover, STGs also lead to some control-time overhead of the four-phase handshake protocol. In this paper, we propose a method for deriving the serial control nodes from Control Data Flow Graphs (CDFGs) such that the concurrence of datapath operations is still preserved. The STGs derived from the serialized control nodes are serial STGs which are simpler for synthesis than the concurrent STGs. We also propose an implementation using these serialized controllers to generate local clocks at any necessary times. The implementation results in very small control-time overhead. The experimental results show that the number of synthesis states is proportional to the number of control signals, and the circuits with satisfiable small control-time overhead are obtained.

Deep submicron technology calls for new design techniques, in which wire and gate delays are accounted to have equal or nearly equal effect on circuit behavior. Asynchronous speed-independent (SI) circuits, whose behavior is only robust to gate delay variations, may be too optimistic. On the other hand, building circuits totally delay-insensitive (DI), for both gates and wires, is impractical because of the lack of effective synthesis methods. The paper presents a new approach for synthesis of globally DI and locally SI circuits. The method, working in two possible design scenarios, either starts from a behavioral specification called Signal Transition Graph (STG) or from the SI implementation of the STG specification. The method locally modifies the initial model in such a way that the resultant behavior of the system does not depend on delays in the input wires. This guarantees delay-insensitivity of the system-environment interface. The suggested approach was successfully tested on a set of benchmarks. Experimental results show that DI interfacing is realized with a relatively moderate cost in area and speed (costs about 40% area penalty and 20% speed penalty).

Although many successful asynchronous control circuit synthesis methods are available, it is still unwieldy to conceive and describe the behaviors of a number of controllers which constitute a control unit of a target system manually. In this paper, an automatic and systematic method to derive an efficient asynchronous control unit from a system specification, a control data flow graph (CDFG), is suggested. In order to acquire an asynchronous control unit of acceptable quality, a new process-oriented method is proposed. In this method, the resulting asynchronous control unit has complete separation of 'execution controllers' and 'execution order controllers' according to the hierarchical decomposition of a given CDFG. This distributive feature leads to a significant improvement in area, performance, implementability and synthesis time for the derived asynchronous control units.

In this paper, we propose an approach to test pattern generation for Speed-Independent (SI) asynchronous control circuits. Test patterns are generated based on a specified sequence, which is derived from the specification of a target circuit in the form of a Signal Transition Graph (STG). Since the sequence represents the behavior of a circuit only with stable states, the state space of the circuit can be represented as reduced one. A product machine, which consists of a fault-free circuit and a faulty circuit, is constructed and then the specified sequence is applied sequentially to the product machine. A fault is detected when the product machine produces inconsistency, i.e., output values of a fault-free circuit and a faulty circuit are different, and the sequentially applied part of the sequence becomes a test pattern to detect the fault. We also propose a test generation method using an undetectable fault identification as well as the specified sequence. Since the reduced state space is a subset of that of a gate level implementation, test patterns based on a specification cannot detect some faults. The proposed method identifies those faults with a circuit topology in advance. BDD is used to implement the proposed methods efficiently, since the proposed methods have a lot of state sets and set operations. Experimental results show that the test generation using a specification achieves high fault coverage over single stuck-at fault model for several synthesized SI circuits. The proposed test generation using a circuit topology as well as a specification decreases execution time for test generation with negligible cost retaining high fault coverage.

This paper proposes a synthesis method to obtain speed-independent asynchronous circuits directly from signal transition graph (STG) specifications with single cycle signals which can be non-persistent and have free-choice operations. The resulting circuits are implemented with basic gates and asynchronous latches, and operate correctly under finite but unbounded gate delays and the zero wire delay assumptions. The proposed method introduces 5 types of lock relations to implement a non-persistent STG. A non-persistent STG can be implemented if every non-persistent signal to a signal t is super-locked with t. The resulting circuits are optimized by extracting of literals, mapping onto asymmetric C-elements, etc. Experimental results show that the proposed synthesis method outperforms the existing synthesis systems such as SYN and SIS.

Signal Transition Graphs (STG's) are Petri nets, which were introduced to represent a behavior of asynchronous circuits. To derive logic functions from an STG, the reachability graph should be constructed. In the verification of STG's some method based on an Occurrence net (OCN) and its prefix, called an unfolding, has been proposed. OCN's can represent both causality and concurrency between two nodes by net structure. In this paper, we propose a method to derive a logic function by generating sub state space of a given STG using the structural properties of OCN.

Signal Transition Graphs (STG'S) [1] are Petrinets [2], which were introduced to represent a behavior of asynchronous circuits. To derive logic functions from an STG, the reachability graph should be constructed. In the verification of STG's some method based on Occurrence nets (OCN) and its prefix, called unfollding, has been proposed [3], [4]. OCN's can represent both causality and concurrency between two nodes by net stryctyre. In this paper, we propose an efficient algorithm to derive a logic function by generating sub-state space of a given STG using the structural properties of OCN. The proposed algorithm can be seem as a parallel algorithm for deriving a logic function.

In this paper, an approach to derive a logic function of asynchronous circuits from a graph-based model called Signal Transition Graphs (STG) is discussed. STG's are Petri nets, whose transitions are interpreted as a signal transition on the circuit inputs or gate outputs, and its marking represents a binary state of the circuit. STG's can represent a behavior of circuit, to derive logic functions, however, the reachability graph should be constructed. In the verification of STG's some method based on Occurrence nets (OCN) and its prefix, called unfolding, has been proposed. OCN's can represent both causality and concurrency between two nodes by net structure. In this paper, we propose a method to derive a logic function by generating substate space of a given STG using the structural properties of OCN. The proposed method can be seem as a parallel algorithm for deriving a logic function.