ABSTRACT
Before undertaking the task of writing a parallel program, which may require a significant amount of effort, it is important to consider what one wishes to gain from the parallel implementation. Is a shorter time to solution the only requirement? Or should the parallel program also be able to tackle larger problem sizes, use a large number of processes, and run with high parallel efficiency to avoid wasting computing resources? In general, parallel execution of a given computational problem can be achieved in multiple ways, and the optimal solution may depend on factors such as the range of problem sizes that will be targeted, the number of processes that will be used, the amount of memory available, and the performance characteristics of the communication network. It is therefore important to take these factors into consideration in the design phase so that the parallel algorithm can be tailored for high performance under the circumstances likely to be encountered in practice. The design process may involve prioritizing performance characteristics, such as whether to minimize the operation count, the memory requirement, or the communication overhead, and then making tradeoffs based on the priorities. For instance, it may be possible to reduce the memory requirement or the communication overhead by allowing some redundant computation.
