Transcript Memories and State Machines

Computer Organization and Design
Memories and State Machines
Montek Singh
Mon, Nov 12, 2012
Lecture 15
Topics
 Memory Arrays
 Transparent Latches
 Edge-triggered Registers
 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
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
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
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
<tPD
Q
Q
CLK
CLK
D
tPD: maximum propagation delay, CLK Q
>tSETUP >tHOLD
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
Designing digital systems using a clock
We will first design the main building blocks of a MIPS
processor, then put it all together!
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.
Clock period must be “long enough”
Clock Period >= tFF + tlogic + tsetup
Fetching Sequential Instructions
32
4
32
P
C
32
Read
Address
32
+
Instruction
flipflop
Instruction
Memory
How about
branches, etc.?
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
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