4. Parallel Computing 14. Introduction

14.9  Speedup and Efficiency

The speedup of a parallel computation is the ratio of the sequential execution time to the

parallel execution time for the same problem. Conventions vary as to whether the same

algorithm has to be used in both time computaions. The most fair comparison is probably

to compare the speed of the parallel algorithm to that of the best-known sequential

algorithm.

An ideal speedup factor would be equal to the number of processors, but rarely is this

achieved. The reasons that prevent it from being achieved are: (i) not all problems lend

themselves to parallel execution; some are inherently sequential, and (ii) there is

overhead involved in creating parallel tasks and communicating between them.

The idea of efficiency attempts to measure overhead; it is defined as the amount of work

actually done in a parallel computation divided by the product of the run-time and the

number of processors, the latter product being regarded as the effort

A thorough study of speedup issues is beyond the scope of this book. Suffice it to say that

difficulty in attaining acceptable speedup on a large class of problems has been one of the

main factors in the slow acceptance of parallel computation. The other factor is the extra

programming effort typically required to achieve parallel execution. The next chapter

mentions Amdahl’s law, which is one attempt at quantifying an important issue, namely

that some algorithms might be inherently sequential.