Class Notes (1,100,000)

CA (620,000)

McGill (30,000)

COMP (700)

COMP 273 (40)

Piotr Przytycki (10)

Lecture 7

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

by OC363662

School

McGill UniversityDepartment

Computer Science (Sci)Course Code

COMP 273Professor

Piotr PrzytyckiLecture

7COMP 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:

An−1. . . A1A0multiplicand

×Bn−1. . . B1B0multiplier

P2n−1. . . Pn−1. . . P1P0product

If the multiplier and multiplicand each have n bits, then the product has at most 2n bits, since

(2n−1) ∗(2n−1) <22n−1

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 signiﬁcant

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 ﬁrst 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 ﬁrst 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 brieﬂy 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 deﬁned 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 ﬁrst 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

**Unlock Document**

###### Document Summary

Suppose we have two unsigned integers, a and b, and we wish to compute their product. Let a be the multiplicand and b the multiplier: 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 bi in the multiplier means we have a contribution 2i times the multiplicand, and so we add the shifted multiplicands. 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.

## More from OC363662

###### COMP 273 Lecture Notes - Lecture 14: Datapath, The Selector, Opcode

Lecture Note

###### COMP 273 Lecture Notes - Lecture 1: Floating Point, Signed Number Representations, Odometer

Lecture Note

###### COMP 273 Lecture Notes - Lecture 10: Louisiana Baptist University, Data Segment, In C

Lecture Note

## Classmates also unlocked

###### COMP 273 Lecture Notes - Lecture 14: Datapath, The Selector, Opcode

Lecture Note

###### COMP 273 Lecture Notes - Lecture 1: Floating Point, Signed Number Representations, Odometer

Lecture Note

###### COMP 273 Lecture Notes - Lecture 10: Louisiana Baptist University, Data Segment, In C

Lecture Note

###### COMP 273 Lecture Notes - Lecture 13: Shift Register, Or Gate, The Selector

Lecture Note

###### COMP 273 Lecture Notes - Lecture 8: Dont, Data Segment, Louisiana Baptist University

Lecture Note

###### COMP 273 Lecture Notes - Lecture 5: The Sketch, Edge Case, Bitwise Operation

Lecture Note

###### COMP 273 Lecture Notes - Lecture 2: Normalized Number, Single-Precision Floating-Point Format, Decimal Mark

Lecture Note

###### COMP 273 Lecture Notes - Lecture 6: Electric Toothbrush, Sequential Logic, Microwave Oven

Lecture Note

###### COMP 273 Lecture Notes - Lecture 12: Nan, Exception Handling, Program Counter

Lecture Note

###### COMP 273 Lecture Notes - Lecture 4: Combinational Logic, Logic Gate, Memory Address

Lecture Note

###### COMP 273 Lecture Notes - Lecture 11: High-Level Programming Language, C Dynamic Memory Allocation, Current Contents

Lecture Note

###### COMP 273 Lecture Notes - Lecture 9: Bit Manipulation, Exception Handling, Opcode

Lecture Note

###### COMP 273 Lecture Notes - Lecture 3: Xor Gate, Bell Labs, Or Gate

Lecture Note

###### [COMP 273] - Midterm Exam Guide - Comprehensive Notes for the exam (63 pages long!)

Study Guide

###### COMP 273- Final Exam Guide - Comprehensive Notes for the exam ( 69 pages long!)

Study Guide