Chapter 3
Circuitos secuenciales
Adaptado de:
Digital Design and Computer Architecture, 2nd Edition
David Money Harris and Sarah L. Harris
Chapter 3 <1>
Chapter 3 :: Topics
Introduction
Latches and Flip-Flops
Synchronous Logic Design
Finite State Machines
Timing of Sequential Logic
Parallelism
Chapter 3 <2>
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. In this mode,
Bravado Blvd light stays green
When R = 1, leave Parade Mode
Chapter 3 <14>
Parade FSM
Unfactored FSM
P
R
TA
TB
Factored FSM
P
R
Controller
FSM
LA
LB
Mode
FSM
M
TA
TB
Lights
FSM
LA
LB
Controller
FSM
Chapter 3 <15>
Factored FSM
TA
Reset
S0
LA: green
LB: red
TA
S1
LA: yellow
LB: red
Reset
S3
LA: red
LB: yellow
S2
LA: red
LB: green
MTB
P
S0
M: 0
S1
M: 1
R
M + TB
Lights FSM
R
Mode FSM
Chapter 3 <16>
FSM Design Procedure
Identify inputs and outputs
Sketch state transition diagram
Write state transition table
Select state encodings
For Moore machine:
For a Mealy machine:
Rewrite state transition table with state encodings
Write output table
Rewrite combined state transition and output table with state
encodings
Write Boolean equations for next state and output logic
Sketch the circuit schematic
Chapter 3 <18>
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
Chapter 3 <19>
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
D
tsetup thold
ta
Chapter 3 <20>
Output Timing Constraints
Propagation delay: tpcq = time after clock edge that the
output Q is guaranteed to be stable (i.e., to stop changing)
Contamination delay: tccq = time after clock edge that Q
might be unstable (i.e., start changing)
CLK
Q
tccq
tpcq
Chapter 3 <21>
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
Chapter 3 <22>
Dynamic Discipline
The delay between registers has a
minimum and maximum delay, dependent
on the delays of the circuit elements
CLK
CLK
Q1
(a)
C
L
R1
D2
R2
Tc
CLK
Q1
D2
(b)
Chapter 3 <23>
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
Tc
R2
Tc
CLK
Q1
D2
tpcq
tpd
tsetup
Chapter 3 <24>
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
Tc tpcq + tpd + tsetup
tpd
CLK
Q1
D2
tpcq
tpd
tsetup
Chapter 3 <25>
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
Tc tpcq + tpd + tsetup
tpd Tc (tpcq + tsetup)
CLK
Q1
D2
tpcq
tpd
tsetup
Chapter 3 <26>
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
R1
CL
D2
R2
thold <
CLK
Q1
D2
tccq tcd
thold
Chapter 3 <27>
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
R1
CL
D2
R2
thold < tccq + tcd
tcd >
CLK
Q1
D2
tccq tcd
thold
Chapter 3 <28>
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
R1
CL
D2
R2
thold < tccq + tcd
tcd > thold - tccq
CLK
Q1
D2
tccq tcd
thold
Chapter 3 <29>
Timing Analysis
CLK
Timing Characteristics
CLK
tccq = 30 ps
tpcq = 50 ps
tsetup = 60 ps
tpd =
X'
Y'
thold = 70 ps
per gate
tpd
= 35 ps
tcd
= 25 ps
tcd =
Setup time constraint:
Hold time constraint:
Tc
tccq + tcd > thold ?
fc =
Chapter 3 <30>
Timing Analysis
CLK
Timing Characteristics
CLK
tccq = 30 ps
tpcq = 50 ps
tsetup = 60 ps
tpd = 3 x 35 ps = 105 ps
X'
Y'
thold = 70 ps
per gate
tpd
= 35 ps
tcd
= 25 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!
Chapter 3 <31>
Timing Analysis
Add buffers to the short paths:
CLK
Timing Characteristics
CLK
tccq = 30 ps
tpcq = 50 ps
B
tsetup = 60 ps
tpd =
X'
Y'
thold = 70 ps
per gate
tpd
= 35 ps
tcd
= 25 ps
tcd =
Setup time constraint:
Hold time constraint:
Tc
tccq + tcd > thold ?
fc =
Chapter 3 <32>
Timing Analysis
Add buffers to the short paths:
Timing Characteristics
CLK
CLK
tccq = 30 ps
tpcq = 50 ps
B
tsetup = 60 ps
X'
Y'
tpd = 3 x 35 ps = 105 ps
thold = 70 ps
per gate
tpd
= 35 ps
tcd
= 25 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!
Chapter 3 <33>
Clock Skew
The clock doesnt 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
R1
C
L
D2
R2
t skew
CLK1
CLK2
CLK
Chapter 3 <34>
Violating the Dynamic Discipline
CLK
taperture
Case I
Q
D
Case II
tsetup thold
Q
D
Q
???
Chapter 3 <41>
Case III
button
Asynchronous (for example, user)
inputs might violate the dynamic
discipline
CLK
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
Chapter 3 <42>
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
Chapter 3 <43>
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?
Chapter 3 <44>
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
Chapter 3 <45>
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.
Chapter 3 <46>
Spatial Parallelism
Latency:
time to
first tray
0
10
15
20
25
30
35
40
45
50
Spatial
Parallelism
Time
Tray 1
Ben 1
Ben 1
Tray 2
Alyssa 1
Alyssa 1
Roll
Tray 3
Ben 2
Ben 2
Tray 4
Alyssa 2
Alyssa 2
Latency = ?
Throughput = ?
Chapter 3 <47>
Bake
Legend
Spatial Parallelism
Latency:
time to
first tray
0
10
15
20
25
30
35
40
45
50
Spatial
Parallelism
Time
Tray 1
Ben 1
Ben 1
Tray 2
Alyssa 1
Alyssa 1
Roll
Tray 3
Ben 2
Ben 2
Tray 4
Alyssa 2
Alyssa 2
Latency = 5 + 15 = 20 minutes = 1/3 hour
Throughput = 2 trays/ 1/3 hour = 6 trays/hour
Chapter 3 <48>
Bake
Legend
Temporal Parallelism
Latency:
time to
first tray
0
10
15
20
25
30
35
40
45
50
Temporal
Parallelism
Time
Tray 1
Tray 2
Ben 1
Ben 1
Ben 2
Tray 3
Ben 2
Ben 3
Ben 3
Latency = ?
Throughput = ?
Chapter 3 <49>
Temporal Parallelism
Latency:
time to
first tray
0
10
15
20
25
30
35
40
45
50
Temporal
Parallelism
Time
Tray 1
Tray 2
Tray 3
Ben 1
Ben 1
Ben 2
Ben 2
Ben 3
Ben 3
Latency = 5 + 15 = 20 minutes = 1/3 hour
Throughput = 1 trays/ 1/4 hour = 4 trays/hour
Using both techniques, the throughput would be 8 trays/hour
Chapter 3 <50>
