Transcript Course Introduction and Overview

Computer Arithmatic
Pradondet Nilagupta
Spring 2005
(original notes from Prof. J. Kelly Flanagan)
204521 Digital System Architecture
March 25, 2016
Computer Arithmetic
This lecture will introduce basic number
representations and introduce basic
integer and floating point arithmetic.
204521 Digital System Architecture
March 25, 2016
2
Arithmetic
Where we've studied so far:
– Boolean algebra and basic logic circuits
– Abstractions:
Instruction Set
Assembly Language and Machine Language
What's up ahead:
– Implementing the Architecture
– So we understand
instructions better
operation
a
32
ALU
result
32
b
32
204521 Digital System Architecture
March 25, 2016
3
Number Representation
Any number can be represented in any base
by the simple sum of each digit's value,
positional notation:
d * base
i
The value 1011 (binary) equals
3
2
1
0
1 * 2 + 0 * 2 + 1 * 2 + 1 * 2 = 11 (decimal).
204521 Digital System Architecture
March 25, 2016
4
Number Representation
as a 32 bit number this would be represented
as follows:
0000 0000 0000 0000 0000 0000 0000 1011
The most significant bit (MSB) is on the left
and the least significant bit (LSB) is on the
right. In the number above, the LSB is called
bit 0 and the MSB is called bit 31.
204521 Digital System Architecture
March 25, 2016
5
Range of Values
With 32 bits it is possible to have unsigned
32
numbers that range from 0 to 2 - 1 =
4,294,967,295.
This is quite reasonable for address
calculations of present machines, but future
32
machines will surely have more than 2
memory locations.
In addition to more memory it is highly useful
to be able to represent negative as well as
positive integers and numbers smaller and
larger then those possible with this format.
204521 Digital System Architecture
March 25, 2016
6
MIPS
32 bit signed numbers:
0000
0000
0000
...
0111
0111
1000
1000
1000
...
1111
1111
1111
0000 0000 0000 0000 0000 0000 0000two = 0ten
0000 0000 0000 0000 0000 0000 0001two = + 1ten
0000 0000 0000 0000 0000 0000 0010two = + 2ten
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1110two
1111two
0000two
0001two
0010two
=
=
=
=
=
+
+
–
–
–
2,147,483,646ten
2,147,483,647ten
2,147,483,648ten
2,147,483,647ten
2,147,483,646ten
maxint
minint
1111 1111 1111 1111 1111 1111 1101two = – 3ten
1111 1111 1111 1111 1111 1111 1110two = – 2ten
1111 1111 1111 1111 1111 1111 1111two = – 1ten
204521 Digital System Architecture
March 25, 2016
7
Signed Integers
Since in the binary number system we have
an even number of unique representations for
a given number of bits we have two choices:
1. Have a balanced system with the same
number of negative and positive values, but
what about zero? If we represent zero we
have an odd number of values to represent.
This can be done by allowing zero to be
represented by two different bit patterns.
204521 Digital System Architecture
March 25, 2016
8
Signed Integers
2. Have an unbalanced system where zero has one
representation, but there is either an extra positive
or negative value.
We would like a balanced system, but this would
require two different representations for the value
zero.
This evil (having two zeros) is better to avoid and not
worth the benefits of having a balanced system.
Consequently, an unbalanced system has been
nearly universally adopted.
204521 Digital System Architecture
March 25, 2016
9
One's Complement
How can we represent negative and positive numbers
in the binary system?
The 1's complement number system using 32 bits
has a range from -(2^31 -1) to +(2^31 - 1).
Zero can be represented as either positive or
negative. The two forms of zero are represented by
0000 0000 0000 0000 0000 0000 0000 0000 (all zeros)
or
1111 1111 1111 1111 1111 1111 1111 1111 (all ones).
204521 Digital System Architecture
March 25, 2016
10
One's Complement
A negative number is formed by representing
its magnitude in normal, positive binary
format and then inverting each bit.
8-bit examples:
1111 1110 = -1
1111 1111 = -0
0000 0000 = +0
0000 0001 = +1
Having two forms of zero is a problem, but
arithmetic is simple.
204521 Digital System Architecture
March 25, 2016
11
Two's Complement
The 2's complement number system using 32 bits has
a range from -2^31 to 2^31 - 1.
Zero has only one representation: all zeros, but there
is one extra negative value.
Negative numbers always have the MSB set to 1 -thus making sign detection extremely simple.
Converting 2's complement numbers to signed
decimal is extremely simple.
204521 Digital System Architecture
March 25, 2016
12
Example 2’s complement
Convert 1011 1010 to signed decimal.
7
6
5
4
3
2
1
1 * -2 + 0 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 0 * 2 + 1 * 2 + 0
0
*2
= -128 + 0 + 32 + 16 + 8 + 0 + 2 + 0
= -70.
This approach is not feasible in hardware due
to speed considerations.
204521 Digital System Architecture
March 25, 2016
13
Two's Complement Shortcuts
Negation in two's complement is
accomplished by inverting each bit of the
number and then adding one to the result.
Example: Convert -70 (decimal) to two's
complement binary.
|-70| = 70 = 0100 0110 (binary)
~ 0100 0110 = 1011 1001 (where ~ denotes bit
inversion)
1011 1001 + 1 = 1011 1010 = -70 (2's comp).
204521 Digital System Architecture
March 25, 2016
14
Sign Extension
To add a 16-bit value to a 32-bit value, the 16bit value must first be sign extended. The two
numbers are right aligned and the sign bit of
the shorter number is replicated to the left
until the two numbers are equal in length.
204521 Digital System Architecture
March 25, 2016
15
Example Sign Extension
0000 0000 0000 0000 0000 0000 0000 1011
+
1011 1010
we must sign extend the second number and then add:
0000 0000 0000 0000 0000 0000 0000 1011
+ 1111 1111 1111 1111 1111 1111 1011 1011
------------------------------------------------------------1 1111 1111 1111 1111 1111 1111 1100 0101
The extra bit on the left is simply discarded, leaving
us with 1111 1111 1111 1111 1111 1111 1100 0101
for our answer.
204521 Digital System Architecture
March 25, 2016
16
Possible Number Representations
Sign Magnitude:
000 = +0
001 = +1
010 = +2
011 = +3
100 = -0
101 = -1
110 = -2
111 = -3
One's Complement
000 = +0
001 = +1
010 = +2
011 = +3
100 = -3
101 = -2
110 = -1
111 = -0
111 = -1
204521 Digital System Architecture
March 25, 2016
Two's Complement
000 = +0
001 = +1
010 = +2
011 = +3
100 = -4
101 = -3
110 = -2
17
Integer Addition
Straight forward approach consists of adding
each bit together from right to left and
propagating
the carry from one bit to the next.
Perform the operation 7 + 6
0111 + 0110 = 1101
204521 Digital System Architecture
March 25, 2016
18
Integer Addition
Add the numbers 2,147,483,647 + 2
0111 1111 1111 1111 1111 1111 1111 1111
0000 0000 0000 0000 0000 0000 0000 0010
This is known as overflow
Overflow can be handled in several ways
An exception or interrupt can be asserted
A bit in a status register can be set
It can be completely ignored
204521 Digital System Architecture
March 25, 2016
19
Integer Subtraction
Straight forward approach consists of negating one
term and performing integer addition.
Perform the operation 7 - 6
0111 - 0110 = 0001
Perform the operation 6 - 7
0110 - 0111 = 1111
204521 Digital System Architecture
March 25, 2016
20
Integer Subtraction
Add the numbers -2,147,483,647 - 2
1000 0000 0000 0000 0000 0000 0000 0001
1111 1111 1111 1111 1111 1111 1111 1110
This is also overflow
Overflow can be handled in several ways
An exception or interrupt can be asserted
A bit in a status register can be set
It can be completely ignored
204521 Digital System Architecture
March 25, 2016
21
Integer Overflow
Overflow can occur whenever the sum of two
N bit numbers cannot be represented by
another N bit number.
Unsigned numbers must be treated
differently than signed numbers.
Unsigned numbers are usually used for
address calculations and it is convenient to
ignore overflow.
In many architectures this is accomplished
by having arithmetic instructions that ignore
the overflow condition.
204521 Digital System Architecture
March 25, 2016
22
Detecting Overflow
No overflow when adding a positive and a negative
number
No overflow when signs are the same for subtraction
Overflow occurs when the value affects the sign:
–
–
–
–
overflow when adding two positives yields a negative
or, adding two negatives gives a positive
or, subtract a negative from a positive and get a negative
or, subtract a positive from a negative and get a positive
Consider the operations A + B, and A – B
– Can overflow occur if B is 0 ?
– Can overflow occur if A is 0 ?
204521 Digital System Architecture
March 25, 2016
23
Effects of Overflow
Most processors hardware automatically generates
an exception (interrupt)
– Control jumps to predefined address for exception
– Interrupted address is saved for possible resumption
– Details will be studied in a later chapter
Don't always want to detect overflow
— new MIPS instructions: addu, addiu, subu
— Here, “u” stands for “un-overflowed”.
note: addiu still sign-extends!
note: sltu, sltiu for unsigned comparisons
204521 Digital System Architecture
March 25, 2016
24
Designing an ALU
Not easy to decide the “best” way to build something
– Don't want too many inputs to a single gate
– Don’t want to have to go through too many gates
– for our purposes, ease of comprehension is important
Let's look at a 1-bit ALU for addition:
CarryIn
a
Sum
b
cout = a b + a cin + b cin
sum = a xor b xor cin
CarryOut
How could we build a 1-bit ALU for add, and, and or?
How could we build a 32-bit ALU?
204521 Digital System Architecture
March 25, 2016
25
Building a 32 bit ALU
CarryIn
a0
b0
Operation
CarryIn
ALU0
Result0
CarryOut
Operation
CarryIn
a1
a
0
b1
CarryIn
ALU1
Result1
CarryOut
1
Result
a2
2
b2
b
CarryIn
ALU2
Result2
CarryOut
CarryOut
Each box is a 1bit ALU
204521 Digital System Architecture
a31
b31
March 25, 2016
CarryIn
ALU31
Result31
26
What about subtraction (a – b) ?
Two's complement approach: just negate b and add.
How do we negate?
A very clever solution:
Binvert
Operation
CarryIn
a
0
1
b
0
Result
1-bit ALU
w/ negation
2
1
CarryOut
204521 Digital System Architecture
March 25, 2016
27
Tailoring the ALU to the MIPS
Need to support the set-on-less-than instruction (slt)
– remember: slt is an arithmetic instruction
– produces a 1 if rs < rt and 0 otherwise
– use subtraction: (a-b) < 0 implies a < b
Need to support test for equality (beq $t5, $t6, $t7)
– use subtraction: (a-b) = 0 implies a = b
204521 Digital System Architecture
March 25, 2016
28
Supporting Set Less Than (slt)
Binvert
Operation
CarryIn
a
Can we figure out the idea?
0
1
Result
b
0
2
1
Less
3
a.
CarryOut
Binvert
Operation
CarryIn
a
0
1
Result
b
0
2
1
Less
3
Set
Overflow
detection
204521 Digital System Architecture
March 25, 2016
b.
Overflow
29
Binvert
CarryIn
a0
b0
CarryIn
ALU0
Less
CarryOut
a1
b1
0
CarryIn
ALU1
Less
CarryOut
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Operation
Result0
Result1
Result2
CarryIn
a31
b31
0
204521 Digital System Architecture
CarryIn
ALU31
Less
March 25, 2016
Result31
Set
Overflow
30
Test for equality
Bnegate
Operation
Notice control lines:
000
001
010
110
111
=
=
=
=
=
and
or
add
subtract
slt
a0
b0
CarryIn
ALU0
Less
CarryOut
Result0
a1
b1
0
CarryIn
ALU1
Less
CarryOut
Result1
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Result2
Zero
•Note: zero is a 1 when the result is zero!
a31
b31
0
204521 Digital System Architecture
CarryIn
ALU31
Less
March 25, 2016
Result31
Set
Overflow
31
Conclusion
We can build an ALU to support the MIPS instruction set
– key idea: use multiplexor to select the output we want
– we can efficiently perform subtraction using two’s complement
– we can replicate a 1-bit ALU to produce a 32-bit ALU
Important points about hardware
– all of the gates are always working
– the speed of a gate is affected by the number of inputs to the gate
– the speed of a circuit is affected by the number of gates in series
(on the “critical path” or the “deepest level of logic”)
Our primary focus: comprehension, however,
– Clever changes to organization can improve performance
(similar to using better algorithms in software)
– we’ll look at two examples for addition and multiplication
204521 Digital System Architecture
March 25, 2016
32
Problem: ripple carry adder is slow
Is a 32-bit ALU as fast as a 1-bit ALU?
Is there more than one way to do addition?
– two extremes: ripple carry and sum-of-products
Can you see the ripple? How could you get rid of it?
c1
c2
c3
c4
=
=
=
=
b0c0
b1c1
b2c2
b3c3
+
+
+
+
a0c0
a1c1
a2c2
a3c3
+
+
+
+
a0b0
a1b1c2 =
a2 b2
c3 =
a3b3
c4 =
Not feasible! Why?
204521 Digital System Architecture
March 25, 2016
33
Carry-look-ahead adder
An approach in-between our two extremes
Motivation:
– If we didn't know the value of carry-in, what could we do?
– When would we always generate a carry?
gi = ai bi
– When would we propagate the carry?
pi = ai + bi
Did we get rid of the ripple?
c1
c2
c3
c4
=
=
=
=
g0
g1
g2
g3
+
+
+
+
p0c0
p1c1
p2c2
p3c3
c2 =
c3 =
c4 =
Feasible! Why?
204521 Digital System Architecture
March 25, 2016
34
Use principle to build bigger adders
CarryIn
a0
b0
a1
b1
a2
b2
a3
b3
CarryIn
Result0--3
ALU0
P0
G0
pi
gi
Carry-lookahead unit
C1
a4
b4
a5
b5
a6
b6
a7
b7
a8
b8
a9
b9
a10
b10
a11
b11
a12
b12
a13
b13
a14
b14
a15
b15
ci + 1
CarryIn
Result4--7
ALU1
P1
G1
pi + 1
gi + 1
C2
ci + 2
CarryIn
Result8--11
ALU2
P2
G2
pi + 2
gi + 2
C3
ci + 3
CarryIn
Result12--15
ALU3
P3
G3
Can’t build a 16 bit adder this
way... (too big)
Could use ripple carry of 4-bit
CLA adders
Better: use the CLA principle
again!
pi + 3
gi + 3
C4
ci + 4
CarryOut
204521 Digital System Architecture
March 25, 2016
35
Longhand Multiplication
Multiply 1000 * 1001 (either decimal or binary will work!)
Multiplicand
1000
Multiplier
1001
1000
0000
0000
1000
------Product
1001000
204521 Digital System Architecture
March 25, 2016
36
Longhand Multiplication
The first number is the multiplicand and the
second the multiplier.
The result is larger than either the
multiplicand or the multiplier. If the size of the
multiplicand is N bits and the size of the
multiplier is M bits then the result is M+N bits
long.
204521 Digital System Architecture
March 25, 2016
37
Simple Multiplication Algorithm
The Multiplicand is stored in a 64 bit register and the
Multiplier is stored in a 32 bit register while the
product register is 64 bits long and initialized to zero.
Test bit 0 of the multiplier
If this bit is 0
Continue
If this bit is 1
Add the multiplicand to the product and store back in
the product register
Shift the multiplicand register left 1 bit
Shift the multiplier register right 1 bit
If this is the 32nd iteration END else continue
204521 Digital System Architecture
March 25, 2016
38
MULTIPLY HARDWARE Version 1
64-bit Multiplicand reg, 64-bit ALU, 64-bit Product reg,
32-bit multiplier reg
Shift Left
64-bit Multiplicand
32-bit Multiplier
Shift Right
64-bit ALU
64-bit Product
204521 Digital System Architecture
Write
Control
March 25, 2016
39
Multiply Algorithm
Version 1
Start
Multiplier0 = 1
Test
Multiplier0
Multiplier0 = 0
1. Add multiplicand to product &
place the result in Product register
2. Shift the Multiplicand register left 1 bit.
3. Shift the Multiplier register right 1 bit.
32nd
repetition?
No: < 32 repetitions
Yes: 32 repetitions
Done
204521 Digital System Architecture
March 25, 2016
40
Try It Yourself, V1
4x4 bit Multiply, Version 1
Show each step for 5 x 11 = 55
Multiplier Multiplicand Product
Operation
0101
0000 1011 0000 0000 initial load
204521 Digital System Architecture
March 25, 2016
41
Solution, V1
5 x 11 = 55
Multiplier
0101
Multiplicand
0000 1011
Product
0000 0000
Operation
initial load
0101
0010
0000 0011
0001 0110
0000 1011
0000 1011
add
shift
0010
0001
0001 0110
0010 1100
0000 1011
0000 1011
no add
shift
0001
0000
0010 1100
0101 1000
0011 0111
0011 0111
add
shift
0000
0000
0101 1000
1011 0000
0011 0111
0011 0111
no add
shift
204521 Digital System Architecture
March 25, 2016
42
Observations on Multiply Version 1
1 clock per cycle --> 32 x 3 = 100 clocks per multiply
– Ratio of multiply frequency to add is 5:1 to 100:1
– But remember Amdahl’s Law!
1/2 bits in multiplicand always 0
– 64-bit adder is wasted
0’s inserted in right side of multiplicand as shifted
– least significant bits of product never changed once formed
Instead of shifting multiplicand to left, shift product
to right?
204521 Digital System Architecture
March 25, 2016
43
A Better Multiplier
In the previous algorithm half of the bits in the
multiplicand register are zero and contain no needed
information. This algorithm requires only a 32 bit ALU
and multiplicand register
If multiplier bit 0 = 0
Continue
if multiplier bit 0 = 1
Add the multiplicand to the left half of the product register
and store the result in the left half
Shift the product and multiplier registers right 1 bit.
If this is the 32nd iteration END otherwise continue
204521 Digital System Architecture
March 25, 2016
44
MULTIPLY HARDWARE Version 2
32-bit Multiplicand reg, 32 -bit ALU, 64-bit
Product reg, 32-bit Multiplier reg
32-bit
Multiplicand
32-bit
Multiplier
32-bit ALU
Shift Right
Shift Right
64-bit Product
Control
Write
204521 Digital System Architecture
March 25, 2016
45
Multiply Algorithm
Version 2
Start
Multiplier0 = 1
Test
Multiplier0
Multiplier0 = 0
1. Add multiplicand to the left half of product &
place the result in the left half of Product register
2. Shift the Product register right 1 bit.
3. Shift the Multiplier register right 1 bit.
32nd
repetition?
No: < 32 repetitions
Yes: 32 repetitions
Done
204521 Digital System Architecture
March 25, 2016
46
Try It Yourself, V2
4x4 bit Multiply, Version 2
Show each step for 5 x 11 = 55
Multiplier Multiplicand Product
Operation
0101
1011
0000 0000 initial load
204521 Digital System Architecture
March 25, 2016
47
Solution, V2
5 x 11 = 55
Multiplier
0101
Multiplicand
1011
Product
0000 0000
Operation
initial load
0101
0010
1011
1011
1011 0000
0101 1000
add
shift
0010
0001
1011
1011
0101 1000
0010 1100
no add
shift
0001
0000
1011
1011
1101 1100
0110 1100
add
shift
0000
0000
1011
1011
0110 1100
0011 0111
no add
shift
204521 Digital System Architecture
March 25, 2016
48
Observations on Multiply Version 2
Right half of product register wastes space
that exactly matches size of multiplier
So put multiplier in right half of product
register ?
204521 Digital System Architecture
March 25, 2016
49
Another Multiplier
In the previous algorithm the lower bits of the
product register are wasted and could be
used to store the multiplier.
If product bit 0 = 0
Continue
if product bit 0 = 1
Add the multiplicand to the left half of the
product register and store the result in the left
half
Shift the product register right 1 bit.
If this is the 32nd iteration END otherwise continue
204521 Digital System Architecture
March 25, 2016
50
MULTIPLY HARDWARE Version 3
32-bit Multiplicand reg, 32 -bit ALU, 64-bit
Product / Multiplier reg
32-bit
Multiplicand
32-bit ALU
Shift Right
64-bit Product / Multiplier
Control
Write
204521 Digital System Architecture
March 25, 2016
51
Multiply Algorithm
Version 3
Start
Product0 = 1
Test
Product0
Product0 = 0
1. Add multiplicand to the left half of product &
place the result in the left half of Product register
2. Shift the Product register right 1 bit.
32nd
repetition?
No: < 32 repetitions
Yes: 32 repetitions
Done
204521 Digital System Architecture
March 25, 2016
52
Try It Yourself, V3
4x4 bit Multiply, Version 3
Show each step for 5 x 11 = 55
Multiplicand
Product / Multiplier Operation
1011
0000 0101
initial load
204521 Digital System Architecture
March 25, 2016
53
Solution, V3
5 x 11 = 55
Multiplicand
1011
Product / Multiplier
0000 0101
Operation
initial load
1011
1011
1011 0101
0101 1010
add
shift
1011
1011
0101 1010
0010 1101
no add
shift
1011
1011
1101 1101
0110 1100
add
shift
1011
1011
0110 1100
0011 0111
no add
shift
204521 Digital System Architecture
March 25, 2016
54
Observations on Multiply Version 3
2 steps per bit because Multiplier & Product
combined
MIPS registers Hi and Lo are left and right
half of Product
Gives us MIPS instruction MultU
What about signed multiplication?
– easiest solution is to make both positive &
remember whether to complement product when
done (leave out the sign bit, run for 31 steps)
– Booth’s Algorithm is more elegant way to multiply
signed numbers using same hardware as before
204521 Digital System Architecture
March 25, 2016
55
Booth's Multiplier
In the previous algorithms only unsigned
numbers were dealt with. Booth's algorithm
deals with signed numbers as well.
If the current and previous bits are
00 -- no addition or subtraction
01 -- end of string of one's so add the multiplicand to
the
left half of the product
10 -- beginning of a string of one's so subtract the
multiplicand from the left half of the product
11 -- middle of a set of one's no addition or subtraction
Shift the product register right 1 bit.
If this is the 32nd iteration END otherwise continue
204521 Digital System Architecture
March 25, 2016
56
Example of Booth's Algorithm
5 = 00101
x -3 = x 11101
---- ------Product
00000 11101 0 subtract and shift
11011 11101 0
11101 11110 1 add and shift
00010 11110 1
00001 01111 0 subtract and shift
11100 01111 0
11110 00111 1 shift only
11111 00011 1 shift only
11111 10001 1
result = 10001
= -01111
= -15 (base10)
204521 Digital System Architecture
March 25, 2016
57
Floating Point Numbers
Although 2's complement numbers have
been used for nearly 25 years, many floating
point number representations were used up
until about 1985.
Different representations make it very difficult
to transfer data from one machine to another.
A standard was and is needed.
204521 Digital System Architecture
March 25, 2016
58
Reals and Floats
Consider the following numbers:
3.1415926
2.718
9
0.000000001 = 1 * 10
9
3,155,760,000 = 3.15576 * 10
The first three numbers cannot be
represented by binary integers for obvious
reasons, and the fourth cannot because
signed 32-bit values are not large enough.
204521 Digital System Architecture
March 25, 2016
59
Reals and Floats
Binary numbers can also be represented in scientific
notation. The general form of this is
s 1.m * 10 ^ e (binary)
where s is either + or - representing the sign of the
number, m is a string of 1s and 0s representing the
fractional part of the mantissa, and e is a + or - string
of 1s and 0s representing an exponent, or the
number's order of magnitude. Note that this is almost
identical in form to standard decimal scientific
notation, except that the 10 represents 2 (decimal),
not 10 (decimal).
204521 Digital System Architecture
March 25, 2016
60
Single Precision Floating Point (FP)
Numbers
Current computer systems dictate that FP numbers
must fit in 32- or 64-bit registers.
32-bit or single precision FP numbers are organized
as follows:
seee eeee emmm mmmm mmmm mmmm mmmm mmmm
where s is the sign of the number, e represents the
biased exponent, and m represents the mantissa.
32-bit values range in magnitude from 10-38 to 1038.
204521 Digital System Architecture
March 25, 2016
61
Double Precision Floating Point
Numbers
64 bit double precision floating point
numbers are organized as follows:
– The MSB is the sign bit
– The next 11 bits are the exponent
– The remaining 52 bits are the significand
-308
308
The range in magnitude is from 10
to 10
The growth of significand and exponent is a
compromise between accuracy and range.
204521 Digital System Architecture
March 25, 2016
62
Implied Normalization
In the IEEE 754 floating point standard, a
leading 1 in the significand is assumed. This
increases the effective length of the
significand in both single and double
precision arithmetic
Numbers are therefore represented by:
S
(-1) * (1.M) * 2
E-127
where S is the sign, M is the significand and E
is the exponent
204521 Digital System Architecture
March 25, 2016
63
Why IEEE 754?
Example
if(x == 0.0)
y = 17.0
else
y = z/x
Can this cause a divide by zero error?
204521 Digital System Architecture
March 25, 2016
64
Why IEEE 754?
In the CDC6600 the adder and subtractor
examine 13 bits while the multiplier/divider
only examines 12 bits. Very small x's cause a
problem.
Solution:
if(1.0 * x == 0.0) CRAY overflow, Why?
y = 17.0
else
y = z/x
204521 Digital System Architecture
March 25, 2016
65
Floating Point Addition
It should be clear that addition and subtraction are
performed in a similar manner.
The steps for adding two floating point numbers is as
follows:
1.We must adjust the smaller number until its exponent
matches that of the larger number.
2.We add the significands together and round
3.Then the result is normalized by shifting the
significand left or right and adjusting the exponent.
4.The number must again be rounded
204521 Digital System Architecture
March 25, 2016
66
Floating Point Addition
Add the numbers 0.5 and -0.4375
In normalized form
-1
0.5 = 1.000*2
-2
-0.4375 = -1.110*2
Shift the significand of the smaller number
right until the exponents of the two numbers
are the same and add the significands
-1
-1
-1
-0.111*2 + 1.000*2 = 0.001*2
204521 Digital System Architecture
March 25, 2016
67
Floating Point Addition
Normalize the result
-1
-2
-3
0.001*2 = 0.010*2 = 0.100*2 = 1.000*2
-4
Round the result
This result already fits in the 4 bit field and no
rounding is needed.
204521 Digital System Architecture
March 25, 2016
68
Floating Point Addition
Continued
Add 9.99910*10 + 1.61010*10
-1
Shift the significand of the smaller number
right until the exponents of the two numbers
are the same and add the significands
1
1.61010*10-1 = 0.016110*10
204521 Digital System Architecture
March 25, 2016
69
Floating Point Addition
Continued
Round the significand = 0.01610*10
1
1
1
0.016*10 + 9.999*10 = 10.015*10
1
Normalize the result
1
2
10.015*10 = 1.0015*10
Round the result
2
1.00210*10
204521 Digital System Architecture
March 25, 2016
70
Floating Point Multiplication
1.Add the biased exponents and subtract off
the bias.
2.Multiply the significands, this is an unsigned
multiply
3.Normalize the product shifting it right and
incrementing the exponent
4.Check for overflow or underflow
5.Round the significand
6.Check to see if it is still normalized
7.Set the sign bit to the appropriate value, this
is simply the XOR of the initial two sign bits
204521 Digital System Architecture
March 25, 2016
71
More FP Multiplication
0.5 * -0.4375
-1
-2
1.000*2 -1.110*2
-1
1.000*2
= 0 01111110 000........many more sig. bits
-1.110*2-2
= 1 01111101 110.........many more sig. bits
204521 Digital System Architecture
March 25, 2016
72
More FP Multiplication
Add exponents and subtract bias
01111110
+ 01111101
------------11111011 = 124 + 127 = 251
+ 10000001
-------------01111100 = 251 - 127 = 124
204521 Digital System Architecture
March 25, 2016
73
More FP Multiplication
Multiply the significands
1.000
x 1.110
------0000
1000
1000
1000
------1110000 = 1.110000
= -1.110*2-3
= 1 01111100 110.......many more sig. bits
204521 Digital System Architecture
March 25, 2016
74
Guard, Round, and Sticky Bits
The guard and round bits are two bits to the
right of the significand used for intermediate
results.
0
2
2
2
2.56*10 + 2.34*10 = 0.0256*10 + 2.34*10
– Guard bit holds 5
– Round bit holds 6
Now we round using two digits, the guard
and round digits
– 0 to 49 round down
– 51 to 99 round up
– 50+sticky round up else even
204521 Digital System Architecture
March 25, 2016
75
Guard, Round, and Sticky Bits
We round up with a 56
= 2.37*10
2
Without guard and round bits we would have
truncated the intermediate result and
acquired
= 2.36*10
2
204521 Digital System Architecture
March 25, 2016
76
Floating Point Division
Don't fear we are not going to do anything in
detail with division.
The hardware and algorithms are quite
similar to multiplication, but instead of using
addition subtraction is used heavily.
204521 Digital System Architecture
March 25, 2016
77
Logical Operations
There are several logical operations that are
useful or needed on a computer system
AND
OR
NAND
NOR
NOT or Invert
XOR
XNOR
204521 Digital System Architecture
March 25, 2016
78
Logical Operations
These functions are usually used to test bits
fields or patterns within a machine word.
These are quite different than the logical
operations used in statements like
if((a = b) || (c == d))
if((a !=b) & & (c == d))
204521 Digital System Architecture
March 25, 2016
79
Time and Space
If we are performing a 32 bit addition all of the
inputs are known immediately, but we must
wait for the carry to ripple the length of the
adder.
In an ancient VLSI adder I designed and
simulated the time for the carry propagation
was 7ns. This would result in a 32 bit add
time of 224ns resulting in a usable system
clock rate of 4.46MHz. This is way too slow.
204521 Digital System Architecture
March 25, 2016
80
Time and Space
Several types of improved adders have been
designed:
– Carry Lookahead Adders
– Carry Skip Adders
– Carry Select Adders
Adder Type
Time
Size
32 bit adder, 7ns ripple
------------------------------------------------------------------------------------Ripple
O(n)
O(n)
7 * 32 = 224
Carry Lookahead O(log n)
O(n log n) 7 * log 32 = 35
Carry Skip
O(sqrt(n)) O(n)
7 * sqrt 32 = 40
Carry Select
O(sqrt(n)) O(n)
7 * sqrt 32 = 40
204521 Digital System Architecture
March 25, 2016
81
Time and Space
Notice that the Carry Lookahead Adder is the fastest,
but also the largest!
The Carry Lookahead Adder generates the carry
signals by generating the P and G signals
described in the text. This added circuitry is
responsible for the large size of this adder.
The Carry Skip Adder only generates the P signals
The Carry Select Adder uses two complete adders,
one with a carry in of 1 and the other 0.
204521 Digital System Architecture
March 25, 2016
82
Fast Multipliers
Many adders can be used in parallel to speed
multiplication. These units are called parallel
multipliers.
The important issue is that increased speed
can be achieved by throwing hardware at the
problem.
Parallel multipliers can be pipelined to allow a
multiplication to begin on each clock cycle.
The result still takes N clock cycles, but
then a new result becomes available each
clock cycle after the first.
204521 Digital System Architecture
March 25, 2016
83
Conclusions
Algorithms such as binary addition for
integer or floating point can usually be made
faster by throwing more hardware at the
problem.
It is the job of the architect and the
implementor to make the speed versus cost
trade-offs.
Understanding the way the datapath of a
machine is implemented is crucial for
compiler and operating system writers.
204521 Digital System Architecture
March 25, 2016
84