DDCAarm - Ch3 - New

Chapter 3
Digital Design and Computer Architecture: ARM® Edition

Sarah L. Harris and David Money Harris
Digital Design and Computer Architecture: ARM® Edition © 2015 Chapter 3 <1>
Chapter 3 :: Topics
• Introduction
• Latches and Flip-Flops
• Synchronous Logic Design
• Finite State Machines
• Timing of Sequential Logic
• Parallelism
Introduction
• Outputs of sequential logic depend on current
and prior input values – it has memory.
• Some definitions:
– State: all the information about past inputs
necessary to explain its future behavior
– Latches and flip-flops: state elements that store
one bit of state
– Synchronous sequential circuits: combinational
logic followed by a bank of flip-flops
Sequential Circuits
• Give sequence to events
• Have memory (short-term)
• Use feedback from output to input to store
information
State Elements
• The state of a circuit influences its future
behavior
• State elements store state
– Bistable circuit
– SR Latch
– D Latch
– D Flip-flop
Bistable Circuit
• Fundamental building block of other state
elements
• Two outputs: Q, Q
• No inputs
I1 Q
Q Q
I2 I1
I2 Q
Bistable Circuit Analysis
• Consider the two possible cases:
0
– Q = 0: 1
I1 Q
then Q = 0, Q = 1 (consistent) 0 1
I2 Q
– Q = 1: 1
I1 Q
0
then Q = 1, Q = 0 (consistent)
1 0
I2 Q
• Stores 1 bit of state in the state variable, Q (or Q)

• But there are no inputs to control the state
SR (Set/Reset) Latch
• SR Latch R
N1 Q
N2 Q
S
• Consider the four possible cases:
– S = 1, R = 0
– S = 0, R = 1
– S = 0, R = 0
– S = 1, R = 1
SR Latch Analysis
– S = 1, R = 0: R
0
1
N1 Q
then Q = 1 and Q = 0 0
Set the output 10

1 N2
0
Q
S
– S = 0, R = 1: R
1
N1
0
Q
1
then Q = 0 and Q = 1
0
Reset the output S
0 N2
1
Q
SR Latch Analysis
– S = 0, R = 0: Qprev = 0 Qprev = 1
then Q = Qprev R
0
N1
0
Q
R
0
N1
1
Q
Memory!
0 N2 Q 0 N2 Q
S S
– S = 1, R = 1:
1
R 0
then Q = 0, Q = 0 N1 Q
0
Invalid State
0
Q ≠ NOT Q S
1 N2
0
Q
SR Latch Symbol
• SR stands for Set/Reset Latch
– Stores one bit of state (Q)
• Control what value is being stored with S, R
inputs
– Set: Make the output 1 SR Latch
Symbol
(S = 1, R = 0, Q = 1)
– Reset: Make the output 0 R Q
(S = 0, R = 1, Q = 0)
S Q
• Avoid invalid state
(when S = R = 1)
D Latch
• Two inputs: CLK, D
– CLK: controls when the output changes
– D (the data input): controls what the output changes to
• Function
– When CLK = 1,
D Latch
D passes through to Q (transparent) Symbol
– When CLK = 0,
Q holds its previous value (opaque) CLK
• Avoids invalid case when D Q
Q ≠ NOT Q Q
D Latch Internal Circuit
CLK R CLK
D R Q Q
S
D Q
S Q Q
D
Q
CLK D D S R Q Q
0 X X 0 0 Qprev Qprev
1 0 1 0 1 0 1
1 1 0 1 0 1 0
D Flip-Flop
• Inputs: CLK, D
D Flip-Flop
• Function Symbols
– Samples D on rising edge of CLK
• When CLK rises from 0 to 1, D
passes through to Q D Q
• Otherwise, Q holds its previous Q
value
– Q changes only on rising edge of CLK
• Called edge-triggered
• Activated on the clock edge
D Flip-Flop Internal Circuit
• Two back-to-back latches (L1 and L2) controlled by
complementary clocks
• When CLK = 0 CLK
– L1 is transparent
– L2 is opaque
– D passes through to N1 CLK CLK
N1
• When CLK = 1 D D Q D Q Q
– L2 is transparent L1 Q L2 Q Q
– L1 is opaque
– N1 passes through to Q
• Thus, on the edge of the clock (when CLK rises from 0 1)
– D passes through to Q
D Latch vs. D Flip-Flop
CLK
D Q D Q
Q Q
CLK
Q (latch)
Q (flop)
Registers: Multi-bit Flip-Flop
CLK
D0 D Q Q0
CLK
D1 D Q Q1
4 4
D3:0 Q3:0
D2 D Q Q2
D3 D Q Q3
Enabled Flip-Flops
• Inputs: CLK, D, EN
– The enable input (EN) controls when new data (D) is stored
• Function
– EN = 1: D passes through to Q on the clock edge
– EN = 0: the flip-flop retains its previous state
Internal
Circuit
Symbol
EN CLK
0
D Q Q D Q
D 1
EN
Resettable Flip-Flops
• Inputs: CLK, D, Reset
• Function:
– Reset = 1: Q is forced to 0
– Reset = 0: flip-flop behaves as ordinary D flip-flop
Symbols
D Q
r
Reset
• Two types:
– Synchronous: resets at the clock edge only
– Asynchronous: resets immediately when Reset = 1
• Asynchronously resettable flip-flop requires
changing the internal circuitry of the flip-flop
• Synchronously resettable flip-flop?
• Two types:
– Synchronous: resets at the clock edge
only
– Asynchronous: resets immediately
when Reset = 1
• Asynchronously resettable flip-
flop requires changing the
internal circuitry of the flip-flop
• Synchronously resettable flip-flop
Settable Flip-Flops
• Inputs: CLK, D, Set
• Function:
– Set = 1: Q is set to 1
– Set = 0: the flip-flop behaves as ordinary D flip-flop
Symbols
D Q
s
Set
Sequential Logic
• Sequential circuits: all circuits that aren’t
combinational
• A problematic circuit:
X
X Y Z
Y
Z
• No inputs and 1-3 outputs 0 1 2 3 4 5 6 7 8 time (ns)
• Astable circuit, oscillates

