Sequential Multiplication Algorithm

• Multiplication extends addition and subtraction, forming a more complex operation.
• The length of the product of an n-bit multiplicand and an m-bit multiplier is n + m bits long.
• Multiply must handle overflow, due to frequently wanting a 32-bit product from two 32-bit numbers.
• Binary multiplication uses 0 and 1, simplifying each step to either placing a copy of the multiplicand or placing 0.

Sequential Multiplication Algorithm and Hardware

• This design mirrors manual multiplication, using registers for the multiplicand, multiplier, and product, along with an ALU.
• The multiplicand register and product register are 64 bits wide, and the multiplier register is 32 bits wide.
• The 32-bit multiplicand starts in the right half of the Multiplicand register and shifts left 1 bit on each step.
• The multiplier shifts in the opposite direction at each step.
• The algorithm begins with the product initialized to 0.
• The multiplicand register needs to be 64-bits to accommodate the shifting to the left 32 times over 32 steps.
• The shift left in step 2 moves the intermediate operands to the left.
• The shift right in step 3 reveals the next bit of the multiplier to examine in the following iteration.
• This process repeats 32 times to determine the product.

Optimization

• Operations can be performed in parallel to increase speed.
• Hardware can be further optimized by halving the width of the adder and registers by using unused portions of the registers and adders.

Signed Multiplication

• Convert the multiplier and multiplicand to positive numbers first, and remember the original signs.
• Run the algorithm, leaving out the signs, for 31 iterations.
• Negate the product only if the original signs disagree.
• Shifting steps extend the sign of the product for signed numbers.
• The lower word contains the 32-bit product.

Faster Multiplication

• Faster multiplication hardware can be built due to increase in hardware resources.
• Whether the multiplicand is added or not is determined at the start of multiplication by examining each of the 32 multiplier bits.
• Faster multiplications involve a 32-bit adder for each bit of the multiplier.
• Can organize 32 additions in a parallel tree.
• Instead of waiting 32 add times, wait log2(32) or five 32-bit add times.

Multiply in MIPS

• MIPS uses Hi and Lo, a pair of 32-bit registers, to store the 64-bit product.
• mult (multiply) and multu (multiply unsigned) instructions are used to produce signed or unsigned products.
• mflo (move from lo) instruction fetches the 32-bit product.
• The assembler may use pseudo-instructions, such as mflo and mfhi, to place the product into registers, specifying three general-purpose registers for multiplication.