程序代写代做代考 case study compiler C assembly Computer Systems Organization

Computer Systems Organization
Session 5 􏰃 Main Theme Bits, Bytes, and Floats Dr. Jean-Claude Franchitti
New York University
Computer Science Department Courant Institute of Mathematical Sciences
Presentation material partially based on textbook slides C􏰄􏰙􏰅􏰆􏰇e􏰈 S􏰉􏰊􏰇e􏰙􏰊: A P􏰈􏰄g􏰈a􏰙􏰙e􏰈􏰋􏰊 Pe􏰈􏰊􏰅ec􏰇􏰜􏰌e
by Randal Bryant and David O􏰋Ha􏰝􏰝a􏰈􏰄􏰎 as well as 􏰜􏰎f􏰄􏰈􏰙a􏰇􏰜􏰄􏰎 f􏰈􏰄􏰙 M􏰜c􏱉ae􏰝 O􏰌e􏰈􏰇􏰄􏰎􏰋􏰊 b􏰄􏰄􏱊: N􏰆􏰙e􏰈􏰜ca􏰝 Computing with IEEE Floating Point Arithmetic Slides copyright © 2020
1

Agenda
1
2
3
Instructor and Course Introduction Bits, Bytes, and Floats
Summary and Conclusion
2

What is the class about?
􏰍Course description and syllabus:
» http://www.nyu.edu/classes/jcf/CSCI-GA.3033-012/
» http://www.cs.nyu.edu/courses/fall20/CSCI-UA.0205–001/ » Accessible via NYU Classes
􏰍 Textbooks:
» Comp􏰆􏰇er S􏰉s􏰇ems: A Programmer􏰋s Perspec􏰇i􏰌e
Randal Bryant and David O’Hallaron Pearson
ISBN-10: 013409266X, ISBN-13: 978-0134092669, 3rd Edition (03/2015) » Recommended:
» The C Programmning Language, Brian W Kernighan and Dennis Ritchie
Prentice Hall; ISBN-10: 0131103628; ISBN-13: 978-01311103627, 2nd Edition (04/88)
3

Icons / Metaphors
Information
Common Realization Knowledge/Competency Pattern Governance
Alignment
Solution Approach
4
4

Bits, Bytes, and Floats: Detailed Agenda
􏰍 Background: Fractional binary numbers 􏰍 IEEE floating point standard: Definition 􏰍 Example and properties
􏰍 Rounding, addition, multiplication
􏰍 Floating point in C 􏰍 Summary
5

Agenda
1
2
3
Instructor and Course Introduction Bits, Bytes, and Floats
Summary and Conclusion
6

Bits, Bytes, and Floats
􏰍 Background: Fractional binary numbers 􏰍 IEEE floating point standard: Definition 􏰍 Example and properties
􏰍 Rounding, addition, multiplication
􏰍 Floating point in C 􏰍 Summary
7

Fractional binary numbers
􏰍 What is 1011.1012?
Turing Award 1989 to William Kahan for design of the IEEE Floating Point Standards 754 (binary) and 854 (decimal)
8

Fractional Binary Numbers
2i
2i-1
•• •
4
2
1
bi
bi-1
•••
b2
b1
b0
b-1
b-2
b-3
•••
b-j
1/2
1/4
1/8
􏰍Representation
» Bits to right of “binary point” represent fractional
powers of 2
» Represents rational number:
2-j
9
•• •

Fractional Binary Numbers: Examples
􏰢 Value 5 3/4
2 7/8 1 7/16
Representation
101.112 010.1112 001.01112
􏰢 Observations
􏰍 Divide by 2 by shifting right (unsigned)
􏰍 Multiply by 2 by shifting left
􏰍 Numbers of form 􏰶.􏰷􏰷􏰷􏰷􏰷􏰷…2 are just below 1.0
􏰍􏰷/􏰱􏰼􏰷/􏰽􏰼􏰷/􏰾􏰼…􏰼􏰷/􏰱i 􏰼…➙1.0 􏰍 Use notation 1.0 􏱋 ε
10

Representable Numbers
􏰍 Limitation #1
» Can only exactly represent numbers of the form x/2k • Other rational numbers have repeating bit representations
» Value • 1/3
• 1/5 • 1/10
Representation
0.0101010101[01]􏰘2 0.001100110011[0011]􏰘2 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?)
11

