1	CE653 – Asynchronous Circuit Design Instructor: C. Sotiriou
2	Contents Indicating Logic Basics Dual-Rail and Other types of Encoding Indicating Logic Types Strongly vs. Weakly Indicating DIMS (Delay Insensitive Minterm Synthesis) NCL (Null Convention Logic) Threshold Gates NCL Flow NCLX (NCL with eXplicit Completion) NCLX Output Completion Network Dual-Polarity DR Logic Monotonic Boolean Networks (MBN) Support for Negative Gates (NAND, NOR, … etc.)
3	Indicating Logic Indicating logic is able to generate a data-dependent Completion Detection (CD/DONE) signal Indicates that valid data have arrived at the C.L. cloud’s outputs What was there before valid data arrived? difficult separating successive data values (Valid_n, Valid_n+1, …) Intermediate value between valid data used (NULL/Spacer) Indicating circuit operation is two-phase: NULL, DATA, NULL, DATA, …
4	Indicating Logic - Encodings Indicating circuit operation is two-phase: NULL, DATA, NULL, DATA, … Boolean Logic encodes two values: 0 or 1, T or F We need DATA and NULL, i.e. three values 0 or 1 or NULL, T or F or NULL Simplest ternary logic is dual-rail Need two wires per Boolean signal
5	Indicating Logic – Strong vs. Weak Indication Dual-rail encoding allows us to detect DATA arrival at Inputs or Outputs Definition[Strongly/Weakly Indicating Logic] A circuit is strongly-indicating iff it waits for all of its inputs to arrive before it computes and produces valid outputs, as well as for all of its inputs to become NULL before it produces NULL outputs
6	Indicating Logic – Orphan Wires/Gates Orphans represent unacknowledged circuit nodes at the POs Definition[Wire Orphan] An orphan wire, or wire orphan is an indicating circuit wire, a signal transition of which, triggered by a given and valid input transition, is NOT acknowledged by a respective signal transition on any PO Definition[Gate Orphan] An orphan gate, or gate orphan is an indicating circuit gate, a signal transition through which, triggered by a given and valid input transition, is NOT acknowledged by a respective signal transition on any PO
7	Indicating Logic – Orphan Wires/Gates Thick lines data evaluation Dotted lines wire orphans which do not propagate, and are unacknowledged, but must be cleared before new data
8	Indicating Logic – Orphan Wires/Gates Orphan on lower input wire of g3 causes erroneous output on z1
9	Indicating Logic – Orphan Wires/Gates In this example, orphans propagate through gates For proper reset dotted lines MUST return to zero But this cannot be checked by inspection of the circuit’s outputs!
10	DIMS – Delay Insensitive Minterm Synthesis
11	DIMS DIMS is the simplest form of DR logic Each signal is instantiated in .t and .f rails Truth-table Minterms directly translated to 2-level DR logic 1^st DR circuit level is C-Elements, 2^nd level is OR gates
12	DIMS (Delay Insensitive Minterm Synthesis) Four-input NAND Example in DIMS
13	NCL – Null Convention Logic
14	Threshold Gates – DIMS Generalisation
15	Threshold Gates – DIMS Generalisation Threshold gates generalisation of C-elements Threshold Gate Output Rises when the number of threshold inputs rises Threshold Gate Output Falls when all inputs fall
16	Threshold Gates – 2 of 3 with hysteresis Hysteresis means Sequential Threshold 23 gate switches: high when 2 of 3 inputs are high low when all 3 inputs are low Boolean Function Format: z = ab + ac + bc + z(a + b + c)
17	NCL Flow 1 – Separate C.L., Registers Combinational Logic and Registers are separated
18	NCL Commercial Flow – Synopsys DC Based
19	NCL Optimisation with Synopsys DC Dual-rail expansion Two phases (set and reset) are separated Set phase ensures circuit functionality Reset phase is implied Optimizations are applied to the set phase
20	NCL Gate Images – Output Rise (Set) Equivalent
21	Image of D-R NAND Gate No Difference to DIMS implementation of standard-cell gates
22	NCL Flow Detailed Example – Step 1 Conventional RTL Description Multiplexer
23	NCL Flow Detailed Example – Step 2 Conventional RTL to Boolean Gates Synthesis
24	NCL Flow Detailed Example – Step 3 Define new type for signal logic – dual_rail_logic type dual_rail_logic is record rail1 : std_logic ; rail0 : std_logic ; end record; Overload common operators/gates:
25	NCL Flow Detailed Example – Step 4 Naive semi-static DIMS implementation – 114 transistors - may be reduced to 63 transistors by merging C-elements with OR-gates - versus 14 for a synchronous circuit
26	NCL Flow Detailed Example – Set Phase During the set phase C-elements in D-R gates behave like AND gates
27	NCL Flow Detailed Example – Step 5 Dual-Rail Expansion Step
28	Set Phase Image Circuit after DR Expansion This circuit contains DCs x.t.x.f = 1 is DC
29	NCL Flow Detailed Example – Step 6 Technology independent optimization (DCs) Technology-mapping of image gates to NCL library gates
30	NCL Flow Detailed Example – Step 7 Final NCL circuit Image gates (Set phase) are replaced by sequential NCL standard-cells with reset pull-ups
31	NCL Flow Results Typically, actual area overhead is >2.5X
32	NCLX – NCL with eXplicit completion
33	NCLX – Explicit Completion Aims to reduce huge area overhead of NCL Strongly-Indicating Logic (alike DIMS/NCL) Key Idea Separate Functional Part (Set Functions for DR Outputs) and Delay-Insensitive Part (Resetting and Orphans) Four Boolean Networks Dual-Rail Functional Part (DR Inputs à DR Outputs) Input Completion Part for Strong-Indication Also referred to as.go signal Intermediate Node Completion Part for Orphan Elimination Output Completion Part for Strong-Indication Input Completion and Local Completion are merged
34	NCLX
35	Dual-Rail Network Conversion - MBN Weakly-Indicating No input, local node completion Timing assumptions required for orphan nodes/gates
36	Monotonic Boolean Network Boolean Network consists of Monotonic Nodes Must be Unate Unate = node function contains each variable in either non-complemented or complemented form
37	Two Phase DR Network Elastic Operation
38	Two Phase DR Network Elastic Operation
39	Two Phase DR Network Elastic Operation
40	Complex NCLX Example
41	NCLX Results Good improvement over NCL Difficult to reduce area further without sacrificing delay-insensitivity
42	Timing Assumptions for DR Logic
43	Dual-Polarity/Phase DR Logic
44	Dual-Polarity DR Logic Methodology All methodologies so far only support positive polarity gates (positive unate) AND/OR, etc. Dual-Polarity DR Logic supports both Positive and Negative Polarity Gates e.g. NAND, NOR, etc. CMOS Negative gates are faster than positive gates Positive gates are Negative gates + inverter General methodology for Boolean Network transformation to a Monotonic Boolean Network Logic Synthesis level
45	Dual-Polarity DR Logic Methodology
46	MBNs (Monotonic Boolean Networks) We can allow for BN nodes to be phased as negative or positive Definition[Increasing/Decreasing Node] BN node f is increasing (decreasing) in positive (negative) variable x_i à x_i: 0→1 (1→0), f cannot change 1→0 (0 →1) Definition[Unate Function] BN function f unate in x_i, iff f is increasing or decreasing in x_i Definition[Positive/Negative Nodes] Node n_iwith local function f_i is +ve (-ve) x_i is +ve (-ve) and f_i is increasing in x_i,OR x_i is -ve (+ve) and f_i is decreasing in x_i. Definition [Monotonic Node] A node is monotonic if it is either +ve or –ve. Definition [Monotonic Boolean Network] A BN is MBN if all its nodes are monotonic MBN is hazard-free under monotonic input transitions
47	Monotonic Boolean Networks Assign polarity to every node to check monotonicity.
48	Monotonic Boolean Networks
49	MBN Transformations Key Questions: given a BN, how do we transform it to an MBN? given an MBN, which transformations and optimizations can we apply to reduce to another MBN? Answers: Provide two transformation procedures, based on the dual-rail code, for generating an MBN from a generic BN: Technology-Independent (TI) Conversion Technology-Mapped (TM) Conversion Provide a set of hazard-non-increasing transformations on MBNs.
50	Technology-Independent DR Conversion For each PI x, create x^t and x^f representing the true and false evaluations of x. For each node implementing y_i = f_i(x₁, …, x_n), create two nodes: y^t_i = DR(f_i(x₁, …, x_n)) and y^f_i = DR(f_i’(x₁, …, x_n)) y = x’, special case, y^t = x^f, y^f = x^t Define DR recursively (based on Shannon Expansion Th.): DR(0) = 0, DR(1) = 1 DR(x.f_x + x’.f_x’) = x^t.DR(f_x) + x^f.DR(f_x’) Theorem[DR Conversion] Given function y = f(x₁, …,x_n), under the assumption that xⁱ = x^t_i = x^f_i’ it holds that y = y^t = y^f’ Proof: by induction on function DR
51	Technology-Independent DR Conversion y = a’b + b(c + d’) would be converted into: y^t = DR(a’b + b(c + d’)) = a^tb^f + b^t(c^t + d^f) y^f = DR(a’b + b(c + d’))’ = (a^f + b^t)(b^f + c^fd^t) How do I convert? Use Shannon’s Expansion Theorem assume that x_i = x^t_i = x^f_i’, for all nodes/POs x in circuit Use the SIS dr package!
52	Technology-Independent Conversion - Example Original BN: y = a’b + b(c + d’)
53	Technology-Independent Conversion - Example Dual-Rail Conversion: y^t = a^tb^f + b^t(c^t + d^f) y^f = (a^f + b^t)(b^f + c^fd^t)
54	Technology-Independent Conversion - Example Technology Mapping to a library
55	Technology-Mapped Conversion For each gate, producing signal y^t_i, from signals y^t_j, …, y^t_k, add a dual gate, based on De Morgan’s law. Label each node as +ve or –ve, starting from the PO’s, according to gate polarities In case of multiple paths from POs to the node, consider the longest For each inconsistently labeled gate input or PI, which is, invert and connect to its dual
56	Technology-Mapped Conversion - Example Original technology-mapped circuit:
57	Technology-Mapped Conversion – Example – Phase Labeling
58	Technology-Mapped Conversion – Example – Phase Correction
59	Technology-Mapped Conversion – Example – Final Result
60	Hazard-non Increasing Transformations Set of transformations that preserve MBN: De Morgan’s laws. Dual global and global flow. Tree decomposition. Gate replication. Collapsing. Kernel-factoring. Cube-factoring.
61	Fast Reset The MBN approach is NOT delay-insensitive Set function performs Completion-Detection Reset is timed Note that typically MBN requires reset at every cycle This is an issue for speed Fast Reset Approach Slice DR Logic Circuit with multiple Reset Levels Reset each level Use a delay element to wait for Reset
62	Dual-Phase DR Results – Scatter 1
63	Dual-Phase DR Results – Scatter 2
64	Dual-Phase DR Results – Scatter 3
65	Dual-Rail MBN Use Cases Synchronous Environment Check against a clock signal Asynchronous Environment Exploit data-dependent latencies
66	Advanced DR Methodologies
67	Gated DR Circuits
68	Gated DR Circuits GDR motivation High degree of power overhead of monotonic DR circuit (~x9) Gated Logic Logic subcircuit prevented from switching Gating Logic Logic controlling (enabling/disabling) when the Gated Logic is prevented from switching Blocking Elements Gates which block signal transitions propagation
69	Gated DR Circuits – Basics A Circuit node is controllable if a subset of its inputs is able to determine node’s value A node implementing the AND logic function is controllable, as the evaluation of any of its inputs to 0 is able to determine node’s value. A node implementing the XOR logic function is not controllable, as every input value is needed in order to evaluate node’s value.
70	GDR Example
71	Mixed SRDR Circuits
72	Mixed SRDR Circuits DR circuits benefits and drawbacks Data-dependent latency (+) Large area overhead (-) Large power overhead (-) NULL (RESET) phase is slow!!! (-) Why not implemented Mixed SR and DR Logic? Slice C.L. circuit’s Logic Levels vertically Use conventional Boolean (SR) logic for first logic levels of C.L. Traversed anyway by most exercised circuit paths Use DR logic only for deep logic levels Exhibit data-dependent elasticity Hide NULL phase of DR Logic Overlap with SR evaluation!!!
73	Mixed SRDR Circuit Architecture DR Logic may RESET while SR Delay is evaluating Hide DR RESET Overhead!!!
74	Mixed SRDR Circuit Example