Arithmetic

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^n-1

• 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

• Issues: balance, number of zeros, ease of operations

• Which is best? Why?

MIPS uses 2's complement

• 32-bit 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)

2's complement operations are easy

Overflow (result too large for finite word)

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 sign-extends 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

D=A|B|C   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) | op & a & b == ~op&a | ~op&b | op&a&b

Multiplexor

Selects one of the inputs to be the output

1-bit 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

1-bit ALU for Addition

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 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

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 1-bit ALU to produce a 32-bit 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 computer-based application that makes the world a better place