Transcript Slide 1

CS37: Computer Architecture
Spring Term, 2005
Instructor: Kate Forbes-Riley
[email protected]
1
CS37: Lecture 7
• Floating point representation
• Floating point addition and multiplication
• Introduction to Machine Language and
Assembly Language
2
Review: GTE (≥)
1) GTE = ¬MSB (i.e, A – B ≥ 0)
2) GTE = (MSB ● Overflow) + (¬MSB ● ¬Overflow)
But this is just: ¬( MSB XOR
Overflow)
(GTE = 1 only if neither or both =1)
MSB result
xor
GTEout
¬
Overflow
3
Review: 32-bit
ALU w/ GTE
If GTEout = 1, A ≥
B, else GTEout = 0
GTEout is sent to
GTEin of LSB;
other GTEins = 0
if OP Code = 4,
GTEins = Result
if A ≥ B, GTE
Result = 00..01;
else GTE Result
= 00..00
Binvert
Op Code
A0
B0
Binvert Cin Op
ALU 0
GTEin
Cout
result
0
A1
B1
0
Binvert Cin Op
ALU 1
GTEin
Cout
result
1
A30
B30
0
Binvert Cin Op
ALU 30
GTEin Cout
result
30
A31
B31
0
…
result
Binvert Cin Op
31
ALU 31
GTEin Cout GTEout
4
Review: Binary Integer Multiplication
100
x
101
100
000
+ 100
10100
multiplicand (m)
multiplier (n)
multiply and shift
intermediate
products (Pb)
product: (p) m+n bits
5
Review: Binary Multiplication (1st version PH3)
000000
000100
101
000100
001000
010
010
010000
001
001
010100
100000
000
product = m + n bits
m’cand in right m bits
test m’plier: LSB = 1
product = product + m’cand
SLL 1 m’cand
SLR 1 m’plier
test m’plier: LSB = 0
SLL 1 m’cand
SLR 1 m’plier
test m’plier: LSB = 1
product = product + m’cand
SLL 1 m’cand
SLR 1 m’plier
6
Floating Point
• Real Numbers: include fractions of whole #s
 123,456.789
105 … 100.10-1 … 10-3
• Scientific notation: a single digit to the left of
the decimal point
 0.123456789 x 106
 0.0123456789 x 107
 0.00123456789 x 108
• Normalized Scientific notation: scientific
notation with no leading zeros
 1.23456789 x 105
7
Floating Point with Binary Numbers
• Real Numbers: include fractions of whole #s
 110111.101101
25 … 20.2-1 … 2-6
• Scientific notation: a single digit to the left of
the binary point (with exponent in base 10)
 0.110111101101 x 26
 0.0110111101101 x 27
• Normalized Scientific notation: scientific
notation with no leading zeros
 1.10111101101 x 25
