MULTIPLY (unsigned)

ECE232: Hardware Organization and Design

Part 4: Datapath Design ? Multiplication and Floating-point representations and operations



Adapted from Computer Organization and Design, Patterson & Hennessy, UCB

MULTIPLY (unsigned)

Paper and pencil example (unsigned):

Multiplicand Multiplier

Product

1000 1001 1000

0000 0000 1000 01001000

m bits x n bits = m+n bit product

Binary makes it easy:

?0 place 0

( 0 x multiplicand)

?1 place a copy

( 1 x multiplicand)

3 versions of multiply hardware & algorithm:

?successive refinement

ECE232: Floating-Point 2

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Unsigned shift-add multiplier (version 1)

64-bit Multiplicand reg, 64-bit ALU, 64-bit Product reg, 32-bit multiplier reg

Multiplicand 64 bits

Shift Left

64-bit ALU

Multiplier Shift Right 32 bits

Product 64 bits

Write

Control

ECE232: Floating-Point 3

Multiplier = datapath + control

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Multiply Algorithm - Version 1

Start

Multiplier0 = 1

1. Test Multiplier0

Multiplier0 = 0

1a. Add multiplicand to product & place the result in Product register

Product 0000 0000 0000 0010 0000 0110 0000 0110

Multiplier 0011 0001 0000

Multiplicand 0000 0010 0000 0100 0000 1000

2. Shift the Multiplicand register left 1 bit.

3. Shift the Multiplier register right 1 bit.

32nd

No: < 32 repetitions

repetition?

Yes: 32 repetitions Done

ECE232: Floating-Point 4

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Observations on Multiply Version 1

1 cycle per step 32x3 = ~ 100 cycles per multiply. However, One cycle per iteration can be saved by shifting multiplier and multiplicand in one cycle 32x2

50% of the bits in multiplicand are 0 64-bit adder is wasted

0s inserted in right of multiplicand as shifted to

the left least significant bits of product never

changed once formed

1001

Instead of shifting multiplicand to left, shift product to the right

1010 0000 1001

0000

1001

10100010

ECE232: Floating-Point 5

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Multiply Hardware - Version 2

32-bit Multiplicand reg, 32 -bit ALU, 64-bit Product reg, 32-bit Multiplier reg

Multiplicand 32 bits

32-bit ALU

Product 64 bits

Shift Right Write

Multiplier Shift Right 32 bits

Control

ECE232: Floating-Point 6

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Multiply Algorithm Version 2

Start

Multiplier0 = 1

1. Test Multiplier0

Multiplier0 = 0

1a. Add multiplicand to the left half of product & place the result in the left half of Product register

Product 1. 00000000 2. 00100000 3. 00010000 4. 00110000 5. 00011000 6. 00001100 7. 00000110

Multiplier Multiplicand

0011

0010

2. Shift the Product register right 1 bit.

0001 0001 0000 0000 0000

0010 0010 0010 0010 0010

3. Shift the Multiplier register right 1 bit.

32nd

No: < 32 repetitions

repetition?

Yes: 32 repetitions Done

ECE232: Floating-Point 7

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Multiply Hardware - Version 3

Product register wastes space that exactly matches size of multiplier

combine Multiplier register and Product register

32-bit Multiplicand reg, 32-bit ALU, 64-bit Product reg, (0-bit Multiplier reg)

Multiplicand

32 bits

32-bit ALU

Product (Multiplier) 64 bits

Shift Right Write

Control

ECE232: Floating-Point 8

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Multiply Algorithm - Version 3

Start

Product0 = 1

1. Test Product0

Product0 = 0

1a. Add multiplicand to the left half of product & place the result in the left half of Product register

2. Shift the Product register right 1 bit.

ECE232: Floating-Point 9

32nd

No: < 32 repetitions

repetition?

Yes: 32 repetitions Done

Adapted from Computer Organization and Design, Patterson & Hennessy, UCB, Kundu, UMass

Koren

Observations on Multiply Version 3

2 steps per bit because Multiplier & Product combined How can you make it faster? What about signed multiplication? ? trivial solution: make both positive & complement product if one

of operands is negative (leave out the sign bit, run for 31 steps) ? apply definition of 2's complement

? need to sign-extend partial products

ECE232: Floating-Point 10 SAdoauptrecdef:roIm. KCoomrepunt,erCOorgmanpizuatteiorn AanrditDhemsigent,icPaAttelgrsoornit&hmHesnn, e2ssnyd, UECdB,itKiounnd,u2, U0M0a2ss

Koren

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download