search

jonas-schmitt / evostencils

Automating the Design of Multigrid Methods with Evolutionary Program Synthesis
GNU Affero General Public License v3.0
11 stars 4 forks source link

How extract optimal components from optimizer output? #2

Closed amkatrutsa closed 1 year ago

amkatrutsa commented 5 years ago

Hello! Could you please add in examples folder scripts that demonstrate the following 1) How to extract optimal components of multigrid method that were found by the genetic algorithm 2) How to compute the spectral radius of iteration matrix that is constructed with optimal components 3) General pipeline of using your tool: from initialization of the equation and initial multigrid components, then constructing optimizer and optimization process, and finally extraction of the optimal components (smoothers, restriction and prolongation matrices, etc...) and compute the optimized spectral radius. The last step proves that found components really provide better convergence.

Thanks in advance!

jonas-schmitt commented 5 years ago

Hi, I'm aware of that that there is very few documentation right now and I will try to address your issues step by step when I have a little bit of time left. Still here a brief explanation about the individual points:

  1. The optimized multigrid method is represented in form of a single expression (you can find the respective data structures in expressions/base.py and expressions/multigrid.py). All steps of evaluation and code generation are performed by transforming or analyzing these data structures.
  2. This is done by transforming a multigrid expression to an LFA Lab expression, whose symbol and spectral radius can then be automatically computed. This happens in the evaluation/convergence.py. In general the iteration matrix can be simply obtained by replacing each occurrence of the right hand side by zero and of the current solution by the unit matrix.
  3. As the evaluation of the spectral radius is only feasible for a hierarchy of at most three grids, we split the optimization into multiple runs. Starting on the coarsest grid, we recursively evolve a multigrid method as coarse grid solver for the next finer levels. This means for example that if we want to optimize on a level range of [3,7], we first evolve a three grid method in the range [3,5], which then acts as a coarse grid solver for the second optimization run on the range [5,7]. Each optimization run consists of the following steps:
    1. A multi-objective optimization (NSGA-II) is performed to derive multigrid expressions that are pareto-optimal with respect to the spectral radius of their iteration matrix and their runtime per iteration according to a roofline model.
    2. We generate an ExaSlang Layer 3 program for each pareto-optimal multigrid expressions, which we then run on the target platform to obtain the fastest solver (time to solution is the metric) on the target platform.
    3. We optimize the relaxation parameters of the fastest solver using CMA-ES based on the measured convergence factor of the generated program for an instance of the problem that we want to solve. Here we directly adjust the relaxation parameters in the C++ program that ExaStencils generates, which means that we just have to recompile the executable for each different set of parameter values using our favourite C++ compiler.
    4. Finally, we generate an ExaSlang Layer 3 program with the optimal set of relaxation parameters.

You can also take a look at my slides for Copper Mountain: https://easychair.org/smart-slide/slide/7g69# I hope this helps!