Computer Organization and Architecture

Module 6
Computer Arithmetic

Department of Computer Science and Engineering

IIT Kharagpur
Computer Arithmetic
Introduction

• Computers are built using tiny electronic switches.

• Typically made up of MOS transistors.
• The state of the switches are typically expressed in binary (ON/OFF).

• To design arithmetic circuits for use in computers, we need to work with binary
numbers.
• How to carry out various arithmetic operations in binary?
• How to implement them efficiently in hardware?

3
Addition / Subtraction
 Addition of Two Binary Digits (Bits)

• When two bits A and B are added, a sum (S) and carry (C) are generated as per
the following truth table:

Inputs Outputs 0 + 0 = 00 S = A’.B + A.B’ = A  B

A B S C 0 + 1 = 01 A S C = A.B
1 + 0 = 01 HA
0 0 0 0 1 + 1 = 10 B C
0 1 1 0
1 0 1 0
1 1 0 1 HALF ADDER

5
Addition of Multi-bit Binary Numbers

0010110 Carry 1111110 Carry

0101011 Number A 0111111 Number A

Number B Number B
+ 0001001 + 0000001
Sum S Sum S
0110100 1000000

• At every bit position (stage), we require to add 3 bits:

 1 bit for number A
 1 bit for number B WE NEED A FULL ADDER
 1 carry bit coming from the previous stage

6
 Full Adder
Inputs Outputs A S
B FA
A B Cin S Cout Cin Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0 S = A’.B’.Cin + A’.[Link]’ + A.B’Cin’ + A.B.C
0 1 1 0 1 = A  B  Cin
1 0 0 1 0 Cout = [Link] + [Link] + A.B + [Link]
1 0 1 0 1 = A.B + [Link] + [Link]
1 1 0 0 1
1 1 1 1 1

7
Various Implementations of Full Adder

A A C
HALF OR Cout
B B ADDER S A C
HALF
Cin B ADDER S S

8
• Delay of a full adder:
• Assume that the delay of all basic gates (AND, OR,
NAND, NOR, NOT) is δ
• Delay for Carry = 2δ
• Delay for Sum = 3δ
(AND-OR delay plus one inverter delay)

9
Parallel Adder Design

• We shall look at the various designs of n-bit parallel adder.

a) Ripple carry adder
b) Carry look-ahead adder
c) Carry save adder
d) Carry select adder

10
Ripple Carry Adder

• Cascade n full adders to create a n-bit parallel adder.

• Carry output from stage-i propagates as the carry input to stage-(i+1).
• In the worst-case, carry ripples through all the stages.

1111110 Carry

0111111 Number A
Number B
+ 0000001
Sum S
1000000

11
 An-1 Bn-1 A2 B2 A1 B1 A0 B0

FAn-1
Cn-1
…… C3
FA2
C2
FA1
C1
FA0
C0

Delay for C1 = 2δ
Cn Sn-1 S2 S1 S0 Delay for C2 = 4δ
Delay for Cn-1 = 2(n-1)δ
Delay for Cn = 2nδ
Two numbers: An-1…A2A1A0 and Bn-1…B2B1B0
Input carry: C0
Sum: Sn-1…S2S1S0 Delay for S0 = 3δ
Output carry: Cn Delay for S1 = 2δ + 3δ = 5δ
Delay for S2 = 4δ + 3δ = 7δ
Delay for Sn-1 = 2(n-1)δ + 3δ = (2n+1) δ
Delay is proportional to n

12
 How to Design a Parallel Subtractor?
• Observation:
• Computing A - B is the same as adding the 2’s complement of B to A.
• 2’s complement is equal to 1’s complement plus 1.
• Let Xi = Bi’.

An-1 Xn-1 A2 X2 A1 X1 A0 X0

FAn-1
Cn-1
…… C3
FA2
C2
FA1
C1
FA0
C0 = 1

Cn Sn-1 S2 S1 S0

13
 xor gate is a
controlled inverter
A Parallel Adder/Subtractor
An-1 A1 A0 Bn-1 B1 B0
ADD’ / SUB
… …
xor xor xor

Cn n-bit Parallel Adder C0

Sn-1 S2 S1 S0

14
Delay of a Carry-Ripple Adder

• Simplest design: cascade full adders Ripple-carry adder: n-bit adder built
from full adders.
• Critical path goes from Cin to Cout Delay of ripple-carry adder goes
• Design full adder to have fast carry delay through all carry bits.

A4 B4 A3 B3 A2 B2 A1 B1

Cout Cin
C3 C2 C1
S4 S3 S2 S1
Dealing with the
problem of carry propagation
1. Reduce the carry propagation time.

2. To detect the completion of the carry propagation time.

We have seen some ways to do the former. How do we do the second one?
Motivation
Carry Completion Sensing

A=0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1
B=0 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1
4 1 5 1
Can we compute the average length of carry
chain?
• What is the probability that a chain generated at position i terminates
at j?
• It terminates if both the inputs A[j] and B[j] are zero or 1.
• From i+1 to j-1 the carry has to propagate.
• p=(1/2)j-i
• So, what is the expected length?
• Define a random variable L, which denotes the length of the chain.
Can we compute the average length of carry chain? (Contd.)

• The chain can terminate at j=i+1 to j=k (the MSB position of

the adder)
• Thus L=j-i for a choice of j.
• Thus expected length is:
approximately 2!
k 1

 ( j  i)2
j  i 1
 ( j i )
 ( k  i )2  ( k 1i )

(the carry definitely ends at position k, so we do not

multiply 2  ( k 1i ) with 1/2.)
k 1 i
  l2
l 1
l
 ( k  i )2  ( k 1i )  2  ( k  i  1)2  ( k 1i )  ( k  i )2  ( k 1i )

 2  2 ( k 1i )
p
[Using, l2
l 1
l
 2  ( p  2)2  p ]
Carry Look-ahead Adder

• The propagation delay of an n-bit ripple carry order has been seen to be
proportional to n.
• Due to the rippling effect of carry sequentially from one stage to the next.

• One possible way to speedup the addition.

• Generate the carry signals for the various stages in parallel.
• Time complexity reduces from O(n) to O(1).
• However, hardware complexity increases rapidly with n.

21
• Consider the i-th stage in the addition process.
• We define the carry generate and carry propagate functions as:
Ai Si
Gi = [Link]
Bi FA
Pi = Ai  Bi
Ci Ci+1
• Gi = 1 represents the condition when a carry is generated in
stage-i independent of the other stages.
Ci+1 = Gi + [Link]
• Pi = 1 represents the condition when an input carry Ci will be
propagated to the output carry Ci+1.

22
 Looking into Generate and Propagate

