Transcript Arithmetic

Arithmetic
By Li Wen
Professor Sin-Min Lee
SJSU CS 147 Fall 2007
Table of Contents

Floating-point arithmetic



High-performance arithmetic






Floating-point addition and subtraction
Floating-point multiplication and division
High-performance addition
High-performance multiplication
High-performance division
Residue Arithmetic
Questions and comments
Reference
Floating-point Arithmetic

Adjusting the significant
1. Make the exponent
equal to the larger
exponent
2. Lost .001 x 23
precision
1. Round to three
significant
2. Lost .0001 x 24
One way to add
101 + 1110
= .101 x 23 + .111 x 24
= .010 x 24 + .111 x 24
= (.010 + .111) x 24
= 1.001 x 24
= .1001 x 25
Lost total
4
= .100 x 25 .001x23 +.0001x2
4
=.0011x2
precision
Floating-point Arithmetic (cont.)
The other way to add
101 + 1110
= .101 x 23 + .111 x 24
Adjusting the significant
= .0101 x 24 + .111 x 24
4
=
(.0101
+
.111)
x
2
Make the exponent
equal to the larger
4
=
1.0011
x
2
exponent
= .10011 x 25
Got total
1. Round to nearest even
= .101 x 25
5

method
2. got .00001 x 25 more
.00001x2 more
Floating-point Arithmetic (cont.)
Both are incorrect
 According to IEEE 754: the final result
should be the same as if the maximum
precision needed is used before applying
the rounding method.
 The correct result is .101 x 25 , which is
the second example above

Floating-point Arithmetic (cont.)
Using guard (g), round (r) and sticky (s) bit
will make the correct result without using
too much hardware.
 Guard (g): one additional digit to the right
 Round (r): one additional digit to the right
 Sticky (s): any nonzero digits to the right of
the round bit
 Round method used: round to nearest
even number on ties

Floating-point Arithmetic (cont.)

Example:
101
1110
.101 x 23
.111 x 24
.0101 x 24
+ .111 x 24
1.00110x24
grs=100
No 1 after r, so s = 0, stick 100 to .100110
.100110 x 25 ≈ .101 x 25
Reason of Complication PP 75
Floating-point Arithmetic (cont.)

Addition example
.1011 x 27
.0111 x 24
.1011
x 27
+.0000111 x 27
.1011111 x 27
grs=111
result
.1100 x 27
Floating-point Arithmetic (cont.)

Subtraction example
.1011 x 27
.0111 x 24
.1011
x 27
- .0000111 x 27
.1010001 x 27
grs=001
result
.1011 x 27
Floating-point Arithmetic (cont.)

Multiplication example
+.101 x 22
x - .110 x 2-3
- . 01111 x 2-1
Result: -.100 x 2-1
2+(-3) = -1
Floating-point Arithmetic (cont.)

Division example
Result:
+ .110 x 25
/+.100 x 24
1.1 x 21
.110 x 22
5-4=1
High-performance arithmetic
The goal is to improve the speed of
arithmetic operation.
 High-Performance Addition, Multiplication,
Division, and Residue Arithmetic

High-Performance Addition
Method used in addition: carry lookahead adder
 Example:
si = aibici+aibici+aibici+aibici
ci+1= bici+aici+aibi
ci+1 = aibi+(ai+bi)ci
ci+1 = Gi+Pici
Where Gi=aibi and Pi = ai+bi

High-Performance Addition (cont.)
Gi = aibi
Gi is called generate, created by AND gate
When Gi = 1, a carry is generated at stage i.

Pi = ai+bi
Pi is called propagate, created by OR gate
When Pi = 1, a carry is propagate at stage i if
either ai or bi is a 1.

High-Performance Addition (cont.)
High-Performance Addition (cont.)
Example 3-2
Carry lookahead adder (CLA)
Group carry lookahead adder (GCLA)
Group Generate (GG)
Group Propagate (GP)

High-Performance Multiplication

Two methods are used for multiplication:
 Skipping
over blocks of 1s
 Cross product in parallel multiplier

The Booth Algorithm
+ or – number
 No addition, but shifting
 No
High-Performance Multiplication (cont.)
 For
example, for multiplier 001110
 From 0 to 1, -21; from 1 to 0 +24; 24-21 = (14)10
 Recorded as 0 +1 0 0 -1 0 by Booth Algorithm
Multiplicand 010101 (21)10
 Operation 1: (21)10 x (-21)
 Operation 2: (21)10 x (24)
 Operation 3: (294)10

High-Performance Multiplication (cont.)




Problem with Booth Algorithm
Saving in the previous example: two operations
needed -1 and +1 are recorded, but consider the
following example: 010101 (21)10
Will be recorded as +1 -1 +1 -1 +1 -1 by the
same algorithm, where six operation will be
needed.
Modified Booth Algorithm (bit-pair recording):
group each (+1,-1) as +1, each (-1,+1) as -1,
and (+1,+1) (-1,-1) cannot occur. Bit pairs table
PP 83
High-Performance Multiplication (cont.)
Method used in Array Multipliers: do each
process in parallel.
 Solve problem: time reduce from w2 to 2w
for the length of w
 Parallel pipelined array multiplier

High-Performance Division
Method used: Newton’s iteration
 Goal: find where the function f(x) crossed
the x axis by starting guess xi then using
the error between f(xi) and zero to refine
the guess.
 Result: until the last two guessed results
are close to each other.

Residue Arithmetic
Residue arithmetic can solve addition,
subtraction, and multiplication problems.
 The first 20 residue number for given
moduli 5,7,9,4, PP 87

References
http://en.wikipedia.org/wiki/Adder_(electro
nics) obtained by 9/23/07
 http://vlsi.uwindsor.ca/presentations/biswa
s4_seminar_1.pdf obtained by 9/23/07
 Computer Architecture and Organization,
Miles Murdocca and Vincent Heuring
