Parallel Computation with Serial Sections Model

• It is assumed (or known) that a fraction $f$ of the given task (computation) is not dividable into concurrent subtasks.
• The remaining part $(1-f)$ is assumed to be dividable into concurrent subtasks.
• The time required to execute the task on $n$ processors is
  $$t_p=t_s*f+(1-f)*(t_s/n)$$

• The speed-up factor is therefore given by

  $$S(n)=\frac{t_s}{t_s*f+(1-f)*(t_s/n)}=\frac{n}{1+(n-1)*f}$$ (3.4)

• According to this equation, the potential speed-up due to the use of $n$ processors is determined primarily by the fraction of code that cannot be divided.
• If the task (program) is completely serial, that is, $f=1$, then no speed-up can be achieved regardless of the number of processors used.

• This principle is known as Amdahl's law.
• It is interesting to note that according to this law, the maximum speed-up factor is given by
  $$lim_{n\rightarrow \infty} S(n)=\frac{1}{f}$$

• Therefore, the improvement in performance (speed) of a parallel algorithm over a sequential one is
  • limited not by the number of processors employed
  • but rather by the fraction of the algorithm that cannot be parallelized.
• According to Amdahl's law, researchers were led to believe that a substantial increase in speed-up factor would not be possible by using parallel architectures.
• NOT parallelizable;
  • communication overhead,
  • a sequential fraction, $f$