Question

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? Assume for arithmetic, load/store, and branch instructions, a processor has 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.

Answer 1

For
`\( p = 1 \)`:

Original CPU time:

`\[ \text{CPU Time}_{\text{original}} = ((2.56 * 10^9 * 1 + 1.28 * 10^9 * 12 + 256 * 10^6 * 5))/(2 * 10^9) \]`

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + 1.28 * 10^9 * 12 + 256 * 10^6 * 5))/(2 * 10^9) \]`

2. For
`\( p = 2 \)`:

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + (1.28 * 10^9 * 12)/1.4 + 256 * 10^6 * 5))/(2 * 10^9) \]`

3. For
`\( p = 4 \)`:

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + (1.28 * 10^9 * 12)/(2.8) + 256 * 10^6 * 5))/(2 * 10^9) \]`

4. For
`\( p = 8 \)`:

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + (1.28 * 10^9 * 12)/(5.6) + 256 * 10^6 * 5))/(2 * 10^9) \]`

To analyze the impact of doubling the CPI (Cycle Per Instruction) of arithmetic instructions on the execution time of a program, we need to use Amdahl's Law and the formula for CPU time:

`\[ \text{CPU Time} = \frac{\text{Instructions} * \text{CPI} * \text{Clock Cycles}}{\text{Clock Frequency}} \]`

The parallelized portion is the arithmetic instructions, and the speedup is given by:

`\[ \text{Speedup} = (1)/(f + (1 - f)/(p)) \]`

where
`\( f \)` is the fraction of the program that is parallelized (in this case, the fraction of arithmetic instructions).

Let's calculate the original and new CPU times for each case when
`\( p = 1, 2, 4, \)` and
`\( 8 \)`, and analyze the impact on execution time:

Given:

- Number of arithmetic instructions =
`\( 2.56 * 10^9 \)`

- Number of load/store instructions =
`\( 1.28 * 10^9 \)`

- Number of branch instructions =
`\( 256 * 10^6 \)`

- Clock frequency =
`\( 2 \)`GHz

- CPI for arithmetic instructions (original) =
`\( 1 \)`

- CPI for load/store instructions =
`\( 12 \)`

- CPI for branch instructions =
`\( 5 \)`

Original CPU time
`(\( p = 1 \))`:

`\[ \text{CPU Time}_{\text{original}} = ((2.56 * 10^9 * 1 + 1.28 * 10^9 * 12 + 256 * 10^6 * 5))/(2 * 10^9) \]`

Now, let's calculate the new CPU times for
`\( p = 2, 4, \)` and
`\( 8 \)` with the doubled CPI for arithmetic instructions
`(\( \text{CPI}_{\text{new}} = 2 \)):`

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + 1.28 * 10^9 * 12 + 256 * 10^6 * 5))/(2 * 10^9) \]`

For
`\( p = 1, 2, 4, \)` and
`\( 8 \)`, compare the new CPU times with the original CPU time to determine the impact:

`\[ \text{Speedup} = \frac{\text{CPU Time}_{\text{original}}}{\text{CPU Time}_{\text{new}}} \]`

Now, let's calculate:1. For
`\( p = 1 \)`:

Original CPU time:

`\[ \text{CPU Time}_{\text{original}} = ((2.56 * 10^9 * 1 + 1.28 * 10^9 * 12 + 256 * 10^6 * 5))/(2 * 10^9) \]`

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + 1.28 * 10^9 * 12 + 256 * 10^6 * 5))/(2 * 10^9) \]`

2. For
`\( p = 2 \)`:

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + (1.28 * 10^9 * 12)/1.4 + 256 * 10^6 * 5))/(2 * 10^9) \]`

3. For
`\( p = 4 \)`:

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + (1.28 * 10^9 * 12)/(2.8) + 256 * 10^6 * 5))/(2 * 10^9) \]`

4. For
`\( p = 8 \)`:

New CPU time:

`\[ \text{CPU Time}_{\text{new}} = ((2.56 * 10^9 * 2 + (1.28 * 10^9 * 12)/(5.6) + 256 * 10^6 * 5))/(2 * 10^9) \]`

Calculate the speedup for each case:

`\[ \text{Speedup} = \frac{\text{CPU Time}_{\text{original}}}{\text{CPU Time}_{\text{new}}} \]`

Now, let's calculate each speedup using the original and new CPU times:

`\[ \text{Speedup} = \frac{\text{CPU Time}_{\text{original}}}{\text{CPU Time}_{\text{new}}} \]`

1. For
`\( p = 1 \)`:

`\[ \text{Speedup}_(p=1) = \frac{\text{CPU Time}_{\text{original}}}{\text{CPU Time}_{\text{new}}, p=1} \]`

2. For
`\( p = 2 \)`:

`\[ \text{Speedup}_(p=2) = \frac{\text{CPU Time}_{\text{original}}}{\text{CPU Time}_{\text{new}}, p=2} \]`

3. For
`\( p = 4 \)`:

`\[ \text{Speedup}_(p=4) = \frac{\text{CPU Time}_{\text{original}}}{\text{CPU Time}_{\text{new}}, p=4} \]`

4. For
`\( p = 8 \)`:

`\[ \text{Speedup}_(p=8) = \frac{\text{CPU Time}_{\text{original}}}{\text{CPU Time}_{\text{new}}, p=8} \]`