Spot the
difference! G[i ]  A[i ].B[i ] G[i ]  A[i ].B[i ]
P[i ]  A[i ]  B[i ] P[i ]  A[i ]  B[i ]
C[i ]  G[i ]  P[i ].C[i  1] C[i ]  G[i ]  P[i ].C[i  1]
S[i ]  P[i ]  C[i  1] S [i ]  A[i ]  B[i ]  C[i  1]

Is it really different?
Both are correct!

• Because, A[i]=1 and B[i]=1 (which may lead to a difference is

taken care of by the term A[i]B[i])
• How do we make an n bit adder?
• The delay of the adder chain needs to be optimized.
 Unrolling the Recurrence
Ci+1 = Gi + PiCi = Gi + Pi (Gi-1 + Pi-1Ci-1) = Gi + PiGi-1 + PiPi-1Ci-1
= Gi + PiGi-1 + PiPi-1 (Gi-2 + Pi-2Ci-2)
= Gi + PiGi-1 + PiPi-1 Gi-2 + PiPi-1Pi-2Ci-2 = …..

i-1 i i
Ci+1 = Gi +  Gk  Pj + C0  Pj
k=0 j=k+1 j=0

25
 Design of 4-bit CLA Adder
4 AND2 gates
C4 = G3 + G2P3 + G1P2P3 + G0P1P2P3 + C0P0P1P2P3 3 AND3 gates
C3 = G2 + G1P2 + G0P1P2 + C0P0P1P2 2 AND4 gates
1 AND5 gate
C2 = G1 + G0P1 + C0P0P1 1 OR2, 1 OR3, 1 OR4 and
C1 = G0 + C0P0 1 OR5 gate

S0 = A0  B0  C0 = P0  C0
4 XOR2 gates
S1 = P1  C1
S2 = P2  C2
S3 = P3  C3

26
 Design of 4-bit CLA Adder
4 AND2 gates
C4 = G3 + G2P3 + G1P2P3 + G0P1P2P3 + C0P0P1P2P3 3 AND3 gates
2 AND4 gates
C3 = G2 + G1P2 + G0P1P2 + C0P0P1P2
1 AND5 gate
C2 = G1 + G0P1 + C0P0P1 1 OR2, 1 OR3, 1 OR4 and
1 OR5 gate
C1 = G0 + C0P0

S0 = A0  B0  C0 = P0  C0
4 XOR2 gates
S1 = P1  C1
S2 = P2  C2
S3 = P3  C3

27
 Design of 4-bit CLA Adder
4 AND2 gates
C4 = G3 + C3P3 2 AND3 gates
1 AND4 gates
C3 = G2 + G1P2 + G0P1P2 + C0P0P1P2
1 AND5 gate
C2 = G1 + G0P1 + C0P0P1 1 OR2, 1 OR3, 1 OR4 and
1 OR2 gate
C1 = G0 + C0P0

S0 = A0  B0  C0 = P0  C0
4 XOR2 gates
S1 = P1  C1
S2 = P2  C2
S3 = P3  C3

28
 C4
The 4-bit CLA Circuit P3
G3

C3
P2
G2

C2 P1
G1
P0
C1 G0
C0

29
 c4
Four-Bit Carry-Lookahead Adder
p3
g3
Complexity
reduced by
c3
deriving the
carry-out p2

indirectly g2
Full carry lookahead is quite practical
for a 4-bit adder c2 p1

c1 = g0  c0 p0 g1
c2 = g1  g0 p1  c0 p0 p1 p0
c3 = g2  g1 p2  g0 p1 p2  c0 p0 p1 p2 c1
c4 = g3  g2 p3  g1 p2 p3  g0 p1 p2 p3 g0
c0
 c0 p0 p1 p2 p3
Delay for all generate and propagate signals are 1
Four-bit carry network with
full lookahead.
gate delay, followed by another 2 gate delays for
the carry bits (total 3 gate delay). A 4-bit RCA requires 8 gate delay for carry, and 9
Sum bits are another, hence total 4 gate delays. gate delay for sum!
 B3 A3 B2 A2 B1 A1 B0 A0

Gi and Pi Generator 3δ
G3 P3 G2 P2 G1 P1 G0 P0

4-bit Carry Look Ahead Circuit 2δ

C3 C2 C1 C0

xor xor xor xor 3δ

C4
S3 S2 S1 S0

31
 Carry Lookahead Beyond 4 Bits

Consider a 32-bit adder

No circuit sharing:
c1 = g0  c0 p0
Repeated computations
c2 = g1  g0 p1  c0 p0 p1
c3 = g2  g1 p2  g0 p1 p2  c0 p0 p1 p2
.
.
. 32-input AND
c31 = g30  g29 p30  g28 p29 p30  g27 p28 p29 p30  . . .  c0 p0 p1 p2 p3 ... p29 p30

...
High fan-ins necessitate
32-input OR tree-structured circuits
 Solution to the Fan-in Problem
High-radix addition (i.e., radix 2h)
Increases the latency for generating g and p signals and sum digits,
but simplifies the carry network (optimal radix?)

Multilevel lookahead

Example: 16-bit addition

Radix-16 (four digits)
Two-level carry lookahead (four 4-bit blocks)

Either way, the carries c4, c8, and c12 are determined first

c16 c15 c14 c13 c12 c11 c10 c9 c8 c7 c6 c5 c4 c3 c2 c1 c0

cout ? ? ? cin

Apr. 2012 Computer Arithmetic, Addition/Subtraction Slide 33

 16-bit Adder Using 4-bit CLA Modules

A15-A12 B15-B12 A11-A8 B11-B8 A7-A4 B7-B4 A3-A0 B3-B0

4-bit CLA 4-bit CLA 4-bit CLA 4-bit CLA C0

Adder C12 Adder C8 Adder C4 Adder

C16 S15-S12 S11-S8 S7-S4 S3-S0

Problem: Carry propagation between modules still slows down the adder

34
 Carry-Lookahead Adder Design
Block generate and propagate signals

g [i,i+3] = gi+3  gi+2 pi+3  gi+1 pi+2 pi+3  gi pi+1 pi+2 pi+3
p [i,i+3] = pi pi+1 pi+2 pi+3

ci+3 ci+2 ci+1

gi+3 p i+3 gi+2 pi+2 gi+1 pi+1 gi pi

4-bit lookahead carry generator

ci

g[i,i+3] p[i,i+3]

Schematic diagram of a 4-bit lookahead carry generator.

 p [i,i+3]

A Building Block for

Carry-Lookahead Addition g [i,i+3]
pi+3
c4
A 4-bit
lookahead gi+3
carryp3generator Block Signal Generation
g3 Intermediate Carries