8
Floating Point with Binary Numbers
• Normalized Scientific notation: always using the
same form simplifies arithmetic and increases
accuracy of stored reals b/c no leading zeros:
leading digit is always 1
1.10111101101 x 25
Significand
Base
Exponent
Common to write significand in binary and base
and exponent in decimal
9
IEEE 754 floating-point standard
• Single precision = 32-bit representation (same
procedure for double = 64 bit: 11 exp; 52 sig)
31
31
sign
0
30 exponent
23
22
significand
0
• 1 sign bit: 1 = negative; 0 = positive
• 8 bits for exponent: determines range of #s that
can be represented
• 23 bits for significand: determines accuracy of
#s that are represented
10
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
• 23 bits for significand represents the fraction.
The leading 1 is implicit!
• Because fraction is already in binary form, we
can just put its (first/add) 23 bits into bits 0-22
• Similarly, we just put the sign in the sign bit
• E.g., 1.10111101101 x 25
31
0
22
significand
0
10111101101000000000000
11
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
• +/- Exponents aren’t represented with two’s
complement!
• Exponent represented with “biased notation”.
This allows efficient sorting with integer HW:
00000001
…
negative exponents <
11111111
positive exponents
12
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
• To compute biased exponent, add bias to
exponent (both decimal) then convert to binary
• Bias for single precision = 127
Exp
Biased Exp
Binary
8-bits
-126
-31
5
126
-126+127 = 1
-31+127 = 96
5+127 = 132
126+127 = 253
20
26+25
27+22
27+26+25+24+23+22+21
00000001
01100000
10000100
11111110
13
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
• So biased exponent represents sign and
magnitude of exponent in 8 bits.
• Note range and reserved biased exponents (see
PH3 pg 194):
Exponent
Biased exp
Significand
Value
-126 to 127
1 to 254
any
+/- reals
128
255
0
infinity (+/- )
128
255
nonzero
NAN
14
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
• To compute the value of this FP representation:
Value = (-1)sign x (1+significand) x 2biased exp – bias
1
10000010
sign
biased exp
10000000000000000000000
(significand fraction)
• Binary Val = -1.10000000000000000000000 x 23
(-1)1 x (1+.10000000000000000000000) x 2130 – 127
• Decimal Val = -12.0
-1 x (1 + 2-1) x 23 = -1 x (1.5) x 8 = -12.0
15
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
• To convert decimal to IEEE binary floating point
• If you’re lucky, it’s easy to manipulate:
0.75 = 3/4 = 3 x 2-2
= 0011. x 2-2 = (1.1 x 21) x 2-2 = 1.1 x 2-1
= (-1)0 x (1 + .10000…000) x 2((-1+127) – 127)
= (-1)0 x (1 + .10000…000) x 2(126 – 127)
31
0
30 exponent
01111110
23
22
significand
0
10000000000000000000000
16
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
• If you’re unlucky, use brute force:
- 3.1415
1. convert integer
(not sign): 11
2. convert fraction:
Does 2-1 fit? Does 2-2
fit? Does 2-3 fit? Does
2-4 fit? …
• Here stop at 2-22 due to integer normalization
17
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
2. Converting fraction part:11.00100100001…
.1415
- .1250 (1/8 = 2-3)
.0165
- .015625 (1/64 = 2-6)
.000875
- .000488 (1/2048 = 2-11)
…
Infinite # reals between 0…1; so some inaccuracy18
IEEE 754 floating point: single precision
31
sign
30 exponent
(biased)
23
22
significand
(fraction)
0
3. Normalize with sign:
-11.00100100001…
-1.100100100001… x 21
4. Convert to IEEE 754 via equation:
= (-1)1 x (1 + .100100001…) x 2((1+127) – 127)
= (-1)1 x (1 + .100100001…) x 2(128 – 127)
1
sign
10000000
(biased exp)
100100100001…
(significand fraction)
19
Convert -128.673828125 to IEEE FP standard
1. Convert integer part (w/o sign):
128 = 10000000
2. Convert fraction part:
2-1
.5
2-2
.25
1 0
2-3
2-4
.125 .0625
1
0
2-5
.03125
2-6
.015625
1
1
2-7
2-8
.0078125 .00390625
0
0
2-9
.001953125
1
= 1010110010000000
3. Normalize with sign:
-10000000.1010110010000000 =
-1.00000001010110010000000 x 27
20
Convert -128.673828125 to IEEE FP standard
-1.00000001010110010000000 x 27
4. Convert to IEEE 754 equation:
(-1)1 x (1 + .00000001010110010000000) x 2((7+127) – 127)
(-1)1 x (1 + .00000001010110010000000) x 2(134 – 127)
5. Convert to IEEE 754 FP representation:
1
sign
10000110
(biased exp)
00000001010110010000000
(significand fraction)
21
IEEE 754 Floating Point: Addition Algorithm
• Add 1.100 x 22 and 1.100 x 21
Step 1: Shift right (SRL) the significand of the
smaller # to match exponent of larger #
1.100 x 21  0.110 x 22 lost accuracy: keep #bits
Step 2: Add the significands
1.100 x 22
+ 0.110 x 22
10.010 x 22
22
IEEE 754 floating point: Addition Algorithm
Step 3: Normalize sum, checking for overflow
(+ exponent too large for (8) bits) and
underflow (- exponent too small for (8) bits)
10.010 x 22  1.0010 x 23
0 < 3 + 127 < 255 ok: no under/overflow
Step 4: Round the sum (variously, see pg 213),
then normalize again if necessary
1.0010 x 23  1.001 x 23 lost accuracy: keep #bits
23
IEEE 754 floating point: Multiplication Algorithm
• Multiply 1.100 x 22 by 1.100 x 21
Step 1:
Add biased
exponents then
subtract bias
(2+127) + (1+127)
= 257 - 127 = 130
Step 2:
Multiply significands
1.100
x 1.100
0000
0000
1100
1100
10.010000
place binary point 3 + 3 digits from right
24
IEEE 754 floating point: Multiplication Algorithm
Step 3: Normalize product, check over/underflow
10.010000 x 2130  1.0010000 x 2131
0 < 131 < 255 ok: no under/overflow
Step 4: Round (variously, see pg 213), then
normalize again if necessary
1.0010000 x 2131  1.001 x 2131 lost accuracy
Step 5: Set sign of product (+ if operands’ signs
are same; else -)
25
1.001 x 2131
Implementation of Floating Point Operations
• Block diagram of FP addition HW on pg 201
• Similar design to integer operations
• But need more HW (PH3 Figure 3.17, 3.18)
 2 ALUs: one for exponent, one for
