Welcome to Computer Organization and Assembly!
FSMs,
Multiplication, and Division
CS/COE 0447
Jarrett Billingsley
1
Class announcements
exams are graded 🙂
CS447
2
2
States and Transitions
CS447
3
3
Characterizing the blinky
state is all the things that are remembered by a system. (hardware or software!)
the blinky can be in two states: on or off.
CS447
4
on
off
when the clock ticks, what happens to the state?
if it was off, it turns on.
if it was on, it turns off.
this is a state transition diagram.
D
Q
– state in programming is all your globals, objects, arrays etc. that are in use at any given time.
4
More states
what states can a ceiling fan be in?
high, medium, low, and off
what says, “go to the next step/state?”
pulling the chain!
CS447
5
off
high
med
low
pull
pull
pull
pull
how many bits of state are needed now?
– I don’t really know why they go high, medium, low, but they do.
– two bits!
5
Automatic Caution Door
consider an automatic swinging door. it has an input: a pad.
CS447
6
closed
opening
open
closing
when someone steps on the pad, it opens.
when no one is stepping on the pad, it closes.
it also has to know when to stop moving, so…
there are really three inputs: the pad, the open sensor, and the closed sensor.
– this is a pretty simplified model; real doors have two pads, a timer, other sensors, modes to stay open/closed, etc.
6
More abstractly…
for each transition, we write the inputs that cause it to happen.
CS447
7
closed
opening
open
closing
pad=1
pad=0
open_sensor=1
closed_sensor=1
pad=0
open_sensor=0
pad=1
closed_sensor=0
we should also make transitions for when to stay in a state.
but we can make it smarter, too. what if someone steps on the pad while it’s closing?
pad=1
AND pad=0
7
It’s getting cluttered
a state transition table is the sequential version of a truth table.
it encodes the same information as a state transition diagram.
CS447
8
Sn Sn+1
off high
high med
med low
low off
off
high
med
low
this input column says “the state at time n.”
the output is the next state: the state at time n+1.
of course, this machine has no inputs (other than the pull-chain), so…
each arrow becomes one row in the table: Sn is the “from” and Sn+1 is the “to.”
8
The door controller (animated)
this is gonna be a bigger table. 3 inputs, 4 states, 9 arrows…
CS447
9
closed
opening
open
closing
pad=1
pad=0
open_sensor=1
closed_sensor=1
pad=0
open_sensor=0
pad=1
closed_sensor=0
AND pad=0
pad=1
Sn pad OS CS Sn+1
0
closed
closed
1
closed
opening
0
opening
opening
1
opening
open
1
open
open
0
open
closing
0
closing
closing
1
closing
opening
1
closing
closed
0
idc
we’ve got a bunch of empty inputs.
what do we put in there?
one way of shortening a big truth or transition table is to use X’s.
CS447
10
Sn pad OS CS Sn+1
closed 0 closed
closed 1 opening
opening 0 opening
opening 1 open
open 1 open
open 0 closing
closing 0 0 closing
closing 1 opening
closing 1 closed
X is a don’t-care. it means “0 or 1.”
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
think about it… with 4 states and 3 inputs, that would be 32 rows, but we got it down to 9!
there’s some weirdness down here in the “closing” state but let’s just handwave that away
– for example, the first row is shorthand for 000, 001, 010, and 011.
– the weirdness is that there’s some overlap in the last two rows; e.g. both would “match” 1 0 1
– really the second to last row should be “closing 1 x 0 | opening” but
– we’re kinda assuming that it’s impossible for the pad AND the closing sensor to both be 1
– it’s just an example okay! don’t worry about it!
10
Finite State Machines (FSMs)
CS447
11
What’s a Finite State Machine (FSM)?
an FSM is a way of thinking about a sequential process where:
CS447
12
there is state (memory)
the state changes based on the current state, transition logic, and (optionally) inputs
there are outputs based on the state
(and maybe on the inputs, too)
D
Q
state
memory
transition
logic
inputs
output
logic
outputs
– this is a sort of pseudo-schematic view but it often does look like this
12
A repeating pattern
many hardware and software problems can be thought of as FSMs
CS447
13
FSMs are used for all sorts of control tasks: appliances, HVAC, infrastructure, etc.
they’re used for parsing: code, file formats, network protocols, etc.
for(int i = 0; i < 10; i++) { ... }
- HVAC = heating, ventilation, air conditioning
- before we had cheap microcontrollers, lots of devices used FSMs made of discrete components to control them
- think vending machines, traffic lights, automatic doors…
- and before THAT, we used mechanical FSMs
- some things still do… you know that weird crunchy-sounding knob on your washing machine? yep.
- mechanical thermostats, mechanical alarm clocks, sewing machines, looms, jukeboxes, etc.
13
Yo dawg I heard you like FSMs
when you're designing a complex system with state...
breaking it into smaller FSMs can be a useful design technique
CS447
14
maybe you're making a game…
setup
play
win
lose
and the whole program is an FSM
player_accel=0
Explosion_frame=3
Explosion_timer=1
Bullet_frame=4
Bullet_frame=17
Object_x=0x3402
Object_y=0x07F0
and each object is an FSM
and every frame they look at inputs, change state, and produce some output
- well you didn't make something quite this complex but it was still FSMs-in-FSMs!
14
The big picture
the overall architecture of any computer looks like this:
CS447
15
Memory
Inputs
Outputs
Registers
Control
Datapath
State
Transition Logic
There are lots of states
your whole computer is an FSM :^)
with 4GB RAM, 32 32-bit registers, plus some more registers in there, and all the input/output devices have memory and regs…
we're talking somewhere on the order of uhhhhh
2137438954496 states
that is, 2 to the "number of bits of storage" states.
it's a finite number of states but it's so ridiculously huge that it's practically infinite
CS447
16
- the number of states is 2 raised to the number of bits of storage.
- so, it adds up really, really fast.
16
What's the limit?
well... theoretically speaking, they're limited.
there are some problems that cannot be solved with a finite number of states.
they are not Turing-complete in the strictest sense.
but in reality, nothing is infinite, so…
for all practical purposes, they can do anything.
put enough of them together, and you get a computer.
or a universe. maybe.
I'm summing up a lot of CS 1502 in a few lines, so… spoilers!
CS447
17
- matter and energy are quantized into finite states; but we don't know if the universe itself is infinite, or if space and time are quantized, and we don't really understand the underlying logic of the state transitions except probabilistically…
17
Multiplication and Division
CS447
18
Can you turn code into hardware? (yes)
we used this algorithm to do multiplication:
CS447
19
while(multiplier != 0)
{
if((multiplier & 1) != 0)
product += multiplicand
multiplicand <<= 1
multiplier >>= 1
}
what is a loop, really?
what can we use to make a decision? and how can we extract 1 bit?
what do we use to remember values over multiple steps?
how do we “stop” the loop?
do we really have to do the things inside the loop in order, like in software?
– a loop is a sequence of actions over time.
– a MUX or write enable can be used to make the decision
– a splitter can be used to extract a bit
– registers are used to remember the values
– stop the loop by just… not changing any of the registers?
– and no, not necessarily; we can probably do some things in parallel. that’s definitely tricky.
19
A very common pattern
have a look at simple_counter.circ
CS447
20
D
Q
+
1
this could really be anything though. like… shifting?
this is a very simple FSM. every clock tick, it adds 1 to the value in the register.
this is the hardware equivalent of “x = x + 1”.
but we can reuse this pattern to come up with several parts of our multiplier.
20
So… what are we gonna need
we’ve got 3 variables: multiplicand, multiplier, and product
we need to shift one left, shift one right, and add to one of them
CS447
21
1
D
Q
multiplicand
1
D
Q
multiplier
D
Q
product
multiplicand <<= 1
multiplier >>= 1
product += multiplicand
<< >>
+
hey, 3×3 and 5×7 work!
but 7×5 doesn’t…
that’s cause it always adds the multiplicand to the product.
21
“Conditional execution”
we have two conditions in the original algorithm:
CS447
22
if((multiplier & 1) != 0)
while(multiplier != 0)
this means, “extract the multiplier’s LSB.”
we want everything to stop changing when multiplier == 0.
we can’t stop the clock, but we can disable all the registers when this happens.
then, we only enable writing to the product when it’s 1.
see slow_mult_4x4.circ for the solution!
– I know I said “MUXes are your first choice for making choices” but in this case, write enables just happen to be… convenient-er
22
Tangent: the fast multiplication circuit
remember there were two phases:
calculating the partial products
summing them
calculating the partial products is easy
it’s just shifts and ANDs
in hardware, shifting can be done by just rerouting wires!
summing the partial products is easy
we use a binary tree of adders!
the product just pops out the end.
of course, this uses a lot of silicon…
have a look at fast_mult_4x4.circ
CS447
23
+
+
+
+
+
+
+
Fun Stuff
Partial Products
What about division?
well… multiplication and division have a lot in common
we can do division with a very similar circuit!
you’ll explore this in lab6.
CS447
24
/docProps/thumbnail.jpeg