Transcript slides in ppt

CPSC 161
Lecture 6
Prof. L.N. Bhuyan
http://www.cs.ucr.edu/~bhuyan/cs161/index
.html
.1
1999©UCB
Numbers
° Bits are just bits (no inherent meaning)
— conventions define relationship between
bits and 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?
.2
1999©UCB
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?
.3
1999©UCB
MIPS
° 32 bit signed numbers:
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
...
0111 1111 1111 1111
2,147,483,646ten
0111 1111 1111 1111
2,147,483,647ten
1000 0000 0000 0000
2,147,483,648ten
1000 0000 0000 0000
2,147,483,647ten
1000 0000 0000 0000
2,147,483,646ten
...
1111 1111 1111 1111
1111 1111 1111 1111
1111 1111 1111 1111
.4
0000 0000 0000 0000two = 0ten
0000 0000 0000 0001two = + 1ten
0000 0000 0000 0010two = + 2ten
1111 1111 1111 1110two = +
1111 1111 1111 1111two = +
maxint
0000 0000 0000 0000two = –
minint
0000 0000 0000 0001two = –
0000 0000 0000 0010two = –
1111 1111 1111 1101two = – 3ten
1111 1111 1111 1110two = – 2ten
1111 1111 1111 1111two = – 1ten
1999©UCB
Two's Complement Operations
° 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 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)
.5
1999©UCB
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):
• e.g., adding two n-bit numbers does not yield an n-bit number
0111
+ 0001
note that overflow term is somewhat misleading,
1000
it does not mean a carry “overflowed”
.6
1999©UCB
MIPS ALU Instructions
° Add, AddU, Sub, SubU, AddI, AddIU
• => 2’s complement adder/sub with overflow
detection
° And, Or, AndI, OrI, Xor, Xori, Nor
• => Logical AND, logical OR, XOR, nor
° SLTI, SLTIU (set less than)
• => 2’s complement adder with inverter,
check sign bit of result
.7
1999©UCB
MIPS arithmetic instruction format
31
R-type:
I-Type:
.8
25
20
op
Rs
Rt
op
Rs
Rt
15
5
Rd
0
funct
Immed 16
Type
op
funct
Type
op
funct
ADDI
10
xx
ADD
00
ADDIU 11
xx
SLTI
12
SLTIU
Type
op
funct
40
00
50
ADDU 00
41
00
51
xx
SUB
00
42
SLT
00
52
13
xx
SUBU 00
43
SLTU 00
53
ANDI
14
xx
AND
00
44
ORI
15
xx
OR
00
45
XORI
16
xx
XOR
00
46
LUI
17
xx
NOR
00
47
1999©UCB
Refined Requirements
(1) Functional Specification
inputs:
2 x 32-bit operands A, B, 4-bit mode
outputs:
32-bit result S, 1-bit carry, 1 bit overflow
operations: add, addu, sub, subu, and, or, xor, nor, slt, sltU
(2) Block Diagram
32
32
A
c
ovf
B
ALU
4
m
S
32
.9
1999©UCB
Refined Diagram: bit-slice ALU
A
32
B
32
a0
b0
ALU0 m
co
cin
s0
a31
b31
ALU0 m
co
cin
s31
4
M
Ovflw
32
S
° Co = a.b + a.Cin + b.Cin
° Sum =
.10
1999©UCB
Seven plus a MUX ?
° Design trick 2: take pieces you know (or can
imagine) and try to put them together
° Design trick 3: solve part of the problem and extend
S-select
CarryIn
and
A
B
1-bit
Full
Adder
Mux
or
Result
add
CarryOut
.11
1999©UCB
Additional operations
° A - B = A + (– B)
• form two complement by invert and add one
S-select
invert
CarryIn
and
A
B
1-bit
Full
Adder
Mux
or
Result
add
CarryOut
Set-less-than? – left as an exercise
.12
1999©UCB
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 ?
.13
1999©UCB
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
.14
1999©UCB
Overflow Detection
° Overflow: the result is too large (or too small) to represent
properly
• Example: - 8 < = 4-bit binary number <= 7
° When adding operands with different signs, overflow cannot
occur!
° Overflow occurs when adding:
• 2 positive numbers and the sum is negative
• 2 negative numbers and the sum is positive
° On your own: Prove you can detect overflow by:
• Carry into MSB ° Carry out of MSB
0
+
.15
1
1
1
1
0
1
1
1
7
0
0
1
1
3
1
0
1
0
–6
+
0
1
1
0
0
–4
1
0
1
1
–5
0
1
1
1
7
1999©UCB
Overflow Detection Logic
° Carry into MSB ° Carry out of MSB
• For a N-bit ALU: Overflow = CarryIn[N - 1] XOR
CarryOut[N - 1]
CarryIn0
A0
B0
A1
B1
A2
B2
1-bit
Result0
ALU
CarryIn1 CarryOut0
1-bit
Result1
ALU
CarryIn2 CarryOut1
1-bit
ALU
B3
1-bit
ALU
Y
X XOR Y
0
0
0
0
1
1
1
0
1
1
1
0
Result2
CarryIn3
A3
X
Overflow
Result3
CarryOut3
.16
1999©UCB
But What about Performance?
° Critical Path of n-bit Rippled-carry adder is
n*CP
CarryIn0
A0
B0
A1
B1
A2
B2
A3
B3
1-bit
Result0
ALU
CarryIn1 CarryOut0
1-bit
Result1
ALU
CarryIn2 CarryOut1
1-bit
Result2
ALU
CarryIn3 CarryOut2
1-bit
ALU
Result3
CarryOut3
Design Trick: throw hardware at it
.17
1999©UCB
Carry Look Ahead (Design trick: peek)
Cin
A0
B1
A
0
0
1
1
S
G
P
C1 =G0 + C0  P0
A
B
S
G
P
A
B
B
0
1
0
1
C-out
0
C-in
C-in
1
“kill”
“propagate”
“propagate”
“generate”
P = A and B
G = A xor B
C2 = G1 + G0 P1 + C0  P0  P1
S
G
P
C3 = G2 + G1 P2 + G0  P1  P2 + C0  P0  P1  P2
A
B
S
G
P
G
P
C4 = . . .
.18
1999©UCB
Cascaded Carry Look-ahead (16-bit): Abstraction
C
L
A
C0
G0
P0
C1 =G0 + C0  P0
4-bit
Adder
C2 = G1 + G0 P1 + C0  P0  P1
4-bit
Adder
C3 = G2 + G1 P2 + G0  P1  P2 + C0  P0  P1  P2
G
P
4-bit
Adder
.19
C4 = . . .
1999©UCB
Additional MIPS ALU requirements
° Mult, MultU, Div, DivU (next lecture)
=> Need 32-bit multiply and divide, signed and
unsigned
° Sll, Srl, Sra (next lecture)
=> Need left shift, right shift, right shift
arithmetic by 0 to 31 bits
° Nor (leave as exercise to reader)
=> logical NOR or use 2 steps: (A OR B) XOR
1111....1111
.20
1999©UCB
Multiplication
° More complicated than addition
• accomplished via shifting and addition
° More time and more area
° Let's look at 3 versions based on a
gradeschool algorithm
0010 (multiplicand)
__x_1011 (multiplier)
° Negative numbers: convert and multiply
• there are better techniques, we won’t look at
them
.21
1999©UCB
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
.22
Done
1999©UCB
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
.23
1999©UCB
Floating Point (a brief look)
° We need a way to represent
• numbers with fractions, e.g., 3.1416
• very small numbers, e.g., .000000001
• very large numbers, e.g., 3.15576  109
° Representation:
• sign, exponent, significand:
2exponent
(–1)sign  significand 
• more bits for significand gives more accuracy
• more bits for exponent increases range
° IEEE 754 floating point standard:
• single precision: 8 bit exponent, 23 bit significand
• double precision: 11 bit exponent, 52 bit significand
.24
1999©UCB
IEEE 754 floating-point standard
° Leading “1” bit of significand is implicit
° Exponent is “biased” to make sorting
easier
• all 0s is smallest exponent all 1s is largest
• bias of 127 for single precision and 1023 for double
precision
• summary: (–1)sign  (1+significand)  2exponent – bias
° Example:
• decimal: -.75 = - ( ½ + ¼ )
• binary: -.11 = -1.1 x 2-1
• floating point: exponent = 126 = 01111110
.25
• IEEE single precision:
10111111010000000000000000000000
1999©UCB
Floating point addition
°
Sign
Exponent
Fraction
Sign
Exponent
1. Compare the exponents of the two numbers.
Shift the smaller number to the right until its
exponent would match the larger exponent
Small ALU
Exponent
difference
0
Start
Fraction
2. Add the significands
1
0
1
0
1
3. Normalize the sum, either shifting right and
incrementing the exponent or shifting left
and decrementing the exponent
Shift right
Control
Overflow or
underflow?
Big ALU
Yes
No
0
0
1
Increment or
decrement
Exception
1
4. Round the significand to the appropriate
number of bits
Shift left or right
No
Rounding hardware
Still normalized?
Yes
Sign
Exponent
Fraction
Done
.26
1999©UCB
Floating Point Complexities
° Operations are more complicated (see text)
° In addition to overflow we can have “underflow”
° Accuracy can be a big problem
• IEEE 754 keeps two extra bits, guard and round
• four rounding modes
• positive divided by zero yields “infinity”
• zero divide by zero yields “not a number”
• other complexities
° Implementing the standard can be tricky
° Not using the standard can be even worse
.27
• see text for description of 80x86 and Pentium bug!
1999©UCB
Chapter Three Summary
° Computer arithmetic is constrained by limited precision
° Bit patterns have no inherent meaning but standards do exist
• two’s complement
• IEEE 754 floating point
° Computer instructions determine “meaning” of the bit
patterns
° Performance and accuracy are important so there are many
complexities in real machines
° Algorithm choice is important and may lead to hardware
optimizations for both space and time (e.g.,
multiplication)
° You may want to look back (Section 3.10 is great reading!)
.28
1999©UCB