3.0 Arithmetic Unit - Part 2

Integer Multiplication Multiplication of Positive Integers Paper-And-Pencil Method v In a positional number system, multiplication is performed by multiplying the multiplicand M by each digit of the multiplier Q. These are then weighted and added. 1 1 0 1 M Q × 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 1 P Ø The length of the product p is the sum of the lengths of the multiplicand m and the multiplier q. Ø The addend exists only, and is a copy of the multiplicand, if the multiplier bit is 1. v The integer multiplier can be implemented using full-adders and AND gates. – Parallel Multiplier Ø Since addition is performed using 2 operands at a time, partial products can be obtained while the addends are being generated. 1 1 0 1 M Q × 1 0 1 1 0 0 0 0 PP0 + 1 1 0 1 1 1 0 1 PP1 + 1 1 0 1 1 0 0 1 1 1 PP2 + 0 0 0 0 1 0 0 1 1 1 PP3 + 1 1 0 1 1 0 0 0 1 1 1 1 P PPi

0

Mj

M3

0

M2

0

M1

0

Qi Cout i

FA

0

Cin i

Q2

0

Q3

0

HALJ

P6

P5

P4

P3

Arithmetic Unit (Part 2)

Q0

Q1

0

PP i+1

P7

M0

P2

P1

P0 1

v Impractical for a dedicated circuit. Ø Requires m×q blocks with 1 full-adder and 1 AND gate each. Ø Very long propagation delay. Serial Integer Multiplier v The circuit size may be reduced by using the existing adder of the ALU. Additionally requires Ø 2 shift registers A and Q to hold the product Ø 1 register M to hold the multiplicand Ø 1 binary cell C to hold the carry-out of the partial product Ø A control sequencer Shift Right

C

A

Q Multiplier

Cout

Control Sequencer

Add Cin

M

Multiplicand

v Process Ø Initialization § Clear A. § M gets multiplicand. § Q gets multiplier. Ø Loop for each bit of multiplier § If Q0 = 1 then Add. § Shift right CAQ. Ø Result contained in register combination AQ. Comments Ø Size of A at least equal to M, not necessarily but typically equal to Q. Ø Speed is a little slower (due to extra shifting time). Ø Size is a lot smaller. Example: 13×11

Init Bit 0

M C 0 0

Bit 1

1

Bit 2 Bit 3

HALJ

1

1101 A 0000 1101 0110 0011 1001 0100 0001 1000

Q 1011 1101 1110 1111 1111

Arithmetic Unit (Part 2)

Add Shift Add Shift Shift Add Shift

2

Signed Integer Multiplication v Basically magnitude multiplication + sign adjustment v Result is size of magnitudes + 1 for sign bit. Computers typically use just the sum of the sizes. v Need to extend the sign bits. Example: –13×11 1 0 0 1 1 M Q × 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 P v If multiplier is negative, need to add negative (2’s complement) of multiplicand, sign-extended and shifted to sign-bit position. Note: msb of multiplier is actually the sign bit, i.e., a 1 means a negative multiplier. Example: 11×–13

0 0 0 0 1 1

0 0 0 0 1 1

0 0 0 0 0 0

0 0 0 0 1 1

× 0 0 0 0 0 1

0 1 0 1 0 0 1 1

1 0 1 0 0 0

× 1 1 0 0 1 0

1 1 1 0 0 0 1 0

0 0 0 1 0 0

0 0 0 1 0

1 1 1 1 1 1 1

0 0 0 1

M Q

s.adj P

Example: –11×–13

1 1 0 0 0 0

1 1 0 0 0 0

1 1 0 0 1 1

1 1 0 0 0 0

1 0 1 0 0

0 1 1 1 0 1 1

1 1 1 1

M Q

s.adj P

Comments Ø Different last step for negative multiplier. Leads to difficulty in circuit design. Booth’s Algorithm v Treats positive and negative multipliers uniformly. v Rewrites multiplier in terms of sums and differences. Ø Convert code according to next bit at right § 0 to 1 ⇒ +1 § 1 to 0 ⇒ –1 § Otherwise, 0 Ø Right of lsb is “nothing”, i.e., equal to 0. J HALJ

Arithmetic Unit (Part 2)

3

13

= 0 1 1 0 ⇒ +1 0 –1 +1 = +24 – 22 + 21 – 20

1 –1

–13

= 1 0 0 1 1 ⇒ –1 0 +1 0 –1 = –24 + 22 – 20 v Multiplication is performed via add (if +1) and subtract (if –1). Example: 11×13

