COD Ch.

4
Arithmetic for Computers
Arithmetic

• Where we've been:

• performance
• abstractions
• instruction set architecture
• assembly language and machine language
• What's up ahead:
• implementing the architecture

operation

32 ALU
result

32
b

32
 MIPS – 2’s complement

• 32 bit signed numbers:

0000 0000 0000 0000 0000 0000 0000 0000two = 0ten

0000 0000 0000 0000 0000 0000 0000 0001two = + 1ten
0000 0000 0000 0000 0000 0000 0000 0010two = + 2ten
... maxint
0111 1111 1111 1111 1111 1111 1111 1110two = + 2,147,483,646ten
0111 1111 1111 1111 1111 1111 1111 1111two = + 2,147,483,647ten
1000 0000 0000 0000 0000 0000 0000 0000two = – 2,147,483,648ten
1000 0000 0000 0000 0000 0000 0000 0001two = – 2,147,483,647ten
1000 0000 0000 0000 0000 0000 0000 0010two = – 2,147,483,646ten
...
1111 1111 1111 1111 1111 1111 1111 1101two = – 3ten
1111 1111 1111 1111 1111 1111 1111 1110two = – 2ten
1111 1111 1111 1111 1111 1111 1111 1111two = – 1ten minint

Negative integers are exactly those that have leftmost bit 1

Two's Complement Operations
• Negation Shortcut: To negate any two's complement integer invert all bits and add
1
• note that negate and invert are different operations!
• why does this work? Remember we don’t know how to add in 2’s complement yet! Later…!

• Sign Extension Shortcut: To convert an n-bit integer into an integer with more than n
bits – i.e., to make a narrow integer fill a wider word – replicate the most significant
bit (msb) of the original number to fill the new bits to its left
• Example: 4-bit 8-bit
0010 = 0000 0010
1010 = 1111 1010
• why is this correct? Prove!
Two’s Complement Addition

• Perform add just as in junior school (carry/borrow 1s)

• Examples (4-bits):
0101 0110 1011 1001 1111
0001 0101 0111 1010 1110
Do these sums now!! Remember all registers are 4-bit including result register!
So you have to throw away the carry-out from the msb!!
• Have to beware of overflow : if the fixed number of bits (4, 8, 16, 32, etc.)
in a register cannot represent the result of the operation
• terminology alert: overflow does not mean there was a carry-out from the msb
that we lost (though it sounds like that!) – it means simply that the result in the
fixed-sized register is incorrect
• as can be seen from the above examples there are cases when the result is correct
even after losing the carry-out from the msb
 Two’s Complement Addition: Verifying
Carry/Borrow method
• Two (n+1)-bit integers: X = xnX’, Y = ynY’
n
Carry/borrow 0 ≤ X’ + Y’ < 2 2n ≤ X’ + Y’ < 2n+1 –
add X + Y (no CarryIn to last bit) 1
(CarryIn to last bit)
xn = 0, yn = 0 ok not ok(overflow!)
xn = 1, yn = 0 ok ok
xn = 0, yn = 1 ok ok
xn = 1, yn = 1 not ok(overflow!) ok

• Prove the cases above!

• Prove if there is one more bit (total n+2 then) available for the result
then there is no problem with overflow in add!
Two's Complement Operations

• Now verify the negation shortcut!

• consider X + (X +1) = (X + X) + 1:
associative law – but what if there is overflow in one of the adds on either
side, i.e., the result is wrong…!
• think minint !
• Examples:
• –0101 = 1010 + 1 = 1011
• –1100 = 0011 + 1 = 0100
• –1000 = 0111 + 1 = 1000
Detecting Overflow

• No overflow when adding a positive and a negative number

• No overflow when subtracting numbers with the same sign
• Overflow occurs when the result has “wrong” sign (verify!):

Operation Operand A Operand B Result

Indicating Overflow

A + B ≥ 0 ≥ 0 < 0
A + B < 0 < 0 ≥ 0
A – B ≥ 0 < 0 < 0
A – B < 0 ≥ 0 ≥ 0

• Consider the operations A + B, and A – B

• can overflow occur if B is 0 ?
• can overflow occur if A is 0 ?
Effects of Overflow

• If an exception (interrupt) occurs

• control jumps to predefined address for exception
• interrupted address is saved for possible resumption

• Details based on software system/language

• SPIM: see the EPC and Cause registers

• Don't always want to cause exception on overflow

