Transcript Double precision floating point

Csci 136 Computer Architecture II
– Floating-Point
Xiuzhen Cheng
[email protected]
Announcement
Homework assignment #5
Readings: Sections 4.8
Problems: 4.14, 4.15, 4.25-4.28, 4.55, 4.56
Project #2 is due March 6
1st Midterm: Thursday, February 26
Floating-Point
What can be represented in N bits?
Unsigned
2’s Complement
1’s Complement
Binary Coded Decimal
Excess M
0
- 2N-1
-2N-1+1
0
-M
to
to
to
to
to
2N-1
2N-1 - 1
2N-1-1
10N/4 – 1
2N - M – 1
(E = e + M)
But, what about?
very large numbers?
Will this fit in an integer?
9,349,398,989,787,762,244,859,087,678
very small number?
0.0000000000000000000000045691
rationals
2/3
irrationals
p
transcendentals
e
Recall Scientific Notation
exponent
Sign, magnitude
decimal point
23
6.02 x 10
Mantissa
1.673 x 10
-24
radix (base)
Sign, magnitude
Issues:
IEEE F.P. Single
± 1.Significand x 2
e - 127
Arithmetic (+, -, *, / )
Representation, Normal form
(What is Normal Form?)
Range and Precision
Rounding
Exceptions (e.g., divide by zero, overflow, underflow)
Errors
Properties ( negation, inversion, if A  B then A - B  0 )
Single-Precision Floating-Point
Representation of floating point numbers in IEEE 754 standard:
1
8
23
single precision
E
sign S
Significand
mantissa:
exponent:
sign + magnitude, normalized
excess 127
binary integer binary significand w/ hidden
integer bit: 1.0+Significand
actual exponent is
biased by 127
e = E - 127
0 < E < 255
S E-127
N = (-1) 2
(1.0+Significand)
Special Cases: 0 is an expoenent of all 0s
0 = 0 00000000 0 . . . 0
Magnitude of numbers that can be represented is in the range:
2
-126
to
which is approximately:
-38
to
1.8 x 10
2
127
3.40 x 10
38
Why use significand vice mantissa?
Representation of floating point numbers in IEEE 754:
single precision
1
S
8
E
23
Significand
We store a normalized binary significand
w/ hidden integer bit instead of the mantissa:
Mantissa = 1.0+Significand
Sign Exponent-127
N = (-1)
2
(1.0+Significand)
Translation: After Normalizing, we ALWAYS
eliminate the leading one in the Mantissa.
Why use biased exponent?
Representation of floating point numbers in IEEE 754:
1 8
23
single precision
S E
Significand
The exponent is stored as an excess 127 binary integer
What does this mean?
actual exponent is "biased" by 127 or 1023
stored exponent = real exponent + 127 for single
stored exponent = real exponent + 1023 for double
Sign E - 127
real number = (-1)
2
(1.0+Significand)
F.P. Comparison
Done as integer comparison. How?
Sign bit is the MSB
Exponent is before Significand
Biased exponent
Double-Precision Floating-Point
Overflow vs. Underflow
Exponent is too large or too small
Can you give an example?
Double precision floating point:
Use two MIPS word: 1 sign bit, 11 exponent bits and 52 bits of
significand
Magnitude of numbers that can be represented:
2.0x10-308 to 2.0x10308
Design favors integer comparison
bias of 1023
Floating-Point Representation Examples
How do we represent -1.5
Show the IEEE 754 binary representation of the
number –0.75 in single and double precision
What decimal number is represented by
1 100,0000,1 010,0000,0000,0000,0000,0000
Floating-Point Representation Examples
How do we represent -1.5
-1.5 = 1 01111111 10 . . . 0
Show the IEEE 754 binary representation of the
number –0.75 in single and double precision
What decimal number is represented by
1 100,0000,1 010,0000,0000,0000,0000,0000
Basic Addition Algorithm
(1) We'll need to convert from significand to mantissa
(2) We'll need to shift the smaller number so that we have
the same exponent:
num of shifts= Larger Number's exponent - Smaller Number's exponent
(2) right shift smaller number that many positions
(3) add or subtract the two numbers
(4) Normalize:
a. left shift result, decrement result exponent (e.g. 0.0001)
b. right shift result, increment result exponent (e.g. 101.1)
continue until MSB of data is 1 (will not be stored)
(5) Check for overflow or underflow
(6) if the result is a 0 mantissa, set the exponent to zero by
special step
An Example for F.P. Addition
Adding numbers 0.5ten and –0.4375ten, assume 4bits of
precision
Floating-Point Multiplication
Algorithm: Z = X * Y
result exponent = X's exponent + Y's exponent
result exponent = sum of stored exponents – bias
remember.. stored exponent = real exponent + bias
Multiply the significands: Zm = Xm x Ym
Normalization and exception checking (overflow
and underflow)
Determine the sign bit
Multiply numbers 0.5ten and –0.4375ten, assume 4bits
of precision
MIPS Floating-Point Instructions
32 floating-point registers: f0, …, f31. Only 16 of them
can be used for single-precision f. p. arithmetic
Floating-point arithmetic
add.s, add.d, sub.s, sub.d, mul.s, mul.d, div.s, div.d, …
Floating-point comparison: c.x.s, c.x.d
Floating-point data transfer: lwc1, swc1, l.d, s.d
Floating-point conditional branch: bc1t, bc1f
See page 291.
Accurate Arithmetic
There are infinite number of numbers between
0 and 1, hence even double precision floating point can
represent only a few of them
We want the floating point representation to be as
close as possible to the real number
IEEE: as if computed the result exactly and rounded
Eg. 2/3ten
Rounding – needs extra bits
IEEE 754 always keeps 2 extra bits on the right
during intermediate calculations, called guard and
round, respectively
Accurate Arithmetic
Compute 2.56x100 + 2.34x102, with 3 significant
decimal digits.
Guard Digits: digits to the right of the first p digits
of significand to guard against loss of digits – can
later be shifted left into the mantissa (significand)
during normalization.
Rounding Digits
When normalizing result, if there are some digits past the
right end of the significand (mantissa)
The number should be rounded
2-bias
0 2 1.69 = 1.6900 * 10
E.g., B = 10, p = 3:
2-bias
0 0 7.85 = - .0785 * 10
2-bias
0 2 1.61
= 1.6115 * 10
The round digit is carried to the right of the guard digit
so that after a normalizing left shifts, the result can still
be rounded.
-4
Consider 1.001 - (1.1 * 2 )
Rounding Digits
IEEE Standard:
four rounding modes: round to nearest even (default
round towards plus infinity
round towards minus infinity
round towards 0
round to nearest:
if guard and round < B/2 then truncate
> B/2 then round up
(add 1 to ULP: unit in last place)
= B/2 then round to nearest even digit
It can be shown that this strategy minimizes the
mean error introduced by rounding
Rounding Digits
Assume round to nearest even (default)
Round 10.1001 (binary) to an integer.
Round 10.1000 (binary) to an integer.
Round 10.0111 (binary) to an integer.
Round 11.1000 (binary) to an integer.
Sticky Bit
The sticky bit is an additional bit placed to the right of
the guard and round bits when doing floating point
calculations.
The sticky bit is set to 1 if it the value calculated for it is
a 1 OR any bit to the right of it is calculated to be a 1.
GRS
1.001
+0.0001001
1.001101
1.010
Note: In computer hardware terms.. a "sticky bit" is a
bit that remains set until it is explicitly cleared.
Denormalized Numbers
For single-precision f. p.
0 is 00000000000000000000000000000000
Smallest normalized number is
1.0000 0000 0000 0000 0000 000 x 2-126
This is actually a pretty big gap...
Gradual underflow: allow a number to degrade in
significance until it becomes 0
By getting rid of implicit leading 1 in front of the
significand... we can represent a smaller number
We denote a denormlized number by 0 exponent and a
non-zero significand
the smallest denormalized number is
0.0000 0000 0000 0000 0000 001 x 2-126 or 1.0 x 2-149
For double-precision f. p.
Smallest denormalized number: 1.0 x 2-1074
Infinity and NaNs
The result of an operation may overflow, i.e., be larger than
the largest number that can be represented
overflow is not the same as divide by zero
(it raises a different exception)
+/- infinity
S 1...1 0...0
We represent infinity by exponent of all 1s and significand
of all 0s. It may make sense to do comparisons with
infinity e.g., Y < infinity may be a valid comparison
Not a number, but not infinity (e.q. sqrt(-4))
invalid operation exception (unless operation is = or =)
NaN
S 1 . . . 1 non-zero
NaNs propagate: f(NaN) = NaN
Pentium Bug
Pentium FP Divider uses algorithm to generate multiple bits per
steps
FPU uses most significant bits of divisor & dividend/remainder to guess
next 2 bits of quotient
Guess is taken from lookup table: -2, -1,0,+1,+2 (if previous guess too
large a reminder, quotient is adjusted in subsequent pass of -2)
Guess is multiplied by divisor and subtracted from remainder to generate
a new remainder
Called SRT division after 3 people who came up with idea
Pentium table uses 7 bits of remainder + 4 bits of divisor = 211
entries
5 entries of divisors omitted: 1.0001, 1.0100, 1.0111, 1.1010,
1.1101 from PLA (fix is just add 5 entries back into PLA: cost
$200,000)
Self correcting nature of SRT => string of 1s must follow error
e.g., 1011 1111 1111 1111 1111 1011 1000 0010 0011 0111 1011 0100
(2.99999892918)
Since indexed also by divisor/remainder bits, sometimes bug
doesn’t show even with dangerous divisor value
Pentium bug appearance
First 11 bits to right of decimal point always correct: bits
12 to 52 where bug can occur (4th to 15th decimal digits)
FP divisors near integers 3, 9, 15, 21, 27 are dangerous
ones:
3.0 > d  3.0 - 36 x 2–22 , 9.0 > d  9.0 - 36 x 2–20
15.0 > d  15.0 - 36 x 2–20 , 21.0 > d  21.0 - 36 x 2–19
0.333333 x 9 could be problem
In Microsoft Excel, try (4,195,835 / 3,145,727) * 3,145,727
= 4,195,835 => not a Pentium with bug
= 4,195,579 => Pentium with bug
(assuming Excel doesn’t already have SW bug patch)
Rarely noticed since error in 5th significant digit
Success of IEEE standard made discovery possible:
all computers should get same answer
Pentium Bug Time line
June 1994: Intel discovers bug in Pentium: takes months to
make change, reverify, put into production: plans good chips in
January 1995 4 to 5 million Pentiums produced with bug
Scientist suspects errors and posts on Internet in September
1994
Nov. 22 Intel Press release: “Can make errors in 9th digit ... Most
engineers and financial analysts need only 4 of 5 digits.
Theoretical mathematician should be concerned. ... So far only
heard from one.”
Intel claims happens once in 27,000 years for typical spread
sheet user:
1000 divides/day x error rate assuming numbers random
Dec 12: IBM claims happens once per 24 days: Bans Pentium
sales
5000 divides/second x 15 minutes = 4,200,000 divides/day
IBM statement: http://www.ibm.com/Features/pentium.html
Intel said it regards IBM's decision to halt shipments of its Pentium
processor-based systems as unwarranted.
Pentium jokes
Q: What's another name for the "Intel Inside" sticker they put on
Pentiums?
A: Warning label.
Q: Have you heard the new name Intel has chosen for the Pentium?
A: the Intel Inacura.
Q: According to Intel, the Pentium conforms to the IEEE standards
for floating point arithmetic. If you fly in aircraft designed using a
Pentium, what is the correct pronunciation of "IEEE"?
A: Aaaaaaaiiiiiiiiieeeeeeeeeeeee!
TWO OF TOP TEN NEW INTEL SLOGANS FOR THE PENTIUM
9.9999973251 It's a FLAW, Dammit, not a Bug
7.9999414610 Nearly 300 Correct Opcodes
Pentium conclusion: Dec. 21, 1994 $500M write-off
“To owners of Pentium processor-based computers and the PC community:
We at Intel wish to sincerely apologize for our handling of the recently
publicized Pentium processor flaw.
The Intel Inside symbol means that your computer has a microprocessor second to
none in quality and performance. Thousands of Intel employees work very hard to
ensure that this is true. But no microprocessor is ever perfect.
What Intel continues to believe is technically an extremely minor problem has taken
on a life of its own. Although Intel firmly stands behind the quality of the current
version of the Pentium processor, we recognize that many users have concerns.
We want to resolve these concerns.
Intel will exchange the current version of the Pentium processor for an
updated version, in which this floating-point divide flaw is corrected, for
any owner who requests it, free of charge anytime during the life of their
computer. Just call 1-800-628-8686.”
Sincerely,
Andrew S. Grove
President /CEO
Craig R. Barrett
Executive Vice President
&COO
Gordon E. Moore
Chairman of the Board