• Period depends on inverter delay
• It has a cyclic path: output fed back to input
SystemVerilog Description
module flop(input logic clk, d,
output logic q);
always_ff @(posedge clk)

q <= d;
endmodule
• Multi-input XOR: Odd parity

module flopenr(input logic clk, en, reset, d,
output logic q);
always_ff @(posedge clk, posedge reset)

if (reset) q <= 0;
else if (en) q <= d;
endmodule

module flopenr #(parameter WIDTH = 4)
(input logic clk, reset, en,
input logic [WIDTH-1:0] d,
output logic [WIDTH-1:0] q);
always_ff @(posedge clk, posedge reset)
if (reset) q <= 0;
else if (en) q <= d;
endmodule

Synchronous Sequential Logic Design
• Breaks cyclic paths by inserting registers
• Registers contain state of the system
• State changes at clock edge: system synchronized to the
clock
• Rules of synchronous sequential circuit composition:
– Every circuit element is either a register or a combinational circuit
– At least one circuit element is a register
– All registers receive the same clock signal
– Every cyclic path contains at least one register
• Two common synchronous sequential circuits
– Finite State Machines (FSMs)
– Pipelines
Chapter 4
Digital Design and Computer Architecture: ARM® Edition

Sarah L. Harris and David Money Harris
Chapter 4 :: Topics
• Introduction
• Combinational Logic
• Structural Modeling
• Sequential Logic
• More Combinational Logic
• Finite State Machines
• Parameterized Modules
• Testbenches
Introduction
• Hardware description language (HDL):
– specifies logic function only
– Computer-aided design (CAD) tool produces or synthesizes
the optimized gates
• Most commercial designs built using HDLs
• Two leading HDLs:
– SystemVerilog
• developed in 1984 by Gateway Design Automation
• IEEE standard (1364) in 1995
• Extended in 2005 (IEEE STD 1800-2009)
– VHDL 2008
• Developed in 1981 by the Department of Defense
• IEEE standard (1076) in 1987
• Updated in 2008 (IEEE STD 1076-2008)
HDL to Gates
• Simulation
– Inputs applied to circuit
– Outputs checked for correctness
– Millions of dollars saved by debugging in simulation instead of
hardware
• Synthesis
– Transforms HDL code into a netlist describing the hardware (i.e., a list
of gates and the wires connecting them)
HDL to Gates
• Simulation
– Inputs applied to circuit
– Outputs checked for correctness
– Millions of dollars saved by debugging in simulation
instead of hardware
• Synthesis
– Transforms HDL code into a netlist describing the hardware
(i.e., a list of gates and the wires connecting them)
IMPORTANT: When using an HDL, think of the hardware the HDL

should implies
SystemVerilog Modules
a
Verilog
SystemVerilog
b Module
y
Module
c
Two types of Modules:

