Performance Metric

Only for homogenous devices. (The first 2 chapters in DAO)

Scaling

Strong Scaling: total problem size stays the same as the number of processors increases

Weak Scaling: the problem size increases at the same rate as the number of processors, keeping the amount of work per processor the same

“The performance improvement to be gained by parallelisation is limited by the proportion of the code which is serial.” -- Gene Amdahl, 1967

Speed-up ratio = T_before / T_after = (T_seq + T_p) / (T_seq + T_p / N) = 1 / (a + (1-a) / N)

Undergrad courses teach this.

The prerequisite of Amdahl's law is that the dataset volumn is fixed which is absolutely uncommon.

Gustafson's Law uncovers that with larger amount of dataset, the speed-up ratio grows(still limited by the upper bound).

let a_seq = t_seq / (t_seq + t_par) s = (t_seq + N * t_par) / (t_seq + t_par) = a_seq + N x a_par

Gustafson's Law assumes that a_seq is fixed. Therefore to increase s, we must increase either N or a_par.

Load imbalance factor

LIF = max load / avg load