Chapter 1, Problem 1.9.1E

Explanation of Solution

Number of processors	Arithmetic instructions	L/S instructions	Branch instructions	Execution Time (Seconds)	Speedup
1	$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$	$1.28\text{×}{\text{10}}^{\text{9}}$	$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$	9.6	1
2	$1.83\text{×}{\text{10}}^{\text{9}}$	$9.14\text{×}{\text{10}}^8$	$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$	7.04	1.36
4	$9.12\text{×}{\text{10}}^8$	$4.57\text{×}{\text{10}}^8$	$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$	3.84	1.83
8	$4.57\text{×}{\text{10}}^8$	$\text{2}\text{.29}\text{×}{\text{10}}^8$	$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$	2.24	1.71

The arithmetic instructions are parallelized to run over multiple cores as follows

$\text{Arithmatic}\text{instructions}\text{=}\frac{\text{Number}\text{of}\text{instructions}}{\text{0}\text{.7}\text{×}\text{Number}\text{of}\text{processors}}$

Substitute, “$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$” for “number of instructions” and “2” for “number of processors” in the above formula

$\begin{array}{c}\text{Arithmatic}{\text{instructions}}_{(2)}\text{=}\frac{\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}\text{2}}\\ \text{=}1.83\text{×}{\text{10}}^{\text{9}}\end{array}$

Thus, the number of arithmetic instructions with 2 processors is $1.83\text{×}{\text{10}}^{\text{9}}$.

Substitute, “$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$” for “number of instructions” and “4” for “number of processors” in the above formula

$\begin{array}{c}\text{Arithmatic}{\text{instructions}}_{(4)}\text{=}\frac{\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}4}\\ \text{=}9.12\text{×}{\text{10}}^8\end{array}$

Thus, the number of arithmetic instructions with 4 processors is $9.12\text{×}{\text{10}}^8$.

Substitute, “$\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}$” for “number of instructions” and “8” for “number of processors” in the above formula

$\begin{array}{c}\text{Arithmatic}{\text{instructions}}_{(8)}\text{=}\frac{\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}8}\\ \text{=}4.57\text{×}{\text{10}}^8\end{array}$

Thus, the number of arithmetic instructions with 8 processors is $4.57\text{×}{\text{10}}^8$.

The L/S instructions are parallelized to run over multiple cores as follows

$\text{L/S}\text{instructions}\text{=}\frac{\text{Number}\text{of}\text{instructions}}{\text{0}\text{.7}\text{×}\text{Number}\text{of}\text{processors}}$

Substitute, “$1.28\text{×}{\text{10}}^{\text{9}}$” for “number of instructions” and “2” for “number of processors” in the above formula

$\begin{array}{c}\text{L/S}{\text{instructions}}_{(2)}\text{=}\frac{1.28\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}\text{2}}\\ \text{=}9.14\text{×}{\text{10}}^8\end{array}$

Thus, the number of L/S instructions with 2 processors is $9.14\text{×}{\text{10}}^8$.

Substitute, “$1.28\text{×}{\text{10}}^{\text{9}}$” for “number of instructions” and “4” for “number of processors” in the above formula

$\begin{array}{c}\text{L/S}{\text{instructions}}_{(4)}\text{=}\frac{1.28\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}4}\\ \text{=}4.57\text{×}{\text{10}}^8\end{array}$

Thus, the number of L/S instructions with 4 processors is $4.57\text{×}{\text{10}}^8$.

Substitute, “$1.28\text{×}{\text{10}}^{\text{9}}$” for “number of instructions” and “8” for “number of processors” in the above formula

$\begin{array}{c}\text{L/S}{\text{instructions}}_{(8)}\text{=}\frac{1.28\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}8}\\ \text{=}2.29\text{×}{\text{10}}^8\end{array}$

Thus, the number of L/S instructions with 8 processors is $2.29\text{×}{\text{10}}^8$.

The total execution time of the program can be calculated using the following formula

$\text{Execution}\text{time}\text{=}\frac{\text{CPI}\text{×}\text{Number}\text{of}\text{instructions}}{\text{Clock}\text{rate}}$

Substitute, “1” for “CPI of arithmetic instructions”, “12” for “CPI of L/S instructions”, “5” for “CPI of branch instructions”,, “$2.56\times {10}^9$” for “number of arithmetic instructions”, “$1.28\times {10}^9$” for “number of L/S instructions” “$0.25\times {10}^9$”for “number of branch instructions” and “$2\times {10}^9$” for “clock rate”

$\begin{array}{c}\text{Execution}{\text{time}}_{(1)}\text{=}\frac{\text{(1×}\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}\text{)}\text{+}\text{(12×}\text{1}\text{.28}\text{×}{\text{10}}^{\text{9}}\text{)}\text{+}\text{(5×}\text{0}\text{.25}\text{×}{\text{10}}^{\text{9}}\text{)}}{\text{2}\text{×}{\text{10}}^{\text{9}}}\\ \text{=}\text{9}\text{.6}\end{array}$