– Behavioral: describe what a module does
– Structural: describe how it is built from simpler
modules
Behavioral SystemVerilog
SystemVerilog:
module example(input logic a, b, c,
output logic y);
assign y = ~a & ~b & ~c | a & ~b & ~c | a & ~b & c;
endmodule
Behavioral SystemVerilog
SystemVerilog:
output logic y);
endmodule
Continuous
assignment • module/endmodule: required to begin/end module
Đầu ra sẽ
• example: name of the module
thay đổi • Operators:
ngay khi
đầu vào ~: NOT
thay đổi &: AND
|: OR
Dùng cho Combinational logic
HDL Simulation
SystemVerilog:
output logic y);
endmodule
HDL Synthesis
SystemVerilog:
output logic y);
endmodule
Synthesis:
b
c y
un5_y y
un8_y
SystemVerilog Syntax
• Case sensitive
– Example: reset and Reset are not the same signal.
• No names that start with numbers
– Example: 2mux is an invalid name
• Whitespace ignored
• Comments:
– // single line comment
– /* multiline
comment */
Structural Modeling - Hierarchy
module and3(input logic a, b, c,
output logic y);
assign y = a & b & c;
endmodule
module inv(input logic a,

output logic y);
assign y = ~a;
endmodule
module nand3(input logic a, b, c

output logic y);
logic n1; // internal signal
and3 andgate(a, b, c, n1); // instance of and3

inv inverter(n1, y); // instance of inv
endmodule
Bitwise Operators
module gates(input logic [3:0] a, b,
output logic [3:0] y1, y2, y3, y4, y5);
/* Five different two-input logic
gates acting on 4 bit busses */
assign y1 = a & b; // AND Synthesis:
assign y2 = a | b; // OR
assign y3 = a ^ b; // XOR
assign y4 = ~(a & b); // NAND
assign y5 = ~(a | b); // NOR
endmodule
// single line comment

/*…*/ multiline comment
Reduction Operators
SystemVerilog:
module and8(input logic [7:0] a,
output logic y);
assign y = &a;
// &a is much easier to write than
// assign y = a[7] & a[6] & a[5] & a[4] &
// a[3] & a[2] & a[1] & a[0];
endmodule
Synthesis:
Conditional Assignment
SystemVerilog:
module mux2(input logic [3:0] d0, d1,
input logic s,
output logic [3:0] y);
assign y = s ? d1 : d0;
endmodule
Synthesis:
? : is also called a ternary operator because it

operates on 3 inputs: s, d1, and d0.
Internal Variables
SystemVerilog:
module fulladder(input logic a, b, cin,
output logic s, cout);
logic p, g; // internal nodes
assign p = a ^ b;
assign g = a & b;
Synthesis:
assign s = p ^ cin;
s
assign cout = g | (p & cin); s
g
endmodule
cin
cout
a
b
un1_cout cout
p
Precedence
Highest ~ NOT
*, /, % mult, div, mod
+, - add,sub
<<, >> shift
<<<, >>> arithmetic shift
<, <=, >, >= comparison
==, != equal, not equal
&, ~& AND, NAND
^, ~^ XOR, XNOR
|, ~| OR, NOR
Lowest ?: ternary operator
Numbers
Format: N'Bvalue
N = number of bits, B = base
N'B is optional but recommended (default is decimal)
Number # Bits Base Decimal Stored
Equivalent
3'b101 3 binary 5 101
'b11 unsized binary 3 00…0011
8'b11 8 binary 3 00000011
8'b1010_1011 8 binary 171 10101011
3'd6 3 decimal 6 110
6'o42 6 octal 34 100010
8'hAB 8 hexadecimal 171 10101011
42 Unsized decimal 42 00…0101010
Bit Manipulations: Example 1
assign y = {a[2:1], {3{b[0]}}, a[0], 6'b100_010};
// if y is a 12-bit signal, the above statement produces:

y = a[2] a[1] b[0] b[0] b[0] a[0] 1 0 0 0 1 0
// underscores (_) are used for formatting only to make

// it easier to read. SystemVerilog ignores them.
Bit Manipulations: Example 2
SystemVerilog:
module mux2_8(input logic [7:0] d0, d1,
input logic s,
output logic [7:0] y);
mux2 lsbmux(d0[3:0], d1[3:0], s, y[3:0]); Synthesis:

mux2 msbmux(d0[7:4], d1[7:4], s, y[7:4]);
mux2
endmodule s s
[7:0] [3:0] [3:0] [7:0]
d0[7:0] d0[3:0] y[3:0] y[7:0]
[7:0] [3:0]
d1[7:0] d1[3:0]
lsbmux
mux2
s
[7:4] [7:4]
d0[3:0] y[3:0]
[7:4]
d1[3:0]
msbmux
Z: Floating Output
SystemVerilog:
module tristate(input logic [3:0] a,
input logic en,
output tri [3:0] y);
assign y = en ? a : 4'bz;
endmodule
Synthesis:
en
[3:0] [3:0] [3:0] [3:0]
a[3:0] y[3:0]
y_1[3:0]
Delays
output logic y);
logic ab, bb, cb, n1, n2, n3;
assign #1 {ab, bb, cb} = ~{a, b, c};
assign #2 n1 = ab & bb & cb;
assign #2 n2 = a & bb & cb;
assign #2 n3 = a & bb & c;
assign #4 y = n1 | n2 | n3;
endmodule
Delays
output logic y);
assign #1 {ab, bb, cb} =
~{a, b, c};
assign #4 y = n1 | n2 | n3;
endmodule
Delays
1
output logic y);
~{a, b, c};
assign #4 y = n1 | n2 | n3;
endmodule
Delays
2
output logic y);
~{a, b, c};
assign #4 y = n1 | n2 | n3;
endmodule
Delays
output logic y);
~{a, b, c};
assign #2 n2 = a & bb & cb; 2
assign #4 y = n1 | n2 | n3;
endmodule
Delays
output logic y);
~{a, b, c};
assign #2 n2 = a & bb & cb; 4
assign #4 y = n1 | n2 | n3;
endmodule
Thiết kế mạch phân kênh 2-4
Dùng quá nhiều điều kiện: Độ trễ quá lớn
Thiết kế mạch dử dụng toán tử Assign và bitwise
Thiết kế mạch dử dụng toán tử Assign và bitwise
Thiết kế mạch có cổng vừa input vừa ouput
Cấu trúc
Sequential Logic
• SystemVerilog uses idioms to describe
latches, flip-flops and FSMs
• Other coding styles may simulate correctly
but produce incorrect hardware
Finite State Machine (FSM)
• Consists of:
CLK
– State register
• Stores current state S’
Next
S
Current
• Loads next state at clock edge State State
– Combinational logic Next State

