Speeding it Up

1. Machine A is modified to produce Machine B, where the clock cycle time of machine B is 15% more than that of machine A; the average number of clocks per instruction in machine B is 60% of the average number of clocks per instruction in machine A. The instruction counts do not change.

   What is the speedup of the modification, if any? Is it reasonable to assume that the instruction counts don't change? That is, under what conditions is it possible to get the type of modification presented in this problem.

   Answer: Let CCT, CPI and IC denote clock cycle time, cycles per instruction and instruction count respectively. We have

   $$\begin{eqnarray*} CCT_B &=& 1.15 CCT_A\\ CPI_B &=& 0.6 CPI_A\\ IC_B &=& IC_A\\... ...C_A*CPI_A*CCT_A)/(IC_B*CPI_B*CCT_B)\\ & =& 1/(0.6*1.15)=1.45\\ \end{eqnarray*}$$
   
   
   
   

   It is not reasonable to assume the instruction counts don't change. After a machine is modified, the machine may use different instruction set with different instruction counts to finish the same job.

2. A program spends 75% of its time in iterative computations. A more robust iteration process is used, which speeds up the computations by a factor of 10. What is the effective speedup?

   Answer: Put the values into the Amdahl's law equation (textbook P.30) :
   

   $${\rm Speedup}= \frac{1}{(1-{\rm FE}) + \frac{\rm FE}{K}}$$
   
   

   Speedup = 1/((1-0.75)+(0.75/10)) = 3.077.

3. A process takes 10 seconds to execute, 8 seconds of which are spent in the square-root routine. Suppose a more efficient square-root program reduces the time spent performing the square-root by 90%.

   What is the effective speedup? What percentage of the new execution time is spent using the new square-root process?

   If I wanted to achieve an effective speedup of 4, how much faster would the new square-root process need to be.

   Answer: Before enhancement, the program spends 8/10=80% of time in the square-root routine. After the enhancement, it takes 8s*10% = 0.8s to do the square-root calculation. Thus, the enhanced speed up = 8/0.8 = 10. Put the values into the equation (textbook P.30). Speedup = 1/((1-0.8) + (0.8/10)) = 3.57.

   In order to obtain an effective speedup of 4, 4 = 1/((1-0.8)+(0.8/ $Speedup_{enhanced}$)). $Speedup_{enhanced}$ = 16.

4. A program spends 20% of the new execution time using an enhancement that speeds up the process by a factor of 10. What is the effective speedup? What percentage of time was spent in the enhanced process during the unenhanced execution.

   Answer: Let $T_{old}$ and $T_{new}$ be the execution time of the program before and after enhancement respectively. We cannot apply the equation (textbook P.30) directly. But, by its principle, we have $T_{old}$ = $T_{new}$ *((1-0.2) + (0.2/0.1)) = 2.8$T_{new}$. Thus, the effective speedup = $T_{old}/T_{new}$ = 2.8.

   During unenhanced execution, the program spends 0.2$T_{new}$*10 = 2$T_{new}$ time for the enhanced process. The corresponding fraction = 2$T_{new}$/$T_{old}$ = 2/2.8 = 71.43%.