Metrics and Evaluations/Problem03a

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

Screen Shot 2014-03-31 at 1.41.43 PM.png

This problem is adapted from Professor Kleffel's course notes at CSUSB