Transcript ch3a

Chapter Three
Numbers
•
•
•
•
Computer words are composed of bits, thus words can be represented
as binary numbers
Binary numbers (base 2)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001...
decimal: 0...2n-1
Of course it gets more complicated:
numbers are finite (overflow)
fractions and real numbers
negative numbers
e.g., no MIPS subi instruction; addi can add a negative number
How do we represent negative numbers?
i.e., which bit patterns will represent which numbers?
Possible Representations
•
•
•
Sign Magnitude:
000 = +0
001 = +1
010 = +2
011 = +3
100 = -0
101 = -1
110 = -2
111 = -3
One's Complement
000 = +0
001 = +1
010 = +2
011 = +3
100 = -3
101 = -2
110 = -1
111 = -0
Two's Complement
000 = +0
001 = +1
010 = +2
011 = +3
100 = -4
101 = -3
110 = -2
111 = -1
Issues: balance, number of zeros, ease of operations
Which one is best? Why?
•
The MIPS word is 32 bits long, so we can represent 232 different 32-bit patterns. It
is natural to let these combinations represent the numbers from 0 to 232 -1.
•
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
...
1111 1111 1111 1111 1111 1111 1111 1101two = 4,294,967,293ten
1111 1111 1111 1111 1111 1111 1111 1110two = 4,294,967,294ten
1111 1111 1111 1111 1111 1111 1111 1111two = 4,294,967,295ten
MIPS
•
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
...
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
Two's Complement Operations
•
Two’s complement representation has the advantage that all negative numbers have a 1 in
the most significant bit. Consequently hardware needs to test only this bit to see if a
number is positive or negative (with 0 considered positive). This bit is often called the
sign bit.
•
What is the decimal value of this 32 bit two’s complement number?
1111 1111 1111 1111 1111 1111 1111 1100
Ans : (1X -231) + (1 X 230) +………………..+ 22 + 0 + 0 = -4ten
•
Negating a two's complement number: invert all bits and add 1
– remember: “negate” and “invert” are quite different!
•
Converting n bit numbers into numbers represented 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), (lhu vs lh), (slt vs sltu), (slti vs sltiu)
•
The function of a signed load is to copy the sign repeatedly to fill the rest of the
register. Unsigned loads simply fill with 0s to the left of the data
• Suppose $s0 has the binary number
1111 1111 1111 1111 1111 1111 1111 1111two
and register $s1 has the binary number
0000 0000 0000 0000 0000 0000 0000 0001two
What are the values of register $t0 and $t1 after these two instructions?
slt $t0, $s0, $s1
sltu $t1, $s0, $s1
Addition & Subtraction
•
•
Just like in grade school (carry/borrow 1s)
0111
0111
+ 0110
- 0110
0110
- 0101
Two's complement operations easy
– subtraction using addition of negative numbers
0111
+ 1010
•
Overflow (result too large for finite computer word): i.e the result of an operation
cannot be represented with the available hardware.
– e.g., adding two n-bit numbers does not yield an n-bit number
Detecting Overflow
•
•
•
•
In 2’s complement, an addition or subtraction overflow occurs when the result
overflows in to the sign bit.
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
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!
note: sltu, sltiu for unsigned comparisons
Multiplication
•
•
•
More complicated than addition
– accomplished via shifting and addition
More time and more area
1101 (multiplicand)
x1011 (multiplier)
Multiplication: Implementation
Start
Multiplier0 = 1
1. Test
Multiplier0 = 0
Multiplier0
1a. Add multiplicand to product and
Multiplicand
place the result in Product register
Shift left
64 bits
Multiplier
Shift right
64-bit ALU
2. Shift the Multiplicand register left 1 bit
32 bits
Product
Write
3. Shift the Multiplier register right 1 bit
Control test
64 bits
No: < 32 repetitions
32nd repetition?
Datapath
Yes: 32 repetitions
Control
Done
Final Version
Start
•Multiplier starts in right half of product
Product0 = 1
1. Test
Product0 = 0
Product0
Multiplicand
32 bits
32-bit ALU
Product
Shift right
Write
Control
test
3. Shift the Product register right 1 bit
64 bits
No: < 32 repetitions
32nd repetition?
What goes here?
Yes: 32 repetitions
Done
•
•
•
•
MIPS provides a separate pair of 32 bit registers to contain the 64 bit product,
called Hi and Lo.
To produce a properly signed or unsigned product, MIPS has two instructions
Mult (multiply) and multu (multiply unsigned)
To fetch the integer 32 bit product, the programmer uses mflo (move from lo )
and mfhi (move from hi)
•
Faster multiplications are possible by essentially providing one 32 bit adder for
each bit of the multiplier: one input is the multiplicand ANDed with a
multiplier bit and the other is the output of a prior adder.