Welcome to Computer Organization and Assembly!
Arithmetic and Decisions
CS/COE 0447
Jarrett Billingsley
1
Class announcements
last day to withdraw is Friday, 3/26
2
CS447
2
Binary addition, in logic
CS447
3
Is a half-truth a lie?
let’s try to come up with a truth table for adding two bits
each column will hold 1 bit
CS447
4
A
B
C
0
0
1
1
0
1
0
1
0
0
0
1
S
0
1
1
0
let’s name the inputs A and B
let’s name the outputs C and S, for Carry and Sum
for the input values, we count up in binary
now let’s fill in the output values
great! But this is wrong.
hey, this C column looks familiar… what about S?
– whenever making a truth table, ALWAYS count up in binary – it’s so easy to miss cases if you jump around
– C and S form a 2-bit number
– C just looks like A & B
– S looks like A xor B
4
The full truth
what we just made was a half-adder
it has a carry output but not a carry input
(which might be useful for the lowest bit)
but might not be, as we’ll see
to make a full adder, we need 3 input bits
CS447
5
A
B
Co
0
0
1
1
0
1
0
1
0
0
0
1
S
0
1
1
0
0
0
1
1
0
1
0
1
Ci
0
0
0
0
1
1
1
1
0
1
1
0
1
0
1
1
00111 110
1011 0010
+0010 1111
1110 0001
A
B
Co
S
Ci
– Ci = Carry in, Co = Carry out
5
The logic of it all
it looks a little messy, but it kinda makes sense if you think of it like this:
it counts how many input bits are “1”
if we look at the outputs in isolation:
S is 1 if we have an odd number of “1s”
Co is 1 if we have 2 or 3 “1s”
there’s a full adder example circuit for you
CS447
6
A
B
Co
0
0
1
1
0
1
0
1
0
0
0
1
S
0
1
1
0
0
0
1
1
0
1
0
1
Ci
0
0
0
0
1
1
1
1
0
1
1
0
1
0
1
1
– Again, Co and S are a 2-bit number
– it might not be obvious, but we can come up with a collection of gates that output each of these columns
6
Sweeping that under the rug…
in programming, we use functions to be able to reuse code
in schematics, we can group these 5 gates into a component
here’s the symbol for a one-bit full adder
CS447
7
+
B
A
Ci
Co
S
inputs are like parameters
outputs are like return values
now we don’t have to care how it adds, just that it does
unfortunately Logisim flips this upside down but whatever.
– Logisim does this with a lot of components (puts the least significant bit up top instead of at the bottom) and I don’t know why.
7
Making a component in Logisim
we can use Project > Add Circuit… to make a new component
CS447
8
then we can edit it by double-clicking it on the left
this is like editing a function’s code
the next lab will go into more detail on how to make components.
now we can place multiple instances of the component on the main circuit, like making function calls.
a component has pins: its inputs and outputs
8
Adding longer numbers
CS447
9
Where do the carries go?
when you add one place, you might get a carry out
that becomes the carry in for the next higher place
CS447
10
1 0 1 1 0 0 1 0
+0 0 1 0 1 1 1 1
Bit Bucket..?
– what is this called?
– how can we handle it?
10
Ripple Carry
if we want to add two three-bit numbers, we’ll need three one-bit adders
we chain the carries from each place to the next higher place, like we do on paper
we have to split the numbers up like so:
CS447
11
+
B0
A0
S0
+
B1
A1
S1
+
B2
A2
S2
A2 A1 A0
B2 B1 B0
S2 S1 S0
+
Logisim’s multi-bit adders do this stuff for you.
– it’s called ripple carry because the carry “ripples” from the LSB to the MSB one place at a time
– well, okay, Logisim’s multi-bit adders are just using the + operator because they’re written in Java but CONCEPTUALLY, OKAY?
11
What goes into multi-bit adders; multi-bit wires?
in reality, a wire can only carry 1 bit.
but we’re living in schematic-land.
if we want to, say, NOT a 32-bit value, we can draw it like:
CS447
12
32
32
this is shorthand for 32 parallel wires and 32 NOT gates.
Logisim calls these wires wire bundles and colors them black.
it doesn’t draw the slashes and numbers though…
orange wires happen when you have two things of different bit widths connected together.
it’s like a type error. you have to make sure the bit widths of the things on both ends are the same.
12
Gate Delay
CS447
13
(courtesy of Kate Temkin)
electrical signals can’t move infinitely fast
transistors can’t turn on and off infinitely fast
since each digit must wait for the next smaller digit to compute its carry…
ripple carry is linear in the number of digits
this is a diagram of how the outputs of a 16-bit ripple carry adder change over time
they added 0xFFFF + 1
it’s measured in picoseconds! so ~100ps total
but if we went to 32 bits, it’d take 200ps
and 64 bits, 400ps…
there are more efficient ways of adding
details, schmetails
300
400
– look-ahead carry is faster but requires O(n^2) space.
– I think there are also some diminishing returns there, so what you usually see is a weird hybrid approach:
– they do look-ahead carry on chunks of bits (fractions of the word size), and then ripple those carries to the next chunk of bits
– I say “details, schmetails” because it doesn’t really matter. we could have an entire lecture on adding binary numbers. it would not improve your understanding of how a computer works.
13
Flip side
remember how we do subtraction?
x – y = x + (-y) = x + ~y + 1
we can NOT y with… what gate?
how do we add 1 without any extra circuitry?
we use a full adder for the LSB, and when
we’re subtracting, set the “carry in” to 1
now we’re doing x + ~y + 1!
CS447
14
+
~B0
A0
S0
+
~B1
A1
S1
1
– we can NOT y with a NOT gate. cmon, it’s literally the name. I GIVE YOU THE ANSWER IN THE QUESTION!!!
14
1 if overflow!
Detecting unsigned overflow in hardware
how did we detect unsigned overflow?
we can look at the MSB’s carry-out.
when adding, if it’s 1, it’s an overflow.
when subtracting, if it’s 0, it’s an overflow.
which interpretation is it? well, we’d have to make a decision…
which we’ll learn about shortly!
CS447
15
+
B0
A0
S0
+
B1
A1
S1
+
B2
A2
S2
15
Detecting signed overflow in hardware
how did we detect signed overflow?
same input signs; different output sign.
that feels truth-table-y.
CS447
16
SB
So
O
0
0
1
1
0
1
0
1
0
1
0
0
0
0
1
1
0
1
0
1
SA
0
0
0
0
1
1
1
1
0
0
1
0
when the input signs differ, we can’t have an overflow, so those rows are all 0.
when the input signs match, overflow happens when the output sign differs.
– oh, you’re doing a lab about this, aren’t you ;V
16
A semi-related tangent
CS447
17
What makes a good word size?
can you think of an example of…
100 of something?
a million of something? a billion?
a quintillion (1018)? more?
28 = 256, 216 ≅ 65,000, 232 ≅ 4 billion, 264 ≅ 18 quintillion
for a given word size, all the circuitry has to be built to support it
64 1-bit adders
128 wires going in
64 wires coming out
wire bundles aren’t real; real circuits have to deal with this problem!
this is the problem of interconnect
(and also has analogies to real-world transportation infrastructure)
CS447
18
– this problem of interconnect is also where those blue X wires come in handy…
– in real circuits, you can save a LOT of space by reusing one wire for multiple purposes
– that’s called a bus, and buses rely on that blue X state to work properly.
18
Hardware that
makes decisions
19
CS447
19
How you’re used to doing it
how do we make decisions in programming?
with if-elses, conditional loops, switches…
CS447
20
if(mode == 1)
return A – B;
else
return A + B;
if mode == 1, is the else clause run?
No.
when you make a decision in software, only one code path is run; the others never happen.
20
How hardware does it
instead of making the decision first and then doing one thing…
hardware does all possible things, then decides which to use.
CS447
21
sum = A + B;
diff = A – B;
if(mode == 1)
return diff;
else
return sum;
when you make a decision in hardware, you do all possible things, then pick only the thing you need, and ignore the rest.
this seems wasteful, but: these two paths can be run at the same time!
hardware is really good at doing things in parallel, so we may as well.
– counterintuitively, it can actually be more complex to “do one thing” than to “do all things.”
– but, that can make your circuits more energy-efficient, so a lot of recent CPU designs include this sort of thing.
– look up “clock gating;” basically, you turn off the parts of the CPU that you aren’t using at any given time.
21
Multiplexers
a multiplexer (mux) outputs one of its inputs based on a select.
22
Y
A
B
S
This is the select input.
Y
A
B
S=0
A
Y
B
S=1
CS447
the unselected input is ignored!
– muxes are universal too! you can build any logic gate – and therefore an entire computer – out of muxes
22
Big muxes
a mux can have any (power-of-2) number of inputs
here’s one with 4 inputs!
to choose among 4 values… how big does the select signal have to be now?
2 bits.
23
Y
A
B
S
CS447
C
D
2
00
01
10
11
this is a bit like a hardware switch-case.
23
Implementing this if-else
now we have enough information to do this:
CS447
24
if(mode == 1)
return A – B;
else
return A + B;
mode
result
the select signal is basically the condition.
–
+
A
B
if
else
we send the input values to all possible branches.
24
Warning: demultipliexers considered pointless
a demultiplexer (demux) is the opposite of a multiplexer, but…
25
In
S
In
S=0
0
In
S=1
0
CS447
with very few exceptions, you won’t need these.
95% of the times I’ve seen people using them, they’re pointless.
but hold that thought for later.
– when we get to register files and instruction decoding, these will become useful!
25
/docProps/thumbnail.jpeg