3.10 Summary

In this chapter, we have seen how to develop mathematical performance models that characterize the execution time, efficiency, and scalability of a parallel algorithm in terms of simple parameters such as problem size, number of processors, and communication parameters. We have also seen how these models can be used throughout the parallel program design and implementation cycle:

 
• Early in the design process, we characterize the computation and communication requirements of our parallel algorithms by building simple performance models. These models can be used to choose between algorithmic alternatives, to identify problem areas in the design, and to verify that algorithms meet performance requirements.

• Later in the design process, we refine our performance models and conduct simple experiments to determine unknown parameters (such as computation time or communication costs) or to validate assumptions. The refined models can be used to increase our confidence in the quality of our design before implementation.

• During implementation, we compare the performance of the parallel program with its performance model. Doing this can help both to identify implementation errors and to improve the quality of the model.

A performance model gives information about one aspect of an algorithm design: its expected parallel performance. We can use this information, when it is combined with estimates of implementation cost, etc., to make informed choices between design alternatives.