3.3 Multiplication

example of multiplication

The first operand is called the multiplicand and the second the multiplier.

The final result is called the product.

 

First version of the multiplication hardware

The 32-bit multiplicand starts in the right half of the Multiplicand register and is shifted left 1 bit on each step.

The multiplier is shifted in the opposite direction at each step.

The algorithm starts with the product initialized to 0.

Control decides when to shift the Multiplicand and Multiplier registers and when to write new values into the Product register.

 

 

Sequential Version of the Multiplication Algorithm and Hardware

The first multiplication algorithm, using the above hardware

 

This algorithm and hardware are easily refined to take 1 clock cycle per step.

 

Refined version of the multiplication hardware

 

The Multiplicand register, ALU, and Multiplier register are all 32 bits wide, with only the Product register left at 64 bits. Now the product is shifted right.

The separate Multiplier register also disappeared.

The multiplier is placed instead in the right half of the Product register.

These changes are highlighted in color.

The Product register should really be 65 bits to hold the carry out of the adder

 

Example) 

Using 4-bit numbers to save space, multiply 2ten x 3ten, or 0010two x 0011two.

 

 Answer)

 

Signed Multiplication

The easiest way to understand how to deal with signed numbers is to first convert the multiplier and multiplicand to positive numbers and then remember the original signs.

The algorithms should then be run for 31 iterations, leaving the signs out of the calculation. 

 

Faster Multiplication

Fast multiplication hardware

An alternative way to organize these 32 additions is in a parallel tree.

Instead of waiting for 32 add times, we wait just the log2 (32) or five 32-bit add times.

 

Multiply in MIPS

MIPS provides a separate pair of 32-bit registers to contain the 64-bit product, called Hi and Lo.

To produce a properly signed or unsigned product, MIPS has two instructions: multiply (mult) and multiply unsigned (multu).

To fetch the integer 32-bit product, the programmer uses move from lo (mflo).

The MIPS assembler generates a pseudoinstruction for multiply that specifies three general-purpose registers, generating mflo and mfhi instructions to place the product into registers.