c3 ci+3

p2 pi+2
A 4-bit
carry g2 gi+2
network

p1 ci+2 pi+1
c2

g1 gi+1
p0 pi
c1 ci+1
g0 gi
ci
c0
 A Two-Level Carry-Lookahead Adder
c12 c8 c4 c0

c 32 c16 g [12,15] g [8,11] g [4,7] g [0,3]

c48 p [12,15] p [8,11] p [4,7] p [0,3]

4-bit lookahead carry generator

g [48,63] g [32,47] g [16,31] g [0,15] 16-bit

p [48,63] p [32,47] p [16,31] p [0,15] Carry-Lookahead
Adder

4-bit lookahead carry generator

g [0,63]
p [0,63] Building a 64-bit carry-lookahead adder from 16 4-bit
adders and 5 lookahead carry generators.

Apr. 2012 Computer Arithmetic, Addition/Subtraction Slide 41

 A Two-Level Carry-Lookahead Adder
c12 c8 c4 c0

c 32 c16 g [12,15] g [8,11] g [4,7] g [0,3]

c48 p [12,15] p [8,11] p [4,7] p [0,3]

4-bit lookahead carry generator

g [48,63] g [32,47] g [16,31] g [0,15] 16-bit

p [48,63] p [32,47] p [16,31] p [0,15] Carry-Lookahead
Adder

4-bit lookahead carry generator

g [0,63]
p [0,63] Building a 64-bit carry-lookahead adder from 16 4-bit
adders and 5 lookahead carry generators.

Apr. 2012 Computer Arithmetic, Addition/Subtraction Slide 42

Carry Select Adder

• Basically consists of two parallel adders (say, ripple-carry adder) and a

multiplexer.

• For two given numbers A and B, we carry out addition twice:

• With carry-in as 0
• With carry-in as 1

• Once the correct carry-in is known, the correct sum is selected by a multiplexer.

43
 Basic building block of a
carry-select adder, with
block size of 4.

• For a multi-bit adder, the number

of bits in each carry select block
can be either uniform or variable.

44
Uniform sized adder
• A 16-bit carry select adder with a uniform block size of 4 is shown.
• The least significant block needs a single adder (since the carry-in is known).
• Total delay is 4 full adder delays, plus 3 MUX delays.

45
Variable-sized adder
• A 16-bit carry select adder with variable block sizes of 2-2-3-4-5 is shown.
• Total delay is 2 full adder delays, plus 4 MUX delays.

46
Carry Save Adder

• Here we add three operands (say, X, Y and Z) together.

• For adding multiple numbers, we have to construct a tree of carry save adders.
• Used in combinational multiplier design.

• Each carry save adder is simply an independent full adder without carry
propagation.
• A parallel adder is required only at the last stage.

47
• An illustrative example: X: 10011
Y: + 11001
X: 10011 X: 10011 Z: + 01011
Y: + 11001 Y: + 11001 S: 00001
Z: + 01011 Z: + 01011 C: 11011
C: 11011 S: 00001 Sum: 110111

A set of full adders generate carry The sum and carry vectors are
and sum bits in parallel added later (with proper shifting)

48
An n-bit Carry Save Adder
Xn-1 Yn-1 Zn-1 X2 Y 2 Z2 X1 Y 1 Z1 X0 Y 0 Z0

Full …. Full Full Full

Adder Adder Adder Adder

Cn-1 Sn-1 C2 S2 C1 S1 C0 S0

The carry input of the full adder is used as the third

input

49
Adding m Numbers: Some
Examples CSA CSA

CSA
CSA

CSA CSA
CSA

Parallel Adder Parallel Adder

Parallel Adder

m=3 m=4 m=6

50
Generating the Status Flags

• Many contemporary processors have a flag register that contains the status of
the last arithmetic / logic operation.
• Zero (Z): tells whether the result is zero.
• Can be used for both arithmetic and logic operations.
• Sign (S): tells whether the result is positive (=0) or negative (=1).
• Can be used for both arithmetic and logic operations.
• Carry (C): tells whether there has been a carry out of the most significant stage.
• Used only for arithmetic operations.
• Overflow (V): tells whether the result is too large to fit in the target register.
• Used only for arithmetic operations (addition and subtraction).

51
 Fn-1 F1 F0
A B F
… Carry out
…
NOR
C Flag
ALU

Z Flag • Overflow can occur during addition

when the sign of the two operands are
F
the same.
F
• Sign of the result becomes different from
Assume A, B and
Fn-1 … the sign of the operand(s).
F are n-bit V = [Link]-1’ + An-1’.Bn-1’.Fn-1
registers S Flag
V = Fn-1  Carry_out

52
• The MIPS32 processor does not have any status flags.
• Why?
• MIPS ISA is designed for efficient pipeline implementation.
• Several instructions can be in various stages of execution in the pipeline.
• Flag registers result in side effects among instructions.
• MIPS stores information about the flags temporarily in a GPR.

slt $t0, $s1, $s2

beq $t0, $zero, Label

53
Multiplication
 Multiplication of Unsigned Numbers
• Multiplication requires substantially more 1 0 1 0 Multiplicand M (10)
hardware than addition. 1 1 0 1 Multiplier Q (13)
• Multiplication of two n-bit number --------
1 0 1 0
generates a 2n-bit product.
0 0 0 0
• We can use shift-and-add method. 1 0 1 0
• Repeated additions of shifted versions of the 1 0 1 0
multiplicand. ---------------
1 0 0 0 0 0 1 0 Product P (130)

55
 A General Case
A3 A2 A1 A0
• Each [Link] is called a partial
B3 B2 B1 B0
product.
----------------------
• Generating the partial
A3B0 A2B0 A1B0 A0B0
products is easy.
A3B1 A2B1 A1B1 A0B1
• Requires just an AND gate for
A3B2 A2B2 A1B2 A0B2 each partial product.
A3B3 A2B3 A1B3 A0B3 • Adding all the n-bit partial
------------------------------------- products in hardware is more
difficult.

56
Design of a Combinational Array Multiplier

• We can directly map the multiplication process as

discussed to hardware.
• We use an array of cells to generate the partial products.
• Instead of adding the partial products at the end, we add the
partial products at every stage of the multiplication.

• The required multiplication cell is as shown.

Full Adder
• Combines capabilities of partial product generation and also
addition of partial products.

57
• Extremely inefficient, and Multiplicand

requires very large amount (PP0)

0 m3 0 m2 0 m1 0 m0

of hardware. q0
0
• Requires n2 multiplication PP1 p0
q1
cells for an n x n multiplier. 0

• Advantage is that it is very PP2

q2
p1

fast. 0
PP3 p2
q3
0
,
p7 p6 p5 p4 p3

