Booth’s algorithm, used to perform signed binary multiplication (in two's complement form) of X * Y using addition, subtraction and arithmetic right shift, is given below:
Assume that each instruction (line) in the algorithm takes 1 clock cycle to perform (including the for-loop mechanisms and each if-then statement). Assume that a machine which can calculate binary multiplication using a hardware circuit has a multiply instruction with a CPI of 15.
Given that 5% of all instructions in a given benchmark are 32-bit binary multiplications (no other multiplications take place), how much faster is the machine with the hardware multiplication circuit over a machine that must perform the multiplication using Booth’s algorithm?
The frequency of the enhancement (the multiplication circuit) is 5% The machine that uses Booth’s algorithm to perform multiplication executes 1 + 4 * 32 instructions (at one cycle each) or has a 129 cycle multiply The machine with the hardware multiplier takes 15 cycles per multiple The speedup in the enhanced mode is then 129 / 15 = 8.6
This problem is adapted from Professor Kleffel's course notes at CSUSB