• add, addi, sub cause exceptions on overflow
• addu, addiu, subu do not cause exceptions on overflow
Review: Basic Hardware
Review: Boolean Algebra & Gates

• Problem: Consider logic functions with three inputs: A, B, C.

• output D is true if at least one input is true
• output E is true if exactly two inputs are true
• output F is true only if all three inputs are true

• Show the truth table for these three functions

• Show the Boolean equations for these three
functions
• Show an implementation consisting of inverters,
AND, and OR gates.
 A Simple Multi-Function Logic Unit

• To warm up let's build a logic unit to support the and and or

instructions for MIPS (32-bit registers)
• we'll just build a 1-bit unit and use 32 of them
operation
selector

a
output
b

• Possible implementation using a multiplexor :

Implementation with a Multiplexor

• Selects one of the inputs to be the output

based on a control input

32 units
.
.

• Lets build our ALU using a MUX (multiplexor):

Implementations
• Not easy to decide the best way to implement something
• do not want too many inputs to a single gate
• do not want to have to go through too many gates (= levels)
• for our purposes, ease of comprehension is important
• Let's look at a 1-bit ALU for addition:

cout = a.b + [Link] + [Link]

sum = [Link] + [Link] +

• How could we build a 1-bit ALU for add, and, anda.b.c
or? + [Link]
in
• How could we build a 32-bit ALU? = a ⊕ b ⊕ cin
exclusive or (xor)
 1-bit Adder Logic

xor

Half-adder with one xor gate

Full-adder from 2 half-adders and

an or gate

Half-adder with the xor gate replaced

by primitive gates using the equation
A⊕B = A.B +A.B
Building a 32-bit ALU

Multiplexor control line

1-bit ALU for AND, OR and add

Ripple-Carry Logic for 32-bit ALU

Status Register
Multiply

• Grade school shift-add method:

Multiplicand 1000
Multiplier x 1001
1000
0000
0000
1000
Product 01001000
• m bits x n bits = m+n bit product
• Binary makes it easy:
• multiplier bit 1 => copy multiplicand (1 x multiplicand)
• multiplier bit 0 => place 0 (0 x multiplicand)
• 3 versions of multiply hardware & algorithm:
 Shift-add Multiplier Version 1

32-bit multiplicand starts at right half of multiplicand register

Product register is initialized at 0

Multiplicand register, product register, ALU are

64-bit wide; multiplier register is 32-bit wide

Algorithm
Shift-add Multiplier Version1

Example: 0010 * 0011:

Itera Step Multiplier Multiplicand Product

-tion
0 init 0011 0000 0010 0000 0000
values
1 1a 0011 0000 0010 0000 0010
2 0011 0000 0100 0000 0010
3 0001 0000 0100 0000 0010
2 …

Algorithm
 Observations on Multiply
Version 1

• 1 step per clock cycle ⇒ nearly 100 clock cycles to multiply two
32-bit numbers
• Half the bits in the multiplicand register always 0
⇒ 64-bit adder is wasted
• 0’s inserted to right as multiplicand is shifted left
⇒ least significant bits of product never
change once formed

• Intuition: instead of shifting multiplicand to left, shift product to right…

 Shift-add Multiplier Version 2

Product register is initialized at 0

Multiplicand register, multiplier register, ALU

are 32-bit wide; product register is 64-bit wide;
multiplicand adds to left half of product register
Algorithm
Shift-add Multiplier Version 2

Example: 0010 * 0011:

Itera Step Multiplier Multiplicand Product

-tion
0 init 0011 0010 0000 0000
values
1 1a 0011 0010 0010 0000
2 0011 0010 0001 0000
3 0001 0010 0001 0000
2 …

Algorithm
Observations on Multiply
Version 2

• Each step the product register wastes space that exactly matches the
current size of the multiplier

• Intuition: combine multiplier register and product register…

 Shift-add Multiplier Version 3

Product register is initialized with multiplier on right

No separate multiplier register; multiplier

placed on right side of 64-bit product register
Algorithm
Shift-add Multiplier Version 3

Example: 0010 * 0011:

Itera Step Multiplicand Product

-tion
0 init 0010 0000 0011
values
1 1a 0010 0010 0011
2 0010 0001 0001
2 …

Algorithm
 Observations on Multiply
Version 3

• 2 steps per bit because multiplier & product combined