Logic
• Computes the next state
• Computes the outputs CL Next
State
Output
Logic
CL Outputs
Finite State Machines (FSMs)
• Next state determined by current state and inputs
• Two types of finite state machines differ in output logic:
– Moore FSM: outputs depend only on current state
– Mealy FSM: outputs depend on current state and inputs
Moore FSM
CLK
M next
next k k output N
inputs state
state state
outputs
logic
logic
Mealy FSM
CLK
M next
next k k state output N
inputs state
state
outputs
logic
logic
FSM Example
• Traffic light controller
– Traffic sensors: TA, TB (TRUE when there’s traffic)
– Lights: LA, LB
Bravado
Dining
Hall
LB
LA TB
LA
Academic TA TA Ave.
Labs TB LB Dorms
Blvd.
Fields
FSM Black Box
• Inputs: CLK, Reset, TA, TB
• Outputs: LA, LB
CLK
Bravado
Dining
Hall
LB
TA Traffic LA
LA TB
LA
Light
Academic TA TA Ave.
TB Controller LB
Labs TB LB Dorms
Blvd.
Fields
Reset
FSM State Transition Diagram
• Moore FSM: outputs labeled in each state
• States: Circles Reset
• Transitions: Arcs S0
L : green A
LB: red
Bravado
Dining
Hall
LB
LA TB
LA
Academic TA TA Ave.
Labs TB LB Dorms
Blvd.
Fields
FSM State Transition Diagram
• Moore FSM: outputs labeled in each state
• States: Circles Reset
T A
S0 T S1
• Transitions: Arcs
A
L : green L : yellow A A
LB: red LB: red
Bravado
Dining
Hall
LB
LA TB
LA
Academic TA TA Ave.
Labs TB LB Dorms S3 S2
LA: red LA: red
Blvd.
Fields
LB: yellow LB: green
TB
TB
FSM State Transition Table
Current Next
State Inputs State
S TA TB S' Reset
TA
S0 TA S1
S0 0 X S1 LA: green
LB: red
LA: yellow
LB: red
S0 1 X S0
S1 X X S2
S2 X 0 S3 S3
LA: red
S2
LA: red
TB
S2 X 1 S2 TB
S3 X X S0
FSM Encoded State Transition Table
Current State Inputs Next State
State Encoding
S1 S0 TA TB S'1 S'0
S0 00
0 0 0 X 0 1
0 0 1 X 0 0 S1 01
0 1 X X 1 0 S2 10
1 0 X 0 1 1
S3 11
1 0 X 1 1 0 Reset
TA
TA
S0 S1
1 1 X X 0 0 LA: green
LB: red
LA: yellow
LB: red
S'1 = S1 xor S0 S3 S2
LA: red LA: red
S'0 = S1S0TA + S1S0TB LB: yellow