Thus, the total execution time of the program with 1 processor is “9.6seconds”.

Substitute, “1” for “CPI of arithmetic instructions”, “12” for “CPI of L/S instructions”, “5” for “CPI of branch instructions”,, “$\frac{2.56\times {10}^9}{\text{0}\text{.7}\text{×}\text{2}}$” for “number of arithmetic instructions”, “$\frac{1.28\times {10}^9}{\text{0}\text{.7}\text{×}\text{2}}$” for “number of L/S instructions” “$0.25\times {10}^9$”for “number of branch instructions”, “and “$2\times {10}^9$” for “clock rate”

$\begin{array}{c}\text{Execution}{\text{time}}_{(2)}\text{=}\frac{\left(\frac{\text{1×}\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}\text{2}}\right)\text{+}\left(\frac{\text{12×}\text{1}\text{.28}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}\text{2}}\right)\text{+}\text{(0}\text{.25}\text{×}{\text{10}}^{\text{9}}\text{)}}{2\times {10}^9}\\ \text{=}\text{7}\text{.04}\end{array}$

Thus, the total execution time of the program with 2 processors is “7.04seconds”.

Substitute, “1” for “CPI of arithmetic instructions”, “12” for “CPI of L/S instructions”, “5” for “CPI of branch instructions”,, “$\frac{2.56\times {10}^9}{\text{0}\text{.7}\text{×}4}$” for “number of arithmetic instructions”, “$\frac{1.28\times {10}^9}{\text{0}\text{.7}\text{×}4}$” for “number of L/S instructions” “$0.25\times {10}^9$”for “number of branch instructions”, “and “$2\times {10}^9$” for “clock rate”

$\begin{array}{c}\text{Execution}{\text{time}}_{(4)}\text{=}\frac{\left(\frac{\text{1×}\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}\text{4}}\right)\text{+}\left(\frac{\text{12×}\text{1}\text{.28}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}\text{4}}\right)\text{+}\text{(0}\text{.25}\text{×}{\text{10}}^{\text{9}}\text{)}}{\text{2}\text{×}{\text{10}}^{\text{9}}}\\ \text{=}\text{3}\text{.84}\end{array}$

Thus, the total execution time of the program with 4 processors is “3.84seconds”.

Substitute, “1” for “CPI of arithmetic instructions”, “12” for “CPI of L/S instructions”, “5” for “CPI of branch instructions”,, “$\frac{2.56\times {10}^9}{\text{0}\text{.7}\text{×}8}$” for “number of arithmetic instructions”, “$\frac{1.28\times {10}^9}{\text{0}\text{.7}\text{×}8}$” for “number of L/S instructions” “$0.25\times {10}^9$”for “number of branch instructions”, “and “$2\times {10}^9$” for “clock rate”

$\begin{array}{c}\text{Execution}{\text{time}}_{(8)}\text{=}\frac{\left(\frac{\text{1×}\text{2}\text{.56}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}8}\right)\text{+}\left(\frac{\text{12×}\text{1}\text{.28}\text{×}{\text{10}}^{\text{9}}}{\text{0}\text{.7}\text{×}8}\right)\text{+}\text{(0}\text{.25}\text{×}{\text{10}}^{\text{9}}\text{)}}{\text{2}\text{×}{\text{10}}^{\text{9}}}\\ \text{=}2.24\end{array}$

Thus, the total execution time of the program with 8 processors is “2.24seconds”.

The relative speedup of the processor can be calculated using the following formula

$\text{Speedup}\text{=}\frac{\text{Execution}{\text{time}}_{\left(\text{required}\right)}}{\text{Execution}{\text{time}}_{\left(\text{current}\right)}}$

Substitute, “9.6” for “execution time of required processor” and “7.04” for “execution time of current processor”

$\begin{array}{c}{\text{Speedup}}_{\text{(2-1)}}\text{=}\frac{\text{9}\text{.6}}{\text{7}\text{.04}}\\ \text{=}\text{1}\text{.36}\end{array}$

Therefore, the relative speedup of 2 processors with a single processor is “1.36”.

Substitute, “9.6” for “execution time of required processor” and “3.84” for “execution time of current processor”

$\begin{array}{c}{\text{Speedup}}_{\text{(4-1)}}\text{=}\frac{\text{9}\text{.6}}{3.84}\\ \text{=}2.5\end{array}$

Therefore, the relative speedup of 4 processors with a single processor is “2.5”.

Substitute, “9.6” for “execution time of required processor” and “2.24” for “execution time of current processor”

$\begin{array}{c}{\text{Speedup}}_{\text{(8-1)}}\text{=}\frac{\text{9}\text{.6}}{2.24}\\ \text{=}4.28\end{array}$

Therefore, the relative speedup of 8 processors with a single processor is “4.28”.