Equal Duration Model

• In this model, it is assumed that a given task can be divided into $n$ equal subtasks, each of which can be executed by one processor.
• If $t_s$ is the execution time of the whole task using a single processor, then the time taken by each processor to execute its subtask is $t_p=t_s/n$.
• Since, according to this model, all processors are executing their subtasks simultaneously, then the time taken to execute the whole task is $t_p=t_s/n$.
• The speedup factor of a parallel system can be defined 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.

  $$S(n)=\frac{t_s}{t_p}=\frac{t_s}{t_s/n}=n$$ (3.1)

  
  

• The above equation indicates that, according to the equal duration model, the speedup factor resulting from using $n$ processors is equal to the number of processors used, $n$.
• One important factor has been overlooked in the above derivation. This factor is the communication overhead, which results from the time needed for processors to communicate and possibly exchange data while executing their subtasks.
• Assume that the time taken due to the communication overhead is called $t_c$ then the actual time taken by each processor to execute its subtask is given by

  $$S(n)=\frac{t_s}{t_p}=\frac{t_s}{t_s/n+t_c}=\frac{n}{1+n*t_c/t_s}$$ (3.2)

  
  

• The above equation indicates that the relative values of $t_s$ and $t_c$ affect the achieved speedup factor.
• A number of cases can then be studied:
  1. if $t_c \ll t_s$ then the potential speedup factor is approximately $n$
  2. if $t_c \gg t_s$ then the potential speedup factor is $t_s/t_c \ll 1$
  3. if $t_c = t_s$ then the potential speedup factor is $n/n+1 \cong 1$, for $n \gg 1$.
• In order to scale the speedup factor to a value between 0 and 1, we divide it by the number of processors, $n$. The resulting measure is called the efficiency, $E$.
• The efficiency is a measure of the speedup achieved per processor. According to the simple equal duration model, the efficiency $E$ is equal to 1 if the communication overhead is ignored.
• However if the communication overhead is taken into consideration, the efficiency can be expressed as

  $$E=\frac{1}{1+n*t_c/t_s}$$ (3.3)

  
  

• Although simple, the equal duration model is however unrealistic. This is because it is based on the assumption that a given task can be divided into a number of equal subtasks that can be executed by a number of processors in parallel.
• However, it is sufficient here to indicate that real algorithms contain some (serial) parts that cannot be divided among processors. These (serial) parts must be executed on a single processor.

  Figure 3.1: Example program segments.

  
• Consider, for example, the program segments given in Fig. 3.1. In these program segments, we assume that we start with a value from each of the two arrays (vectors) $a$ and $b$ stored in a processor of the available $n$ processors.
  • The first program block can be done in parallel; that is, each processor can compute an element from the array (vector) $c$. The elements of array $c$ are now distributed among processors, and each processor has an element.
  • The next program segment cannot be executed in parallel. This block will require that the elements of array $c$ be communicated to one processor and are added up there.
  • The last program segment can be done in parallel. Each processor can update its elements of $a$ and $b$.