TB
TB
LB: green
FSM Output Table
Current State Outputs
S1 S0 LA1 LA0 LB1 LB0 Output Encoding
0 0 0 0 1 0 green 00
0 1 0 1 1 0 yellow 01
1 0 1 0 0 0
red 10
1 1 1 0 0 1 TA
Reset
TA
LA1 = S1
S0 S1
LA: green LA: yellow
LB: red LB: red
LA0 = S1S0
LB1 = S1 S3
LA: red
S2
LA: red
TB
LB0 = S1S0 TB
FSM Schematic: State Register
CLK
S'1 S1
S'0 S0
r
Reset
state register
FSM Schematic: Next State Logic
CLK
S'1 S1
TA S'0 S0
r
TB Reset
S1 S0
inputs next state logic state register
FSM Schematic: Output Logic
CLK LA1
S'1 S1
LA0
TA S'0 S0
LB1
r
TB Reset
S1 S0 LB0
inputs next state logic state register output logic outputs
module trafficFSM(input logic clk, reset,
input logic ta, tb,
output logic [1:0] la, lb);
logic [1:0] state, nextstate, sb;
logic tab, tbb, p1, p2;
// state register
flopr #(2) statereg(clk, reset, nextstate, state);
// next state logic

not n0(sb[0], s[0]);
not n1(sb[1], s[1]);
not n2(tab, ta);
not n3(tbb, tb);
xor x1(nextstate[1], state[0], state[1]);
and a1(p1, sb[0], sb[1], tab);
and a2(p2, sb[0], s[1], tbb);
or o1(nextstate[0], p1, p2);
// output logic
buf b1(la[1], s[1]);
and a3(la[0], s[0], sb[1]);
inv n4(lb[1], s[1]);
and a4(lb[0], s[0], s[1]);
endmodule

FSM Timing Diagram
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10
CLK
Reset
TA
TB
S'1:0 ?? S0 (00) S1 (01) S2 (10) S3 (11) S0 (00) S1 (01)
S1:0 ?? S0 (00) S1 (01) S2 (10) S3 (11) S0 (00)
LA1:0 ?? Green (00) Yellow (01) Red (10) Green (00)
LB1:0 ?? Red (10) Green (00) Yellow (01) Red (10)
0 5 10 15 20 25 30 35 40 45 t (sec)
TA
Reset
S0 TA S1
LB: red LB: red
S3 S2
LA: red LA: red
TB
TB
FSM State Encoding
• Binary encoding:
– i.e., for four states, 00, 01, 10, 11
• One-hot encoding
– One state bit per state
– Only one state bit HIGH at once
– i.e., for 4 states, 0001, 0010, 0100, 1000
– Requires more flip-flops
– Often next state and output logic is simpler
Moore vs. Mealy FSM
• Alyssa P. Hacker has a snail that crawls down a paper tape
with 1’s and 0’s on it. The snail smiles whenever the last two
digits it has crawled over are 01. Design Moore and Mealy
FSMs of the snail’s brain.
Phân tích theo mô hình Moore
Note:
- Output phụ thuộc state, được thể hiện trong vòng state
- Kích thích Input làm chuyển state
reset A=0 A=1
Y=0 Y=0 Y=1

A=0
A=1 A=0
A=1
Phân tích theo mô hình Mealy
Note:
- Output phụ thuộc state và kích thích Input, được thể hiện trên thay đổi
- Kích thích Input làm chuyển state
A=0/Y=0 A=0/Y=0
reset
𝑆0 𝑆1
A=1/Y=0
A=1/Y=1
State Transition Diagrams
Moore FSM
Reset
0 1
S0 S1 S2
0 0 1
1 0 0
1
Mealy FSM
Reset
0/0
S0 S1
1/0 0/0
1/1
Mealy FSM: arcs indicate input/output

