Performance Analysis

Question 1

What is speedup?

Answer 1

S_p(n) = T_s(n)/ T_p(n)
A measure of how much faster a program runs on parallel compared to serial.

Question 2

What is cost?

Answer 2

C_p(n) = pT_p(n)
Measure of total amount of work performed by all processors

Question 3

What is efficiency?

Answer 3

E_p(n) = S_p(n)/p = T_s/(pT_p)
In ideal case it should equal 1

Question 4

What is the effect of overhead?

Answer 4

• Cost will be be more than serial run time
• Speedup will be less than p
• Efficiency will be less than 1

Question 5

How does overhead affect parallel run time and efficiency?

Answer 5

T_p = T_s/p + T_overhead
Efficiency decreases as number of processes increases as there is more overhead from each process.

Question 6

What does the parallel runtime comprise of?

Answer 6

• Local computation runtime
• Runtime of the exchange of data between processors
• Runtime of the synchronisation of the processors when accessing shared data
• Waiting time due to unequal load distribution / waiting to access shared data

Question 7

What is Amdahl’s Law?

Answer 7

When a fraction r of a parallel program must be executed sequentially then the speedup is:
S_p = 1/(r + (1-r)/p)
Which will always be <= 1/r

Question 8

What is scalability? What does it mean for a program to be scalable?

Answer 8

Scalability captures the performance behaviour for an increasing number of processors.
A program is scalable if the efficiency remains constant if the number of processors and the problem size are increased

Question 9

What is a limitation of Amdahl’s Law?

Answer 9

The law cannot capture the increase in speedup for increasing problem size

Question 10

What is Gustafson’s Law?

Answer 10

The behaviour of the special case that the sequential program part has a constant execution time.
Let the constant execution time be c, and t_p(n,p) be be the execution time of the parallelizable part of the program.
S_p = (c + t_p(n,1))/(c + t_p(n,p))
If the parallel part is perfectly parallelizable then t_p(n,p) = (T_s - c)/p

Question 11

What is the difference between strongly scalable and weakly scalable?

Answer 11

If the efficiency stays constant when increasing the number of processors -> strongly scalable
If the efficiency stays constant when both the number of processors and the problem size increase -> weakly scalable