Parallel Programming: for Multicore and Cluster Systems- P18: Innovations in hardware architecture, like hyper-threading or multicore processors, mean that parallel computing resources are available for inexpensive desktop computers. In only a few years, many standard software products will be based on concepts of parallel programming implemented on such hardware, and the range of applications will be much broader than that of scientific computing, up to now the main application area for parallel computing | 162 4 Performance Analysis of Parallel Programs Speedup and Efficiency The cost of a parallel program captures the runtime that each participating processor spends for executing the program. Cost of a Parallel Program The cost Cp n of a parallel program with input size n executed on p processors is defined by Cp n p Tp n . Thus Cp n is a measure of the total amount of work performed by all processors. Therefore the cost of a parallel program is also called work or processor-runtime product. A parallel program is called cost-optimal if Cp n T n . if it executes the same total number of operations as the fastest sequential program which has runtime T n . Using asymptotic execution times this means that a parallel program is cost-optimal if T n Cp n e 1 see Sect. for the definition . Speedup For the analysis of parallel programs a comparison with the execution time of a sequential implementation is especially important to see the benefit of parallelism. Such a comparison is often based on the relative saving in execution time as expressed by the notion of speedup. The speedup Sp n of a parallel program with parallel execution time Tp n is defined as Sp n T n Tin where p is the number of processors used to solve a problem of size n. T n is the execution time of the best sequential implementation to solve the same problem. The speedup of a parallel implementation expresses the relative saving of execution time that can be obtained by using a parallel execution on p processors compared to the best sequential implementation. The concept of speedup is used both for a theoretical analysis of algorithms based on the asymptotic notation and for the practical evaluation of parallel programs. Theoretically Sp n p always holds since for Sp n p a new sequential algorithm could be constructed which is faster than the sequential algorithm that has been used for the computation of the speedup. The new sequential algorithm is derived from the parallel .
