Speedup Amdahl Gustafson

Question 1

What is scalability in prallel programming?

Answer 1

• speedup when we increase number of processors
• what happens if we have infite processors
• linear speed up is the wish

Question 2

Define parallel Speedup.

Answer 2

Speedup Sp on p CPU’S –> Sp = T1/Tp

(informally: time on one processor / time on p processors)

Question 3

Define Efficiency with Sp and p.

Answer 3

Efficiency: Sp / p

(informally: Speedup / number of processors)

Question 4

Why is Sp < p in the normal case?
Means that the speedup is not linear to the amount of processors.

Answer 4

• Programs may not contain enough parallelism
• overheads introduced by parallelization
• architectural limitations

Question 5

Assume Parallel program:

• sequential part: 20%
• parallel part: 80% (assume it scales linearly)
• T1 = 10

Answer 5

see picture

Question 6

Formula for Efficiency

Answer 6

Ep = Sp / p

Question 7

Formula Speedup

Answer 7

Sp = T1 / Tp

Question 8

Gives the ingrediants to Amdahl’s Law. First define Sp without using f. Thand use f as non parallizible part.

Answer 8

Amdahls law gives a bound on speedup.

Speedup is Sp := T1 / Tp

T1 := Wser + Wpar (W for work)
Tp ≥ Wser + (Wpar / P) (P number of processors)

Hence we have:
Sp ≤ (Wser + Wpar) / (Wser + (Wpar / P))

NOW using f for nonparallizible part:

Wser = f\*T1
Wpar = (1-f)\*T1

Sp ≤ 1 / (f + ( (1-f) / P)

Question 9

Give Amdahls Law formula.
First for Wser than for Wpar and than for Sp using f.

Answer 9

Wser = f\*T1
Wpar = (1-f)\*T1

Sp ≤ 1 / (f + ( (1-f) / P)

Question 10

What is a takeaway of Amdahls Law

Answer 10

all non- parallel parts of a program (no matter how small) can cause problems for scalability

Question 11

What is the difference to Amdahls Law using Gustafsons Law? IMPORTANT

Answer 11

The time stays the same when thinking about Gustafsons Law.

Even if more processors are used the runtime stays the same.
More processors allow to solve larger problems in the same time.

Question 12

What is the formula to Gustafsons Law. Give Sp

Answer 12

f := sequential part

Sp = f + p( 1 - f) = p - f ( p - 1 )

Question 13

Which law is used when talking about the pessimistic case?

Answer 13

Admhahl’s Law

Question 14

Which law is used when talking about the optimistic case?

Answer 14

Gustafson’s Law

Question 15

Which law is used when talking about constant work?

Answer 15

Amdahl’s Law

Question 16

Which law is used when talking about constant time?

Answer 16

Gustafson’s Law

Question 17

Which law is used when talking about the worst case?

Answer 17

Amdahl’s Law

Question 18

With wich law is linear speedup possible only theoretically? And why?

Answer 18

With Gustafson’s Law since the time to perform the taks stays the same using more processors