Product: p7 p6 p5 p4 p3 p2 p1 p0

58
Unsigned Sequential Multiplication

• Requires much less hardware, but requires several clock cycles to perform
multiplication of two n-bit numbers.
• Typical hardware complexity: O(n)
• Typical time complexity: O(n)

• In the “hand multiplication” that we have seen:

• If the i-th bit of the multiplier is 1, the multiplicand is shifted left by i bit positions, and added
to the partial product.
• The relative position of the partial products do not change; it is the multiplicand that gets
shifted left.

59
• In the “shift-and-add” multiplication that we discuss now, we make the following
modifications.
• We do not shift the multiplicand (i.e., keep its position fixed).
• We right shift an 2n-bit partial product at every step.

60
 START

A = 0; C = 0; M: n-bit multiplicand
COUNT = n;
M = multiplicand; Q: n-bit multiplier
Q = multiplier;
A: n-bit temporary register
0 1
Q0
C: 1-bit carry out from adder
A=A+0 A=A+M

Logical Shift Right (C, A, Q )

COUNT = COUNT – 1;

COUNT = 0? STOP

61
 C A Q
Example 1: (10) x (13)
0 0 0 0 0 0 0 1 1 0 1 Initialization
Assume 5-bit numbers.
0 0 1 0 1 0 0 1 1 0 1 A = A + M Step 1
M: (0 1 0 1 0)2 0 0 0 1 0 1 0 0 1 1 0 Shift
Q: (0 1 1 0 1)2 0 0 0 1 0 1 0 0 1 1 0 A = A + 0 Step 2
0 0 0 0 1 0 1 0 0 1 1 Shift
Product = 130
= (0 0 1 0 0 0 0 0 1 0)2 0 0 1 1 0 0 1 0 0 1 1 A = A + M Step 3
0 0 0 1 1 0 0 1 0 0 1 Shift
0 1 0 0 0 0 0 1 0 0 1 A = A + M Step 4
0 0 1 0 0 0 0 0 1 0 0 Shift
0 0 1 0 0 0 0 0 1 0 0 A = A + 0 Step 5
0 0 0 1 0 0 0 0 0 1 0 Shift

62
 C A Q
Example 2: (29) x (21)
0 0 0 0 0 0 1 0 1 0 1 Initialization
Assume 5-bit numbers.
0 1 1 1 0 1 1 0 1 0 1 A = A + M Step 1
M: (1 1 1 0 1)2 0 0 1 1 1 0 1 1 0 1 0 Shift
Q: (1 0 1 0 1)2 0 0 1 1 1 0 1 1 0 1 0 A = A + 0 Step 2
0 0 0 1 1 1 0 1 1 0 1 Shift
Product = 609
= (1 0 0 1 1 0 0 0 0 1)2 1 0 0 1 0 0 0 1 1 0 1 A = A + M Step 3
0 1 0 0 1 0 0 0 1 1 0 Shift
0 1 0 0 1 0 0 0 1 1 0 A = A + 0 Step 4
0 0 1 0 0 1 0 0 0 1 1 Shift
1 0 0 1 1 0 0 0 0 1 1 A = A + M Step 5
0 1 0 0 1 1 0 0 0 0 1 Shift

63
Data Path for Shift-and-Add Multiplier

C A Q Q0

Carry
out n-bit registers
ADDER

M Control Unit ..
.
MUX

64
 Signed Multiplication
• We can extend the basic shift-and-add multiplication method to handle signed numbers.
• One important difference:
• Require to sign-extend all the partial products before they are added.
• Recall that for 2’s complement representation, sign extension can be done by replicating the sign bit
any number of times.

0101 = 0000 0101 = 0000 0000 0000 0101 = 0000 0000 0000 0000 0000 0000 0000 0101

1011 = 1111 1011 = 1111 1111 1111 1011 = 1111 1111 1111 1111 1111 1111 1111 1011

65
An Example: 6-bit 2’s 1 1 0 1 0 1 (-11)
complement multiplication X 0 1 1 0 1 0 (+26)
-------------------------
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 1 0 1
Note: For n-bit multiplication, 0 0 0 0 0 0 0 0 0 0
since we are generating a 2n- 1 1 1 1 1 0 1 0 1
bit product, overflow can never 1 1 1 1 0 1 0 1
occur.
0 0 0 0 0 0 0
-------------------------
1 1 1 0 1 1 1 0 0 0 1 0 (-286)

66
Booth’s Algorithm for Signed Multiplication

• In the conventional shift-and-add multiplication as discussed, for n-bit multiplication,

we iterate n times.
• Add either 0 or the multiplicand to the 2n-bit partial product (depending on the next bit of the
multiplier).
• Shift the 2n-bit partial product to the right.

• Essentially we need n additions and n shift operations.

• Booth’s algorithm is an improvement whereby we can avoid the additions whenever

consecutive 0’s or 1’s are detected in the multiplier.
• Makes the process faster.

67
 Basic Idea Behind Booth’s Algorithm
• We inspect two bits of the multiplier (Qi, Qi-1) at a time.
• If the bits are same (00 or 11), we only shift the partial product.
• If the bits are 01, we do an addition and then shift.
• If the bits are 10, we do a subtraction and then shift.

• Significantly reduces the number of additions / subtractions.

• Inspecting bit pairs as mentioned can also be expressed in terms of Booth’s Encoding.
• Use the symbols +1, -1 and 0 to indicate changes w.r.t. Qi and Qi-1.
• 01  +1, 10  -1, 00 or 11  0.
• For encoding the least significant bit Q0, we assume Q -1 = 0.

68
• Examples of Booth encoding:
a) 0 1 1 1 0 0 0 0 :: +1 0 0 -1 0 0 0 0
b) 0 1 1 1 0 1 1 0 :: +1 0 0 -1 +1 0 -1 0
c) 0 0 0 0 0 1 1 1 :: 0 0 0 0 +1 0 0 -1
d) 0 1 0 1 0 1 0 1 :: +1 -1 +1 -1 +1 -1 +1 -1

• The last example illustrates the worst case for Booth’s multiplication (alternating 0’s
and 1’s in multiplier).
• In the illustrations, we shall show the two multiplier bits explicitly instead of showing the
encoded digits.

69
 START

A = 0; Q -1 = 0; M: n-bit multiplicand
COUNT = n;
M = multiplicand; Q: n-bit multiplier
Q = multiplier;
A: n-bit temporary register
01 10
Q0Q -1
Q -1: 1-bit flip-flop
A=A+M 00 or A=A–M
11
Arithmetic Shift Right (A, Q , Q -1) Skips over consecutive 0’s
COUNT = COUNT – 1; and 1’s of the multiplier Q

