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

摘要

Multigrid methods are among the most efficient algorithms for solving discretized partial differentialequations. Typically, a multigrid system offers various configuration options to tune performance fordifferent applications and hardware platforms. However, knowing the best performing configuration inadvance is difficult, because measuring all multigrid system variants is costly. Instead of directmeasurements, we use machine learning to predict the performance of the variants. Selecting arepresentative set of configurations for learning is nontrivial, although, but key to prediction accuracy. Weinvestigate 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 configurationoptions and their interactions on the time to perform a multigrid iteration and relate this to existing domainknowledge. In an experiment on a multigrid system working on triangular grids, we found that combiningpair-wise sampling with the D-Optimal experimental design for selecting a learning set yields the mostaccurate predictions. After measuring less than 1 % of all variants, we were able to predict theperformance of all variants with an accuracy of 95.9 %. Furthermore, we were able to verify almost allknowledge on the performance behavior of multigrid methods provided by 2 experts.