Amdahl's Law

• We defined the speedup factor of a parallel system as the ratio between the time taken by a single processor to solve a given problem instance to the time taken by a parallel system consisting of $n$ processors to solve the same problem instance (see Eqn. 3.4).
• Similar to Grosch's law, Amdahl's law made it so pessimistic to build parallel computer systems due to the intrinsic limit set on the performance improvement (speed) regardless of the number of processors used.
• An interesting observation to make here is that according to Amdahl's law, $f$ is fixed and does not scale with the problem size, $n$. However, it has been practically observed that some real parallel algorithms have a fraction that is a function of $n$. Let us assume that $f$ is a function of $n$ such that $lim_{n\rightarrow \infty} f(n)=0$

  $$lim_{n\rightarrow \infty} S(n)=lim_{n\rightarrow \infty} \frac{n}{1+(n-1)*f(n)}=n$$ (3.7)

  
  

• This is clearly in contradiction to Amdahl's law. It is therefore possible to achieve a linear speedup factor for large-sized problems, given that $lim_{n\rightarrow \infty} f(n)=0$, a condition that has been practically observed.
• For example, researchers at the Sandia National Laboratories have shown that using a 1024-processor hypercube multiprocessor system for a number of engineering problems, a linear speedup factor can be achieved.
• Consider, for example, the well-known engineering problem of multiplying a large square matrix $A(m \times m)$ by a vector $X(m)$ to obtain a vector, that is, $C(m)$. Assume further that the solution of such a problem is performed on a binary tree architecture consisting of $n$ nodes (processors).
  • Initially, the root node stores the vector $X(m)$ and the matrix $A(m \times m)$ is distributed row-wise among the $n$ processors such that the maximum number of rows in any processor is $m/n+1$.
  • A simple algorithm to perform such computation consists of the following three steps:
    1. The root node sends the vector $X(m)$ to all processors in $O(m*log n)$
    2. All processors perform the product $C_i=\sum_{j=1}^m a_{ij}*x_j$ in
       $$O(m*(m/n+1))=O(m)+O(\frac{m^2}{n})$$

    3. All processors send their $C_i$ values to the root node in $O(m*log n)$.
  • According to the above algorithm, the amount of computation needed is
    $$O(m*log n)+O(m)+O(\frac{m^2}{n})+O(m*log n)=O(m^2)$$

  • The indivisible part of the computation is equal to
    $$O(m)+O(m*log n)$$

  • Therefore, the fraction of computation that is indivisible
    $$f(m)=\frac{(O(m)+O(m*log n))}{O(m^2)}=O(\frac{(1+log n)}{m})$$

  • Notice that $lim_{m\rightarrow \infty} f(m)=0$. Hence, contrary to Amdahl's law, a linear speedup can be achieved for such a large-sized problem.
• It should be noted that in presenting the above scenario for solving the matrix vector multiplication problem, we have assumed that the memory size of each processor is large enough to store the maximum number of rows expected.
• This assumption amounts to us saying that with $n$ processors, the memory is $n$ times larger. Naturally, this argument is more applicable to message passing parallel architectures than it is to shared memory ones.