Transcript Memories and State Machines

Computer Organization and Design
Memories and State Machines
Montek Singh
Mon, April 13, 2011
Lecture 14
Memory, Latches, & Registers
1)
2)
3)
4)
Structured Logic Arrays
Memory Arrays
Transparent Latches
How to save a few bucks
at toll booths!
5) Edge-triggered Registers
6) Finite State Machines
Memory as a Lookup Table
A
B
AB Fn(A,B)
00
01
10
11
0
1
1
0
MUX
Logic
Fn(A,B)
 A multiplexer to implement a lookup table:
 Remember that, in theory, we can build any 1-output
combinational logic block with multiplexers
 For an N-input function we need a 2N input multiplexer
 BIG Multiplexers?
 How about 10-input function? 20-input?
A Mux’s Guts
Decoder
A decoder
generates
all possible
product
terms for
a set of
inputs
A
B
0
A
B
1
A
B
2
A
B
3
I 00
I 01
I 10
I 11
Selector
Multiplexers
can be partitioned
into two sections.
A DECODER that
Y
identifies the
desired input,and
a SELECTOR that
enables that input
onto the output.
Hmmm, by sharing the decoder part of the logic MUXs
could be adapted to make lookup tables with any
number of outputs
A New Combinational Device
D1
D2
DECODER:
k SELECT inputs,
N=
DN
2k
DATA OUTPUTs.
Selected Dj HIGH;
all others LOW.
k
NOW, we are well on our way to building a general
purpose table-lookup device.
We can build a 2-dimensional ARRAY of decoders
and selectors as follows ...
Have I
mentioned
that HIGH
is a synonym
for ‘1’ and
LOW means
the same
as ‘0’
Shared Decoding Logic
There’s an
extra level
of inversion
that isn’t
necessary
in the logic.
However,
it reduces
the capacitive
load on the
module driving
this one.
A
B
Cin
Decoder
These are just
“DeMorgan”ized
NOR gates
0
1
2
3
4
5
6
7
S
This ROM stores 16 bits
in 8 words of 2 bits.
Cout
Configurable Selector
We can build a general purpose “table-lookup” device called a ReadOnly Memory (ROM), from which we can implement any truth table
and, thus, any combinational device
Made from PREWIRED connections , and CONFIGURABLE
connections that can be either connected
or not connected
Logic According to ROMs
 ROMs ignore the structure of combinational functions
...
 Size, layout, and design are independent of function
 Any Truth table can be “programmed” by minor
reconfiguration:
 Metal layer (masked ROMs)
 Fuses (Field-programmable PROMs)
 Charge on floating gates (EPROMs)
 ... etc.
 Model: LOOK UP value of function in truth table...
 Inputs: “ADDRESS” of a T.T. entry
 ROM SIZE = # TT entries...
2N x #outputs
 ... for an N-input boolean function, size = __________
Analog Storage: Using Capacitors
 We’ve chosen to encode information using voltages and we
know from physics that we can “store” a voltage as “charge”
on a capacitor
bit line
word
line
N-channel
FET serves
as an
access
switch
VREF
To write:
Drive bit line, turn on access fet,
force storage cap to new voltage
To read:
precharge bit line, turn on access fet,
detect (small) change in bit line voltage
 Pros:
 compact!
 Cons:
 it leaks! refresh
 complex interface
 reading a bit, destroys it
– (you have to rewrite the
value after each read)
 it’s NOT a digital circuit
This storage circuit is the
basis for commodity DRAMs
A “Digital” Storage Element
 It’s also easy to build a settable DIGITAL storage
element (called a latch) using a MUX and FEEDBACK:
Here’s a feedback path,
so it’s no longer a
combinational circuit.
A
G D QIN QOUT
0
Q
Y
D
B
G
S
1
“state” signal
appears as both
input and output
0
0
1
1
--0
1
0
1
---
0
1
0
1
Q stable
Q follows D
Looking Under the Covers
 Let’s take a quick look at the equivalent circuit for our MUX
when the control is LOW (the feedback path is active)
0
D
1
Q
G=0
1
1
G=0
D
Q
Q
Advantages:
1) Maintains remembered state for as
This storage circuit is the
long as power is applied.
basis for commodity SRAMs
2) State is DIGITAL
Disadvantage:
1) Requires more transistors
Static D Latch
D Q
D Q
G
G
Positive latch
Negative latch
What is the
difference?
Q follows D
1
D
G
D
Q
Q stable
0
Q
G
“static” means latch will hold data (i.e., value of Q) while G is
inactive, however long that may be.
Latch Timing
 Circuits with memory must follow some rules
 Guarantee that inputs to sequential devices are valid and
