Next: Exercises
Up: 3 A Quantitative Basis for Design
Previous: 3.9 Case Study: ShortestPath Algorithms
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.
Next: Exercises
Up: 3 A Quantitative Basis for Design
Previous: 3.9 Case Study: ShortestPath Algorithms
© Copyright 1995 by Ian Foster