1 0 1 0 0 0

1 0 1 0 0 0

1 0 1 0 1 1

1 0 1 0 0 0

× 1 0 0 0 1 0

0 1 +1 1 1 1 0 1 0

1 0 0 0 0 0 0

× 1 0 1 0 0 1

0 1 –1 1 0 0 0 1 1

1 0 0 0 0 1 0

0 1 –1 1 1 1

1 0 +1 0 1

1 1 –1 1

1 1 1 1

M –M Q Sub Add Sub 0 Add P

Example: 11×–13

1 0 0 0 1 1

1 0 0 0 1 1

1 0 0 0 0 0

1 0 0 0 1 1

0 1 +1 1 0 1

1 0 0 0 0

1 1 –1 1

0 0 0 1

M –M Q Sub 0 Add 0 Sub P

Fast Integer Multiplication v Bit-Pair Recording – reduces to half the number of summands v Carry-Save Addition – reduces time of addition in parallel multipliers Bit-Pair Recording v The number of summands is reduced by pairing multiplier bits and ensuring left bit is 0 (Extended Booth Representation), i.e., 0 0 ⇒ 0 0 0 +1 ⇒ 0 +1 0 –1 ⇒ 0 –1 +1 0 ⇒ 0 +2 +1 –1 ⇒ 0 +1 –1 0 ⇒ 0 –2 –1 +1 ⇒ 0 –1 Ø Multiplication is either by: § 1 (copy) or 2 (copy shift) § positive (M) or negative (–M) HALJ

Arithmetic Unit (Part 2)

4

Example: 11×9 9 = 0 1 0 0 1 +1 –1 0 +1 –1 +1 –2 +1

0 1 0 0

0 1 0 0

0 1 1 0

× 0 1 1 1

0 0 0 1

0 1 +1 0 0 1 0

1 0 1 0 1 0 –2 1 0 1 1 0

1 1 +1 1

0 0 1 1

M –M Q PP0 PP1 PP2 P

Example: 11×–9 –9 = 1 0 1 1 1 –1 +1 0 0 –1 +2 –1 –1

1 0 1 1

1 0 1 1

1 0 0 1

× 1 0 0 0

1 1 1 0

0 1 –1 1 1 1 1

1 0 1 0 1 0 +2 0 1 0 1 0

1 1 –1 1

1 1 0 1

M –M Q PP0 PP1 PP2 P

Carry-Save Addition v The parallel multiplier can be improved by improving the adder portion. v Consider the addition of 3 numbers: W + X + Y = Z v Using standard ripple-carry adders

0

Z5

W3 X3

W2 X 2

W1 X 1

W0 X0

FA

FA

FA

FA

Y3

Y2

Y1

0

Y0

FA

FA

FA

FA

FA

Z4

Z3

Z2

Z1

Z0

0

Ø A carry-lookahead circuit can improve the upper level. The lower level cannot benefit from a carry-lookahead circuit due to the large diversity in the delays.

HALJ

Arithmetic Unit (Part 2)

5

v This process can be improved by using carry-save addition. W3 X3 Y3 W2 X 2 Y2 W1 X1 Y1 W0 X0 Y 0 FA

FA

FA

FA

FA

FA

FA

Z4

Z3

Z2

Z1

FA

0

Z5

0 Z0

Ø The carry-in inputs are used for the third input and carry-outs are saved for the next level. Ø The inputs to both levels arrive at close intervals, hence, the second level may be improved with the use of a carry-lookahead circuit. v Considering these, a parallel multiplier may be implemented using a tree structure by grouping summands by threes.

Integer Division v Unlike subtraction, division cannot easily be performed using multiplication since it is difficult to take the reciprocal of a number. v Division is performed by repeated subtraction. Ø Loop for each digit of dividend from highest § Determine largest multiplier for divisor § Subtract § Bring down next digit Comments v The size of the quotient is the difference of the sizes (counted from leftmost 1) of the dividend and the divisor. v There is no simple algorithm to implement signed division. Typically, Ø Both dividend and divisor are converted to positive, Ø Unsigned division is performed, and Ø Sign is adjusted accordingly. v Another problem is on how to treat the remainder of a signed division, i.e., whether or not the remainder should be negative if the quotient is negative. Restoring (Unsigned) Division v In restoring division, the multiplier to the divisor is determined by first subtracting the divisor. If the result is negative, the divisor is restored (added back). Ø Initialization § Clear A. Requires 1 extra bit for A to be used as a sign bit. § Q gets dividend. § M gets divisor. Ø Loop for each bit of the dividend Q § Shift AQ to the left. § Subtract (A ← A – M) HALJ