Moore FSM State Transition Table
Current State Encoding
State Inputs Next State
S1 S0 S'1 S'0
S0 00
A
0 0 0 0 1 S1 01
0 0 1 0 0
0 1 0 0 1
S2 10
Moore FSM
0 1 1 1 0 Reset
0 1
1 0 0 0 1
S0 S1 S2
0 0 1
1 0 0
1
1 0 1 0 0
S1’ = S0A
S0’ = A
Moore FSM Output Table
Moore FSM
Current State Output Reset
0 1
S1 S0 Y
S0 S1 S2
0 0 0 1
0
0
0
0
1
1
0 1 0
1 0 1
Y = S1
Mealy FSM State Transition & Output Table
Current Next
State Input State Output
S0 A S'0 Y
State Encoding
0 0 1 0
0 1 0 0 S0 0
1 0 1 0
S1 1
1 1 0 1
Mealy FSM
Reset
0/0
S0 = A
’
S0 S1
Y = S0 A 1/0 0/0
1/1
Moore Mealy
A CLK
S'1 S1
Y A
CLK
S'0 S0 Y
S'0 S0
r r
Reset
Reset
Moore & Mealy Timing Diagram
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10 Cycle 11
CLK
Reset
A 0 1 0 1 1 0 1 1 1
Moore Machine
S ?? S0 S1 S2 S1 S2 S0 S1 S2 S0
Y
Mealy Machine
S ?? S0 S1 S0 S1 S0 S1 S0
Factoring State Machines
• Break complex FSMs into smaller interacting
FSMs
• Example: Modify traffic light controller to have
Parade Mode.
– Two more inputs: P, R
– When P = 1, enter Parade Mode & Bravado Blvd
light stays green
– When R = 1, leave Parade Mode
Parade FSM
P
Unfactored FSM R
TA
Controller LA
FSM LB
TB
P
Factored FSM R
Mode
FSM
TA Lights LA
TB FSM LB
Controller
FSM
Unfactored FSM
Factored FSM
TA
Reset
S0 TA S1
LB: red LB: red
P
Reset
S3 S2 P
S0 S1
LA: red LA: red
M: 0 M: 1
LB: yellow LB: green R
MTB
M + TB R
Lights FSM Mode FSM
FSM Design Procedure
1. Identify inputs and outputs
2. Sketch state transition diagram
3. Write state transition table
4. Select state encodings
5. For Moore machine:
a. Rewrite state transition table with state encodings
b. Write output table
5. For a Mealy machine:
Rewrite combined state transition and output table with
state encodings
6. Write Boolean equations for next state and output logic
7. Sketch the circuit schematic
Timing
• Flip-flop samples D at clock edge
• D must be stable when sampled
• Similar to a photograph, D must be stable
around clock edge
• If not, metastability can occur
Input Timing Constraints
• Setup time: tsetup = time before clock edge data must be
stable (i.e. not changing)
• Hold time: thold = time after clock edge data must be stable
• Aperture time: ta = time around clock edge data must be
stable (ta = tsetup + thold)
CLK
tsetup thold
ta
Dynamic Discipline
• Synchronous sequential circuit inputs must
be stable during aperture (setup and hold)
time around clock edge
• Specifically, inputs must be stable
– at least tsetup before the clock edge
– at least until thold after the clock edge
Output Timing Parameters
• Contamination delay: tccq = time after clock edge that Q
might be unstable (i.e., start changing)
• Propagation delay: tpcq = time after clock edge that the
output Q is guaranteed to be stable (i.e., to stop changing)
CLK
tccq
tpcq
Dynamic Discipline
• The delay between registers has a minimum
and maximum delay, dependent on the
delays of the circuit elements
CLK CLK
Q1 CL D2
R1 R2
(a)
Tc
CLK
Q1
D2
(b)
Setup Time Constraint
• Depends on the maximum delay from register R1
through combinational logic to R2
• The input to register R2 must be stable at least tsetup
before clock edge
CLK CLK
Q1 CL D2
R1 R2 Tc ≥ tpcq + tpd + tsetup

Tc
CLK tpd ≤ Tc – (tpcq + tsetup)
Q1
D2
tpcq tpd tsetup (tpcq + tsetup): sequencing overhead
Hold Time Constraint
• Depends on the minimum delay from register R1
through the combinational logic to R2
• The input to register R2 must be stable for at least
thold after the clock edge
CLK CLK
Q1 CL D2
R1 R2
thold < tccq + tcd
CLK
tcd > thold - tccq
Q1
D2
tccq tcd
thold
Timing Analysis
CLK CLK Timing Characteristics
A tccq = 30 ps
tpcq = 50 ps
B tsetup = 60 ps
thold = 70 ps
X' X
per gate
C
tpd = 35 ps
D
Y' Y tcd = 25 ps
tpd = 3 x 35 ps = 105 ps
tcd = 25 ps
Setup time constraint: Hold time constraint:
Tc ≥ (50 + 105 + 60) ps = 215 ps tccq + tcd > thold ?
fc = 1/Tc = 4.65 GHz (30 + 25) ps > 70 ps ? No!
Timing Analysis
Add buffers to the short paths: Timing Characteristics
CLK CLK tccq = 30 ps
A
tpcq = 50 ps
tsetup = 60 ps
B
thold = 70 ps
X' X
per gate
C
tpd = 35 ps
D
Y' Y tcd = 25 ps
tpd = 3 x 35 ps = 105 ps
tcd = 2 x 25 ps = 50 ps
Setup time constraint: Hold time constraint:
Tc ≥ (50 + 105 + 60) ps = 215 ps tccq + tcd > thold ?
fc = 1/Tc = 4.65 GHz (30 + 50) ps > 70 ps ? Yes!
Clock Skew
• The clock doesn’t arrive at all registers at same time
• Skew: difference between two clock edges
• Perform worst case analysis to guarantee dynamic
discipline is not violated for any register – many
registers in a system!
delay CLK
CLK1 CLK2
Q1 C D2
L
R1 R2
t skew
CLK1
CLK2
CLK
Setup Time Constraint with Skew
• In the worst case, CLK2 is earlier than CLK1
CLK1 CLK2
Q1 C D2
L
R1 R2
Tc
CLK1
Tc ≥ tpcq + tpd + tsetup + tskew
CLK2
tpd ≤ Tc – (tpcq + tsetup + tskew)
Q1
D2
tpcq tpd tsetup tskew
Hold Time Constraint with Skew
• In the worst case, CLK2 is later than CLK1
CLK1 CLK2
Q1 C D2
L
R1 R2
CLK1
CLK2 tccq + tcd > thold + tskew

