Question

Assume for arithmetic, load/store, and branch instructions, a processor have CPIs of 1, 12, and 5, respectively. Also assume that on a single processor a program requires the execution of 2.56E9 arithmetic instructions, 1.28E9 load/store instructions, and 256 million branch instructions. Assume that each processor has a 2 GHz clock frequency.

Assume that, as the program is parallelized to run over multiple cores, the number of arithmetic and load/store instructions per processor is divided by 0.7 x p (where p is the number of processors) but the number of branch instructions per processor remains the same.

1.9.1 Find the total execution time for this program on 1, 2, 4, and 8 processors, and show the relative speedup of the 2, 4, and 8 processor result relative to the single processor result.

1.9.2 If the CPI of the arithmetic instructions was doubled, what would the impact be on the execution time of the program on 1, 2, 4, or 8 processors?

1.9.3 To what should the CPI of load/store instructions be reduced in order for a single processor to match the performance of four processors using the original CPI values?

Short answer

1.9.1)

Execution time for processor 1: 9.6 sec

Execution time for processor 2: 7.02 sec

Execution time for processor 4: 3.86 sec

Execution time for processor 8: 2.25 sec

Relative speed taken by processor 2: 1.37

Relative speed taken by processor 4: 2.49

Relative speed taken by processor 8: 4.27

1.9.2)

Impact on execution time on 1 processor: 10.88ms

Impact on execution time on 2 processor: 7.954ms

Impact on execution time on 4 processor: 4.297ms

Impact on execution time on 8 processor: 2.468ms

1.9.3)

reduced CPI of load/store instructions is 25%

Step-by-step solution

Consider the following data

CPI for

$$\begin{gathered} Arithmeticinstruction:\hspace{0.17em}1 \\ Load/Storeinstruction:\hspace{0.17em}12 \\ Branchinstruction:5 \end{gathered}$$

No. of Instruction per processor

$$\begin{gathered} Arithmetic:2.56\times {10}^9 \\ Load/Store:1.28\times {10}^9 \\ Branch:256\times {10}^{6}instructions \end{gathered}$$

Clock rate=

When a program is distributed to operate on multicore processors, the amount of arithmetic and load store operations per processor is divided by 0.7 and multiplied by the number of processors p, but the branch command remains unchanged. There are four processors: 1,2,4,8. To calculate the execution, the processor uses the following method:

Write a formula for execution time for a processor:

$Executiontime=\frac{clockcycle}{clockrate}$.........(1)

Write a formula for clock cycle.

$$\begin{gathered} Clockcyles=CP{I}_{fp}xNo.FPinstr.+CP{I}_{int}xNo.INTinstr. \\ +CP{I}_{1/z}xNo.L/Sinstr.+CP{l}_{branch}xNo.branchinstr \end{gathered}$$............(2)

Write a formula forRelative speedup

$Relativespeedup=\frac{Timetakenby1processor}{Timetakenbypprocessors}$.....................(3)

Execution time for processor 1, processor 2, processor 4, and processor 8

1.9.1

Execution time for processor 1:

Compute the clock cycle using the following strategy:

$$\begin{gathered} Clockcycle=CP{I}_{fp}xNo.FPinstr.+CP{l}_{int},*No.INTinstr+ \\ CP{I}_{1/z}xNo.L/Sinstr.+CP{I}_{branch},*No.branchinstr \end{gathered}$$

Therefore,

$\begin{array}{rcl}Clockcycle& =& \text{2560000000 x1 + 1280000000x12 + 256000000 x5}\\ & =& \text{2560000000 + 15360000000 + 1280000000}\\ & =& \text{19200000000 cycles}\end{array}$

Now calculate the execution time with the help of following method:

$Executiontimeforaprocessor=\frac{clockcycle}{clockrate}$

Therefore,

$$\begin{gathered} CPUexecutiontime \\ =19200000000cycles/2\times {10}^{9}cycles/sec \\ =9600000000/{10}^9 \\ =9.6sec \end{gathered}$$

$\begin{array}{rcl}Relativespeedup& =& \frac{Timetakenby1processor}{Timetakenbypprocessors}\\ & =& 9.6/9.6\\ & =& 1\\ & & \end{array}$

Execution time for processor 2:

When a programme is distributed to operate on multicore processors, the amount of arithmetic and load store operations per processor is divided by 0.7 and multiplied by the number of processors p, but the branch command remains unchanged.There are four processors: 1,2,4,8.

