20 September 2005
Arithmetic and its implementation
Exam next Thursday
Arithmetic
Where we've been:
Abstractions
Instruction Set Architecture
Assembly Language and Machine Language
What's ahead:
Implementing the Architecture
ALU
Numbers
Bits are just bits (no inherent meaning)
conventions define relationship between bits and numbers
Binary numbers (base 2)
binary: 0 1 10 11 100 101 110 111 1000 ...
decimal: 0...2^n1
Of course it gets more complicated:
numbers are finite (overflow)
fractions and real numbers
negative numbers
 e.g., no MIPS subi; addi can add a negative number)
How do we represent negative numbers?
which bit patterns will represent which numbers?
Possible Representations
Bits 
Sign Magnitude 
1's complement 
2's complement 
000 
+0 
+0 
+0 
001 
+1 
+1 
+1 
010 
+2 
+2 
+2 
011 
+3 
+3 
+3 
100 
0 
3 
4 
101 
1 
2 
3 
110 
2 
1 
2 
111 
3 
0 
1 
Issues: balance, number of zeros, ease of operations
Which is best? Why?
MIPS uses 2's complement
32bit signed numbers
0000 0000 0000 0000 0000 0000 0000 0000 = 0 0000 0000 0000 0000 0000 0000 0000 0001 = +1 0000 0000 0000 0000 0000 0000 0000 0010 = +2 ... 0111 1111 1111 1111 1111 1111 1111 1110 = +2,147,483,646 0111 1111 1111 1111 1111 1111 1111 1111 = +2,147,483,647 1000 0000 0000 0000 0000 0000 0000 0000 = –2,147,483,648 1000 0000 0000 0000 0000 0000 0000 0001 = –2,147,483,647 1000 0000 0000 0000 0000 0000 0000 0010 = –2,147,483,646 ... 1111 1111 1111 1111 1111 1111 1111 1101 = – 3 1111 1111 1111 1111 1111 1111 1111 1110 = – 2 1111 1111 1111 1111 1111 1111 1111 1111 = – 1
2's complement operations
Negate a 2's complement number by inverting all bits and add 1
remember: “negate” and “invert” are quite different!
3 == (0011) == ~0011 + 1 == 1100 + 1 == 1101
Converting n bit numbers into numbers with more than n bits:
MIPS 16 bit immediate gets converted to 32 bits for arithmetic
copy the most significant bit (the sign bit) into the other bits
0010 > 0000 0010
1010 > 1111 1010
"sign extension" (lbu vs. lb)
Addition & Subtraction
Just like in grade school (carry/borrow 1's)
00111 
00111 
00110 
+ 00110 
 00110 
 00101 
01101 
00001 
00001 
2's complement operations are easy
00000111 
00000111 
 00000110 
+ 11111010 

00000001 
Overflow (result too large for finite word)
01110000 
+ 00010000 
10000000 
Detecting Overflow
No overflow when adding a positive and a negative number
No overflow when signs are the same for subtraction
Overflow occurs when the value affects the sign:
overflow when adding two positives yields a negative
or, adding two negatives gives a positive
or, subtract a negative from a positive and get a negative
or, subtract a positive from a negative and get a positive
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
An exception (interrupt) occurs
Control jumps to predefined address for exception
Interrupted address is saved for possible resumption
Details based on software system / language
example: flight control vs. homework assignment
Don't always want to detect overflow
 new MIPS instructions: addu, addiu, subu  note: addiu still signextends the operand  note: sltu, sltiu for unsigned comparisons
Logic Functions
Boolean Algebra & Gates
Consider a logic function with three inputs: A, B, and 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.
Truth Table
A 
B 
C 
D 
E 
F 
0 
0 
0 
0 
0 
0 
0 
0 
1 
1 
0 
0 
0 
1 
0 
1 
0 
0 
0 
1 
1 
1 
1 
0 
1 
0 
0 
1 
0 
0 
1 
0 
1 
1 
1 
0 
1 
1 
0 
1 
1 
0 
1 
1 
1 
1 
0 
1 
D=ABC E=(~A&B&C)(A&~B&C)(A&B&~C) F=A&B&C
An ALU
Let's build an ALU to support andi and ori instructions. We'll build a 1 bit ALU and use 32 of them.
ALU truth table
op 
a 
b 
result 
0 
0 
0 
0 
0 
0 
1 
1 
0 
1 
0 
1 
0 
1 
1 
1 
1 
0 
0 
0 
1 
0 
1 
0 
1 
1 
0 
0 
1 
1 
1 
1 
~op & (ab)  op & a & b == ~op&a  ~op&b  op&a&b
Multiplexor
Selects one of the inputs to be the output
1bit ALU for Addition
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
Ease of comprehension is most important to us
1bit ALU for Addition
a 
b 
cin 
sum 
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 
Cout = a&b  a&Cin  b&Cin sum = a&~b&~Cin  ~a&b&~Cin  ~a&~b&Cin  a&b&Cin
Building a 32 bit ALU
What about subtraction?
2's complement: just negate b and add, how?
Tailoring the ALU to MIPS
Need to support the setonlessthan instruction (slt)
remember: slt is an arithmetic instruction
produces a 1 if rs < rt and 0 otherwise
use subtraction: (ab) < 0 implies a < b
Need to support test for equality (beq $t5, $t6, $t7)
use subtraction: (ab) = 0 implies a = b
Implement SLT
Test for equality
Conclusion
We can build an ALU to support the MIPS instruction set
key idea: use multiplexor to select the output we want
we can efficiently perform subtraction using two’s complement
we can replicate a 1bit ALU to produce a 32bit ALU
Important points about hardware
all of the gates are always working
the speed of a gate is affected by the number of inputs to the gate
the speed of a circuit is affected by the number of gates in series (on the “critical path” or the “deepest level of logic”)
Our primary focus: comprehension, however,
Clever changes to organization can improve performance (similar to using better algorithms in software)
Educational Highlight
IEEE Computer Society 7th Annual International Design Competition
Work in a team to design a computerbased application that makes the world a better place