ESE 345 Lecture Notes - Lecture 9: Divisor, Critical Path Method, Shift Register
Document Summary
Can be used to reduce critical path of multiply. Example: 53 bit multiply (for floating point): At least 53 levels with naive techniques. At each stage shift a left (x2) Use next bit of b to determine whether to add in shifted multiplicand. Accumulate 2n bit partial product at each stage. 64 bit multiplicand reg, 64 bit alu, 64 bit product reg, 32 bit multiplier reg. 1 clock [er cycle => 100 clocks per multiply. Ratio of multiply to add 5:1 to 100 : 1. 0"s inserted in left of multiplicand as shifted. Least significant bits of product never changed once formed. 32 bit multiplicand reg, 32 bit alu, 64 bit product reg, 32 bit multiplier reg. Multiplicand stays still and product moves right. Product register wastes space that exactly matches size of multiplier. 32 bit multiplicand reg, 32 bit alu, 64 bit product reg, (0 bit multiplier reg) 2 steps per bit because multiplier and product combined.