Consider a parallel algorithm for a problem of size N with P threads. The parallel algorithm has the following measured running times (ms):
N=10 N=100 N=1000
P = 1: 3.45 45.2 472 P = 2: 1.81 24.86 271.4
P = 4: 0.99 14.69 171.1
P = 8: 0.58 9.605 120.95
i) What are the corresponding speed-ups and efficiencies?
ii) Does this algorithm satisfy strong or weak scalability or none? Explain why.
iii) Use Amdahl’s law to infer the percentage of parallelizable portion of the algorithm. Explain your derivation.