A performance model for Krylov subspace methods on mesh-based parallel computers

We develop a performance model for Krylov subspace methods implemented on distributed memory parallel computers for which the underlying communication network is a two-dimensional mesh. The model is based on the runtime of a single iteration or cycle of iterations (for methods like GMRES(m)), because the iteration count is problem dependent. Moreover, we intend to use the model only for parallel implementations that do not change the mathematical properties of the method (significantly). The main purpose of this model is a qualitative analysis of the performance; the model is not meant for very accurate predictions. We express the efficiency, speed-up, and runtime as functions of the number of processors scaled by the number of processors that gives the minimal runtime for the given problem size (P-max). This provides a natural way to analyze the performance characteristics for the range of the numbers of processors that can be used effectively. The approach is particularly interesting because it turns out that the performance is characterized completely by the sequential runtime and P-max. The efficiency as a function of the number of processors relative to P-max is independent of the problem size and parameters describing the machine and solution method. Analogous relations can be obtained for the speed-up and runtime. P-max itself, of course, depends on N and the other parameters, and a simple equation for P-max is given. The performance model is also used to evaluate the improvements in the performance if we reduce the communication as described in [7,9,8]. Although the scope of the performance model is limited by assumptions on the load balance and the processor grid, there are several obvious generalizations. One important and straightforward generalization is to higher dimensional meshes. We will discuss such generalizations at the end of this article.