• What about signed multiplication?
• easiest solution is to make both positive and remember whether to negate
product when done, i.e., leave out the sign bit, run for 31 steps, then negate if
multiplier and multiplicand have opposite signs

• Booth’s Algorithm is an elegant way to multiply signed numbers using same

hardware – it also often quicker…
Motivating Booth’s algorithm
• Example 0010 * 0110. Traditional:
0010
0110
0000 shift (0 in multiplier)
0010
x
add (1 in multiplier)
0010 add (1 in multiplier)
0000 shift (0 in multiplier)
00001100
• Same example. But observe there are two successive 1’s in multiplier
0110 = 22 + 21 = 23 – 21, so can replace successive 1’s by subtract and then add:
0010
0110
0000 shift (0 in multiplier)
-0010 sub (first 1 in multiplier)
0000 shift (middle of string of 1’s)
0010 add (previous step had last 1)
00001100
 Motivating Booth’s Algorithm

bit = 2n m
• Math idea: string of 1’s …011…10… hasbit = 2

value the sum 2n + 2n-1 + … + 2m = 2successive

n+1
– 2m 1’s

• Replace a string of 1s in multiplier with an initial subtract when we first see

a one and then later add after the last one
• What if the string of 1’s started from the left of the (2’s complement) number,
e.g., 11110001 – would the formula above have to be modified?!
 Booth from Multiply Version 3
• Modify Step 1 of the algorithm Multiply Version 3 to consider 2 bits of the multiplier: the current bit and the bit to the right
(i.e., the current bit of the previous step). Instead of two outcomes, now there are four:

Case Current Bit Bit to the Right Explanation Example Op

1a 0 0 Middle of run of 0s 0001111000 none
1b 0 1 End of run of 1s 0001111000 add
1c 1 0 Begins run of 1s 0001111000 sub
1d 1 1 Middle of run of 1s 0001111000 none

• Modify Step 2 of Multiply Version 3 to sign extend when the product is shifted right (arithmetic right shift, rather than
logical right shift) because the product is a signed number
• Now draw the flowchart for Booth’s algorithm !
• Multiply Version 3 and Booth share the same hardware, except Booth requires one extra flipflop to remember the bit to the
right of the current bit in the product register – which is the bit pushed out by the preceding right shift
 Booth Example (2 x 7)

Operation Multiplicand Product next?

0. initial value 0010 0000 0111 0 10 -> sub P = P - M

1c. 0010 1110 0111 0 shift P (sign ext)

2. 0010 1111 0011 1 11 -> nop
1d. 0010 1111 0011 1 shift P (sign ext)
2. 0010 1111 1001 1 11 -> nop
1d. 0010 1111 1001 1 shift P (sign ext)
2. 0010 1111 1100 1 01 -> add P = P + M
1b. 0010 0001 1100 1 shift P (sign ext)
2. 0010 0000 1110 0 done
 Booth Algorithm (2 * -3)

Operation Multiplicand Product next?

[Link] value 0010 0000 1101 0 10 -> sub P = P - M

1c. 0010 1110 1101 0 shift P (sign ext)

2. 0010 1111 0110 1 01 -> add P = P + M
1b. 0010 0001 0110 1 shift P (sign ext)
2. 0010 0000 1011 0 10 -> sub P = P - M
1c. 0010 1110 1011 0 shift P
2. 0010 1111 0101 1 11 -> nop
1d. 0010 1111 0101 1 shift P
2. 0010 1111 1010 1 done
Verifying Booth’s Algorithm
• multiplier a = a31 a32… a0, multiplicand = b
• ai ai-1 Operation
0 0 nop
0 1 add b
1 0 sub b
1 1 nop
• 0, nop
I.e., if ai-1 – ai = +1, add b
–1, sub b
• Therefore, Booth computes sum:
(a–1 – a0) * b * 20
+ (a0 – a 1) * b * 21
+ (a1 – a2) * b * 22
…
+ (a30 – a31) * b * 231
= … simplify telescopic sum! …
MIPS Notes

• MIPS provides two 32-bit registers Hi and Lo to hold a 64-bit product

• mult, multu (unsigned) put the product of two 32-bit register
operands into Hi and Lo: overflow is ignored by MIPS but can be
detected by programmer by examining contents of Hi
• mflo, mfhi moves content of Hi or Lo to a general-purpose register
• Pseudo-instructions mul (without overflow), mulo (with overflow),
mulou (unsigned with overflow) take three 32-bit register operands,
putting the product of two registers into the third
 Divide