Why Not Fractional Binary Number?
􏰍 Not efficient
􏱌3 * 2100􏰗1010000000 ….. 0
􏱌Given a finite length (e.g. 32-bits), cannot represent very large nor very small numbers (ε􏰗0)
12

Bits, Bytes, and Floats
􏰍 Background: Fractional binary numbers 􏰍 IEEE floating point standard: Definition 􏰍 Example and properties
􏰍 Rounding, addition, multiplication
􏰍 Floating point in C 􏰍 Summary
13

IEEE Floating Point
􏰍 IEEE Standard 754
» Established in 1985 as uniform standard for floating point
arithmetic
• Before that, many idiosyncratic formats
» The IEEE standards committee consisted mostly of hardware people, plus a few academics led by W. Kahan at Berkeley.
» Supported by all major CPUs
􏰍 Driven by numerical concerns
» Nice standards for rounding, overflow, underflow
» Consistent representation of floating point numbers by all machines .
» Consistent treatment of exceptional situations such as division by zero.
» Hard to make fast in hardware
• Numerical analysts predominated over hardware designers in defining standard
14

Floating Point Representation
􏰍 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)
s
exp
frac
15

Precision Options
􏰍 Single precision: 32 bits
1 8-bits 23-bits
􏰍 Double precision: 64 bits
1 11-bits 52-bits
􏰍 Extended precision: 80 bits (Intel only) 1 15-bits 63 or 64-bits
s
exp
frac
s
exp
frac
s
exp
frac
16

Three Encoding Schemes Based on Exp
􏰍 exp ≠ 0..0 or 11…1 􏰗 normalized encoding
􏰍 exp = 0… 000 􏰗 denormalized encoding
􏰍 exp = 1111…1 􏰗 special value encoding » frac = 000…0
» frac = something else
17

