For many linear and nonlinear systems that arise from the discretization of partial differential equations the construction of an efficient multigrid solver is a challenging task. Here we present a novel approach for the optimization of geometric multigrid methods that is based on evolutionary computation, a generic program optimization technique inspired by the principle of natural evolution. A multigrid solver is represented as a tree of mathematical expressions which we generate based on a tailored grammar. The quality of each solver is evaluated in terms of convergence and compute performance using automated local Fourier analysis (LFA) and roofline performance modeling, respectively. Based on these objectives a multi-objective optimization is performed using strongly typed genetic programming with a non-dominated sorting based selection. To evaluate the model-based prediction and to target concrete applications, scalable implementations of an evolved solver can be automatically generated with the ExaStencils framework. We demonstrate our approach by constructing multigrid solvers for the steady-state heat equation with constant and variable coefficients that consistently perform better than common V- and W-cycles.
翻译:对于部分差异方程式离散产生的许多线性和非线性系统而言,建造高效的多电格求解器是一项具有挑战性的任务。在这里,我们介绍了一种基于进化计算、一种受自然进化原则启发的通用程序优化技术的优化几何多格方法的新颖方法。多格求解器代表着一棵我们根据量身定制的语法生成的数学表达方式的树。每个求解器的质量分别用自动的本地Fourier分析(LFA)和屋顶性能模型来从趋同和计算性能的角度进行评估。基于这些目标,采用非主排序法选择的强烈打字的遗传程序进行多目标优化。为了评估基于模型的预测并针对具体应用,可以用ExaStencils框架自动生成进化的进化求解器的可缩放实施。我们展示了我们的方法,即为稳定状态的热方程式建造多格求解器,其常值和可变系数比通用的V和W周期更好。