UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.

ICS51 – Adders & Arithmetic Logic Unit (ALU)

Arithmetic Logic Unit - Introduction

• The Arithmetic Logic Unit (ALU) is the main component of the CPU. It performs
most instruction operations, mathematic and comparisons.
• The ALU performs addition and subtraction of two numbers, as well as logical
operations such as bitwise AND & OR of two values. For branching, it also
performs arithmetic to determine the slt (set on less than) instruction.
• ALUs also have additional hardware for Overflow and Zero detection

• The main component of the ALU is the adder. To build a 32-bit adder, we build
smaller simpler components and combine them together. The smallest of these units
is a 1-bit half adder.

1-bit Half Adder

• A 1-bit half adder takes the two 1-bit input values to perform the addition on. It creates two outputs, sum of
the inputs and a carry bit
o sum = ⊕ = ̅ + �
o carry =
• It is called a half adder because the unit does not take a carry-in value
o The carry-in is the carry-out of the addition for the previous digit of the values

1-bit Half Adder


UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.

1-bit Full Adder
• A 1-bit full adder takes the two 1-bit input values and a 1-bit carry-in to perform
the addition on. It creates two outputs, sum of the inputs and a carry bit
o Sum = ⊕ ⊕ [carry-in]
o CarryOut = Majority (A , B , Cin) .
 When any two or more inputs are 1, we have Cout .
• One approach to building a full adder is to chain together two half adders

• CarryOut can occur by a carry on either of the two half adders. Therefore, an OR gate is required to combine
these into a single output.
• To build an n-bit Adder, the 1-bit adders are chained together

1-bit Full Adder

Building ALUs
• An ALU has more functionality than the addition of 2 values
o Consider a 1-bit ALU that performs the operations:
a + b, a AND b, a OR b

• The unit will take two 1-bit input values (a and b) , a
carryIn bit, and create two 1-bit outputs, Result and
CarryOut
• To build a single black box unit which can output different
values, control bits are needed. The control bits specify to
the hardware which operation to output. Define the control
bits using the following table

Operation Control
Bits {C1, C0}
ALU
Operation
0 0 AND
0 1 OR
1 0 ADD 1 1 --------
UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.


• Note that this unit, orders the operation control bits differently than done in the video. The order is decided
by the designer and the ALU unit is built to that specification.

1-bit ALU

• A 32-bit ALU is built by connecting 32 of these 1-bit ALUs serially
o The carryOut of the previous digit is connected to the carryIn of
the next unit
o The control bits are connected to each 1-bit ALU unit

o The carryOut has to propagate from ALU0 to ALU31 – this takes
time making the unit slow
o This is called a ripple-carry ALU
o AND/OR operations are done in parallel. They are done quickly,
but because the addition operation takes longer, it is the critical
path

Adding other operations to the ALU: NAND & NOR
• Other operations can be added to the 1-bit ALU by extending the logic
• Whenever possible the existing hardware in the unit should be re-used

1-bit ALU – Extending Functionality

ALU: Adding Subtraction
• Subtraction can only be performed on n-bit numbers, where n > 1.
• The correct result can only be calculated when chaining 1-bit ALUs together. Part of the functionality for
subtraction can be added to the 1-bit ALU unit and the remaining logic can be added to the chained units
when building the n-bit ALU
• How is subtraction performed? Using 2’s complement addition
o A – B = A + 2’s complement of B
= A + (1’s comp. of B) + 1
o The 1’s complement value of B can be obtained by NOT-ing the bits of B
• The addition of A + (1’s comp. of B) is performed inside the 1-bit ALU
• The + 1 is performed when chaining together the n-bit ALU using the carry-in of the LSB (least significant
bit) unit.

• To add the subtraction operation to the unit, the adder needs to have the ability to add A+B as well as A +
B’ – This means CHOOSING between adding B or B’ depending on the control.
o A mux can be used to choose between B or B’
o Binvert is the control for the new mux. Binvert is not an input to the unit, but a Boolean expression.
The expression is a function of the Operation (control bits). Depending on the control bits for
subtraction, the expression for Binvert is determined.

UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.


ALU: Adding Set on Less Than
• Most MIPS branch instructions are pseudo-instructions which are broken down using the set on less
than instruction, slt rd, rs, rt .
• The set on less than instruction performs the following operation:
o Set destination register rd to 1 if rs is less than rt, 0 otherwise.
o To set rd to 1, we must create a 1 on the LSB of the result, the leftmost bits must be all zeros.

o rs is a and rt is b. If the result of a - b is negative, then rs• In this case the sign bit of the result will be 1.
• If rs>=rt, then the sign bit of the result will be 0.

• To support this operation in the 1-bit ALU, an output Set is added and a 1-bit input called Less.
o The Set is the result of the adder (before the multiplexor). The Set line of the MSB ALU unit is the sign
bit of the result.
o The Less input enables the sign bit to be connected to the Result of the LSB.
• The Less bit is set to 0 for the upper (or leftmost) 31 bits.



• In this figure, Ainvert was added to support NAND and
NOR functionality also
• Remember, both Ainvert and Binvert are Boolean
expressions based on the Operation control bits

• The Result outputs for the rightmost bit (the LSB) is also
selected from the Less input of that bit, but this value
actually comes from the Set output of the special 1-bit
ALU in the MSB. This Set value of the leftmost bit is
fed back as the Less input of the rightmost bit.

1-bit ALU – Subtraction
1-bit ALU – Set on Less Than
UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.


• Note that the Bnegate signal is fed in as the Binvert to each of the 32 1-bit ALUs.
o It is also fed in as the Cin input to the LSB ALU. This gives us the extra 1 value to add to the 1’s
complement of b in order to obtain its 2’s complement when doing subtraction a - b.
• This ALU has hardware for zero detection. If the Result of the ALU operation is the value zero, then the OR-
NOT (basically NOR) will result in a 1. Think of the Zero output as a flag for if the Result is the value 0.
o The beq instruction (and the pseudoinstruction beqz,
which translates to beq) both use the Zero line

Zero Detection


Building a Generic 1-bit ALU - Full Example

• When generic 1-bit ALU units are created, the same hardware
can be used for all bits of the n-bit ALU
• Often a special 1-bit ALU is built for the MSB (most
significant bit) to add extra logic for overflow detection
Set bit from MSB
is fed back to Less
input of LSB
Set bit from MSB
Less is set to 0 on
all upper bits

UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.



The Harris/Harris book builds an n-bit ALU with this instruction in the following way:

When the ALU operations are performed on N-bits, you are essentially using gates which handle N-bits at a
time. In the case of SLT, when when A-B is performed, the sign bit can be routed to the LSB of outpt Y and all
higher bits set to 0. In this way, the Y value is 1 if A is < B and , 0 if A>= B.

The same concept can applied when building ALU from 1-bit ALUs (or any ALU unit of < N bits).

Symbol for the ALU:
• The same symbol is used for adder as well.
• Less is not shown because it is internal to the ALU

The MIPS datapath uses the ALU control:

ALU control
bits
Operation
0 00 AND
0 01 OR
0 10 add
1 10 subtract
1 11 set on less than

Bnegate

• Earlier it was explained how NOR and NAND can be implemented using a inversion in the 1-bit ALUs.
However, for simplification, we have not included this in the ALU control bits above.
o Note that with NOR provided, we can use it to implement NOT as a pseudo-instruction. How?

Building Generic 1-bit ALU – Example #1 Building Generic 1-bit ALU – Example #2


two-bit Operation selector for the MUXes
which select the outputs of the 32 1-bit ALUs

学霸联盟