Arithmetic Unit (Part 2)

6

§ If negative (An = 1), restore (A ← A + M) and reset Q0 (← 0) § Else set Q0 (← 1) Ø Quotient in Q while remainder in A. Shift Left Cout

An

A

Q

Q0

Dividend

Add/Sub Cin

M

Control Sequencer

Divisor

Example: 11 ÷ 3 –M M Init Bit 0

Bit 1

Bit 2

Bit 3

11101 00011 A 00000 00001 11110 00001 00010 11111 00010 00101 00010 00101 00010

Rem→ 00010

Q 1011 011– 0110 110– 1100 100– 1001 001– 0011 0011

Shift Sub Restore Shift Sub Restore Shift Sub No Restore Shift Sub No Restore ←Quotient

Non-Restoring (Unsigned) Division v The non-restoring division defers restoration to reduce operations. Ø Addition is performed instead of subtraction in the next step. Ø This requires a final restoration, when last operation yielded a negative remainder. v The same set-up is used. Ø Initialization § Clear A § Q gets dividend. § M gets divisor. Ø Loop for each bit of the dividend Q § If A (previous result) is negative (An = 1) • Shift AQ to the left. • Add (A ← A + M)

HALJ

Arithmetic Unit (Part 2)

7

§

Else • Shift AQ to the left. • Subtract (A ← A – M) § Q 0 ← An Ø Perform restoration if last result in A is negative, i.e., if An = 1 then A ← A + M Ø Quotient in Q while remainder in A. Example: 11 ÷ 3 –M M Init Bit 0

11101 00011 A 00000 00001 11110

Bit 1

11100 11111

Bit 2

11111 00010

Bit 3

00101 00010

Rem→ 00010

Q 1011 011– 0110 110– 1100 100– 1001 001– 0011 0011

Shift Sub Clear Q0 Shift Add Clear Q0 Shift Add Set Q0 Shift Sub Set Q0 ←Quotient

Example: 13 ÷ 3 –M M Init Bit 0

11101 00011 A 00000 00001 11110

Bit 1

11101 00000

Bit 2

00000 11101

Bit 3

11011 11110

Q 1101 101– 1010 010– 0101 101– 1010 010– 0100

00001 Rem→ 00001

HALJ

0100

Shift Sub Clear Q0 Shift Add Set Q0 Shift Sub Clear Q0 Shift Add Set Q0 Restore (Add) ←Quotient

Arithmetic Unit (Part 2)

8

Floating-Point Arithmetic v Real numbers are difficult to represent. This involves a certain amount of approximation with knowledge of a few significant digits at the start of the number, e.g., π ≈ 3.1415926536 c ≈ 299,792,458 v One approach is to use fixed-point representation where the number is given according to a fixed number of decimal places (and precision). Ø Conceals some of what we know for small numbers. Ø Demands more than we know for large numbers. v Scientists and engineers use scientific notation where a number is expressed as M×10E e.g.,

c ≈ 2.998 × 10 8 Avogadro' s Number ≈ 6.0247 × 10 23 Planck' s Constant ≈ 6.6254 × 10 −27 Ø The mantissa M is a signed number and is said to be normalized if 1 ≤ |M| <10. Ø The power of 10 is always an integer and is called the exponent E. Floating-Point Representation v Computers represent real numbers using scientific notation in base 2. ⇒ floating-point (−1) S × M × 2 E Ø The mantissa is also typically normalized (1 ≤ |M| <2) and can be represented as 1 plus a fraction, i.e., M = 1 + F or 1.F

v Common schemes used include the IEEE-754 (Institute of Electrical and Electronics Engineers Standard 754). IEEE Single Precision Representation 31 30

S

23 22

E'

0

F (–1)S×1.F×2E’–127

v Uses 32 bits: 1-bit sign, 23-bit fraction, 8-bit exponent. Ø The fraction is normalized. The smallest fraction is at 2–23 or approximately 1.2×10–7 for 7-digit precision. Ø For ease in comparing numbers, the exponent is biased by 127 to represent negative values (excess-127). Ø Due to some exceptions, the approximate effective range is ±1.17×10–38 to ±3.40×1038.

HALJ

Arithmetic Unit (Part 2)

