Speedup definition and solved example in Parallel Algorithm

To evaluate the performance gain achieved by parallelizing a given application over a sequential implementation, speedup is the measure that gives this relative benefit of solving a problem in parallel. Speedup of a system is defined as the ratio of the time taken to solve a problem on a single processing element to the time required to solve the same problem on a parallel computer with p identical processing elements. We denote speedup by the symbol S. Observed speedup of a algorithm which has been parallelized, defined as:

              wall-clock time of serial execution
S =       ——————————————-
wall-clock time of parallel execution

 or

                        T (n, 1)                           T_s
S(n, p) =        ———–            =           ——
T (n, p)                              T_p

Where, T_s is the execution time taken to perform the computation on one processor and T_p is the execution time needed to perform the same computation using p processors.

Note that T(n,1) is taken to be the running time of the best sequential algorithm and not the running time of the parallel algorithm when running on one processor, In particular, we do not obtain T(n, 1) by substituting p = 1 in T(n, p).

Example:

Figure: Depth First Search

Time taken of the best sequential algorithm when one processing element is used [T(n, 1)] = 14t_c
Time taken of the parallel algorithm when two processing element is used [T(n, 2)] = 5t_c
Hence, The speedup of the system (S) = [T(n, 1)] / [T(n, 2)]
= 14t_c / 5t_c = 2.8

It is fair to evaluate the performance of parallel computation with respect to the farthest sequential algorithm for solving the same problem in single-processing element architecture. The maximum speedup value can be achieved where there is no communication overhead and the workload of all the processors is balanced. In such a system, every processor requires T(n,1) / p units time to complete its task, so the speedup value will be;

                         T (n, 1)                            T (n, 1)
S(n, p) =        ———–            =         ————–      = p
T (n, p)                             T (n, 1)/p

There is a very simple reason behind the speedup value cannot be higher than p. In such a case, all the processors could be emulated by a single sequential one obtaining a serial execution time lower than T(n,1). But this is not possible because T(n,1) represent the execution time of the fastest sequential algorithm.