Compute the clock cycle using the following strategy:

$$\begin{gathered} Clockcyles=CP{I}_{fp}xNo.FPinstr.+CP{l}_{int},xNo.INTinstr+CP{I}_{1/z}xNo.L/Sinstr. \\ +CP{l}_{branch},*No.branchinstr \end{gathered}$$

Therefore,

$$\begin{gathered} clockcycle \\ =\frac{2560}{0.7*8}*2+\frac{1289}{0.7*8}*12+256*5 \\ =914.23+2742.86+1280 \\ =4937.08cycle \end{gathered}$$

Now calculate the execution time with the help of following method:

$Executiontimeforaprocessor=\frac{clockcycle}{clockrate}$

Therefore

$$\begin{gathered} CPUexecutiontime \\ =14040000000cycles/2*{10}^{8}cycles/sec \\ =7020000000/{10}^9 \\ =7.02sec \end{gathered}$$

$\begin{array}{rcl}Relativespeedup& =& \frac{Timetakenby1processor}{Timetakenby2processors}\\ & & \text{=}\frac{9.6}{7.02}\\ & & \text{=1.37}\end{array}$

Execution time for processor 4:

When a programme is distributed to operate on multicore processors, the amount of arithmetic and load store operations per processor is divided by 0.7 and multiplied by the number of processors p, but the branch command remains unchanged. There are four processors: 1,2,4,8.

Compute the clock cycle using the following strategy:

$$\begin{gathered} Clockeyes=CP{I}_{fp},xNo.FPinstr.+CP{I}_{int},xNo.INTinstr+ \\ CP{I}_{1/z},xNo.L/Sinstr.+CP{l}_{branch}*No.branchinstr \end{gathered}$$

Therefore,

$$\begin{gathered} clockcycle \\ =\left(2560000000*1\right)/\left(0.7*4\right)+\left(1280000000*12\right)/\left(0.7*4\right)+256000000*5 \\ =7720000000cycles \end{gathered}$$

Now calculate the execution time with the help of following method:

$Executiontimeforaprocessor=\frac{clockcycle}{clockrate}$

Therefore,

$\begin{array}{rcl}& & CPUexecutiontime\\ & =& 1720000000cycles/2*{10}^{9}cycles/sec\\ & =& 3.86sec\\ Relativespeedup& =& \frac{Timetakenby1processor}{Timetakenby4processors}\\ & =& 9.6/3.86\\ & =& 2.49\end{array}$

Execution time for processor 8:

When a programme is distributed to operate on multicore processors, the amount of arithmetic and load store operations per processor is divided by 0.7 and multiplied by the number of processors p, but the branch command remains unchanged. There are four processors: 1,2,4,8.

Compute the clock cycle using the following strategy:

$$\begin{gathered} Clockcyles=CP{l}_{fp}xNo.FPinstr.+CPIint,xNo.INTinstr+ \\ CP{I}_{1/z}xNo.L/Sinstr.+CP{l}_{branch}*No.branchinstr \end{gathered}$$

Therefore,

localid="1655192387163" $$\begin{gathered} clockcycle \\ =\frac{2560000000*1}{0.7*8}+\frac{1280000000*12}{0.7*8}+256000000*5 \\ =\frac{25600000000}{5.6}+\frac{15360000000}{5.6}+1280000000 \\ =4500000000cycles \end{gathered}$$

Now calculate the execution time with the help of following method:

$Executiontimeforaprocessor=\frac{clockcycle}{clockrate}$

Therefore,

$$\begin{gathered} CPUexecutiontime \\ =4500000000cycles/2*{10}^{9}Cycle/sec \\ =2250000000/{10}^9 \\ =2.25sec \end{gathered}$$

Time taken by processor

$\begin{array}{rcl}Relativespeedup& =& \frac{Timetakenby1processor}{Timetakenby8processor}\\ & =& 9.6/225\\ & =& 4.27\\ & & \end{array}$

Execution time with double Arithmetic instructions.

1.9.2

Execution time for processor 1 when Arithmetic instructions are doubled:

If an Arithmetic instruction is doubled (CPI=2) then Execution time for processor 1 can be calculated as:

First calculate the Clock cycle, which can be calculated as:

Clock cycle