Q1
tcd > thold + tskew – tccq
D2
tccq tcd
tskew thold
Violating the Dynamic Discipline
Asynchronous (for example, user) tsetup thold
inputs might violate the dynamic CLK

discipline
taperture
CLK
button
D
Case I
D Q
Q
D
Case II
Q
Case III
???
Q
Metastability
• Bistable devices: two stable states, and a
metastable state between them
• Flip-flop: two stable states (1 and 0) and one
metastable state
• If flip-flop lands in metastable state, could stay
there for an undetermined amount of time
metastable
stable stable
Flip-Flop Internals
• Flip-flop has feedback: if Q is somewhere between
1 and 0, cross-coupled gates drive output to either
rail (1 or 0) R
N1 Q
N2 Q
S
• Metastable signal: if it hasn’t resolved to 1 or 0
• If flip-flop input changes at random time, probability
that output Q is metastable after waiting some time, t:
P(tres > t) = (T0/Tc ) e-t/τ
tres : time to resolve to 1 or 0

T0, τ : properties of the circuit
Metastability
• Intuitively:
T0/Tc: probability input changes at a bad time (during aperture)
τ: time constant for how fast flip-flop moves away from

metastability
• If flip-flop samples metastable input, if you wait long

enough (t), the output will have resolved to 1 or 0 with
high probability.
Synchronizers
• Asynchronous inputs are inevitable (user interfaces,
systems with different clocks interacting, etc.)
• Synchronizer goal: make the probability of failure (the
output Q still being metastable) low
• Synchronizer cannot make the probability of failure 0
CLK
SYNC
D Q
Synchronizer Internals
• Synchronizer: built with two back-to-back flip-flops
• Suppose D is transitioning when sampled by F1
• Internal signal D2 has (Tc - tsetup) time to resolve to 1
or 0 CLK
D2
CLK
D Q
F1 F2
Tc
CLK
D2 metastable
tres tsetup tpcq
Synchronizer Probability of Failure
For each sample, probability of failure is:
P(failure) = (T0/Tc ) e-(T c - tsetup)/τ
CLK CLK
D2
D Q
F1 F2
Tc
CLK
D2 metastable
tres tsetup tpcq
Synchronizer Mean Time Between Failures
• If asynchronous input changes once per second,
probability of failure per second is P(failure).
• If input changes N times per second, probability of failure
per second is:
P(failure)/second = (NT0/Tc) e-(T - t c setup )/τ
• Synchronizer fails, on average, 1/[P(failure)/second]

• Called mean time between failures, MTBF:
MTBF = 1/[P(failure)/second] = (Tc/NT0) e(Tc - tsetup)/τ
Example Synchronizer
CLK CLK
D2
D Q
F1 F2
• Suppose: Tc = 1/500 MHz = 2 ns τ = 200 ps

T0 = 150 ps tsetup = 100 ps
N = 10 events per second
• What is the probability of failure? MTBF?
P(failure) = (150 ps/2 ns) e-(1.9 ns)/200 ps
= 5.6 × 10-6
P(failure)/second = 10 × (5.6 × 10-6 )
= 5.6 × 10-5 / second
MTBF = 1/[P(failure)/second] ≈ 5 hours
Parallelism
• Two types of parallelism:
– Spatial parallelism
• duplicate hardware performs multiple tasks at once
– Temporal parallelism
• task is broken into multiple stages
• also called pipelining
• for example, an assembly line
Parallelism Definitions
• Token: Group of inputs processed to produce
group of outputs
• Latency: Time for one token to pass from
start to end
• Throughput: Number of tokens produced
per unit time
Parallelism increases throughput
Parallelism Example
• Ben Bitdiddle bakes cookies to celebrate traffic light
controller installation
• 5 minutes to roll cookies
• 15 minutes to bake
• What is the latency and throughput without parallelism?
Latency = 5 + 15 = 20 minutes = 1/3 hour