􏰑N􏰄􏰈􏰙a􏰝􏰜􏰸ed􏰤 Va􏰝􏰆e􏰊
􏰍 When: exp ≠ 000…0 and exp ≠ 111…1
􏰍 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 = 􏰷.xxx…x2 » xxx…x:bitsoffracfield
» Minimum when frac􏱍􏰶􏰶􏰶…􏰶 (M = 1.0)
» Maximum when frac􏱍􏰷􏰷􏰷…􏰷 (M = 2.0 􏱋 ε􏰖
» Get extra leading bit for “free”
v = (–1)s M 2E
Range(E)=[-126,127] Range(E)=[-1022,1023]
18

Normalized Encoding Example
􏰍 Value: float F = 15213.0;
» 1521310
􏰍 Significand M =
frac =
􏰍 Exponent E =
Bias = Exp =
􏰍 Result:
s exp
= 111011011011012
= 1.11011011011012 x 213
1.11011011011012 110110110110100000000002
muumuu
25L I 2 E O
v = (–1)s M 2E E = Exp–Bias
Z th I
13
127
140 = 100011002
ion air
11011011011010000000000
frac
0
10001100
19

De􏰎􏰄􏰈􏰙a􏰝􏰜􏰸ed Va􏰝􏰆e􏰊 (􏰑S􏰆b􏰎􏰄􏰈􏰙a􏰝 E􏰎c􏰄d􏰜􏰎􏰛􏰤 a􏰊 􏰅e􏰈 854 S􏰇a􏰎da􏰈d)
􏰍 Condition: exp 􏱍 􏰶􏰶􏰶…􏰶
􏰍 Exponent value: E = 1 – Bias (instead of E = 0 – Bias)
􏰍 Significand coded with implied leading 0: M = 0.xxx…x2, instead of M = 1.xxx…x2
• xxx…x: bits of frac
􏰍 Cases
» exp=000􏰘0,frac=000􏰘0
• Representszerovalue
• 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
20

Special Values Encoding
􏰍 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
21

Visualization: Floating Point Encodings
−􏱎 NaN
−Normalized
+Denorm +Normalized 􏰚0 +0
+􏱎
NaN
−Denorm
22

Bits, Bytes, and Floats
􏰍Background: Fractional binary numbers 􏰍IEEE floating point standard: Definition 􏰍Example and properties
􏰍Rounding, addition, multiplication 􏰍Floating point in C
􏰍Summary
23

Tiny Floating Point Example
s
exp
frac
1 4-bits 3-bits
􏰍 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
24

Dynamic Range (Positive Only)
0 0000 000
0 0000 001
Denormalized 0 0000 010
-6 0
-6 1/8*1/64
-6 2/8*1/64
-6 6/8*1/64
-6 7/8*1/64
-6 8/8*1/64
-6 9/8*1/64
-1 14/8*1/2 -1 15/8*1/2 0 8/8*1
0 9/8*1
0 10/8*1
7 14/8*128
7 15/8*128
n/a inf
= 1/512
= 2/512
= 6/512
= 7/512
= 8/512
= 9/512
= 14/16 = 15/16 =1
= 9/8
= 10/8
= 224 = 240
closest to zero
largest denorm smallest norm
closest to 1 below closest to 1 above
largest norm
numbers
􏰘
0 0000 110 0 0000 111 0 0001 000 0 0001 001 􏰘
0 0110 110 0 0110 111 0 0111 000
sexpfracE Value
Normalized
numbers 0 0111 001
0 0111 010
􏰘
0 1110 110
0 1110 111
0 1111 000
v = (–1)s M 2E n: E = Exp – Bias d: E = 1 – Bias
25

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
s
exp
frac
toward zero.
8 values
1 3-bits 2-bits
-15 -10 -5 0 5 10 15
Denormalized Normalized Infinity
26

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
27

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
28

Bits, Bytes, and Floats
􏰍 Background: Fractional binary numbers 􏰍 IEEE floating point standard: Definition 􏰍 Example and properties
􏰍 Rounding, addition, multiplication
􏰍 Floating point in C 􏰍 Summary
29

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
30

Rounding
􏰍 Rounding Modes (illustrate with $ rounding)
$1.40 $1.60 $1.50 $2.50 –$1.50
» Towards zero $1 » Round down (−􏱎) $1 » Round up (+􏱎) $2 » Nearest Even (default) $1
$1 $1 $1 $1 $2 $2 $2 $2
$2 –$1 $2 –$2 $3 –$1 $2 –$2
31

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.8950001 7.8950000 7.8850000
7.89 (Less than half way) 7.90 (Greater than half way) 7.90 (Half way—round up) 7.88 (Half way—round down)
32

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 2 3/32 2 3/16 2 7/8 2 5/8
Binary 10.000112 10.001102 10.111002 10.101002
Rounded Action
10.002 (<1/2—down) 10.012 (>1/2—up) 11.002 ( 1/2—up) 10.102 ( 1/2—down)
Rounded Value 2
2 1/4
3
2 1/2
33

FP Multiplication
􏰍 (–1)s1 M1 2E1 x (–1)s2 M2 2E2 􏰍 Exact Result: (–1)s M 2E
» Sign s:
» Significand M: » Exponent E:
s1 ^ s2 M1 x M2 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
34

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
Get binary points lined up
(–1)s1 M1 +
E1–E2 (–1)s2 M2
􏰍 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)s M 35 Mathematical Properties of FP Add 􏰍 Compare to those of Abelian Group » Closed under addition? Yes • But may generate infinity or NaN » Commutative? Yes » Associative? No • Overflow and inexactness of rounding • (3.14+1e10)-1e10 = 0, 3.14+(1e10-1e10) = 3.14 » 0 is additive identity? Yes » Every element has additive inverse? • Yes, except for infinities & NaNs 􏰍 Monotonicity » a ≥ b ⇒ a+c ≥ b+c? • Except for infinities & NaNs Almost Almost 36 Mathematical Properties of FP Mult 􏰍 Compare to Commutative Ring » Closed under multiplication? • But may generate infinity or NaN » Multiplication Commutative? Yes Yes » Multiplication is Associative? No • Possibility of overflow, inexactness of rounding • Ex:(1e20*1e20)*1e-20=inf,1e20*(1e20*1e-20)=1e20 » 1 is multiplicative identity? Yes » Multiplication distributes over addition? No • 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 Almost 37 Bits, Bytes, and Floats 􏰍 Background: Fractional binary numbers 􏰍 IEEE floating point standard: Definition 􏰍 Example and properties 􏰍 Rounding, addition, multiplication 􏰍 Floating point in C 􏰍 Summary 38 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 39 Floating Point Puzzles 􏰍 For each of the following C expressions, either: » Argue that it is true for all argument values » Explain why not true ROUNDINDS NOTSAME NOM • x == (int)(float) x • x == (int)(double) x • f == (float)(double) f Yes • d == (double)(float) d NO • f == -(-f); • 2/3 == 2/3.0 NO int 􏰒 = 􏰘; float f = 􏰘; do􏰆ble d = 􏰘; Assume neither dnorfis NaN • d<0.0 •d>f
• d*d>=0.0 • (d+f)-d == f
Yes
Yes
⇒ ((d*2)<0.0) ⇒ -f>-d
40

