Transcript Computer Arthmetic - University of Waikato

Computer Arthmetic
Chapter Three P&H
Data Representation






Why do we not encode numbers as strings of ASCII
digits inside computers?
What is overflow when applied to binary operations
on data
Why do we not use signed magnitude to represent
numbers inside computers?
What is the two’s compliment number
representation?
How is a twos compliment number sign extended?
Why does MIPs have:


lb and lbi instructions
slt and slti instructions
Addition and Subtraction

No overflow possible when:




Overflow occurs when:



Adding numbers with different signs
Subtracting numbers with same sign
one of numbers is zero
Adding two numbers with same sign and sign of
result is different
Subtracting numbers with different signs & result is
the same sign as second number
MIPs handles overflow with an exception
MIPs ALU Design

MIPS ALU requirements

Add, AddU, Sub, SubU, AddI, AddIU


And, Or, AndI, OrI, Xor, Xori, Nor



=> 2’s complement adder/sub with overflow detection
=> Logical AND, logical OR, XOR, nor
SLTI, SLTIU (set less than)
=> 2’s complement adder with inverter, check
sign bit of result
Different Implementations

Not easy to decide the “best” way to build something
Don't want too many inputs to a single gate
Don’t want to have to go through too many gates
for our purposes, ease of comprehension is important




Let's look at a 1-bit ALU for addition:
CarryIn
a
Sum
b
cout = a b + a cin + b cin
sum = a xor b xor cin
CarryOut

How could we build a 1-bit ALU for add, and, and or?

How could we build a 32-bit ALU?
Building a 32 bit ALU
CarryIn
a0
b0
Operation
CarryIn
ALU0
Result0
CarryOut
Operation
CarryIn
a1
a
0
b1
CarryIn
ALU1
Result1
CarryOut
1
Result
a2
2
b
b2
CarryIn
ALU2
Result2
CarryOut
CarryOut
a31
b31
CarryIn
ALU31
Result31
What about subtraction (a – b) ?

Two's complement approach: just negate b and add.
How do we negate?

A very clever solution:

Binvert
Operation
CarryIn
a
0
1
b
0
2
1
CarryOut
Result
Tailoring the ALU to the MIPS


Need to support the set-on-less-than instruction (slt)

remember: slt is an arithmetic instruction

produces a 1 if rs < rt and 0 otherwise

use subtraction: (a-b) < 0 implies a < b
Need to support test for equality (beq $t5, $t6, $t7)

use subtraction: (a-b) = 0 implies a = b
Binvert
Operation
CarryIn
Supporting slt
a
0
1
Result
b
0
2
1
Less
3
a.
CarryOut
Binvert
Operation
CarryIn
a
0
1
Result
b
0
2
1
Less
3
Set
Overflow
detection
b.
Overflow
Binvert
CarryIn
a0
b0
CarryIn
ALU0
Less
CarryOut
a1
b1
0
CarryIn
ALU1
Less
CarryOut
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Operation
Result0
Result1
Result2
CarryIn
a31
b31
0
CarryIn
ALU31
Less
Result31
Set
Overflow
Test for equality
Bnegate

Notice control lines:
000
001
010
110
111
=
=
=
=
=
and
or
add
subtract
slt
Operation
a0
b0
CarryIn
ALU0
Less
CarryOut
Result0
a1
b1
0
CarryIn
ALU1
Less
CarryOut
Result1
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Result2
Zero
•Note: zero is a 1 when the result is zero!
a31
b31
0
CarryIn
ALU31
Less
Result31
Set
Overflow