Performance

Question 1

Speedup

Answer 1

• How much faster the program suns on p proceesses than on 1 process

Sp(n) = Ts(n)/Tp(n)

Question 1

Cost

Answer 1

• Total amount of work perfomancee by all processors p

Cp(n) = p x Tp(n)

Question 2

Efficiency

Answer 2

Captures the fraction of time for which a processor is usefully employed

Ep(n) = Sp(n)/p = (Ts(n)/Tp(n))/p = Ts(n)/(p x Tp(n)) = Ts(n)/Cp(n)

Question 3

Effect of overhead

Answer 3

• Cost > Serial Run time
• Speedup < p
• Efficiency < 1
• Comes from messages sentt tying to communicate with MPI

Ideal

Tp(n) = Ts(n) / p

Typical

Tp(n) = Ts(n)/p + Toverhead

Question 4

Amdahl’s Law

Answer 4

• If a fraction of our program stays serial speedup < 1/r

Sp = Ts / (r x Ts(n) + (((1 - r) x Ts(n)) / p)

Question 5

Limitations of Amdahl’s Law

Answer 5

• An increase in the speedup of a program for increasing problem size n cannot be captured by Amdahl’s law
• Amdahl’s law assumes that the sequential part of the program is a constant fraction of the total problem
  size, e.g., for r = 10%n

Question 6

Gustafson’s Law

Answer 6

• Assumes the sequential part of the program does not increase as the size of the program increases so it is a constant and not a constant percentage

Sp(n) = (C + tp(n, 1)) / (C + tp(n, p))

C = Constant executiion time of the sequential part of the program
tp(n, p) = Execution time of the parrellisable part of the program

tp(n, 1) = Ts(n) - C (if the parallel part is perfectly parallisable)
tp(n, p) = (Ts(n) - C) / p

Sp(n) = (C + Ts(n) - C) / (C + (Ts(n) - C) / p) = (C / (Ts(n) - C) + 1) / (C / (Ts(n) - C) + 1/p)

Question 7

Scalability

Answer 7

A problem is scalable if it can handle ever increasing problem sizes

Ts = n = problem size
Tp = n/p + 1; the program has a fixed overhead of 1, independent of the problem size

Then

E = Ts / (p x Tp) = n / (p x (n/p + 1)) = (v x n) / (v x n + k x p)

Question 8

Strongly Scalable

Answer 8

If, when we increase the number of processes/ threads, the efficiency stays more or less the same
without increasing the problem size, the program is said to be strongly scalable.

Question 9

Weakly Scalable

Answer 9

If the efficiency stays more or less the same when we increase the problem size at the same rate as
the number of processes/ threads, then the program is said to be weakly scalable.