Creating Floating Point Number
􏰍 Steps
» Normalize to have leading 1
» Round to fit within fraction
» Postnormalize to deal with effects of rounding
3-bits
s
exp
frac
􏰍 Case Study
» Convert 8-bit unsigned numbers to tiny floating point format
Example Numbers
128 10000000 15 00001101 33 00010001 35 00010011
138 10001010 63 00111111
1 4-bits
41

Normalize
s
exp
frac
􏰍 Requirement 1 4-bits 3-bits
» Set binary point so that numbers of form 1.xxxxx
» Adjust all to have leading one • Decrement exponent as shift left
Value Binary
128 10000000 15 00001101 17 00010001 19 00010011
138 10001010 63 00111111
Fraction Exponent
1.0000000 7
1.1010000 3
2 2
1.0001000
1.0011000
1.0001010 7
1.1111100
4 24 4 24
27 5 25
42

Rounding
1.BBGRXXX
Sticky bit: OR of remaining bits
􏰍 Round up conditions
» Round = 1, Sticky = 1 ➙ > 0.5
» Guard = 1, Round = 1, Sticky = 0 ➙ Round to even
Last Bit
nun
Guard bit: LSB of result Round bit: 1st bit removed
Value Fraction
128 1.0000000 II
15 1.1010000 I
17 1.0001000 A
19 1.0011000
138 1.0001010
63 1.1111100 II
GRS Incr?
000 N 100 N 010 N 110 Y 011 Y 111 Y
Rounded
1.000
1.101
1.000
1.010
1.001
10.000
43

Postnormalize
􏰍 Issue
» Rounding may have caused overflow
» Handle by shifting right once & incrementing exponent
Value Rounded Exp Adjusted Result
128 1.000 7 15 1.101 3 17 1.000 4 19 1.010 4
138 1.001 7 63 10.000 5
128 15 16 20 134 1.000/6 64
44

Interesting Numbers
Description
{single,double} Numeric Value
0.0
2– {23,52} x 2– {126,1022}
(1.0 – ε) x 2– {126,1022}
1.0 x 2– {126,1022}
1.0
(2.0 – ε) x 2{127,1023}
􏰍 􏰍
􏰍
􏰍
􏰍 􏰍
Zero
Smallest Pos. Denorm. » Single ≈ 1.4 x 10–45
» Double ≈ 4.9 x 10–324
Largest Denormalized » Single ≈ 1.18 x 10–38 » Double ≈ 2.2 x 10–308
exp frac
00…00 00…00 00…00 00…01
00…00 11…11
Smallest Pos. Normalized
» Just larger than largest denormalized
One 01…11 00…00
Largest Normalized 11…10 11…11 » Single ≈ 3.4 x 1038
» Double ≈ 1.8 x 10308
00…01 00…00
45

Bits, Bytes, and Floats: Summary
􏰍 As for integers, floats are stored in memory as 1s and 0s
􏰍 The binary presentation by itself does not carry a
meaning, it depends on the interpretation.
􏰍 IEEE Floating Point has clear mathematical properties
􏰍 Represents numbers of form (–1)s x M x 2E
􏰍 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
46

Agenda
1
2
3
Instructor and Course Introduction Bits, Bytes, and Floats
Summary and Conclusion
47

Assignments & Readings
􏰍 Readings
» Slides and Handouts posted on the course web site
» Syllabus, make sure you understand the rules associated with grading, due dates, lateness, etc.
» Textbook: Chapter 2.4 􏰍 Assignment #1 / Lab #1
» Lab #1 TBD in later sessions
􏰍 Development environment
» C development environment setup
» Create GitHub account
» See Announcements regarding invitation to join the course GitHub and related instructions to access the materials for the course and recitations (including private versions of them that you will work on during recitations)
48

Next Session: C Programming
49

Questions, Comments, Discussions ?
50