9

IEEE Double Precision Representation 63 62

S

52 51

E'

0

F (–1)S×1.F×2E’–1023

v Uses 64 bits: 1-bit sign, 52-bit fraction, 11-bit exponent. Ø The fraction is normalized. The smallest fraction is at 2–52 or approximately 2.2×10–16 for 16-digit precision. Ø The exponent is biased by 1023 (excess-1023). Ø Due to some exceptions, the approximate effective range is ±2.23×10±308 to ±1.80×10±308. IEEE-754 Exceptions Single Precision E’ 255 FFH 255 FFH 0 00H 0 00H

Double Precision E’ 2047 7FFH 2047 7FFH 0 000H 0 000H

Fraction F 0 ≠0 0 ≠0

Value ±Infinity NaN, overflow, error etc. 0 Denormalized

Examples: 9.7578125 to IEEE Floating-Point Notation Ø Conversion to IEEE Single-Precision § Determine sign bit ⇒ S = 0 (positive) § Convert to binary ⇒ 1001.11000012 § Shift dot ⇒ 1.00111000012×23 § Determine F ⇒ 00111000010000000000000 (Extended to 23 bits) or 1C2000H § Determine E’ ⇒ E + 127 = 130 = 100000102 = 82H § Combine ⇒ 0 10000010 00111000010000000000000 or grouping by 4’s ⇒ 0100 0001 0001 1100 0010 0000 0000 0000 = 411C 2000H Ø Conversion to IEEE Double-Precision § Differs mainly in E’ ⇒ E + 1023 = 1026 = 100000000102 = 402H § Combining gives ⇒ 0 10000000010 001110000100000000…0 or ⇒ 0100 0000 0010 0011 1000 0100 0000 00…0 ⇒ 4023 8400 0000 0000H Ø NB. It is actually easier to work in hexadecimal. J Guard Bits and Truncation v Guard bits are extra bits in the fraction retained during arithmetic operations to increase accuracy. v Truncation refers to the removal of the guard bits to fit into the representation. v 3 Common Truncation Methods: Chopping, von Neumann Method, Round-Off Chopping Ø Guard bits are dropped regardless of the value. Ø Biased error: 0 to +1 of lsb Von Neumann Method Ø Drop guard bits if all are 0, else set lsb to 1. Ø Unbiased error: –1 to +1 of lsb

HALJ

Arithmetic Unit (Part 2)

10

Round-Off Ø Add 1 to lsb if msb of guard bits is 1, else just chop. Ø Unbiased error: –0.5 to +0.5 of lsb Examples: Mantissa 1.00000 1.0001× 1.0010× 1.0011×

Chopping 1.000 1.000 1.001 1.001

Von Neumann 1.000 1.001 1.001 1.001

Round-off 1.000 1.001 1.001 1.010

Floating-Point Addition/Subtraction v Adjust exponent to largest (Align mantissas). v Add/subtract mantissas. v Normalize mantissa and truncate Floating-Point Multiplication/Division v Add/Subtract exponents v Multiply/divide mantissas v Normalize mantissa and truncate Examples: 10010 − 0.110

= + 1.10012 × 2 6 = − 1.100110011001100110011012 × 2 −4

Ø 100 + (–0.1) § Align mantissa of –0.1 § Add (Subtract) § No need to normalize § Result Ø 100 – (–0.1) § Align mantissa of –0.1 § Subtract (Add) § No need to normalize § Result Ø 100 × (–0.1) § Add exponents § Multiply mantissa § Normalize § Adjust sign § Result Ø 100 ÷ (–0.1) § Subtract exponents § Divide mantissa § Normalize § Adjust sign § Result HALJ

= =

42C8 0000H BDCC CCCDH

⇒ –0.000000000110011001100110011001101×26 ⇒ +1.100011111001100110011001100110011×26 ⇒ 42C7 CCCDH ⇒ –0.000000000110011001100110011001101×26 ⇒ +1.100100000110011001100110011001101×26 ⇒ 42C8 3333H ⇒ 6 + (–4) = 2 ⇒ 10.100000000000000000000000000101 ⇒ 1.0100000000000000000000000000101×23 ⇒ 1 (negative) ⇒ C120 0000H ⇒ 6 – (–4) = 10 ⇒ 0.1111100111111111111111111111110000011000 ⇒ 1.1111001111111111111111110000011000×29 ⇒ 1 (negative) ⇒ C47A 0000H Arithmetic Unit (Part 2)

11