significand
 Logic for Shifts
 Logic for Rounding
26
Machine Languages: Instruction Sets
• An “instruction” is a specific sequence of binary
numbers that tells the control to perform a single
operation in a single step via the datapath
• An “instruction set” is the set of all instructions
that a computer understands
• “Machine Language” is the numeric version of
these instructions
• “Assembly Language” is a symbolic notation that
the assembler translates into machine language
(basically a 1-to-1 correspondence)
27
C Program
C compiler
MIPS AL Program
MIPS assembler
MIPS ML Program
swap(int v[], int k) {
int tmp;
tmp = v[k];
v[k] = v[k+1];
v[k+1] = tmp;}
swap: muli $2, $5, 4
add $4, $2
lw $15, 0($2)
lw $16, 4($2)
sw $16, 0($2)
sw $15, 4($2)
jr $31
00000000101000010000000000011000
00000000100011100001100000100001
10001100011000100000000000000000
…
Processors and Assembly Languages
• Many different CPU architectures (machine
languages, assembly languages, assemblers,
instruction set types, etc.) PH3 CH 2 and X86 1.2
have some comparative discussion
• PH3 focuses mainly on the MIPS architecture
• We will learn the modern Intel 80x86 assembly
language because it is the most prevalent today
• However, X86 is much more complex, due to
backwards compatibility with earlier versions;
thus, we will gloss over some details.
• We will use the X86 book on the website.
29
Instruction Set Types
• MIPS uses RISC (Reduced Instruction Set
Computer)
 Fixed instruction length: 32 bits
 Fewer instruction formats
• X86 uses CISC (Complex Instruction Set
Computer)
 Instructions vary from 1 to 17 bytes; more
common operations are shorter
 More instruction formats
30
Machine Language Programs
• An ML “program” consists of a specific
sequence of instructions (machine code)
• In other words, ML programs are just
sequences of (sequences of) binary numbers
• Therefore, both ML programs and data can be
treated alike: both can be stored in memory to
be read and written to: stored program concept
31
Inside Computer: Stored Program Concept
Processor
Control
Datapath
ALU
R
E
G
I
S
T
E
R
S
Main Memory (volatile)
Accounting program
(machine code)
Editor program
(machine code)
Monthly bills data
DEVICES
IN
PUT
OUT
PUT
Master’s thesis data
Both the data and the programs for manipulating that
data are stored in memory
32
Inside Computer: Stored Program Concept
Processor
Control
Datapath
ALU
R
E
G
I
S
T
E
R
S
Main Memory
Accounting program
(machine code)
Editor program
(machine code)
Monthly bills data
DEVICES
IN
PUT
OUT
PUT
Master’s thesis data
Control takes program as input; each instruction tells it to do
operations on data in memory, via datapath and registers
33
Using Registers
• Basic repeated pattern occurs when
performing a program:
 Load values from memory into registers
 Operate on values in registers
 Store values from registers into memory
• Why use registers as intermediary?
 Main memory is large (~1 GB) but slow
 Registers are much faster: they are closer
(on processor!) and smaller
34
Using Registers
• Processor uses registers for “scratch paper”:
 Registers are the primary source and
destination for the results of operations
 These results are often used repeatedly, so
keeping them in registers is faster
• Some registers are “general purpose” (can be
used for anything), others play specific roles
• MIPS has 32 32-bit registers (don’t worry about
names right now); 24 are general purpose
registers
35
Using Registers
• X86 has 8 32-bit registers:
 ESP, EBP: often play specific roles
 EAX, ECX, EDX, EBX, ESI, EDI: truly general
purpose registers
• Don’t worry about the 16-bit registers
discussed in the X86 book; most exist for
backwards compatibility
• Why does X86 have so many fewer registers
than MIPS? In part, because X86 has much
more complex instructions
36
How Instructions access Memory
• To access memory elements (e.g., load/store
data), the instruction must know memory
organization
• Memory is organized as a huge array, where the
memory address is the index to the array
…
…
2
10
1
00001
0
101
Memory address
Data
37
How Instructions access data in Memory
• In x86, memory is byte-addressable: address 0
is the first byte, address 1 is the second byte,
etc. (different in MIPS)
…
…
2
1 byte = 8 bits
1
1 byte = 8 bits
0
1 byte = 8 bits
Memory address
Data
• Note: in x86, 2 bytes = word; 4 bytes = double word
• Protected mode: each program has own virtual
address space, managed by OS (details later)
38
Assignment
• Reading:
 PH Sections 3.6, skim 3.7 – 3.10
 Skim PH3, Chapter 2
 X86 book (as needed)
39