Back to Arithmetic Integer Multiplication

Before, we did Recall decimal multiplication from grammar school (non negative)
• Representation of integers multiplicand 1000 base ten
• Addition/Subtraction
multiplier 1001 base ten
• Logical ops
partial 1000
Forecast
products 0000
• Integer Multiplication
0000
• Integer Division
• Floating-point Numbers 1000
• Floating-point Addition/Multiplication 1001000 base ten

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 1 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 2

Integer Multiplication Example (Fig 4.25)

Convert to binary
Multiplicand
Use carry-save adders in a wallace tree Shift left
n bits times m bits = n+m bits (32 + 32 = 64) 64 bits

Example next (Figure 4.27)

Multiplier
• Multiplicand = 2 = 0010
64-bit ALU Shift right
• Multiplier = 3 = 0011 32 bits
• Product = 6 = 0110
Product
Control test
Write
64 bits

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 3 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 4
 Example (Fig. 4.26) Integer Multiplication

2. Shift the Multiplicand register left 1 b

No: < 32 repetition

3. Shift the Multiplier register right 1 b
Two optimizations

Multiplier0 = 0
• observation: upper-half of 64 bits are all zero

Yes: 32 repetitions
• use 32-bit ALU and shift product right

32nd repetition?
• instead of multiplicand left (multiplier still goes right)
Multiplier0

place the result in Product register

1a. Add multiplicand to product and
Multiplier0 = 1 1. Test
Start

• observation: only half of product is used

Done
• put multiplier in not-yet-used part of product

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 5 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 6

Integer Multiplication Integer Multiplication

Combinational multiplier What about negative multiplicand and/or multiplier
1000 * 1001 • grammar school
1000 • Booth’s encoding
1 1000 AND bits to get partial products Grammar school
0 0000 ADD PPs in tree to get product
• sign-prod = sign-mplicand XOR sign-mplier; negative = 0
0 0000 Use carry-save addition: 3 to 2 reduction every step
• if multiplicand < 0 {multiplicand = -multiplicand; negative++}
1 1000
• if multiplier < 0 {multiplier = -multiplier; negative++}
1001000
• product = multiplicand*multiplier
• if negative == 1 product = -product

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 7 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 8
 Integer Multiplication Booth’s Encoding
Booth encoding -- mind bending like carry-lookahead In binary
Skipping over 9’s in decimal - look for beginning and end of 9’s • works for 1’s - 1 less than 2
• we already are fast on zeroes
12345

* 09990 = -10 + 10000

-123450 12345*10 current bit bit to right info

+123450000 12345*10000 1 0 start 1’s -1
1 1 middle of 1’s 0
123326550
0 1 end of 1’s +1
But in decimal only works for 9’s - 1 less than base (10)
0 0 middle of 0’s 0

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 9 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 10

Booth’s Encoding Booth Encoding

-2k 1k 512 256 128 64 32 16 8 4 2 1 0 1010 -> -6 8 bits = 11111010 -(-6) = 00000110

1 1 1 0 0 1 1 1 0 1000 0110 -> +6 Boothenc = +1 0 -1 - = +0-0

0 0 -1 0 +1 0 0 -1 +1 -1 0 0 0 11111010 *0 = 0

0 -2 +2 -1 +1 0 1111010_ *- = 00001100

-2048 + 1024 + 512 + 64 + 32 + 16 + 4 111010__ *0 = 0

-1*512 + 1*128 + -1*16 + 1*8 + -1*4 11010___ *+ = 11010000

-2*256 + 2 *64 + -1*16 + 1*4 11011100 = -36

all equivalent

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 11 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 12
 Booth Encoding Redundant Representations
negative multiplier Normally
1010 = -6 • d2*b2 + d1*b1 + d0*b0; b base, di usually (0, 1, . . . base-1}

1110 = -2 booth enc 000-0 Booth Encoding

0000110_ = 00001100 = +12 • b = 2, di = {-1, 0, +1}