Throughput = 1 tray/ 1/3 hour = 3 trays/hour
Parallelism Example
• What is the latency and throughput if Ben
uses parallelism?
– Spatial parallelism: Ben asks Allysa P. Hacker to
help, using her own oven
– Temporal parallelism:
• two stages: rolling and baking
• He uses two trays
• While first batch is baking, he rolls the
second batch, etc.
Spatial Parallelism
Latency:
time to
first tray
0 5 10 15 20 25 30 35 40 45 50
Time
Tray 1 Ben 1 Ben 1
Roll
Parallelism
Tray 2 Alyssa 1 Alyssa 1

Spatial
Bake
Tray 3 Ben 2 Ben 2
Legend
Tray 4 Alyssa 2 Alyssa 2

Throughput = 2 trays/ 1/3 hour = 6 trays/hour
Temporal Parallelism
Latency:
time to
first tray
0 5 10 15 20 25 30 35 40 45 50
Time
Tray 1 Ben 1 Ben 1
Parallelism
Temporal
Tray 2 Ben 2 Ben 2
Tray 3 Ben 3 Ben 3

Throughput = 1 trays/ 1/4 hour = 4 trays/hour
Using both techniques, the throughput would be 8 trays/hour

DDCAarm - Ch3 - New

Uploaded by

Copyright:

Available Formats

DDCAarm - Ch3 - New

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DDCAarm - Ch3 - New

Uploaded by

Copyright:

Available Formats

Chapter 3

Digital Design and Computer Architecture: ARM® Edition

• Stores 1 bit of state in the state variable, Q (or Q)

Set the output 10

• No inputs and 1-3 outputs 0 1 2 3 4 5 6 7 8 time (ns)

• Astable circuit, oscillates

always_ff @(posedge clk)

• Multi-input XOR: Odd parity

always_ff @(posedge clk, posedge reset)

• Multi-input XOR: Odd parity

• Multi-input XOR: Odd parity

Digital Design and Computer Architecture: ARM® Edition

IMPORTANT: When using an HDL, think of the hardware the HDL

Two types of Modules:

module inv(input logic a,

module nand3(input logic a, b, c

and3 andgate(a, b, c, n1); // instance of and3

// single line comment

? : is also called a ternary operator because it

// if y is a 12-bit signal, the above statement produces:

// underscores (_) are used for formatting only to make

mux2 lsbmux(d0[3:0], d1[3:0], s, y[3:0]); Synthesis:

– Combinational logic Next State

S'0 = S1S0TA + S1S0TB LB: yellow

inputs next state logic state register

inputs next state logic state register output logic outputs

// next state logic

• Multi-input XOR: Odd parity

S'1:0 ?? S0 (00) S1 (01) S2 (10) S3 (11) S0 (00) S1 (01)

S1:0 ?? S0 (00) S1 (01) S2 (10) S3 (11) S0 (00)

LA1:0 ?? Green (00) Yellow (01) Red (10) Green (00)

LB1:0 ?? Red (10) Green (00) Yellow (01) Red (10)

reset A=0 A=1

Y=0 Y=0 Y=1

Mealy FSM: arcs indicate input/output

R1 R2 Tc ≥ tpcq + tpd + tsetup

fc = 1/Tc = 4.65 GHz (30 + 25) ps > 70 ps ? No!

tpcq tpd tsetup tskew

CLK2 tccq + tcd > thold + tskew

inputs might violate the dynamic CLK

tres : time to resolve to 1 or 0

τ: time constant for how fast flip-flop moves away from

• If flip-flop samples metastable input, if you wait long

tres tsetup tpcq

tres tsetup tpcq

• Synchronizer fails, on average, 1/[P(failure)/second]

MTBF = 1/[P(failure)/second] = (Tc/NT0) e(Tc - tsetup)/τ

• Suppose: Tc = 1/500 MHz = 2 ns τ = 200 ps

Parallelism increases throughput

Latency = 5 + 15 = 20 minutes = 1/3 hour

Tray 2 Alyssa 1 Alyssa 1

Latency = 5 + 15 = 20 minutes = 1/3 hour

Tray 2 Ben 2 Ben 2

Tray 3 Ben 3 Ben 3

Latency = 5 + 15 = 20 minutes = 1/3 hour

You might also like