Performance‐influence models of multigrid methods: A case study on triangular grids. (26th January 2017)

• Record Type: Journal Article
• Authors: Grebhahn, Alexander; Rodrigo, Carmen; Siegmund, Norbert; Gaspar, Francisco J.; Apel, Sven
• Other Names: Lengauer Christian guestEditor.; Bolten Matthias guestEditor.; Falgout Robert guestEditor.; Schenk Olaf guestEditor.; Zhou Xiaobo guestEditor.; Zhao Laiping guestEditor.
• Is Part Of: Concurrency and computation. Volume 29:Number 17(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-01-26
• Subjects: configurable systems -- multigrid method -- performance prediction -- sampling -- SPL Conqueror -- triangular grids; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4057
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Multigrid methods are among the most efficient algorithms for solving discretized partial differential equations. Typically, a multigrid system offers various configuration options to tune performance for different applications and hardware platforms. However, knowing the best performing configuration in advance is difficult, because measuring all multigrid system variants is costly. Instead of direct measurements, we use machine learning to predict the performance of the variants. Selecting a representative set of configurations for learning is nontrivial, although, but key to prediction accuracy. We investigate 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 configuration options and their interactions on the time to perform a multigrid iteration and relate this to existing domain knowledge. In an experiment on a multigrid system working on triangular grids, we found that combining pair‐wise sampling with the D‐Optimal experimental design for selecting a learning set yields the most accurate predictions. After measuring less than 1 % of all variants, we were able to predict the performance of all variants with an accuracy of 95.9 %. Furthermore, we were able to verify almost all knowledge on the performance behavior of multigrid methods provided by 2 experts.