COUNT = 0? STOP

70
 A Q Q -1
Example 1: (-10) x (13)
0 0 0 0 0 0 1 1 0 1 0 Initialization
Assume 5-bit numbers.
0 1 0 1 0 0 1 1 0 1 0 A = A - M Step 1
M: (1 0 1 1 0)2 0 0 1 0 1 0 0 1 1 0 1 Shift
-M: (0 1 0 1 0)2 1 1 0 1 1 0 0 1 1 0 1 A = A + M Step 2
Q: (0 1 1 0 1)2 1 1 1 0 1 1 0 0 1 1 0 Shift
Product = -130 0 0 1 1 1 1 0 0 1 1 0 A = A - M Step 3
= (1 1 0 1 1 1 1 1 1 0)2 0 0 0 1 1 1 1 0 0 1 1 Shift

0 0 0 0 1 1 1 1 1 0 1 Shift Step 4

1 0 1 1 1 1 1 1 0 0 1 A = A + M
Step 5
1 1 0 1 1 1 1 1 1 0 0 Shift

71
 A Q Q -1
Example 2:
0 0 0 0 0 0 0 1 1 1 0 0 0 Initialization
(-31) x (28)
0 0 0 0 0 0 0 0 1 1 1 0 0 Shift Step 1
Assume 6-bit
numbers. 0 0 0 0 0 0 0 0 0 1 1 1 0 Shift Step 2

M: (1 0 0 0 0 1)2 0 1 1 1 1 1 0 0 0 1 1 1 0 A = A - M Step 3
-M: (0 1 1 1 1 1)2 0 0 1 1 1 1 1 0 0 0 1 1 1 Shift
Q: (0 1 1 1 0 0)2
0 0 0 1 1 1 1 1 0 0 0 1 1 Shift Step 4
Product = -868 0 0 0 0 1 1 1 1 1 0 0 0 1 Shift Step 5
= (1 1 0 0 1 0
0 1 1 1 0 0)2 1 0 0 1 0 0 1 1 1 0 0 0 1 A = A + M Step 6
1 1 0 0 1 0 0 1 1 1 0 0 0 Shift

72
Arithmetic Data Path for Booth’s Algorithm
shift right

An-1 A Q Q0 Q- -1

n-bit registers
SUBTRACT
ADD /

Control Unit ..
M .
Add / Subtract

73
Design of Fast Multiplier

a) Bit-Pair Recoding of Booth’s Multiplication

• A technique that halves the maximum number of summands; derived directly from the
Booth’s algorithm.
• If we group the Booth-coded multiplier digits in pairs, we observe:
• (+1, -1): (+1, -1) * M = 2 * M – M = M
• (0, +1): (0, +1) * M = M
• We need a single addition instead of a pair of addition & subtraction.
• Other similar rules can be framed.
• Shown on next slide.

74
Original Booth-coded Pair Equivalent Recoded Pair
(+1, 0) (0, +2) • Every equivalent recoded pair
has at least one 0.
(-1, +1) (0, -1) • Worst-case number of
(0, 0) (0, 0) additions or subtractions is
50% of the number of
(0, 1) (0, 1) multiplier bits.
(+1, 1) -- • Reduces the worst-case time
required for multiplication.
(+1, -1) (0, +1)
(-1, 0) (0, -2)

75
Example: (+13) X (-22) in 6-bits.

Original: Multiplier -- 1 0 1 0 1 0
Booth: Multiplier -- -1 +1 -1 +1 -1 0
Recoded: Multiplier -- 0 -1 0 -1 0 -2

0 0 1 1 0 1
. -1 . -1 . -2
• M = 0 0 1 1 0 1 (+13)
--------------------------
1 1 1 1 1 1 1 0 0 1 1 0
• -1 * M = 1 1 0 0 1 1
1 1 1 1 1 1 0 0 1 1 • -2 * M = 1 0 0 1 1 0
1 1 1 1 0 0 1 1
--------------------------
1 1 0 1 1 1 1 0 0 0 1 0

76
b) Carry Save Multiplier
• We have seen earlier how carry save adders (CSA) can be used to add several numbers with
carry propagation only in the last stage.
• The partial products can be generated in parallel using n2 AND gates.
• The n partial products can then be added using a CSA tree.
• Instead of letting the carries ripple through during addition, we save them and feed it to the
next row, at the correct weight positions.

77
4 x 4 Carry
Save
Multiplier

p7 p6 p5 p4 p3 p2 p1 p0

78
• Wallace Tree Multiplier
• A Wallace tree is a circuit that reduces the problem of summing n n-bit numbers to the problem
of summing two Θ(n)-bit numbers.
• It uses n/3 (floor of) carry-save adders in parallel to convert the sum of n numbers to the sum of
2n/3 (ceiling of) numbers.
• It then recursively constructs a Wallace tree on the 2n/3 (ceiling of) resulting numbers.
• The set of numbers is progressively reduced until there are only two numbers left.
• By performing many carry-save additions in parallel, Wallace trees allow two n-bit numbers to be
multiplied in Θ(log2 n) time using a circuit of size Θ(n2).

79
 m(0) m(1) m(2) m(3) m(4) m(5) m(6) m(7)
8 9 10 11 12 13 14 15
• The figure shows a Wallace tree that adds 8
CSA CSA
partial products m(0), m(1), …, m(7).
• The partial product m(i) consists of (n + i) 10 10 13 13
bits.
CSA CSA
• Each line represents an entire number – 13 15
13
the label of an edge indicates the number
of bits. CSA 15
• The carry-lookahead adder at the bottom 15 15
adds a (2n-1)-bit number to a 2n-bit
number to give the 2n-bit product. CSA
15 15
Parallel Adder
Product 16

80
Division
Introduction

Instruction Latency Cycles /

• Division is more complex than
Issue
multiplication.
Load / Store 3 1
• Example: Typical values in
Pentium-3 processor  Integer Multiply 4 1

• Not easy to construct high-speed Integer Divide 36 36

dividers.
Floating-point Add 3 1
• The ratios have not changed
Floating-point Multiply 5 2
much in later processors.
Floating-point Divide 38 38

82
• Latency:
• Minimum delay after which the first result is obtained, starting from the time when the first set of
inputs is applied.

• Cycles/Issue:
• Whenever a new set of inputs is applied to a functional unit (e.g. adder), it is called an issue.
• Pipelined implementation of arithmetic unit reduces the number of clock cycles between successive
issues.
• For non-pipelined arithmetic units (e.g. divider), the number of clock cycles between successive
issues is much higher.
• Next input can be applied only after the previous operation is complete.

83
The Process of Integer Division

• In integer division, a divisor M and a dividend D are given.

