maximum speed up achieved

Question

If only 80% of the execution time of the application could run in parallel, what is the maximum speedup you could achieve?

I did something like this,

1-.8 = .2 
overall speedup = 1/0.2 = 5

I am not sure weather I attempted right or wrong? Please clarify.

Answer 1

You need to take that 20% as constant because it needs serial execution.

Also have in mind that Sp depends on number of processors. ALWAYS. We can do theorics because N of processors is a 'known' variable . But more processors also bring with them less 'ideality'. What results on a higher error when you increase the number of processors. Ideal is a linear function (Sp/p), in reality it is not.

All parallel programs contain:

• Parallel sections
• Serial sections

Serial sections limit the parallel effectiveness

Amdahl’s Law states this formally: Effect of multiple processors on speed up

Sp = Ts/Tp <= 1/(fs + (fp/p))

• Sp: execution time of secuential algorithm
• Tp: execution time of parallel algorithm
• fs: serial fraction of the code
• fp: parallel fraction of the code
• p: number of processors

so in your case

Sp will be minor or equal to:

1/(0.2 + 0.8/p)

What resuts in max Sp:

2 proccessors: 1,666

4 processors: 2,5 ... .