Question

2. The formula for speed-up based on Amdhal's Law is given below. The below table shows the percentages of read section, initialization section, computation section, write back section, optimized section, and the required speed-up for different programs. Answer if the required speed-up can be achieved for each of the configuration given in the table. Torrected improvement factor Tunaffected Read Initialization Computation Write Required Speed-up Possible Yes/No ? Optimized section Computation Computation 20% 10% 10% 10% 50% 60% 20% 20% 2

Answer 1

Speed-up is given by 1 / [ (1-Fraction Enhanced) + (Fraction Enhanced/Speed Up Enhanced) ]

For Part 1:

Fraction Enhanced = Computation Part = 50%

Speed-Up Enhanced = Speed Up in the enhanced part = Speed up in the Computation part

Let the speed up enhanced be ∞ (infinite), to find the maximum speed up possible due to enhancing the computation part.

So, maximum speed up = 1 / [ (1-Fraction Enhanced) + (Fraction Enhanced/Speed Up Enhanced) ]

= 1 / [ (1-50%) + (50%/∞) ]

= 1/ [(1-50%) + 0] since for any finite whole number n, n/∞ is 0

= 2

The maximum speed up is 2, so a speed up of 3 is not possible.

For Part 2:

Fraction Enhanced = Computation Part = 60%

Speed-Up Enhanced = Speed Up in the enhanced part = Speed up in the Computation part

Let the speed up enhanced be ∞ (infinite), to find the maximum speed up possible due to enhancing the computation part.

So, maximum speed up = 1 / [ (1-Fraction Enhanced) + (Fraction Enhanced/Speed Up Enhanced) ]

= 1 / [ (1-60%) + (60%/∞) ]

= 1/ [(1-60%) + 0] since for any finite whole number n, n/∞ is 0

= 2.5

The maximum speed up is 2.5, so a speed up of 2 is possible.

To achieve a speed up of 2, let the speed up in computation part be s.

so, 2 = 1 / [ (1-60%) + (60%/s) ] following from Amdahl's Law

i.e., s = 6

i.e. if computation part is enhanced by a factor of 6, it will enhance the full program by a factor of 2.