• The objective is to find a third number Q, called the quotient, such that
D = Q x M + R
where R is the remainder such that 0 ≤ R < M.

• The relationship D = Q x M suggests that there is a close correspondence

between division and multiplication.
• Dividend, quotient and divisor correspond to product, multiplicand and multiplier,
respectively.
• Similar algorithms and circuits can be used for multiplication and division.

84
 • One of the simplest division methods is the sequential digit-by-digit algorithm similar to that
used in pencil-and-paper methods.
0 1 1 0 Quotient Q = Q0Q1Q2Q3
Divisor M 1 1 0 1 0 0 1 0 1 Dividend D = R0
1 1 0 Q0.M (Does not go; Q0 = 0)
-------------
1 0 0 1 0 1 R1
D = 37 = (1 0 0 1 0 1)2 - 1 1 0 Q1.2-1.M (Does go; Q1 = 1)
M = 6 = (1 1 0)2 -------------
0 1 1 0 1 R2
Quotient Q = 6
- 1 1 0 Q2.2-2.M (Does go; Q2 = 1)
Remainder R = 1
-------------
0 0 0 1 R3
1 1 0 Q3.2-3.M (Does not go; Q3 = 0)
-------------
0 0 1 R4 = Remainder R

85
• In the example, the quotient Q = Q0Q1Q2… is computed one bit at a time.
• At each step i, the divisor shifted i bits to the right (i.e. 2-i.M) is compared with the current partial
remainder Ri.
• The quotient bit Qi is set to 0 (1) if 2-i.M is greater than (less than) Ri .
• The new partial remainder Ri+1 is computed as:
Ri+1 = Ri - Qi.2-i.M

86
• Machine implementation:
• For hardware implementation, it is more convenient to shift the partial remainder to the left
relative to a fixed divisor; thus
Ri+1 = 2Ri - Qi.M (instead of Ri+1 = Ri - Qi.2-i.M)
• The final partial remainder is the required remainder shifted to the left, so that R = 2-3.R4
(see next slide).

87
 Divisor M Quotient Q
1 1 0 1 0 0 1 0 1 Dividend = 2R0
1 1 0 Q0.M 0
Do not ---------------
subtract 1 0 0 1 0 1 R1
1 0 0 1 0 1 0 2R1
1 1 0 Q1.M 0 1
D = 37 = (1 0 0 1 0 1)2 ---------------
0 1 1 0 1 0 R2
M = 6 = (1 1 0)2
0 1 1 0 1 0 0 2R2
Quotient Q = 6 1 1 0 Q2.M 0 1 1
Remainder R = 1 ---------------
0 0 0 1 0 0 R3
0 0 0 1 0 0 0 2R3
1 1 0 Q3.M 0 1 1 0
---------------
0 0 1 0 0 0 R4 = 23.R

88
Two alternatives to division

• We shall discuss two approaches:

a) Restoring division
b) Non-restoring division
(a) Restoring Division: The Data Path

Next quotient bit

An A Dividend Q Q0

Q and M are n-bit registers

A is an (n+1)-bit register
SUBTRACT
ADD /

Control Unit ..
Divisor M .
Add / Subtract

90
Basic Steps (Restoring Division)
Repeat the following steps n times:
a) Shift the dividend left one bit at a time into register A.
b) Subtract the divisor M from this register A (trial subtraction).
c) If the result is negative (i.e. not going):
• Add the divisor M back into the register A (i.e. restoring back).
• Record 0 as the next quotient bit.
d) If the result is positive:
A Q
• Do not restore the intermediate result.
• Record 1 as the next quotient bit.
M

91
 START
Restoring Division
A = 0; M = divisor; • Quotient in Q
Q = dividend; COUNT = n • Remainder in A

Shift left A, Q

A Q
A=A–M Trial subtraction

No Yes M
A –ve ?
Q0=1 Q0=0
A=A+M Restoration No
Yes
COUNT = COUNT – 1 COUNT = 0? STOP

92
• Analysis:
• For n-bit divisor and n-bit dividend, we iterate n times.
• Number of trial subtractions: n
• Number of restoring additions: n/2 on the average
• Best case: 0
• Worst case: n

93
 A Simple Example: 8/3 for 4-bit representation (n=4)
Initially: 0 0 0 0 0 1 0 0 0 Shift: 0 0 1 0 0 0 0 0 –
Subtract: 0 0 1 1
Shift: 0 0 0 0 1 0 0 0 – Set Q0: 0 0 0 0 1
Subtract: 0 0 1 1 0 0 0 0 0 0 0 0 1
Set Q0: 1 1 1 1 0 Shift: 0 0 0 1 0 0 0 1 -
Restore: 0 0 1 1 Subtract: 0 0 1 1
0 0 0 0 1 0 0 0 0 Set Q0: 1 1 1 1 1
Shift: 0 0 0 1 0 0 0 0 – Restore: 0 0 1 1
Subtract: 0 0 1 1 0 0 0 1 0 0 0 1 0
Set Q0: 1 1 1 1 1
Remainder Quotient
Restore: 0 0 1 1
00010 = 2 0010 = 2
0 0 0 1 0 0 0 0 0

94
(b) Non-Restoring Division A Q

• The performance of restoring division algorithm can be improved by exploiting

the following observation.
• In restoring division, what we do actually is: Shift left means
• If A is positive, we shift it left and subtract M.
multiplying by 2.
• That is, we compute 2A – M.
• If A is negative, we restore is by doing A + M, shift it left, and then subtract M.
• That is, we compute 2(A + M) – M = 2A + M.

• We can accordingly modify the basic division algorithm by eliminating the

restoring step  NON-RESTORING DIVISION.

95
• Basic steps in non-restoring division:
a) Start by initializing register A to 0, and repeat steps (b)-(d) n times.
b) If the value in register A is positive,
• Shift A and Q left by one bit position.
• Subtract M from A.
c) If the value in register A is negative,
• Shift A and Q left by one bit position.
• Add M to A.
d) If A is positive, set Q0 = 1; else, set Q0 = 0.
e) If A is negative, add M to A as a final corrective step.

96 96
 START

Non-Restoring Division A Q
A = 0; M = divisor;
Q = dividend; COUNT = n M

No A -ve ? Yes No
Shift left A, Q Shift left A, Q COUNT = 0?
A=A–M A=A+M
Yes
No
No Yes A<0?
Q0 = 1 A -ve ? Q0 = 0
Yes

COUNT = COUNT – 1 A=A+M STOP

Correction

97
 A Simple Example: 8/3 for n=4
