Performance-influence models of multigrid methods: A case study onrntriangular grids

摘要

Multigrid methods are among the most efficient algorithms for solving discretized partial differentialrnequations. Typically, a multigrid system offers various configuration options to tune performance forrndifferent applications and hardware platforms. However, knowing the best performing configuration inrnadvance is difficult, because measuring all multigrid system variants is costly. Instead of directrnmeasurements, we use machine learning to predict the performance of the variants. Selecting arnrepresentative set of configurations for learning is nontrivial, although, but key to prediction accuracy. Werninvestigate different sampling strategies to determine the tradeoff between accuracy and measurement effort. In a nutshell, we learn a performance-influence model that captures the influences of configurationrnoptions and their interactions on the time to perform a multigrid iteration and relate this to existing domainrnknowledge. In an experiment on a multigrid system working on triangular grids, we found that combiningrnpair-wise sampling with the D-Optimal experimental design for selecting a learning set yields the mostrnaccurate predictions. After measuring less than 1 % of all variants, we were able to predict thernperformance of all variants with an accuracy of 95.9 %. Furthermore, we were able to verify almost allrnknowledge on the performance behavior of multigrid methods provided by 2 experts.