L8_1 Floating-Point_Arithmetic
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 1 The material in this presentation cannot be copied in any form without written permission
Learning Objectives
• To understand the algorithm for arithmetic operations using IEEE 754 floating-point values.
EECS 370 – Introduction to Computer Organization
2
Floating Point Representation
10.625 10 1010.101 2 1.010101 2 3
This must be a 1! So don’t store it.
+/-
1 bit 8 bits 23 bits
10.62510 = 0 10000010 010101000000000000000002
Significand (1010101)
EECS 370 – Introduction to Computer Organization
3
Exponent (3)
Floating Point – Example
Problem: What is the value (in decimal) of the following IEEE 754 floating point encoded number?
1
10000101
01011001000000000000000
sign bit
1
– (negative)
exponent
10000101
133 – 127 = 6 (biased by 127)
significand
01011001000000000000000
add implicit 1
-1.01011001 x 26
shift radix point 6 places
-1010110.01
-1010110.01=-(26 +24 +22 +21 +2-2)=-(64+16+4+2+1⁄2)= -86.2510
EECS 370 – Introduction to Computer Organization
4
Floating Point Multiply – Example
10.625 10
10 10
Algorithm:
1. Convert to binary
2. Convert binary numbers to IEEE 754 floating-point 3. Multiply
1. Sign bit – xor
2. Add exponents – mind the bias! (127) 3. Multiply significands
EECS 370 – Introduction to Computer Organization
Floating Point Multiply – Example
10.625
10 10 = 10102
10 1010 1 101
1 0101 0 1 00 0000 0 0 1 01 0101 00
1 10 1010 0 1 EECS 370 – Introduction to Computer Organization
10
= 1010.1012
0 10000010 01010100000000000000000
xor+
0 10000010 01000000000000000000000
-127
0 10000101 10101001000000000000000
1101010.012
= 106.2510
6
Floating Point Addition
• More complicated than floating point multiplication!
• If exponents are unequal, must shift the significand of the smaller
number to the right to align the corresponding place values
• Once numbers are aligned, simple addition (could be subtraction, if one of the numbers is negative)
• Renormalize (shift to get back into proper “scientific notation”)
• Added complication: rounding to the correct number of bits to store
could denormalize the number, and require one more step
EECS 370 – Introduction to Computer Organization
7
Floating Point Addition
1.Shift smaller exponent right to match larger.
2.Add significands
3.Normalize and update exponent
4.Check for “out of range”
Normalize: shift significand (mantissa) for integer part to be 1 and remaining bits are fractions
Example:
1010.101 2
Normalized is
1.010101 2 3
EECS 370 – Introduction to Computer Organization
8
Floating Point Addition – Example
Problem: Add two numbers using IEEE floating point addition: 101.125 + 13.75 1.Convert to IEEE 754 format
2.Shift smaller exponent right to match larger.
3.Add significands
4.Normalize and update exponent 5.Check for “out of range”
EECS 370 – Introduction to Computer Organization
9
Floating Point Addition – Example
Problem: Add two numbers using IEEE floating point addition: 101.125 + 13.75 101.125
0
10000101
10010100100000000000000
0
10000010
10111000000000000000000
Sum Significands
1100101001 + 0 0 01 1 0 1 1 1 0
1 1 1 0 0 1 0 1 11
Sum didn’t overflow, so no re-normalization needed
13.75
Shift by 6 – 3 = 3 13.75
Shift mantissa by difference in exponent
0
10000101
00110111000000000000000
0
10000101
1100101110000000000000
EECS 370 – Introduction to Computer Organization
10
= 1.1100101112 x 26
= 114.87510
More Precision and Range
• We have described IEEE-754 binary32 floating point format, commonly known as “single precision” (“float” in C/C++)
• 24 bits precision; equivalent to about 7 decimal digits • 3.4 * 1038 maximum value
• Good enough for many but not all calculations
• IEEE-754 also defines a larger binary64 format, “double precision” (double data type in C/C++)
• 53 bits precision, equivalent to about 16 decimal digits
• 1.8 * 10308 maximum value
• Most accurate physical values currently known only to about 47 bits precision, about 14 decimal digits
EECS 370 – Introduction to Computer Organization
11
Floating Point Precision
EECS 370 – Introduction to Computer Organization
12
8
Logistics
• There are 3 videos for lecture 8
• L8_1 – IEEE_Floating-Point_Arithmetic
• L8_2 – Basic-Electronics_Logic-Gates • L8_3 – Combinational-Logic
• There is one worksheet for lecture 8
1. Logic gates – complete at the end of all 3 videos.
EECS 370 – Introduction to Computer Organization
13
L8_2 Basic-Electronics_Logic-Gates
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 14 The material in this presentation cannot be copied in any form without written permission
Office Hours
• Drop by office hours, ask questions, say ‘hi’
• Just in case you did not see them on the calendar:
Tuesdays 11am to 12 noon (EST) – individual meetings
Group office hours: Tuesdays 4pm to 4:30 pm
Thursdays 9:45 am to 10:15 am Thursdays 2:30 pm to 3:00 pm
EECS 370 – Introduction to Computer Organization
15
https://umich.zoom.us/j/92153246345
Learning Objectives
• To identify logic gates used in combinational logic circuits and describe their operations.
• Be able to create the functionality of any logic gate with the NOR gate, (and therefore, the nor instruction in LC-2K).
EECS 370 – Introduction to Computer Organization
16
Levels of Abstraction
• Quantum level, solid state physics
• Conductors, Insulators, Semiconductors
• Doping silicon to make diodes and transistors
• Simple gates, Boolean logic, and truth tables
• Combinational logic: muxes, decoders
• Clocks
• Sequential logic: latches, memory
• State machines
• Processor Control: Machine instructions
• Computer Architecture: Defining a set of instructions
EECS 370 – Introduction to Computer Organization
17
Start with the Materials: Conductors and Insulators
• Conductor: a material that permits electrical current to flow easily. (low resistance to current flow)
• Lattice of atoms with free electrons
• Insulator: a material that is a poor conductor of electrical current (High resistance to current flow)
• Lattice of atoms with strongly held electrons
• Semi-conductor: a material that can switch between an (okay) conductor and an
(okay) insulator
• Controlled via an external voltage
• Basis for “logical switches” that make up digital circuits
EECS 370 – Introduction to Computer Organization
18
Making a Transistor
• Our first level of abstraction is the transistor (basically 2 diodes sitting back-to-back)
• Electrical engineers use a symbol like this: EECS 370 – Introduction to Computer Organization
19
gate
Source: Intel
Recent Pictures and the Near Future
drain
source
90nm technology 2003
65nm technology 2005
45nm technology 2008
7nm technology 5nm technology 2018 2020
EECS 370 – Introduction to Computer Organization
20
30nm
20nm
32nm technology 2010
15nm
14nm technology 2014
Transistor Count
2020 – NVIDIA RTX 3090 28 Billion Transistors
EECS 370 – Introduction to Computer Organization
21
Present and Future Problems
• Area is the least of them
• Power density – Watts/mm2
• Leakage current • Reliability (faults)
interconnect via
• Process variation (not all transistors are equal) EECS 370 – Introduction to Computer Organization
22
transients
Testing burn-in
As for power: Cooking-aware Computing
Source: The New York Times, 25 June 2002
Liquid Nitrogen Cooling
EECS 370 – Introduction to Computer Organization
23
Basic Gate: Inverter
CS abstraction – logic function
Truth Table
Schematic symbol (CS/EE)
IO
I
O
0
1
1
0
EECS 370 – Introduction to Computer Organization
24
Basic Gate: NAND
Truth Table
A
B
Y
0
0
1
0
1
1
1
0
1
1
1
0
A B
Y
EECS 370 – Introduction to Computer Organization
25
A B
Y
A B
Y
A B
Y
Basic Gates: AND, OR, XOR
AND
OR
XOR
Truth Table
Truth Table
Truth Table
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
0
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
EECS 370 – Introduction to Computer Organization
26
Basic Gates: NOR
A B
Y
NOR
Truth Table
A
B
A||B
Y
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
EECS 370 – Introduction to Computer Organization
27
Logic Gate Exercise
• NOR is logically complete
• This means that all gates can be implemented using only NORs
• All gates can be implemented in LC-2K • NAND is also logically complete
• Exercise:
• Implement INV using only NOR gates • Implement AND using only NOR gates • Implement OR using only NOR gates
• Hint Demorgan’s Law:
• A || B = !(!A && !B)
• !(A || B) = !A && !B
EECS 370 – Introduction to Computer Organization
28
Logic Gate Exercise – INV (!) using NOR
NOR
IO AY
Truth Table
!(A || B) = A NOR B A substitute A for B B !(A || A) = A NOR A
!(A) = A NOR A
Y
!A
= A NOR A
Truth Table
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
0
I
O
0
1
1
0
EECS 370 – Introduction to Computer Organization
29
Logic Gate Exercise – AND using NOR
!(A || B) = !A && !B = A NOR B
!A NOR !B = A && B
substitute A NOR A for !A substitute B NOR B for !B
A && B = (A NOR A) NOR (B NOR B)
A
B
Y
A
B
A && B
Y
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
EECS 370 – Introduction to Computer Organization
30
Logic Gate Exercise – OR using NOR
NOR
AYA BB
Truth Table
OR
Y
A
B
A||B
Y
!Y
0
0
0
1
0
0
1
1
0
1
1
0
1
0
1
1
1
1
0
1
EECS 370 – Introduction to Computer Organization
31
Logistics
• There are 3 videos for lecture 8
• L8_1 – IEEE_Floating-Point_Arithmetic
• L8_2 – Basic-Electronics_Logic-Gates • L8_3 – Combinational-Logic
• There is one worksheet for lecture 8
1. Logic gates – complete at the end of all 3 videos.
EECS 370 – Introduction to Computer Organization
32
L8_3 Combinational-Logic
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 33 The material in this presentation cannot be copied in any form without written permission
Learning Objectives
• To create circuits using combinations of basic gates.
EECS 370 – Introduction to Computer Organization
34
Building Complexity: Addition (1)
GOAL: We want to design a circuit that performs binary addition
0110
10 111 + 00 110
11 101
A
B
C
S
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
Let us start by adding two bits • Design a circuit that takes two
1. 2.
(S and C)
Make a truth table
Design a circuit
A
B
S
C
bits as input (A and B)
• Generates a sum and carry bit
EECS 370 – Introduction to Computer Organization
35
Half-Adder
0110
10 011 + 00 110
11 001
Building Complexity: Addition (1)
• Now we can add two bits, but how do we deal with carry bits? • We must design a circuit that can add three bits
Cin
A
B
Cout
S
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
• Inputs: A, B, Cin
• Outputs:S,Cout 1. Design a truth table 2. Circuit
How do we combine these?
Full-Adder
A B Cin
Cout S
•
EECS 370 – Introduction to Computer Organization
36
8-bit Ripple Carry Adder
A7 B7 A6 B6 A5 B5 A4 B4 A3 B3 A2 B2 A1 B1 A0 B0
C
Carry
S7 S6 S5 S4 S3 S2 S1 S0
Unfortunately, this has a very large propagation time for 32 or 64 bit adds
EECS 370 – Introduction to Computer Organization
37
Full adder
Full adder
Full adder
Full adder
Full adder
Full adder
Full adder
Full adder
Symbol
C
Building Complexity: Selecting
• We want to design a circuit that can select between two inputs – Let us start with a one-bit version
1. Draw a truth table
Circuit
A S
B
Multiplexer (Mux)
A
BS
C
000 001 010 011 100 101 110 111
0 0 0 1 1 0 1 1
Is A if S is 0 Is 0 if S is 1
C
Is 0 if S is 0 Is B if S is 1
Is A if S is 0 Is B if S is 1
EECS 370 – Introduction to Computer Organization
38
Multiplexer – Example
EECS 370 – Introduction to Computer Organization
39
Symbol
Problem: Build a 4×1 mux using only 2×1 muxes
C
Multiplexer – Example
Problem: Build a 4×1 mux using only 2×1 muxes
A B
C D
S0
Out
S1
S0
Out
0
0
A
0
1
B
1
0
C
1
1
D
EECS 370 – Introduction to Computer Organization
40
S1
Symbol
Out
Building Complexity: Decoding
• Another common device is a decoder
• Input: N-bit binary number
• Output: 2N bits, exactly one of which will be high
Decoder
A0 A1
Out0 Out1
Out2 Out3
EECS 370 – Introduction to Computer Organization
41
Combinational Circuits Implement Boolean Expressions
• Output is determined exclusively by the input
• No memory: Output is valid only as long as input is • Adder is the basic gate of the ALU (Future lecture)
• Decoder is the basic gate of indexing
• MUX is the basic gate controlling data movement
Decoder Mux A A0 Out
Half-Adder
SA1 0 A
B Out1 S C
B Out3
C
Out2
EECS 370 – Introduction to Computer Organization
42
Logistics
• There are 3 videos for lecture 8
• L8_1 – IEEE_Floating-Point_Arithmetic
• L8_2 – Basic-Electronics_Logic-Gates • L8_3 – Combinational-Logic
• There is one worksheet for lecture 8
1. Logic gates – complete at the end of all 3 videos.
EECS 370 – Introduction to Computer Organization
43