Initially: 0 0 0 0 0 1 0 0 0 Shift: 0 0 0 1 0 0 0 1 –
Subtract: - 0 0 1 1
Shift: 0 0 0 0 1 0 0 0 – Set Q0: 1 1 1 1 1 0 0 1 0
Subtract: - 0 0 1 1 Correction Add: Quotient
Set Q0: 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0010 = 2
Shift: 1 1 1 0 0 0 0 0 – 0 0 0 1 1
0 0 0 1 0
Add: 0 0 1 1
Set Q0: 1 1 1 1 1 0 0 0 0 Remainder
00010 = 2
Shift: 1 1 1 1 0 0 0 0 –
Add: 0 0 1 1
Set Q0: 0 0 0 0 1 0 0 0 1

98
Data Path for Non-Restoring Division

Next quotient bit

An A Q Q0

Q and M are n-bit registers

A is an (n+1)-bit register
SUBTRACT
ADD /

Control Unit ..
M .
Add / Subtract

99
High Speed Dividers

• Some of the methods used to increase the speed of multiplication can also be
modified to speed up division.
• High-speed addition and subtraction.
• High-speed shifting.
• Combinational array divider (implementing restoring division).

• The main difficulty is that it is very difficult to implement division in a pipeline to

improve the performance.
• Unlike multiplication, where carry-save Wallace tree multipliers can be used for pipeline
implementation.

100
Floating-Point Numbers
Representing Fractional Numbers

• A binary number with fractional part

B = bn-1 bn-2 …..b1 b0 . b-1 b-2 ….. b-m
corresponds to the decimal number If the radix point is allowed to
n-1 move, we call it a floating-point
D =  b i 2i
i = -m representation.

• Also called fixed-point numbers.

• The position of the radix point is fixed.

102
 Some Examples
1011.1  1x23 + 0x22 + 1x21 + 1x20 + 1x2-1 = 11.5
101.11  1x22 + 0x21 + 1x20 + 1x2-1 + 1x2-2 = 5.75
10.111  1x21 + 0x20 + 1x2-1 + 1x2-2 + 1x2-3 = 2.875

Some Observations:
• Shift right by 1 bit means divide by 2
• Shift left by 1 bit means multiply by 2
• Numbers of the form 0.111111…2 has a value less than 1.0 (one).

103
 Limitations of Representation

• In the fractional part, we can only represent numbers of the form x/2k exactly.
• Other numbers have repeating bit representations (i.e. never converge).
• Examples:
3/4 = 0.11
7/8 = 0.111 • More the number of bits, more
5/8 = 0.101 accurate is the representation.
1/3 = 0.10101010101 [01] …. • We sometimes see: (1/3)*3 ≠ 1.
1/5 = 0.001100110011 [0011] ….
1/10 = 0.0001100110011 [0011] ….

104
Floating-Point Number Representation (IEEE-754)

• For representing numbers with fractional parts, we can assume that the fractional point
is somewhere in between the number (say, n bits in integer part, m bits in fraction
part).  Fixed-point representation
• Lacks flexibility.
• Cannot be used to represent very small or very large numbers
(for example: 2.53 x 10-26, 1.7562 x 10+35, etc.).

• Solution :: use floating-point number representation.

• A number F is represented as a triplet <s, M, E> such that
F = (-1)s M x 2E

105
F = (-1)s M x 2E
• s is the sign bit indicating whether the number is negative (=1) or positive (=0).
• M is called the mantissa, and is normally a fraction in the range [1.0,2.0].
• E is called the exponent, which weights the number by power of 2.

Encoding:
• Single-precision numbers: total 32 bits, E 8 bits, M 23 bits
• Double-precision numbers: total 64 bits, E 11 bits, M 52 bits

s E M

106
 Points to Note
• The number of significant digits depends on the number of bits in M.
• 7 significant digits for 24-bit mantissa (23 bits + 1 implied bit).
• The range of the number depends on the number of bits in E.
• 1038 to 1038 for 8-bit exponent.

How many significant digits? Range of exponent?

224 = 10x 2127 = 10y
24 log102 = x log1010 127 log102 = y log1010
x = 7.2  7 significant decimal places y = 38.1  maximum exponent value
38 (in decimal)

107
 “Normalized” Representation
• We shall now see how E and M are actually encoded.
• Assume that the actual exponent of the number is EXP
(i.e. number is M x 2EXP).
• Permissible range of E: 1 ≤ E ≤ 254 (the all-0 and all-1 patterns are not allowed).
• Encoding of the exponent E:
The exponent is encoded as a biased value: E = EXP + BIAS
where BIAS = 127 (28-1 – 1) for single-precision, and
BIAS = 1023 (211-1 – 1) for double-precision.

108
• Encoding of the mantissa M:
• The mantissa is coded with an implied leading 1 (i.e. in 24 bits).
M = 1 . xxxx...x
• Here, xxxx…x denotes the bits that are actually stored for the mantissa. We get the extra
leading bit for free.
• When xxxx…x = 0000…0, M is minimum (= 1.0).
• When xxxx…x = 1111…1, M is maximum (= 2.0 – ε).

109
An Encoding Example

• Consider the number F = 15335

1533510 = 111011111001112 = 1.1101111100111 x 213

• Mantissa will be stored as: M = 1101111100111 00000000002

• Here, EXP = 13, BIAS = 127.  E = 13 + 127 = 140 = 100011002

0 10001100 11011111001110000000000 466F9C00 in hex

110
Another Encoding Example

• Consider the number F = -3.75

-3.7510 = -11.112 = -1.111 x 21

• Mantissa will be stored as: M = 111000000000000000000002

• Here, EXP = 1, BIAS = 127.  E = 1 + 127 = 128 = 100000002

1 10000000 11100000000000000000000 C0700000 in hex

111
 Special Values Zero is represented by the
all-zero string.
• When E = 000…0
Also referred to as de-
• M = 000…0 represents the value 0.
normalized numbers.
• M ≠ 000…0 represents numbers very close to 0.

• When E = 111…1
• M = 000…0 represents the value ∞ (infinity).
NaN represents cases
when no numeric value
• M ≠ 000…0 represents Not-a-Number (NaN).
can be determined, like
uninitialized values, ∞*0,
∞-∞, square root of a
negative number, etc.

112
 Summary of Number Encodings
 -Normalized -Denorm +Denorm +Normalized +

NaN 0 +0 NaN

Denormal numbers have very small magnitudes (close to 0) such that trying to
normalize them will lead to an exponent that is below the minimum possible value.
• Mantissa with leading 0’s and exponent field equal to zero.
• Number of significant digits gets reduced in the process.

113
 Rounding
• Suppose we are adding two numbers (say, in single-precision).
• We add the mantissa values after shifting one of them right for exponent alignment.
• We take the first 23 bits of the sum, and discard the residue R (remaining bits).