$$\begin{gathered} =2560\times 2+1280\times 12+256\times 5 \\ =21760cycles \end{gathered}$$

Now execution time can be calculated as:

$$\begin{gathered} CPUexecutiontime \\ =21760cycles/2x10cycles/sec \\ =10.88ms \end{gathered}$$

Execution time for processor 2 when Arithmetic instructions are doubled:

If an Arithmetic instruction is doubled (CPI=2) then Execution time for processor 2 can be calculated as:

$$\begin{gathered} Clockcycle \\ =\left(2560/0.7*2\right)*2+1280/\left(0.7*2\right)*12+256*5 \\ =3657.14+1097143+1280 \\ =15908.57cycles \end{gathered}$$

Now execution time can be calculated as:

$$\begin{gathered} CPUexecutiontime \\ =15908.57cycles/2*{10}^{9}cycles/sec \\ =7.954ms \end{gathered}$$

Execution time for processor 4 when Arithmetic instructions are doubled:

If an Arithmetic instruction is doubled (CPI=2) then Execution time for processor 4 can be calculated as:

$$\begin{gathered} clock\text{cycle} \\ =\frac{2560}{0.7*4}*2+\frac{1280}{0.7*4}*12+256*5 \\ =1828.57+5485.71+1280 \\ =8594 \end{gathered}$$

Now execution time can be calculated as:

CPU execution time

$$\begin{gathered} =8594.28cycles/2*{10}^{9}cycles/sec \\ =4.297ms \end{gathered}$$

Execution time for processor 8 when Arithmetic instructions are doubled:

If an Arithmetic instruction is doubled (CPI=2) then Execution time for processor 8 can be calculated as:

$$\begin{gathered} clockcycle \\ =\frac{2560}{0.7*8}*2+\frac{1289}{0.7*8}*12+256*5 \\ =914.23+2742.86+1280 \\ =4937.08cycle \end{gathered}$$

Now execution time can be calculated as:

$$\begin{gathered} =4937.08cycles/2x{10}^{9}cycles/sec \\ =2.468ms \end{gathered}$$

Determine the reduced CPI of load/store instructions.

1.9.3

For 4 processors:

When a programme is distributed to operate on multicore processors, the amount of arithmetic and load store operations per processor is divided by 0.7 and multiplied by the number of processors p, but the branch command remains unchanged. There are four processors: 1,2,4,8.

Therefore,

clock cycle

$$\begin{gathered} =\left(2560000000/2.8\right)+\left(15360000000/2.8\right)+1280000000 \\ =7720000000cycles \end{gathered}$$

Now calculate the execution time with the help of following method:

$Executiontimeforaprocessor=\frac{clockcycle}{clockrate}$

Therefore,

$$\begin{gathered} CPUexecutiontime \\ =7720000000cycles/2x{10}^{9}cycles/sec \\ =3860000000/{10}^9 \\ =3.86\sec \end{gathered}$$

Reducing CPI of a single processor to match the performance of 4 processors:

Compute the clock cycle using the following strategy:

$$\begin{gathered} Clockcyles=CP{I}_{fp}xNo.FPinstr.+CP{I}_{int}xNo.INTinstr.+ \\ CP{I}_{1/z}xNo.L/Sinstr.+CP{I}_{branch}xNo.branchinst{r}_{} \end{gathered}$$

Therefore,

clock cycle

$$\begin{gathered} =2560000000x1+1280000000xa+256000000x5 \\ =2560000000+1280000000a+1280000000 \\ =3840000000+1280000000xa \end{gathered}$$

Now calculate the execution time with the help of following method:

$Executiontimeforaprocessor=\frac{clockcycle}{clockrate}$

Therefore,

CPU execution time

$$\begin{gathered} =\frac{3840000000+1280000000*a}{2*{10}^{9}cycle/\sec } \\ =\frac{3840000000}{2*{10}^9}+\frac{1280000000*a}{2*{10}^9} \\ =3.86=1.92+0.64*a \\ =1.94=0.64*a \\ =a=3.03 \end{gathered}$$

The reduced CPI is calculated as follows:

Original CPI for load instructions=12

$\begin{array}{rcl}ReducedCPI& =& \frac{a}{originalCPIforloadinstructions}\\ & =& 3.03/12=0.25or25\%\end{array}$

Thus, the reduced CPI of load/store instructions is 25%.