1	CE653 – Asynchronous Circuit Design Instructor: C. Sotiriou
2	Contents STG Presentation Add: Synthesis Conditions for Implementability Boundedness, Consistency, CSC Encodability Slides 36, 37 Irreducible vs. Reducible CSC Monotonic Covers Definition
3	Understanding SI Model Check circuit for disabled transitions in State Graph: There are no disabled transitions 1à1 or 0à0 in the State Graph Thus circuit is SI This analysis assumes the unbounded delay model
4	Understanding SI Model Check circuit for disabled transitions in State Graph: Disabled transitions 1à1 or 0à0 in the State Graph Thus circuit is not SI Circuit is also not semi-modular This analysis assumes the unbounded delay model
5	Design flow
6	Specification
7	Token flow
8	State graph
9	Next-state functions
10	Gate netlist
11	Design flow
12	VME Bus Example
13	STG for READs
14	NEED Choice to select between READ OR WRITE
15	NEED Choice to select between READ OR WRITE
16	SI Asynchronous Circuit Synthesis Goal: Derive a hazard-free circuit under a given delay model and mode of operation Speed Independence Unbounded gate / environment delays Certain wire delays shorter than certain paths in the circuit Wires LONGER than GATES!!! SI Implementability Conditions Consistency Signal transitions alternate in all PTnet paths and thus Reachability Graph Complete State Coding (CSC) Each pair of Reachability Graph States have different state encoding, or if the share the same encoding, they enable different non-input (output) signals è distinguishable Persistency è Semi-Modularity Outputs cannot be disabled once enabled, Inputs cannot be disabled by Outputs
17	Design flow
18	STG for the READ cycle
19	Reachability Graph – Binary Encoding
20	Reachability Graph – Binary Encoding
21	Defining Excitation and Quiescent Regions
22	Forming the Next State Function
23	Extracting the Boolean Expression of the Next State Function
24	Design flow
25	Concurrency Reduction (Manual/Automatic) at State Graph Level
26	Concurrency Reduction – Migration to STG/PTnet Level
27	State Encoding Conflicts
28	Resolving Conflicts through Signal Insertion
29	Signal Insertion
30	Design flow
31	Complex-Gate Implementation
32	Implementability Conditions - Revisited Consistency Rising and falling transitions of each signal alternate in any trace Complete state coding (CSC) Next-state functions correctly defined Persistency No event can be disabled by another event (unless they are both inputs)
33	Implementability Conditions - Revisited Consistency + CSC + persistency There exists a speed-independent circuit that implements the behavior of the STG under the assumption that any Boolean function can be implemented with one complex gate
34	Understanding Persistency
35	Simple STG Example - 1
36	Simple STG Example - 2
37	Simple STG Example - 3
38	C-Element Based Implementation Correctness Conditions: S (set) and R (reset) must be mutually exclusive S must cover ER(z+) and must not intersect ER(z-) U QR(z-) R must cover ER(z-) and must not intersect ER(z+) U QR(z+)
39	Monotonic Covers Definition[Monotonic Cover] Cover Cube C is a monotonic cover for ER(a) iff: C covers all states ER(a) C covers no states outside ER(a) U QR(a) C changes only once inside QR(a*) A Monotonic Cover ensures SI implementation using simple gates
40	C-Element Based Example
41	C-Element Based Example If the Reset R = a’c’ has an unbounded delay Then, starting from state 0000: a+ ; R- ; b+ ; a- ; c+ ; S+ ; d+ ; The a-, c+ transition can cause a hazard at the Reset logic
42	C-Element Based Example
43	C-Element Based Example
44	Technology Mapping C-Element Implementations
45	Speed-Independence - Summary Implementability conditions Consistency Complete State Coding (CSC) Persistency Circuit architectures Complex (hazard-free) gates C elements with monotonic covers
46	Synthesis Exercise Derive circuits for outputs x and z Both complex gate and C-element based implementations
47	Synthesis Exercise – x Output
48	Synthesis Exercise – z Output
49	Logic Decomposition - Example
50	Logic Decomposition - Example Can we decompose yz into an independent AND gate?
51	Logic Decomposition - Example Introduce common factor signal s = yz
52	Logic Decomposition - Example Signal s can now be added back to the STG/PTnet
53	Timing Assumptions Relative Timing Assumptions can significantly reduce circuit complexity Timing assumptions effectively remove or make redundant PTnet/STG edges Extreme example: Ain is not necessary, as controller and receiver are faster than sender Each timing assumption must be guaranteed by timing constraints at schematic or physical level or even system level Relative Timing Assumptions can be used to optimise timing by a great deal!
54	Timing Assumptions Example – SI Netlist
55	Timing Assumptions Example – SI Netlist – Adding Timing Assumptions
56	Timing Assumptions Example – SI Netlist – Adding Timing Assumptions
57	Timing Assumptions Example – SI Netlist – Adding Timing Assumptions – State Graph
58	Timing Assumptions Example – SI Netlist – Adding Timing Assumptions – State Graph
59	Timing Assumptions Example – SI Netlist – Adding Timing Assumptions – State Graph
60	Timing Assumptions Example – SI Netlist – Adding Timing Assumptions – Boolean Logic Original Circuit had CSC issue!!!
61	Timing Assumptions Example – SI Netlist – Adding Timing Assumptions – Boolean Logic Timing assumptions add DC and resolve CSC!!!
62	Timing Assumptions Example – SI Netlist with Timing Constraint
63	Timing Assumptions Example – SI Netlist with Timing Constraint
64	STG Logic Synthesis - Conclusions STGs have a high expressiveness power at a low level of granularity (similar to FSMs for synchronous systems) Very effective approach for asynchronous control circuit design Not suitable for datapath design Circuits with choice require attention for determinism (no confusion!) Synthesis from STGs can be fully automated Synthesis tools often suffer from the state explosion problem (symbolic techniques are used) State Space generation is exponential