• IEEE-754 format supports four rounding modes:

a) Truncation
b) Round to +∞ (similar to ceiling function)
c) Round to -∞ (similar to floor function)
d) Round to nearest

114
• To implement rounding, two temporary bits are maintained:
• Round Bit (r): This is equal to the MSB of the residue R.
• Sticky Bit (s): This the logical OR of the rest of the bits of the residue R.

• Decisions regarding rounding can be taken based on these bits:

a) R > 0: if r + s = 1
b) R = 0.5: if r.s’ = 1
c) R > 0.5: if r.s = 1 // ‘+’ is logical OR, ‘.’ is logical AND

• Renormalization after Rounding:

• If the process of rounding generates a result that is not in normalized form, then we need to re-
normalize the result.

115
Some Exercises

Decode the following single-precision floating-point numbers.

a) 0011 1111 1000 0000 0000 0000 0000 0000
b) 0100 0000 0110 0000 0000 0000 0000 0000
c) 0100 1111 1101 0000 0000 0000 0000 0000
d) 1000 0000 0000 0000 0000 0000 0000 0000
e) 0111 1111 1000 0000 0000 0000 0000 0000
f) 0111 1111 1101 0101 0101 0101 0101 0101

116
Floating-Point Arithmetic
 Floating Point Addition/Subtraction
• Two numbers: M1 x 2E1 and M2 x 2E2 , where E1 > E2 (say).
• Basic steps:
• Select the number with the smaller exponent (i.e. E2) and shift its mantissa right by (E1-E2) positions.
• Set the exponent of the result equal to the larger exponent (i.e. E1).
• Carry out M1 ± M2, and determine the sign of the result.
• Normalize the resulting value, if necessary.

118
 Addition Example
• Suppose we want to add F1 = 270.75 and F2 = 2.375
F1 = (270.75)10 = (100001110.11)2 = 1.0000111011 x 28
F2 = (2.375)10 = (10.011)2 = 1.0011 x 21
• Shift the mantissa of F2 right by 8 – 1 = 7 positions, and add:
1000 0111 0110 0000 0000 0000
1 0011 0000 0000 0000 0000 000
1000 1000 1001 0000 0000 0000 0000 000

• Result: 1.00010001001 x 28
Residue

119
 Subtraction Example
• Suppose we want to subtract F2 = 224 from F1 = 270.75
F1 = (270.75)10 = (100001110.11)2 = 1.0000111011 x 28
F2 = (224)10 = (11100000)2 = 1.111 x 27
• Shift the mantissa of F2 right by 8 – 7 = 1 position, and subtract:
1000 0111 0110 0000 0000 0000
111 0000 0000 0000 0000 0000 000
0001 0111 0110 0000 0000 0000 000
• For normalization, shift mantissa left 3 positions, and decrement E by 3.
• Result: 1.01110110 x 25

120
121
Floating-Point Multiplication

• Two numbers: M1 x 2E1 and M2 x 2E2

• Basic steps:
• Add the exponents E1 and E2 and subtract the BIAS.
• Multiply M1 and M2 and determine the sign of the result.
• Normalize the resulting value, if necessary.

122
Multiplication Example

• Suppose we want to multiply F1 = 270.75 and F2 = -2.375

F1 = (270.75)10 = (100001110.11)2 = 1.0000111011 x 28
F2 = (-2.375)10 = (-10.011)2 = -1.0011 x 21

• Add the exponents: 8 + 1 = 9

• Multiply the mantissas: 1.01000001100001
• Result: - 1.01000001100001 x 29

123
 s1 E1 M1 s2 E2 M2
23
8 23
1 1
8
8-bit Adder 24 x 24 Multiplier

9 1111111

s1 s2 48
9-bit Subtractor

8
XOR

Normalizer
8 23
s3 E3 M3

124
Floating-Point Division

• Two numbers: M1 x 2E1 and M2 x 2E2

• Basic steps:
• Subtract the exponents E1 and E2 and add the BIAS.
• Divide M1 by M2 and determine the sign of the result.
• Normalize the resulting value, if necessary.

125
Division Example

• Suppose we want to divide F1 = 270.75 by F2 = -2.375

F1 = (270.75)10 = (100001110.11)2 = 1.0000111011 x 28
F2 = (-2.375)10 = (-10.011)2 = -1.0011 x 21

• Subtract the exponents: 8 – 1 = 7

• Divide the mantissas: 0.1110010
• Result: - 0.1110010 x 27
• After normalization: - 1.110010 x 26

126
 s1 E1 M1 s2 E2 M2
23
8 23
1 1
8
8-bit Subtractor 24-bit Divider
9 1111111

s1 s2 48
9-bit Adder

8
XOR

Normalizer
8 23
s3 E3 M3

127
FLOATING-POINT ARITHMETIC in MIPS32

128
• The MIPS32 architecture defines the following floating-point registers (FPRs).
• 32 32-bit floating-point registers F0 to F31, each of which is capable of storing a single-
precision floating-point number.
• Double-precision floating-point numbers can be stored in even-odd pairs of FPRs (e.g.,
(F0,F1), (F10,F11), etc.).

• In addition, there are five special-purpose FPU control registers.

129
 F0
F1 FIR
F2 FCCR

F3 FEXR
F4 FENR
FPRs
F5 FCSR
..
. Special-purpose
Registers
F30
F31

130
Typical Floating Point Instructions in MIPS32

• Load and Store instructions

• Load Word from memory
• Load Double-word from memory
• Store Word to memory
• Store Double-word to memory

• Data Movement instructions

• Move data between integer registers and floating-point registers
• Move data between integer registers and floating-point control registers

131
• Arithmetic instructions
• Floating-point absolute value
• Floating-point compare
• Floating-point negate
• Floating-point add
• Floating-point subtract
• Floating-point multiply
• Floating-point divide
• Floating-point square root
• Floating-point multiply add
• Floating-point multiply subtract

132
• Rounding instructions:
• Floating-point truncate
• Floating-point ceiling
• Floating-point floor
• Floating-point round

• Format conversions:
• Single-precision to double-precision
• Double-precision to single-precision

133
 Example: Add a scalar s to a vector A

for (i=1000; i>0; i--)

A[i]= A[i] + s;
R1: initially points to A[1000]
(F2,F3): contains the scalar s
Loop: L.D F0,0(R1) R2: initialized such that 8(R2) is the
ADD.D F4,F0,F2 address of A[1]
S.D F4,0(R1) We assume double precision (64 bits):
ADDI R1,R1,-8 • Numbers stored in (F0,F1), (F2,F3), and (F4,F5).
BNE R1,R2,Loop

134