Multigrid methods have many parameters that influence the execution time of the method. To identify a good parameter configuration, we need to predict the execution time of the method for various parameter configurations.
It is not sufficient to predict the time of the individual operations that a method performs, but it is also necessary to predict their number. Multigrid methods are iterative, i.e., they compute a sequence of iterations that converge towards the solution sought. The number of iterations needed to reach a certain accuracy depends on the convergence rate of the method.
The parameters of a Multigrid method influence its convergence rate. The convergence rate is not available directly, but it can be estimated using local Fourier analysis.
As part of project ExaStencils, we developed LFA Lab, a flexible software library that performs a local Fourier analysis. LFA Lab takes as input the formula for the error propagator of the method and a description of the operations involved in this formula. Using this information, LFA Lab is able to predict the convergence rate of a given multigrid method.
By combining the convergence rate estimate with a performance model, it becomes possible to predict the execution time of a multigrid method for a given parameter configuration. This knowledge can then be used to identify an optimal parameter configuration.