9/28/21 1 Queen’s University CISC 221: Computer Architecture Instructors: Yuanzhu Chen Floating Point CISC 221: Computer Architecture Fall 2021 1 2 Queen’s University CISC 221: Computer Architecture Outline ¢ Background: Fractional binary numbers ¢ IEEE floating point standard: Definition ¢ Example ¢ Properties ¢ Rounding, addition, multiplication ¢ Floating point in C 2 9/28/21 2 3 Queen’s University CISC 221: Computer Architecture Background & Motivation 3 4 Queen’s University CISC 221: Computer Architecture ¢ What is 1011.1012? Fractional Binary Numbers 4 9/28/21 3 5 Queen’s University CISC 221: Computer Architecture 2i 2i-1 4 2 1 1/2 1/4 1/8 2-j bi bi-1 ••• b2 b1 b0 b-1 b-2 b-3 ••• b-j • • • Fractional Binary Numbers ¢ Representation § Bits to right of “binary point” represent fractional powers of 2 § Represents rational number: • • • 5 6 Queen’s University CISC 221: Computer Architecture Fractional Binary Numbers: Examples ¢ Value Representation 5 3/4 101.112 2 7/8 010.1112 1 7/16 001.01112 ¢ Observations § Divide by 2 by shifting right (unsigned) § Multiply by 2 by shifting left § Numbers of form 0.111111…2 are just below 1.0 § 1/2 + 1/4 + 1/8 + … + 1/2i + … ➙ 1.0 § Use notation 1.0 – ε 6 9/28/21 4 7 Queen’s University CISC 221: Computer Architecture Representable Numbers ¢ Limitation #1 § Can only exactly represent numbers of the form x/2k § Other rational numbers have repeating bit representations § Value Representation § 1/3 0.0101010101[01]…2 § 1/5 0.001100110011[0011]…2 § 1/10 0.0001100110011[0011]…2 ¢ Limitation #2 § Just one setting of binary point within the w bits § Limited range of numbers (very small values? very large?) 7 8 Queen’s University CISC 221: Computer Architecture IEEE Standard 754 8 9/28/21 5 9 Queen’s University CISC 221: Computer Architecture IEEE Floating Point ¢ IEEE Standard 754 § Established in 1985 as uniform standard for floating point arithmetic § Before that, many idiosyncratic formats § Supported by all major CPUs ¢ Driven by numerical concerns § Nice standards for rounding, overflow, underflow § Hard to make fast in hardware § Numerical analysts predominated over hardware designers in defining standard 9 10 Queen’s University CISC 221: Computer Architecture ¢ Numerical Form: (–1)s M 2E § Sign bit s determines whether number is negative or positive § Significand M normally a fractional value in range [1.0,2.0). § Exponent E weights value by power of two ¢ Encoding § MSB s is sign bit s § exp field encodes E (but is not equal to E) § frac field encodes M (but is not equal to M) Floating Point Representation s exp frac 10 9/28/21 6 11 Queen’s University CISC 221: Computer Architecture Precision options ¢ Single precision: 32 bits ¢ Double precision: 64 bits ¢ Extended precision: 80 bits (Intel only) s exp frac 1 8-bits 23-bits s exp frac 1 11-bits 52-bits s exp frac 1 15-bits 63 or 64-bits 11 12 Queen’s University CISC 221: Computer Architecture “Normalized” Values ¢ When: exp ≠ 000…0 and exp ≠ 111…1 § (o.w., denormalized and special values; coming up next) ¢ Exponent coded as a biased value: E = Exp – Bias § Exp: unsigned value of exp field § Bias = 2k-1 - 1, where k is number of exponent bits § Single precision: 127 (Exp: 1…254, E: -126…127) § Double precision: 1023 (Exp: 1…2046, E: -1022…1023) ¢ Significand coded with implied leading 1: M = 1.xxx…x2 § xxx…x: bits of frac field § Minimum when frac=000…0 (M = 1.0) § Maximum when frac=111…1 (M = 2.0 – ε) § Get extra leading bit for “free” v = (–1)s M 2E 12 9/28/21 7 Carnegie Mellon 13 Queen’s University CISC 221: Computer Architecture Normalized Encoding Example ¢ Value: float F = 15213.0; § 1521310 = 111011011011012 = 1.11011011011012 x 213 ¢ Significand M = 1.11011011011012 frac= 110110110110100000000002 ¢ Exponent E = 13 Bias = 127 Exp = 140 = 100011002 ¢ Result: 0 10001100 11011011011010000000000 s exp frac v = (–1)s M 2E E = Exp – Bias 13 14 Queen’s University CISC 221: Computer Architecture Denormalized Values ¢ Condition: exp = 000…0 ¢ Exponent value: E = 1 – Bias (instead of E = 0 – Bias) ¢ Significand coded with implied leading 0: M = 0.xxx…x2 § xxx…x: bits of frac ¢ Cases § exp = 000…0, frac = 000…0 § Represents zero value § Note distinct values: +0 and –0 (why?) § exp = 000…0, frac ≠ 000…0 § Numbers closest to 0.0 § Equispaced v = (–1)s M 2E E = 1 – Bias 14 9/28/21 8 15 Queen’s University CISC 221: Computer Architecture Special Values ¢ Condition: exp = 111…1 ¢ Case: exp = 111…1, frac = 000…0 § Represents value ¥ (infinity) § Operation that overflows § Both positive and negative § E.g., 1.0/0.0 = −1.0/−0.0 = +¥, 1.0/−0.0 = −¥ ¢ Case: exp = 111…1, frac ≠ 000…0 § Not-a-Number (NaN) § Represents case when no numeric value can be determined § E.g., sqrt(–1), ¥ − ¥, ¥ ´ 0 15 16 Queen’s University CISC 221: Computer Architecture Visualization: Floating Point Encodings +¥−¥ -0 +Denorm +Normalized−Denorm−Normalized +0NaN NaN 16 9/28/21 9 17 Queen’s University CISC 221: Computer Architecture Toy Example 17 18 Queen’s University CISC 221: Computer Architecture Tiny Floating Point Example ¢ 8-bit Floating Point Representation § the sign bit is in the most significant bit § the next four bits are the exponent, with a bias of 7 § the last three bits are the frac ¢ Same general form as IEEE Format § normalized, denormalized § representation of 0, NaN, infinity s exp frac 1 4-bits 3-bits 18 9/28/21 10 19 Queen’s University CISC 221: Computer Architecture s exp frac E Value 0 0000 000 -6 0 0 0000 001 -6 1/8*1/64 = 1/512 0 0000 010 -6 2/8*1/64 = 2/512 … 0 0000 110 -6 6/8*1/64 = 6/512 0 0000 111 -6 7/8*1/64 = 7/512 0 0001 000 -6 8/8*1/64 = 8/512 0 0001 001 -6 9/8*1/64 = 9/512 … 0 0110 110 -1 14/8*1/2 = 14/16 0 0110 111 -1 15/8*1/2 = 15/16 0 0111 000 0 8/8*1 = 1 0 0111 001 0 9/8*1 = 9/8 0 0111 010 0 10/8*1 = 10/8 … 0 1110 110 7 14/8*128 = 224 0 1110 111 7 15/8*128 = 240 0 1111 000 n/a inf Dynamic Range (non-negative) closest to zero largest denorm smallest norm closest to 1 below closest to 1 above largest norm Denormalized numbers Normalized numbers v = (–1)s M 2E n: E = Exp – Bias d: E = 1 – Bias 19 20 Queen’s University CISC 221: Computer Architecture -15 -10 -5 0 5 10 15 Denormalized Normalized Infinity Distribution of Values ¢ 6-bit IEEE-like format § e = 3 exponent bits § f = 2 fraction bits § Bias is 23-1-1 = 3 ¢ Notice how the distribution gets denser toward zero. 8 values s exp frac 1 3-bits 2-bits 20 9/28/21 11 21 Queen’s University CISC 221: Computer Architecture Distribution of Values (close-up view) ¢ 6-bit IEEE-like format § e = 3 exponent bits § f = 2 fraction bits § Bias is 3 s exp frac 1 3-bits 2-bits -1 -0.5 0 0.5 1 Denormalized Normalized Infinity 21 22 Queen’s University CISC 221: Computer Architecture Properties 22 9/28/21 12 23 Queen’s University CISC 221: Computer Architecture Interesting Numbers Description exp frac Numeric Value ¢ Zero 00…00 00…00 0.0 ¢ Smallest Pos. Denorm. 00…00 00…01 2– {23,52} x 2– {126,1022} § Single ≈ 1.4 x 10–45 § Double ≈ 4.9 x 10–324 ¢ Largest Denormalized 00…00 11…11 (1.0 – ε) x 2– {126,1022} § Single ≈ 1.18 x 10–38 § Double ≈ 2.2 x 10–308 ¢ Smallest Pos. Normalized 00…01 00…00 1.0 x 2– {126,1022} § Just larger than largest denormalized ¢ One 01…11 00…00 1.0 ¢ Largest Normalized 11…10 11…11 (2.0 – ε) x 2{127,1023} § Single ≈ 3.4 x 1038 § Double ≈ 1.8 x 10308 {single,double} 23 24 Queen’s University CISC 221: Computer Architecture Special Properties of the IEEE Encoding ¢ FP Zero Same as Integer Zero § All bits = 0 ¢ Can (Almost) Use Unsigned Integer Comparison § Must first compare sign bits § Must consider −0 = 0 § NaNs problematic § Will be greater than any other values § What should comparison yield? § Otherwise OK § Denorm vs. normalized § Normalized vs. infinity 24 9/28/21 13 25 Queen’s University CISC 221: Computer Architecture Floating Point Operations 25 26 Queen’s University CISC 221: Computer Architecture Floating Point Operations: Basic Idea ¢ x +f y = Round(x + y) ¢ x ´f y = Round(x ´ y) ¢ Basic idea § First compute exact result § Make it fit into desired precision § Possibly overflow if exponent too large § Possibly round to fit into frac 26 9/28/21 14 27 Queen’s University CISC 221: Computer Architecture Rounding ¢ Rounding Modes (illustrate with $ rounding) ¢ $1.40 $1.60 $1.50 $2.50 –$1.50 § Towards zero $1 $1 $1 $2 –$1 § Round down (−¥) $1 $1 $1 $2 –$2 § Round up (+¥) $2 $2 $2 $3 –$1 § Nearest Even (default) $1 $2 $2 $2 –$2 27 28 Queen’s University CISC 221: Computer Architecture Closer Look at Round-To-Even ¢ Default Rounding Mode § Hard to get any other kind without dropping into assembly § All others are statistically biased § Sum of set of positive numbers will consistently be over- or under- estimated ¢ Applying to Other Decimal Places / Bit Positions § When exactly halfway between two possible values § Round so that least significant digit is even § E.g., round to nearest hundredth 7.8949999 7.89 (Less than half way) 7.8950001 7.90 (Greater than half way) 7.8950000 7.90 (Half way—round up) 7.8850000 7.88 (Half way—round down) 28 9/28/21 15 29 Queen’s University CISC 221: Computer Architecture Rounding Binary Numbers ¢ Binary Fractional Numbers § “Even” when least significant bit is 0 § “Half way” when bits to right of rounding position = 100…2 ¢ Examples § Round to nearest 1/4 (2 bits right of binary point) Value Binary Rounded Action Rounded Value 2 3/32 10.000112 10.002 (<1/2—down) 2 2 3/16 10.001102 10.012 (>1/2—up) 2 1/4 2 7/8 10.111002 11.002 ( 1/2—up) 3 2 5/8 10.101002 10.102 ( 1/2—down) 2 1/2 29 30 Queen’s University CISC 221: Computer Architecture Floating Point Addition ¢ (–1)s1 M1 2E1 + (-1)s2 M2 2E2 §Assume E1 > E2 ¢ Exact Result: (–1)s M 2E §Sign s, significand M: § Result of signed align & add §Exponent E: E1 ¢ Fixing §If M ≥ 2, shift M right, increment E §if M < 1, shift M left k positions, decrement E by k §Overflow if E out of range §Round M to fit frac precision (–1)s1 M1 (–1)s2 M2 E1–E2 + (–1)s M Get binary points lined up 30 9/28/21 16 31 Queen’s University CISC 221: Computer Architecture FP Multiplication ¢ (–1)s1 M1 2E1 x (–1)s2 M2 2E2 ¢ Exact Result: (–1)s M 2E § Sign s: s1 ^ s2 § Significand M: M1 x M2 § Exponent E: E1 + E2 ¢ Fixing § If M ≥ 2, shift M right, increment E § If E out of range, overflow § Round M to fit frac precision ¢ Implementation § Biggest chore is multiplying significands 31 32 Queen’s University CISC 221: Computer Architecture Mathematical Properties of FP Add ¢ Compare to those of Abelian Group § Closed under addition? § But may generate infinity or NaN § Commutative? § Associative? § Overflow and inexactness of rounding § (3.14+1e10)-1e10 = 0, 3.14+(1e10-1e10) = 3.14 § 0 is additive identity? § Every element has additive inverse? § Yes, except for infinities & NaNs ¢ Monotonicity § a ≥ b⇒ a+c ≥ b+c? § Except for infinities & NaNs Yes Yes Yes No Almost Almost 32 9/28/21 17 33 Queen’s University CISC 221: Computer Architecture Mathematical Properties of FP Mult ¢ Compare to Commutative Ring § Closed under multiplication? § But may generate infinity or NaN § Multiplication Commutative? § Multiplication is Associative? § Possibility of overflow, inexactness of rounding § Ex: (1e20*1e20)*1e-20= inf, 1e20*(1e20*1e-20)= 1e20 § 1 is multiplicative identity? § Multiplication distributes over addition? § Possibility of overflow, inexactness of rounding § 1e20*(1e20-1e20)= 0.0, 1e20*1e20 – 1e20*1e20 = NaN ¢ Monotonicity § a ≥ b & c ≥ 0 ⇒ a * c ≥ b *c? § Except for infinities & NaNs Yes Yes No Yes No Almost 33 34 Queen’s University CISC 221: Computer Architecture Floating Point in C 34 9/28/21 18 35 Queen’s University CISC 221: Computer Architecture Floating Point in C ¢ C Guarantees Two Levels §float single precision §double double precision ¢ Conversions/Casting § Casting between int, float, and double changes bit representation § double/float → int § Truncates fractional part § Like rounding toward zero § Not defined when out of range or NaN: Generally sets to TMin § int → double § Exact conversion, as long as int has ≤ 53 bit word size § int → float § Will round according to rounding mode 35 36 Queen’s University CISC 221: Computer Architecture Floating Point Puzzles ¢ For each of the following C expressions, either: § Argue that it is true for all argument values § Explain why not true • x == (int)(float) x • x == (int)(double) x • f == (float)(double) f • d == (double)(float) d • f == -(-f); • 2/3 == 2/3.0 • d < 0.0 ⇒ ((d*2) < 0.0) • d > f ⇒ -f > -d • d * d >= 0.0 • (d+f)-d == f int x = …; float f = …; double d = …; Assume neither d nor f is NaN 36 9/28/21 19 37 Queen’s University CISC 221: Computer Architecture Summary Casting Signed ↔ Unsigned: Basic Rules ¢ Bit pattern is maintained ¢ But reinterpreted ¢ Can have unexpected effects: adding or subtracting 2w ¢ Expression containing signed and unsigned int § int is cast to unsigned 37 38 Queen’s University CISC 221: Computer Architecture Summary: Expanding, Truncating: Basic Rules ¢ Expanding (e.g., short int to int) § Unsigned: zeros added § Signed: sign extension § Both yield expected result ¢ Truncating (e.g., unsigned to unsigned short) § Unsigned/signed: bits are truncated § Result reinterpreted § Unsigned: mod operation § Signed: similar to mod § For small numbers yields expected behavior 38 9/28/21 20 39 Queen’s University CISC 221: Computer Architecture Summary: Integer Operations ¢ Addition: § Unsigned/signed: Normal addition followed by truncate, same operation on bit level § Unsigned: addition mod 2w § Mathematical addition + possible subtraction of 2w § Signed: modified addition mod 2w (result in proper range) § Mathematical addition + possible addition or subtraction of 2w ¢ Multiplication: § Unsigned/signed: Normal multiplication followed by truncate, same operation on bit level § Unsigned: multiplication mod 2w § Signed: modified multiplication mod 2w (result in proper range) 39 40 Queen’s University CISC 221: Computer Architecture Summary: Floating Point Numbers ¢ IEEE Floating Point represents numbers of form M x 2E ¢ Has clear mathematical properties ¢ One can reason about operations independent of implementation § As if computed with perfect precision and then rounded ¢ Not the same as real arithmetic § Violates associativity/distributivity § Makes life difficult for compilers & serious numerical applications programmers 40