Week 2 Tutorial  Building an ALU
1 Introduction
 This week, we are going to build an Arithmetic Logic Unit from scratch,
using a handful of simple logic gates and other components.
 The ALU will take in two 32bit values, and 2 control lines. Depending
on the value of the control lines, the output will be the addition,
subtraction, bitwise AND or bitwise OR of the inputs.
 Schematically, here is what we want to build:
 Note! This is an interface for the ALU: what goes in, what
comes out. It also shows the ALU as an abstraction: you can't
see how it works, but you do know what it does.
 Also note that there are three status outputs as well as the main
result: is the result zero, was there a carry, and did the operation
result in an overflow?
 Note: just a reminder on the difference between a carry and an overflow:
 Carry: was there a carry in the mostsignificant bit which
we could not output in the given number of bits (32 bits, above).
 Overflow: does the sign of the output differ from the inputs,
indicating (for example) that a sum of two positive numbers has overflowed
and is now a negative result!
 Some of the data and control lines are shown with a slash and a number
like 32.
 This indicates that the line is actually 32 lines in parallel, e.g.
the result is 32bits wide. If you don't see a slash in the diagrams
below, you can assume that the line is only 1bit wide.
1.1 Basic Components
 We are going to use four logic gates: AND, OR, NOT and XOR. You should
have seen these already in other subjects. Below are the icons for
each, and their truth table.
 We are going to use another component, the multiplexor. The
job of the multiplexor is to choose one of several inputs, based on
a control line, and send the chosen input to the output.
 This multiplexor above is a 1bit wide 2way multiplexor: 2 inputs,
1 bit wide each. If you add extra control lines, you can choose more
inputs: 2 control lines is used in a 4way multiplexor, 3 control
lines in an 8way multiplexor etc.
 And by using multiple multiplexors in parallel, you can make Nbit
wide multiplexors.
 I'm not going to show you the internals of the multiplexor. You should,
however, know that it can be easily built with the 4 logic gates above.
1.2 Bitwise AND
 Bitwise AND is very useful, for example to calculate an IP network's
identity:
 131.245.7.18 AND 255.255.255.0 => 131.245.7.0
 Building the logic to do 32bit AND on two inputs is easy: as each
bit is independent, we just need 32 AND gates in parallel.
 Note the interface diagram on the right. Each time we build a larger
component, we are going to hide it behind an interface.
1.3 Bitwise OR
 32bit bitwise OR is just as easy as bitwise AND, we just need 32
OR gates in parallel.
1.4 Addition
 Addition isn't going to be so easy.
 We saw previously that we have to add bits, and this may produce a
carry. Columns further up need to accept a carry as input, along with
two inputs, and produce the 1bit output and another carry for the
next column up.
 The component which will perform a 1bit ADD, receiving a carry in
and producing a 1bit output and a carry out is called a full
adder. Its interface looks like the following:
 Internally, here is what a full adder looks like, just 5 logic gates.
 The truth table for the full adder is:
Cin  A  B  Result  Cout 

0  0  0  0  0 
0  0  1  1  0 
0  1  0  1  0 
0  1  1  0  1 
1  0  0  1  0 
1  0  1  0  1 
1  1  0  0  1 
1  1  1  1  1 
 At some point sit down, try some inputs, and convince yourself that
the logic works as advertised!
 To make a 32bit full adder, we simply have to string 32 of these
1bit full adders together.
 Except for the leastsignificant adder, each one is going to receive
its carry from the one below and pass up its own carry to the one
above.
 For the most significant bit, if the carry is a 1, then we ran out
of bits to store the result.
 When the final carry output is 1, this indicates that the result was
too big to fit into 32 bits.
 I'm going to delay showing you the interface diagram for the 32bit
full adder, because we can modify it to also do subtraction.
1.5 Subtraction
 We could build a completely separate component, a 32bit subtractor,
once we work out how to build a 1bit subtractor.
 Fortunately, we can simplify things a bit.
 According to the rules of maths: 32=3+(2).
 If we could negate one of the inputs, we could use the existing 32bit
full adder.
 We have already seen two algorithms to negate a twos complement binary
integer.
 One of them works as follows: invert every bit in the number, then
add 1.
 Putting all of the above together, we can say:
A  B = A + (B) = A + ~B + 1
 Inverting every bit is easy: we can use a NOT gate for each bit in
B.
 But now we need to do A + ~B + 1. How can we do this?
 We are going to use a very clever trick.
 Set the initial carryin to 1 instead of 0, thus adding an extra 1
to the sum.
 And instead of using NOT gates, we will use XOR gates.
 If we are doing addition (Control=0), then one arm of the XOR gates
is zero, and the B bits go into the adders unchanged, and the carryin
is zero.
 If we are doing subtraction (Control=1), then one arm of the XOR gates