1001 Quotient
Divisor 1000 1001010 Dividend
–1000
10
101
1010
–1000
10 Remainder

• Junior school method: see how big a multiple of the divisor can be
subtracted, creating quotient digit at each step
• Binary makes it easy ⇒ first, try 1 * divisor; if too big, 0 * divisor
• Dividend = (Quotient * Divisor) + Remainder
• 3 versions of divide hardware & algorithm:
 Divide Version 1

32-bit divisor starts at left half of divisor register

Quotient register is
initialized to be 0

Remainder register is initialized with the dividend at right

Divisor register, remainder register, ALU are

64-bit wide; quotient register is 32-bit wide

Why 33? We shall see later… Algorithm

Divide Version 1
Example: 0111 / 0010:

Itera- Step Quotient Divisor Remainder

tion
0 init 0000 0010 0000 0000 0111
1 1 0000 0010 0000 1110 0111
2b 0000 0010 0000 0000 0111
3 0000 0001 0000 0000 0111
2 …
3
4
5

Algorithm
 Observations on Divide Version 1

• Half the bits in divisor always 0

• ⇒ 1/2 of 64-bit adder is wasted
• ⇒ 1/2 of divisor register is wasted
• Intuition: instead of shifting divisor to right, shift remainder to left…

• Step 1 cannot produce a 1 in quotient bit – as all bits corresponding to the

divisor in the remainder register are 0 (remember all operands are 32-bit)
• Intuition: switch order to shift first and then subtract – can save 1
iteration…
 Divide Version 2 Start

1. Shift the Remainder register left 1 bit

Remainder register is initialized 2. Subtract the Divisor register from the

left half of the Remainder register and
with the dividend at right place the result in the left half of the
Remainder register

Remainder >
– 0 Remainder < 0
Test Remainder

3a. Shift the Remainder register to the 3b. Restore the original value by adding
left, setting the new rightmost bit to the Divisor register to the left half of the
Also0. shift the Quotient register to the left Remainder register and place the sum
setting to the new rightmost bit to 1. in the left half of the Remainder register.
Divisor register, quotient register, Also shift the Remainder register to the
left, setting the new rightmost bit to 0
ALU are 32-bit wide; remainder Also shift the Quotient register to the left
setting to the new rightmost bit to 0.
register is 64-bit wide

No: < 32 repetitions

32nd repetition?

Yes: 32 repetitions
Why this correction step? We shall see later… Algorithm
Done. Shift left half of Remainder right 1 bit
 Observations on Divide Version 2

• Each step the remainder register wastes space that exactly matches the
current size of the quotient

• Intuition: combine quotient register and remainder register…

 Divide Version 3

Remainder register is initialized with the dividend at right

No separate quotient register; quotient
is entered on the right side of the 64-bit
remainder register
Algorithm
Why this correction step? We shall see later…
Divide Version 3
Example: 0111 / 0010:

Itera- Step Divisor Remainder

tion
0 init 0010 0000 0111
1 0010 0000 1110
1 2 0010 1110 1110
3b 0010 0001 1100
2 …
3
4

Algorithm
 Number of Iterations

• Why the extra iteration in Version 1?

• Why the final correction step in Versions 2 & 3?
Ovals represent loop iterations
Main insight – sub(i+1) must actually follow shifti of
the divisor (or remainder, depending on version) and
Shift: see the version descriptions the resulting bit in the quotient appears on shift(i+1)
for which registers are shifted

shift1 shift2 … shift32 shift33

sub1 sub2 sub3 … sub32 sub33

V1 starts loop One loop iteration

Critical situation! Only the quotient shift is
here: unnecessary necessary as it corresponds to the
sub step V2 & 3 start outcome of the previous sub.
loop here So V1 is ok even though the last divisor
shift is redundant, as final divisor is ignored
V2 & 3 initial step:
any way; V2 & 3 must repair remainder
before loop starts
as it has shifted left one time too many
Observations on Divide Version 3

• Same hardware as Multiply Version 3

• Signed divide:
• make both divisor and dividend positive and perform division
• negate the quotient if divisor and dividend were of opposite signs
• make the sign of the remainder match that of the dividend
• this ensures always
• dividend = (quotient * divisor) + remainder
• –quotient (x/y) = quotient (–x/y) (e.g. 7 = 3*2 + 1 & –7 = –3*2 – 1)