SYST 27198
CPU Architecture and
Assembly
Dr. Rachel Jiang
Sheridan Institute of Technologies and
Advanced Learning
Winter 2017
Rachel Jiang, 2007
Acknowledgement
This notes is based on Professor Victor
Ralevich’s course Notes of
“Structured Computer Organization”
Updated by Rachel Jiang
Feb. 2017
2019-02-07 2
Dr. Rachel Jiang
Chapter Five
Computer Arithmetic
Implementation
2019-02-07 3
Dr. Rachel Jiang
Digital Logic
2019-02-07 4
Dr. Rachel Jiang
Topics
Integer addition and subtraction
Hardware implementation of adders and
subtractors
Integer multiplication and division
Unsigned multiplication and division
Signed multiplication and division
Floating Point Arithmetic
High Performance Arithmetic
2019-02-07 5
Dr. Rachel Jiang
“Hardware and software are logically
equivalent”
- Andrew [Link]
“Hardware is just petrified software.”
- Karen Panetta Lentz
R Jiang, June 30th, 2011
2019-02-07 6
Dr. Rachel Jiang
Fixed Point Addition and
Subtraction
Half adder
2019-02-07 7
Dr. Rachel Jiang
Full Adder
2019-02-07 8
Dr. Rachel Jiang
Ci+1 = Ai ·Bi + Ai ·Ci + Bi ·Ci
Si = Ai ⊕Bi ⊕Ci
2019-02-07 9
Dr. Rachel Jiang
Hardware Implementation of
Adders & Subtractors
Addition of two n-bit numbers A and B
can be carried out using n consecutive
FAs in arrangement known as a carry-
ripple through added (CRT).
Two binary numbers A and B are added
from right to left, creating a sum and a carry
at the outputs of each full adder for each bit
position.
2019-02-07 10
Dr. Rachel Jiang
Four Full adders
connected in a ripple-carry chain form a
four-bit ripple-carry adder
Ripple-carry adder
2019-02-07 11
Dr. Rachel Jiang
Example:
Ripple Carry Addition
2019-02-07 12
Dr. Rachel Jiang
Constructing Larger Adders
A 16-bit adder can be made up of a
cascade of four 4-bit ripple-carry adders.
2019-02-07 13
Dr. Rachel Jiang
Inclass Exercise I
Provide the unsigned integer addition of 78
and 69 in 8- bit binary format
01001110
+0 1 0 0 0 1 0 1
‘ ‘‘
------------------------
10010011
How many carry out/in in the calculation? on
which bits did the carry outs/ins happen?
Where did the carry out on the most left bit go if
there is one?
2019-02-07 14
Dr. Rachel Jiang
Example:
Ripple Borrow Subtraction
2019-02-07 15
Dr. Rachel Jiang
Full Subtractor
2019-02-07 16
Dr. Rachel Jiang
Ripple-Borrow Subtractor
• A ripple-borrow subtractor can be
composed of a cascade of full
subtractors
• Two binary numbers A and B are
subtracted from right to left, creating a
difference and a borrow at the outputs of
each full subtractor for each bit position.
2019-02-07 17
Dr. Rachel Jiang
Full Subtractor
If the subtrahend bi is larger than the
minuend ai, or there is a borrow from
a previous digit
then the borrow must be propagated
to the next most significant bit.
difference (ai – bi )
2019-02-07 18
Dr. Rachel Jiang
Ripple-borrow subtractor
2019-02-07 19
Dr. Rachel Jiang
Inclass Exercise II
Provide the sign integer subtraction of 78
and 70 in 8- bit binary format
How many borrows happened in the
calculation and on which bit the borrowing
happened
What is the result of the subtraction?
2019-02-07 20
Dr. Rachel Jiang
subtraction of 78 and 69
01001110
-01000101
‘
--------------------------
00001001
2019-02-07 21
Dr. Rachel Jiang
Combined Adder/Subtractor Unit
2019-02-07 22
Dr. Rachel Jiang
Combined Adder/Subtractor Unit
A single ripple-carry adder can perform
both addition (if signal=0) and
subtraction (if signal=1), by forming the
two’s complement negative for B when
subtracting
Note that +1 is added at c0 for two’s
complement
2019-02-07 23
Dr. Rachel Jiang
Inclass Exercise III
What is the value for the input of
(𝐴𝐴𝐴𝐴𝐴𝐴 /SUBTRACT) to make a subtractor?
When B = 1101 and A= 0101 what will be
the value for S when c0 is 0/1?
2019-02-07 24
Dr. Rachel Jiang
Multiplication
• When two n-bit unsigned integers are
multiplied, the result can be up to 2n-bits
large.
• Multiplication of two 4-bit unsigned binary
integers produces an 8-bit result.
2019-02-07 25
Dr. Rachel Jiang
A hardware implementation of
a serial multiplier
2019-02-07 26
Dr. Rachel Jiang
Example
multiplication using the serial multiplier
2019-02-07 27
Dr. Rachel Jiang
Inclass Exercise IV
Provide the detailed calculation steps
using 4-bit binary multiplication and then the
serial multiplier for
1011*0101
2019-02-07 28
Dr. Rachel Jiang
Unsigned Division
In division algorithm, instead of shifting
the product to the right as it was done in
case of multiplication, we shift quotient
to the left, and we subtract instead of
adding
When two n-bit unsigned numbers are
being divided, the result is not larger
than n bits.
2019-02-07 29
Dr. Rachel Jiang
A serial divider
2019-02-07 30
Dr. Rachel Jiang
Division example using a serial divider
Restore A
2019-02-07 31
Dr. Rachel Jiang
Division example using a serial divider
At the beginning:
Q is dividend register
M is divisor register
A and high order bit in M are 0
At the end of the restoring division
process, register A contains (positive value of)
remainder, and register Q contains the
integer value of the quotient.
2019-02-07 32
Dr. Rachel Jiang
Inclass Exercise IV
Provide the detailed calculation steps
using the serial divider for
1111 / 0011
2019-02-07 33
Dr. Rachel Jiang
Multiplication of Signed Integers
Sign extension to the target word
size is needed for the negative
operand(s).
A target word size of 8 bits is used
here for two 4-bit signed operands
only a 7-bit target word size is needed
for the result
each operand reduces to a sign bit and
a 3-bit magnitude, producing a sign-bit
and a 6-bit result
2019-02-07 34
Dr. Rachel Jiang
Multiplication of Signed Integers
2019-02-07 35
Dr. Rachel Jiang
Inclass Exercise V
Provide the results for Multiply two 4-bit
signed operands: 1101*0011
2019-02-07 36
Dr. Rachel Jiang
Floating Point Arithmetic
Floating-Point Representation (Scientific
Notation)
A floating-point (FP) number can be
represented in the form:
±m·be
where m (mantissa) is the fractional part of the
number and most often is represented as a
signed fraction, e is exponent, and b is base
(or radix) of the exponent.
2019-02-07 37
Dr. Rachel Jiang
Floating-Point Representation
(IEEE 754 Format)
Characteristics of the IEEE754 Single and
Double FP Formats
2019-02-07 38
Dr. Rachel Jiang
Floating Point Addition/Subtraction
FP arithmetic differs from integer arithmetic
exponents must be handled as well as the
magnitudes of the operands
To add/sub two FP numbers
do the following:
1. Compare the magnitudes of two exponents and make
suitable alignment of the number with the smaller
exponent.
2. Perform the addition/subtraction.
3. Perform normalization by shifting the resulting mantissa
and adjusting the resulting exponent
2019-02-07 39
Dr. Rachel Jiang
Example
Perform the floating point operation:
(.101 x 23 + .111 x 24)2
Start by adjusting the smaller exponent to be equal
to the larger exponent, and adjust the fraction
accordingly.
0.101 x 23 = 0.0101 x 24,
= 0.010 x 24 - losing .001 x 23 of precision in the
process.
The resulting sum is
(.010 + .111) x 24 = 1.001 x 24 = .1001 x 25
rounding to three significant digits, .100 x 25, and we
have lost another 0.001 x 24 in the rounding process.
2019-02-07 40
Dr. Rachel Jiang
Floating Point Multiplication
Multiplication of a pair of FP numbers X = mx·2a
and Y = my·2b is represented as
X·Y = (mx·my)·2a+b
A general algorithm for multiplication of two
FP numbers is:
1. Compute the exponent of the product by
adding the exponents together.
2. Multiply the two mantissas.
3. Normalize and round the final product
2019-02-07 41
Dr. Rachel Jiang
Example
Calculate the product of
X = 1.000*2-2 and Y = -1.010*2-1
1. Add exponents: -2 + (-1) = -3
2. Multiply mantissas:
1.000*(-1.010) = -1.010000
3. Normalize and round:
X*Y = -1.010*2-3
2019-02-07 42
Dr. Rachel Jiang
Floating Point Division
Division of a pair of FP numbers
X = mx·2a and Y = my·2b
is represented as
X/Y = (mx/my)·2a-b
A general algorithm for multiplication of two FP
numbers is:
1. Compute the exponent by subtracting the exponents.
2. Divide the mantissas and determine the sign of the
result.
3. Normalize and round the resulting value, if necessary.
2019-02-07 43
Dr. Rachel Jiang
Example
Perform the floating point operation:
(+.110 x 25) / (+.100 x 24)2
The source operand signs are the same, which means
that the result will have a positive sign. We subtract
exponents for division, and so the exponent of the result
is 5 – 4 = 1.
We divide fractions, producing the result:
110/100 = 1.10
Putting it all together, the result of dividing
(+.110 x 25) by (+.100 x 24) produces (+1.10 x 21)
After normalization, the final result is (+.110 x 22)
2019-02-07 44
Dr. Rachel Jiang
Inclass Exercise VI
Provide the calculation steps and the result
where X = 1.011*2-2 and Y = 1.010*2-3
a = 0.2345*105; b = 0.1432*103
a+b X+Y
a–b X-Y
a*b X·Y
a/b X/Y
2019-02-07 45
Dr. Rachel Jiang
High Performance Arithmetic
Carry Lookahead Addition
The speed of arithmetic operations is
most often the bottleneck to performance
The ripple-carry adder may introduce too
much delay into a system
The carry propagation time is proportional to
the number of bits in the operands.
we calculated the Boolean expression for the
sum (si) and carry outputs (ci+1) of a full adder
2019-02-07 46
Dr. Rachel Jiang
2019-02-07 47
Dr. Rachel Jiang
Ci+1 = Ai ·Bi + Ai ·Ci + Bi ·Ci
Si = Ai ⊕Bi ⊕Ci
2019-02-07 48
Dr. Rachel Jiang
Gi and Pi are generate and propagate
functions, respectively, for the effect
they have on a carry.
When Gi = 1, a carry is generated at
stage i.
When Pi = 1, then a carry is
propagated through stage i is either ai
or bi is 1.
2019-02-07 49
Dr. Rachel Jiang
Carry Look ahead Adder
2019-02-07 50
Dr. Rachel Jiang
Carry Look ahead Adder
Each independent piece requires one
gate delay for Gi and Pi and two more to
generate ci+1.
The depth of three gate delays is
added, but the ripple-carry chain is
removed
If each full-adder introduces a gate delay
of 2, then a four-bit carry lookahead adder
will have a maximum gate delay of five.
2019-02-07 51
Dr. Rachel Jiang
Inclass Exercise VII
Prove c2 = G1 + P1 G0 using boolean
table(s)
2019-02-07 52
Dr. Rachel Jiang
The Booth Algorithm
Booth multiplication reduces the number of
additions for intermediate results.
Positive and negative numbers treated alike
2019-02-07 53
Dr. Rachel Jiang
The Worst Case Booth Example
A worst case situation in which the simple
Booth algorithm requires twice as many
additions as serial multiplication
2019-02-07 54
Dr. Rachel Jiang
Bit-Pair Recoding (Modified Booth Algorithm)
2019-02-07 55
Dr. Rachel Jiang
Coding of Bit Pairs
2019-02-07 56
Dr. Rachel Jiang
2019-02-07 57
Dr. Rachel Jiang
Questions?
???
2019-02-07 58
Dr. Rachel Jiang