is one. This inverts all of the B bits before they get to the adders.
As well, the carryin is now 1, so we achieve the result of doing
A  B = A + ~B + 1!
 Overall, we end up with this unit which can do addition and subtraction:
 If the operation bit is 0, we pass in B and perform A+B. If the operation
bit is 1, we invert B and do A + ~B + 1.
 We can now distinguish between data lines (which pass data
around) and control lines (which control the actions of the
components).
 The data lines are also known as datapaths.
 The Operation line above is a control line, as it controls
the action being performed. But note, it is also used as a 1value
for the carryin, so it is also a piece of data!
1.6 Overflow Output
 We've seen that a carry occurs when the final addition or subtraction
is too big to fit into 32 bits.
 A related mathematical output is overflow. This indicates that
the sign of the maths result differs from the sign of the two inputs.
 Imagine we were using 4bit numbers: you do 7 + 7 and get the result
2!
 Why? Because 7 (0111) + 7 (0111) = 1110, which in 4bit twoscomplement
is 2.
 Overflow occurs when the size of the inputs is such that there is
a carry which changes the mostsignificant sign bit.
 The ALU will always output both carry and overflow, but both only
makes sense when the operation is add or subtract.
 When we are doing the logical operations (AND and OR), the values
on the carry and overflow outputs have no meaning.
 As overflow is only maths related, this should be implemented in the
ADD/SUBTRACT unit.
 The logic is follows: when adding, if the sign of the two inputs is
the same, but the result sign is different, then we have an overflow.
 The boolean expression is [`a31]·[`b31]·result31+a31·b31·[`result31].
 We have to do this only for addition, so we take the b31 value after
the XOR gate, i.e. just as it goes into the mostsignificant adder.
1.7 Negative Output
 When is the result negative? When its mostsignificant bit is 1.
 We can wire this bit directly out of the ALU, so that it indicates
if the result is negative.
1.8 Zero Output
 One thing left to do is to provide the zero output: is the result
zero?
 This is only true if all of the bits of the result are zero.
We can do this for the logical and the maths units.
 To do this, we can use a 32bit OR gate followed by a 1bit NOT gate:
 The OR gate outputs a 0 only if all input bits are 0. If any input
bit is a 1, the OR's output is a 1.
 The NOT gate simply inverts this, giving the result:
 if any result bit is on, the output is 0, i.e. not zero.
 if all result bits are off, the output is 1, i.e. zero.
1.9 Putting It All Together
 We are getting close to being able to build the full ALU.
 We now have three main units:
 a 32bit bitwise AND unit,
 a 32bit bitwise OR unit, and
 a 32bit ADD/SUBTRACT unit with a control line.
 the logic to output carry, overflow, zero and negative.
 We can pass the inputs A and B to all three units, and perform all
three operations in parallel:
 But, we need to choose which of the three results we want, based on
the two control lines coming into the ALU. We would like:
c_{1}  c_{0}  Result 

0  0  A AND B 
0  1  A OR B 
1  0  A + B 
1  1  A  B 
 How do we control which of the four operations actually becomes the
result? With multiplexors again.
 When c_{0}=0, the ANDORresult is A AND B, and the ADDSUBresult
is A + B.
 When c_{0}=1, the ANDORresult is A OR B, and the ADDSUBresult is
A  B.
 Now we just have to choose between these two results, and that is
done with the second multiplexor, which chooses either the bitwise
logic result or the maths result.
 To finish off, we can draw the three components, the multiplexors
and the zero logic, to reveal the final 32bit ALU.
 The dotted line shows the interface to the ALU.
1.11 Implementing the ALU
 Here is the above ALU implemented in Logisim:
ALUweek2.circ
 This is only an 8bit version, but extending it to be a 32bit CPU
is simple but tedious.
 Download the file, run Logisim, and open the above circuit.
 Select the Hand icon in the topleft of the Logisim window, then click
on the data inputs and the two control inputs to change their values.
 Try out some additions, a subtraction, some ANDs and ORs, and satisfy
yourself that the ALU works as advertised.
 See if you can put in some input values which cause an oveflow.
1.12 Conclusion
 That's about all we can cover in terms of ALU design in this subject.
 Obviously, real ALUs perform many more operations, and use many performance
optimisations.
 This is just a taste of ALU design, but you should now understand
that:
 an ALU is just a collection of logic components;
 the logic components can be made from ordinary logic gates;
 data can flow in parallel to multiple units;
 everything operates in parallel: several units can produce output
internally;
 control logic, via multiplexors, chooses which output to use as the
result.
 For more interested students, the ALU chapter in Patterson & Hennessy
goes into much more detail and covers more operations such as multiplication
and division.
File translated from
T_{E}X
by
T_{T}H,
version 3.85.
On 2 May 2011, 12:26.