stable during periods when they may influence state changes
 This is assured with additional timing specifications
>tPULSE
G
D
>tSETUP >tHOLD
tPULSE (minimum pulse width): guarantee G is active for long enough
for latch to capture data
tSETUP (setup time): guarantee that D value has propagated through
feedback path before latch becomes opaque
tHOLD (hold time): guarantee latch is opaque and Q is stable before
allowing D to change again
Flakey Control Systems
Here’s a strategy
for saving 2
bucks the next
time you find
yourself at a toll
booth!
Flakey Control Systems
Here’s a strategy
for saving 2
bucks the next
time you find
yourself at a toll
booth!
Flakey Control Systems
Here’s a strategy
for saving 2
bucks the next
time you find
yourself at a toll
booth!
WARNING:
Professional Drivers Used!
DON’T try this
At home!
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
Escapement Strategy
The Solution:
Add two gates
and only open
one at a time.
(Psst… Don’t
tell the toll
folks)
Key Idea: At no time is there an
open path through both
gates…
Edge-triggered Flip Flop
D
D Q
D Q
G
G
master
slave
Q
D
D Q
Q
CLK
CLK
 Logical “escapement”:
 Double-gated toll booth built using logic gates
 Observations:
 only one latch “transparent” at any time:
 master closed when slave is open (CLK is high)
 slave closed when master is open (CLK is low)
 no combinational path all the way through flip flop
Transitions mark
instants, not
intervals
 Q only changes shortly after 0 1 transition of CLK, so flip
flop appears to be “triggered” by rising edge of CLK
Flip Flop Waveforms
D
D Q
D Q
G
G
master
slave
Q
D
D Q
CLK
CLK
D
CLK
Q
master closed
slave open
slave closed
master open
Q
Flip Flop Timing
D
D Q
CLK
Q
<tPD
Q
CLK
D
>tSETUP >tHOLD
tPD: maximum propagation delay, CLK Q
tSETUP: setup time
guarantee that D has propagated through feedback path before master
closes
tHOLD: hold time
guarantee master is closed and data is stable before allowing D
to change
Synchronous Systems
data
Flipflop
Combinational
logic
Flipflop
trailing
edge
Clock
leading
edge
On the leading edge of the clock, the input of a flipflop is
transferred to the output and held.
We must be sure the output of the combinational logic has
settled before the next leading clock edge.
Fetching Sequential Instructions
4
P
C
Read
Address
+
Instruction
flipflop
Instruction
Memory
How about branch?
Datapath for R-type Instructions
ALU Operation
Inst Bits 25-21
Inst Bits 20-16
Inst Bits 15-11
5
5
5
3
Read Reg. 1 (rs)
Read Reg. 2 (rt)
data 1
Write Reg. (rd)
data 2
32
Write Data
RegWrite
32
32
MUX Blocks
Select
2 1 0
Select
Input
3
0
1
2
3
4
5
6
7
In
8
Out
The select signal determines which of the inputs is connected
to the output
Out
Inside there is a 32 way MUX per bit
Read Reg 1
5
Register 0
Register 1
Register 2
Register 3
Data 1
32 to1 MUX
Register 4
Register ...
Register 30
LOT’S OF
CONNECTIONS!
Register 31
For EACH bit in the 32 bit register
And this is just one port!
Remember, there’s
data1 and data2 coming
out of the register file!
Our Register File has 3 ports
2 Read Ports
This is one reason we have only a
small number of registers
What’s another reason?
Inst Bits 25-21
Inst Bits 20-16
Inst Bits 15-11
5
5
5
Read Reg. 1
Read Reg. 2
data 1
Write Reg.
data 2
32
32
32
Write Data
REALLY LOTS OF CONNECTIONS!
1 Write Port
RegWrite
Finite State Machines
 What is a State Machine?
 Remember automata?
 It is defined by the following:
 Set of STATES
 Set of INPUTS
 Set of OUTPUTS
 A mapping from (STATES, INPUTS) to …
… the next STATE and an OUTPUT
 STATE represents memory!
Implementing an FSM
Outputs
Inputs
Function
(comb. logic)
State
(flipflops)
Clock
Summary
 Regular Arrays can be used to implement arbitrary
logic functions
 Memories
 ROMs are HARDWIRED memories
 RAMs include storage elements that are read-write
 dynamic memory: compact, only reliable short-term
 static memory: controlled use of positive feedback
 For static storage:
 Level-sensitive D-latches; edge-triggered flipflops
 Timing issues: setup and hold times
 Finite State Machines (FSM)
 With just a register and some logic, we can implement a state
machine