b * a2 a1 a0 = Carry-Save addition
• (a1-a2)*b*22 + (a0-a1)*b*21 + (0-a0)*b*20 • b = 2, di = { 0, 1, 2, 3}

• -a2*b*22+ (2*a1-a1)*b*21+ (2*a0-a0)*b*20 2-bit Booth Encoding

• b = 4, di = {-2, -1, 0, +1, +2}
• [a2*-22 + a1*21+ a0*20] !!

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 13 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 14

2-bit Booth Encoding 2-bit Booth Encoding

n-bit encoding retires n multiplier bits at a time For each partial product, mux controlled by multiplier digits

Eg., -2 - 2’sC, shift left one bit

1 1 1 0 0 1 1 1 0 1 0 0 “0” -1 - 2’sC

0 0 -1 0 +1 0 0 -1 +1 -1 0 0 -------- 1 bit enc 0

0 -2 +2 -1 +1 0 -------- 2 bit enc +1 pass through

+2 shift left one bit

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 15 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 16
 Integer Division Integer Division
divisor - 1000 dividend 1001010 - grammar school But hardware can’t inspect to see if divisor fits, so
1000)1001010( 1001 - quotient Subtract

1000 • if non-negative then set quotient to 1

• else set quotient to 0, add back the divisor (or “restore”)
10

101 Figure

1010 Can do multiplication-like optimizations

1000

10 - remainder

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 17 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 18

Integer Division Integer Division

Non-restoring division - a key optimization in division 0010101

Recall restoring division: + 11000 -divisor*22

divisor 1000, 2’sC 1 . . . 11000 11101 => < 0

+01000 +divisor*22

00101

001010 next bit down

+111000 -divisor*22

000010 (-d*22 + d*22) - d*21

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 19 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 20
 Integer Division Integer Division
Now non-restoring But quotient bits are {1, 1}
0010101 quotient bit = 1 if partial remainder is >= 0 (i.e., subtract)

+ 11000 -divisor*22 quotient bit = 1 if partial remainder is < 0 (i.e., add)

11101 => < 0 convert the weird quotient into 2’sC

111010 next bit down for any 2’sC negative numbers:

quotient bit = 1 if partial remainder and divisor are same sign

+001000 +divisor*21
quotient bit = 1 if partial remainder and divisor are opposite sign
000010 (-d*22+d*21) == -d*21

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 21 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 22

SRT Division and Pentium Bug Pentium Bug

Normalize so 1 <= dividend, divisor < 2 partial-remainder = dividend

Use radix 4 for divisor loop {

• base = 2 • determine next quotient digit
• get 2 bits of quotient per iteration • subtract quotient-digit*divisor from partial-remainder (CSA)

Use redundant quotient representation • shift over 2 bits (radix 4)

• digits {-2, -1, 0, +1, +2} instead of {0,1,2,3} }

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 23 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 24
 Pentium Bug Pentium Bug
Determine next quotient digit Incomplete testing did not expose,
conceptually - a table-lookup into table[partial-remainder, divisor] • since the algorithm self-corrects
• as long as the partial-remainder is “in range”
guess next 2 quotient bits
some part of the table is not “accessible” incorrect quotient for some dividend, divisor pairs

so optimized as don’t cares in PLA 1.14*10-10 fail on random

Max error in 5th significant digit,

• because you can’t get out of range for many iterations
But some of the don’t cares (5) actually occur in practice!

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 25 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 26

Pentium Bug Booth 2-bit Encoding

Analysis curr bits bit to right info Op
• There are are actually much worse errors in Pentium
00 0 mid of 0’s 0
• Errata book (and other microprocessors)
00 1 end of 1’s +1
• These can cause completely incorrect results 01 0 single 1 +1
• People believe hardware is always perfect 01 1 end of 1’s +2
• (for software you pay for their bugs!!) 10 0 beg of 1’s -2
• Pentium bug caught public attention 10 1 single 0 -1
• and Intel handled poorly 11 0 beg of 1’s -1
11 1 mid of 1’s 0

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 27 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 28
 Non-restoring Division Floating-Point Numbers
Final step may need correction if want to represent real numbers
• remainder and dividend opp signs, correction needed But uncountably infinite
• dividend, divisor same sign, remainder += D, quotient -=ulp
Recall scientific notation
• dividend, divisor opp sign, emainder -= D, quotient +=ulp
• 3.15576 *109 (#seconds in a century!)
convert wierd quotient to 2’sC : 1 is 1, 1 is 0 • 3,155,760,000
shift left by one bit • exponent says where the decimal point “float”
complement MSB Recall normalization
shift 1 into LSB • use 3.14*1010 NOT 0.314*1011 or 31.4*109
• MSD is [1,9] except for 0.0
© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 29 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 30

Floating-Point Numbers Floating-Point Numbers

computer floating-point is similar except binary usually
• number is -1s * f * 2e (note base is not stored) •s=S
• IEEE 754 uses base 2 • e = E - bias
• reduce relative error (wobble) • f = 1+ F/2n
• most significant bit is always 1, so don’t store it
• e.g., -1s * (1.F) * 2(E-1023)
For IEEE FP, store s, e,f as S, E, F
•SE F range n bias
• 1 8 23 single-precision 2*10+/-38 23 127
• 1 11 52 double-precision 2*10+/-308 52 1023

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 31 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 32
 Floating-Point Numbers Floating-Point Addition
Exceptions Like scientific notation
•S E F number
9.997 * 102
•0 0 0 0
• 0 max 0 +inf + 4.631 * 10-1

• 1 max 0 -inf First step: align decimal points, second step: add
• x max !=0 NaN 9.997 * 102
•x 0 !=0 denorm f = 0 + F/2n
+ 0.004631 * 102
see book for table
10.001631 * 102

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 33 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 34

Floating-Point Addition Floating-Point Subtraction

Third step: normalize the result Subtraction similar
• often already normalized • when adding different signs
• otherwise move only one digit • subtracting same signs

1.0001631 * 103

Example presumes infinite precision; with FP must round

Figure

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 35 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 36
 Floating-Point Multiplication Floating-Point Multiplication
Example: Hardware: Figure
• 3.0 * 101 Exponent:
2
• 5.0 * 10 e+ = e1 + e2
• algorithm: multiple mantissas, add exponents E+ = e+ + 1023 = E1 - 1023 + E2 -1023 + 1023
• check exponent in bounds --> exception
E+ = E1 + E2 - 1023
• normalize (and round)
-1023 = -(1111111111) = 0000000000 + 1 = +1
• set sign
With 2’sC E+ = E1 + E2 + carryin!

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 37 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 38

Floating-Point Multiplication Floating-Point Division

Significand E/ = E1 - E2 + 1023 = E1 - (E2 - 1) = E - (1’sC(E2))
23 or 52 bit non-negative integer multiplier For significand, use integer SRT with radix 4 or 16 (la Pentium)

carry save adders in a wallace tree

a shifter to normalize

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 39 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 40
 Rounding Rounding
6-9 up Need infinite bits? No - hold least significant bits
5 to even to make unbiased • guard bits - used for normalization - one bit right of LSB
• round bit - main round bit - one bit right of guard bit
1-4 down
• sticky - logical OR of all less significant bits
0 unchanged
• round sticky
xxxx.1 . . . 1 .. up •11 round up
xxxxx.10000 to even •10 round even
xxx.0 .. . . 1 .. . down • 0 1 round down

xxx.0000000000 unchanged • 0 0 no round

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 41 © 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 42

Rounding
IEEE FP bounds error to 1/2 “units of the last place” ULP

Keeping error small and unbiased is important

• can accumulate after billions of operations

other rounding modes

Mixing small and large numbers in FP

(3.1415 ... + 6 *1022 ) - 6 *1022 != 3.1415 .. + (6 *1022 - 6 *1022)

© 2000 by Mark D. Hill CS/ECE 552 Lecture Notes: Chapter 4 43