L9_1 Combinational-Logic- Timing
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 1 The material in this presentation cannot be copied in any form without written permission
Learning Objectives
• To identify the propagation delay in combinational logic circuits.
EECS 370 – Introduction to Computer Organization
2
Combinational Circuits Implement Boolean Expressions
• Output is determined exclusively by the input
• No memory: Output is valid only as long as input is
• Adder is the basic gate of the ALU (this lecture)
• Decoder is the basic gate of indexing (we will use this next lecture) • MUX is the basic gate controlling data movement
Decoder Mux A A0 Out
Half-Adder
SA1 0 A
B Out1 S C
B Out3
C
Out2
EECS 370 – Introduction to Computer Organization
3
Propagation Delay in Combinational Gates
• Gate outputs do not change exactly when inputs do.
• Transmission time over wires (~speed of light)
• Saturation time to make transistor gate switch
Every combinatorial circuit has a propagation delay (time between input and output stabilization)
IO
I
Vdd
gnd
EECS 370 – Introduction to Computer Organization
4
ideal O gnd real
Vdd
Timing in Combinational Circuits
Delay of gate G2
dG2 dG3
dG2 dG3
A S
MUX
X
C
G2 Y
A S
B
X Y
C
G1
B
G3
What is the input/output delay (or simply, delay) of the MUX?
EECS 370 – Introduction to Computer Organization
5
time
Waveform viewers are part of designers’ daily life
EECS 370 – Introduction to Computer Organization
6
What is the delay of this Circuit?
A B C
D E
Each oval represents one gate ( the type does not matter)
# = delay of each gate
Longest path: 3 + 5 + 2 = 10
352F
6
1
EECS 370 – Introduction to Computer Organization
7
Example: Building a Circuit
Problem: Build an ALU (Arithmetic Logic Unit) for LC-2K
• Use some of the blocks we have learned about so far to build a circuit
• Using – full adder, NOR, mux
• Input A, 32 bits
• Input B, 32 bits
• Input S, 1 bit
• Output, 32 bits
• When S is low, the output is A+B, when S is high, the output is NOR(a,b)
32 wires
32
32 32 32
Full Adder Circuit
32
32 32
32
32
EECS 370 – Introduction to Computer Organization 32
8
LC-2K ALU (Arithmetic Logic Unit)
32 A
32
32
Symbol
Full Adder Circuit
0
Input A
Input B
output
A L U
B
32
32
1
S
EECS 370 – Introduction to Computer Organization
9
operation
Logistics
• There are 3 videos for lecture 9
• L9_1 – Combinational-Logic-Timing
• L9_2 – Memory_Latches-Clocks • L9_3 – Finite-State-Machines
• There are two worksheet for lecture 9
1. Circuit design – combinational logic – you are ready for this now
2. Circuit design – sequential logic
EECS 370 – Introduction to Computer Organization
10
L9_2 Memory_Latches-Clocks
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 11 The material in this presentation cannot be copied in any form without written permission
Learning Objectives
• To identify and understand the operation of simple devices to retain memory in circuits.
• To understand the inclusion of timing with the clock circuit
EECS 370 – Introduction to Computer Organization
12
EECS 370 – Introduction to Computer Organization
13
What is sequential logic?
• So far, we’ve covered combinational
• Output is determined from input
• But computers don’t work that way — they have state
• Examples of state • Registers
• Memory
• Sequential logic’s output depends not only on the current input, but
also on its current state
• This lecture will show you how to build sequential logic from gates
• The key is feedback EECS 370 – Introduction to Computer Organization
14
Using Feedback to “Remember”
EECS 370 – Introduction to Computer Organization
15
This remembers its initial value! Very basic memory
What’s wrong with this, though?
“high” is:
• logical 1
• 1 state
• “set”
• high voltage “low” is:
• logical 0
• 0 state
• “Unset”
• low voltage
Q is not Q
Your First Memory: S-R Latch
R
Q
S
Q
• Output Q and Q should have memory, i.e., retain their value for some input changes
• Output Q and Q should always have opposite
values
16
EECS 370 – Introduction to Computer Organization
Your First Memory: S-R Latch
R
SRQQ
Problem: Create a truth table for this circuit
Q
S
Q
• Output Q and Q should have memory, i.e., retain their value for some input changes
• Output Q and Q should always have opposite
values
17
EECS 370 – Introduction to Computer Organization
Your First Memory: S-R Latch
R
SRQQ
00QQ 0101 1010 1100
Invalid ~ AVOID!
Q and Q are supposed to be opposite of each other, so this is a state we avoid. This state can also lead to unstable future states. Try setting S = 0 and R = 0 now!
Problem: Create a truth table for this circuit
Q
S
Q
• Output Q and Q should have memory, i.e., retain their value for some input changes
• Output Q and Q should always have opposite
values
18
EECS 370 – Introduction to Computer Organization
D Latch
D
R
Q
S
Q
G signal
DGQQ
0
Gating
EECS 370 – Introduction to Computer Organization
19
D Latch
D
R
Q
G signal
Gating
S
Q
Next state is set
DGQQ
00QQ
0101 10QQ 1110
Set state
is retained
when gate is low
No invalid states ☺
EECS 370 – Introduction to Computer Organization
20
DQ G
D Latch – Gate and Data
D G Q
EECS 370 – Introduction to Computer Organization
21
DQ G
D Latch – Gate and Data
D
G
Q
Indicates uncertainty of initial state
Q changes when G is high. Q is preserved when G is low
EECS 370 – Introduction to Computer Organization
22
DQ G
Adding a Clock to the Mix
• Problem if we build complex circuits with feedback, these “latches” can become unstable when transparent
• “Glitches” propagate around and around • Take 270 to learn more
• We can solve this if we introduce a clock
• Alternating signal that switches between 0 and 1 states at a fixed frequency
(e.g., 100MHz)
• Only store the value the instant the clock changes
• What should the clock frequency be?
• It depends on the longest propagation delay between state and next state
combination logic
• And a few other things outside of the scope of 370 (shout out 270)
EECS 370 – Introduction to Computer Organization
23
Clocks
• Clock signal
• Periodic pulse
• Generated using oscillating crystal or ring oscillator
• Distributed throughout chip using clock distribution net
rising edge
falling edge
EECS 370 – Introduction to Computer Organization
24
Rising-Edge Triggered D Flip-Flop
Data
Dq G
dQ G
Clock
Data Clock
q
Q Latching starts
Value remembered by flip-flop
Latching edge
EECS 370 – Introduction to Computer Organization
25
D
Q
D Flip-Flop – Clock and Data
Data Clock
Q
EECS 370 – Introduction to Computer Organization
26
D
Q
D Flip-Flop – Clock and Data
Data Clock
Q
EECS 370 – Introduction to Computer Organization
27
D
Q
What Happens if Data Changes on a Clock Edge?
Data Clock
Q
EECS 370 – Introduction to Computer Organization
28
BAD
• Unpredictable: Q could be high, low or in a meta-stable state
• Likely need to increase your clock period to allow enough time for signal propagation
D
Q
Why Edge-Triggered Flip-Flops?
Latch
DQ G
D
Q
Flip-flop
In edge-triggered flip-flops, the latching edge provides convenient abstraction of “instantaneous” change of state.
EECS 370 – Introduction to Computer Organization
29
Adding an Enable Input
• Q only updates on a positive clock edge if ‘en’ is high • Think of ‘en’ as ‘write enabled’
EECS 370 – Introduction to Computer Organization
30
DQ
en
Logistics
• There are 3 videos for lecture 9
• L9_1 – Combinational-Logic-Timing
• L9_2 – Memory_Latches-Clocks • L9_3 – Finite-State-Machines
• There are two worksheet for lecture 9
1. Circuit design – combinational logic
2. Circuit design – sequential logic – you are ready for this now
EECS 370 – Introduction to Computer Organization
31
L9_3 Finite-State-Machines
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 32 The material in this presentation cannot be copied in any form without written permission
Learning Objectives
• To define and understand the concept of state as it pertains to architecture
• Ability to model a controller as a machine expressed as states and transitions, i.e., a finite state machine.
EECS 370 – Introduction to Computer Organization
33
Finite State Machines
• So far we can do two things with gates:
1. Combinational Logic: implement Boolean expressions
• Adder, MUX, Decoder, logical operations etc 2. Sequential Logic: store state
• Latch, Flip-Flops
• How do we combine them to do something interesting?
• Let’s take a look at implementing the logic needed for a vending machine
• Discrete states needed: remember how much money was input • Store sequentially
• Transitions between states: money inserted, drink selected, etc • Calculate combinationally or with a control ROM (more on this later)
EECS 370 – Introduction to Computer Organization
34
State
Very important concept in architecture
• Represents all the stored information in a system at a point in time • Finite State Machine:
• Model of a system which enumerates all states that system may be in, and the conditions which allow transitions between states
• Often expressed as a directed graph or table
EECS 370 – Introduction to Computer Organization
35
FSM Example – Vending Machine
• We could use a general purpose processor
• However, a custom controller will be: • Faster
• Lower power
• Cheaper to produce in high volume
• On the other hand, a custom controller: • Will be slower to design
• More expensive in low volume
• Goals:
• Take money, vend drinks.
EECS 370 – Introduction to Computer Organization
36
Input and Output
• Inputs:
• Coin trigger
• Refund button
• 10 drink selectors
• 10 pressure sensors • Detect if there are
still drinks left
• Outputs:
• 10 drink release latches • Coin refund latch
EECS 370 – Introduction to Computer Organization
37
Operation of Machine
• Accepts quarters only
• All drinks are $0.75
• Once we get the money, a drink can be selected
• If they want a refund, release any coins inserted
• No free drinks!
• No stealing money.
EECS 370 – Introduction to Computer Organization
38
Building the Controller
• Finite State
• Remember how many coins have been put in the machine and what inputs
are acceptable
• Read-Only Memory (ROM)
• Define the outputs and state transitions • Custom combinational circuits
• Reduce the size (and therefore cost) of the controller EECS 370 – Introduction to Computer Organization
39
Finite State Machines
A Finite State Machine (FSM) consists of:
• K states:
• N inputs:
• M outputs:
S = {s1, s2, … ,sk}, s1 is initial state
I = {i1, i2, … ,in}
O = {o1, o2, … ,om}
• Transition function T(S,I) mapping each current state and input to
next state
• Output Function P(S) or P(S,I) specifies output • P(S) is a Moore Machine
• P(S,I) is a Mealy Machine
EECS 370 – Introduction to Computer Organization
40
FSM for Vending Machine
Refund
0 coins
1 coin
3 coins
Ran out of specific drink selection
2 coins
Coin trigger Refund button Drink Select
Is this a Mealy or Moore Machine?
Mealy ~ output is based on current state AND input
EECS 370 – Introduction to Computer Organization
41
Vend drink Refund Refund
Implementing a FSM
Outputs
Inputs
Implement transition functions
(using a ROM and combinational circuits)
Current state
D
Q
D
Q
2-bit state
Next state
EECS 370 – Introduction to Computer Organization
42
Logistics
• There are 3 videos for lecture 9
• L9_1 – Combinational-Logic-Timing
• L9_2 – Memory_Latches-Clocks • L9_3 – Finite-State-Machines
• There are two worksheet for lecture 9
1. Circuit design – combinational logic
2. Circuit design – sequential logic
EECS 370 – Introduction to Computer Organization
43