Multiply

CSCE230: Computer Organization

Instructor: Witawas Srisa-an

Multiplication First multiplier algorithm Figure 1: Multiplication Hardware

Multiplicand Shift left 64 bits

Multiplier Shift right

64-bit ALU

32 bits Product

Control test

Write 64 bits

Figure 2: ASM chart for first multiplication algorithm

Start

Multiplier0 = 1

1. Test Multiplier0

Multiplier0 = 0

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

2. Shift the Multiplicand register left 1 bit

3. Shift the Multiplier register right 1 bit

32nd repetition?

No: < 32 repetitions

Yes: 32 repetitions

Done

Summer 2003

1/5

CSE: University of Nebraska-Lincoln

CSCE230: Computer Organization

Instructor: Witawas Srisa-an

For example: multiplicand multiplier x

0011 0110 Table 1: Example of the first algorithm performing 3 x 6

Test Value

Product (L)

Product (R)

Multiplicand

Multiplier

Iteration

-

0000

0000

00000011

0110

0

0

0000

0000

00000110

0011

1

1

0000

0110

00001100

0001

2

1

0001

0010

00011000

0000

3

0

0001

0010

00110000

0000

4

Second multiplier algorithm The differences between the first algorithm include: • 32-bit multiplicand register instead of 64-bit • 32-bit ALU instead of 64-bit • Product register is shifted instead of multiplicand register Figure 3: Second multiplication hardware

Multiplicand 32 bits

Multiplier Shift right

32-bit ALU

32 bits

Product

Shift right Write

Control test

64 bits

Summer 2003

2/5

CSE: University of Nebraska-Lincoln

CSCE230: Computer Organization

Instructor: Witawas Srisa-an

Figure 4: ASM chart for the second multiplication algorithm

Start

Multiplier0 = 1

1. Test Multiplier0

Multiplier0 = 0

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

2. Shift the Product register right 1 bit

3. Shift the Multiplier register right 1 bit

32nd repetition?

No: < 32 repetitions

Yes: 32 repetitions

Done

For example: multiplicand multiplier x

0011 0110 Table 2: Example of the second algorithm performing 3 x 6

Test Value

Product (L)

Product (R)

Multiplicand

Multiplier

Iteration

-

0000

0000

0011

0110

0

0

0000

0000

0011

0011

1

1

0001

1000

0011

0001

2

1

0010

0100

0011

0000

3

0

0001

0010

0011

0000

4

Summer 2003

3/5

CSE: University of Nebraska-Lincoln

CSCE230: Computer Organization

Instructor: Witawas Srisa-an

Third multiplier algorithm The differences between the second algorithm include: • no multiplier register (initialize right half of product to multiplier value) Figure 5: Third multiplication hardware

Multiplicand 32 bits

32-bit ALU

Product

Shift right Write

Control test

64 bits

Figure 6: ASM chart for the third multiplication algorithm Start

Product0 = 1

1. Test Product0

Product0 = 0

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

2. Shift the Product register right 1 bit

32nd repetition?

No: < 32 repetitions

Yes: 32 repetitions

Done

Summer 2003

4/5

CSE: University of Nebraska-Lincoln

CSCE230: Computer Organization

Instructor: Witawas Srisa-an

For example: multiplicand multiplier x

0011 0110 Table 3: Example of the third algorithm performing 3 x 6

Test Value

Product (L)

Product (R)

Multiplicand

Iteration

-

0000

0110

0011

0

0

0000

0011

0011

1

1

0001 (A & S)

1001

0011

2

1

0010

0100

0011

3

0

0001

0010

0011

4

Booth’s Algorithm 1. Depend on the current and previous bit of the multiplier: 00: Middle of the “0” string, no operation 01: End of the string, add multiplicand to the left half of the product 10: Beginning of the string, subtract multiplicand from the left half of the product 11: Middle of the “1” string, no operation 2. Shift the Product register right 1 bit. For example: multiplicand multiplier x

0011 0110 Table 4: Example of Booth’s algorithm performing 3 x 6

Test Value

Product (L)

Product (R)

Multiplicand

Multiplier

Iteration

-

0000

0000

0011

0110

0

00

0000

0000

0011

0110

1

10

1110

1000

0011

0110

2

11

1111

0100

0011

0110

3

01

0010

0010

0011

0110

4

Summer 2003

5/5

CSE: University of Nebraska-Lincoln