In this chapter we will examine the gap between the expected execution time of a parallel algorithm and the actual running time achieved by executing its encoding as a ParC
program in an actual shared memory machine. Though there is such a gap for sequential programs, it is more problematic with parallel programs where users often encounter cases of parallel programs that fail to run fast enough or as fast as expected. In particular, a parallel program that runs on a parallel machine with P
processors is expected to run about P
times faster than its sequential version. There are two issues involved with this problem:
Determining the execution time of a parallel program and comparing it with a desired execution time.
If there is a significant gap between the two, we need to identify which factors in the parallel program should be corrected so that the performance is improved.