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:

- A ← 0, Q ← X, Q-1 ← 0, M ← Y
- For I = 1 to n do a. If Q0Q-1 = 01 then A ← A + M b. If Q0Q-1 = 10 then A ← A – M c. Arithmetic Right Shift (A || Q) The answer is stored in the combination of (A || Q)

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.

- 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

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?

**Solution**

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