Class Notes (1,100,000)
CA (620,000)
McGill (30,000)
COMP (700)
Lecture 7

COMP 273 Lecture Notes - Lecture 7: Finite-State Machine, Normalized Number, Floating Point


Department
Computer Science (Sci)
Course Code
COMP 273
Professor
Piotr Przytycki
Lecture
7

Page:
of 6
COMP 273 7 - sequential logic 3 Feb. 1, 2016
Integer multiplication
Suppose we have two unsigned integers, A and B, and we wish to compute their product. Let Abe
the multiplicand and Bthe multiplier:
An1. . . A1A0multiplicand
×Bn1. . . B1B0multiplier
P2n1. . . Pn1. . . P1P0product
If the multiplier and multiplicand each have n bits, then the product has at most 2n bits, since
(2n1) (2n1) <22n1
which you can verify for yourself by multiplying out the left side. For example, if we are multiplying
two 32 bit unsigned integers, then we may need as many as 64 bits to represent the product.
Recall your grade school algorithm for multiplying two numbers. We can use the same algorithm
if the numbers are written in binary. The reason is that shifting a binary number one bit to the
left is the same as multiplying by 2, just as decimal multiplication by ten shifts digits left by one.
In the case of binary, each 1 bit biin the multiplier means we have a contribution 2itimes the
multiplicand, and so we add the shifted multiplicands.
1001101
×0010111
1001101
10011010
100110100
0000000000
10011010000
000000000000
+0000000000000
product
In the grade school algorithm, we compute all the left shifts in advance, building up several rows
of numbers which correspond to the digits of the multiplier. Then, this set of numbers is added
together to yield the product (as above).
Let’s consider an alternative algorithm that avoids writing out all the rows with the shifted
multiplicands. Instead the algorithm shifting the multiplicand (left i.e. multiply by 2) at each step
i. When bit Biof the multiplier is 1, the shifted multiplicand is added to an accumulated total.
When bit Biis 0, nothing is added to the total.
What hardware could we use to multiply two n= 32 bit unsigned numbers?
shift registers: the multiplicand is shifted left. If we are multiplying two 32 bit numbers then
we use a 64 bit shift left register for the multiplicand. (We shift the multiplicand to the left
at most 32 times.)
a 32 bit register for the multiplier. We use a shift right register, and read the least significant
bit (LSB, i.e. bit 0) to decide whether to add the shifted multiplicand on each step or not.
last updated: 4th Feb, 2016 1
COMP 273 7 - sequential logic 3 Feb. 1, 2016
a 64 bit adder
a 64 bit register which accumulates the product
a counter to keep track of how many times we’ve shifted.
“Algorithm” for multiplying two unsigned integers:
//
// Let P, A, B be the product, multiplicand, and multiplier registers.
//
P= 0
load Aso lower 32 bits contain multiplicand (upper 32 bits are 0)
load Bso it contains multiplier (32 bits)
for counter = 0 to 31 {
if (LSB of Bis 1)
P:= P+A
endif
shift Aleft by one bit
shift Bright by one bit
}
P
adder
A
LSB
B
shift right register (32 bits)shift left register (64 bits)
DD
shift/load
shift/load
write enable / clear counter
combin.
circuit
We must provide a control signal to the shift registers telling them whether to shift or not at
each clock cycle. On the first clock cycle, we would load the multiplier and multiplicand registers,
rather than shifting the values in these registers. (Where would we load them from? We would load
them from some other registers that are not drawn in the circuit.) On subsequent clock cycles, we
would perform the shift.
Similarly, we must provide a signal to the product register telling it whether we should clear the
product register (only on the first clock cycle), or whether we should write in the value coming out
of the ALU (only on subsequent clock cycles and only when the LSB of the B register is 1.
Finally, notice that all the instructions within the “for loop” can be performed in parallel within
a clock cycle.
last updated: 4th Feb, 2016 2
COMP 273 7 - sequential logic 3 Feb. 1, 2016
Fast integer multiplication (sketch only – not on exam)
In the lecture, I briefly sketched out an alternative scheme which performs n-bit multiplication more
quickly. The idea will be familiar to most of you, namely to those who have taken COMP 250. The
idea is to take the nrows defined by the grade school multiplication algorithm (see page 1) and use
n
2fast adders to add rows 1 and 2, 3 and 4, 5 and 6, etc. Then the outputs from these adders could
be paired and run through n
4adders which would give the sum of rows 1 to 4, 5 to 8, etc. The bits
would all need to be aligned properly as in the table on page 1, but this doesn’t need shift registers.
It just requires that certain output lines be fed into the correct input lines, and 0’s be fed in where
appropriate.
In principle the multiplication can be done in one clock cycle, using only combinational circuits.
However, the clock cycle would need to be long to ensure that the all signals (carries, etc) have
propagated through this circuit. Since the same clock is used for all gates in the processor (including
the ALU) this means we would need a slow clock, which is not what we want.
To avoid the slow clock requirement, it is common to break the multiplication into stages and
have a multiplication run in multiple clock cycles. This can be done by using registers to hold
intermediate results. In particular, the n
2sums could be written to n
2registers at the end of the
multiplication’s first clock cycle. The next n
4sums could be written to n
4registers at the end of the
second clock cycle. Those of you who have already done COMP 250 know that log nclock cycles
would be needed in total to compute the multiplication. This is still faster than the grade school
algorithm which took nsteps.
Integer division (sketch only – not on exams)
When we perform integer division on two positive integers, e.g. 78/21, or more generally “divi-
dend/divisor”, the result is two positive integers, namely a quotient and a remainder.
78 = 3 21 + 15
dividend = quotient divisor + remainder
Suppose we have two 32 bit unsigned integers: a dividend and a divisor. Suppose they are both
positive numbers. How do we compute the quotient and the remainder ? We can apply the “long
division” algorithm we learned in grade school. As with multiplication, we need a set of shift
registers. See slides for a rough sketch of the corresponding circuit. The algorithm is not obvious,
but here it is for completeness (and fun?).
“Algorithm” for long division:
divisor := 2n* divisor // Make the divisor bigger than the dividend
quotient := 0
remainder := dividend
for i = 0 to n
shift quotient left by one bit
if (divisor remainder)
set LSB of quotient to 1
remainder := remainder - divisor
shift divisor to right
last updated: 4th Feb, 2016 3