Equal Duration Model

Assume that a given computation can be divided into concurrent tasks for execution on the multiprocessor.

• In this model ($t_s$: execution time of the whole task using a single processor),
  • a given task can be divided into $n$ equal subtasks,
  • each of which can be executed by one processor,
  • the time taken by each processor to execute its subtask is
    $$t_p=\frac{t_s}{n}$$

  • since all processors are executing their subtasks simultaneously, then the time taken to execute the whole task is
    $$t_p=\frac{t_s}{n}$$

• The speed-up factor of a parallel system can be defined as
  • the ratio between the time taken by a single processor to solve a given problem
  • to the time taken by a parallel system consisting of $n$ processors to solve the same problem.

• Speed Up;

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

• This equation indicates that, according to the equal duration model, the speed-up factor resulting from using $n$ processors is equal to the number of processors used ($n$).
• One important factor has been ignored in the above derivation.
• This factor is the communication overhead, $t_c$, which results from the time needed for processors to communicate and possibly exchange data while executing their subtasks.
• 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)

• This equation indicates that the relative values of $t_s$ and $t_c$ affect the achieved speed-up factor.

• A number of cases can then be studied:
  1. if $t_c \ll t_s$ then the potential speed-up factor is approximately $n$
  2. if $t_c \gg t_s$ then the potential speed-up factor is $t_s/t_c \ll 1$
  3. if $t_c = t_s$ then the potential speed-up factor is $n/n+1 \cong 1$, for $n \gg 1$.
• In order to scale the speed-up 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 speed-up 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.
• However, 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.

  

• In Figure 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$.