Toward transparent and parsimonious methods for automatic performance tuning
Vers des méthodes transparentes et parcimonieuses pour l’optimisation automatique des performances
Résumé
The end of Moore's Law and the breakdown of Dennard's scaling mean that increasing hardware complexity and optimizing code efficiently are indispensable to maintain the exponential performance improvements of the past decades. Hand optimizing code is not suited to the sheer number of configurations of many code optimization problems, but fitting these problems into the mathematical optimization and learning frameworks enables applying methods from these domains to automatically optimize code for performance, a process called autotuning. Commonly used autotuning methods are either not conducive to statistical analysis, such as genetic algorithms, or reliant on restrictive hypotheses about the target search space, such as gradient descent. In this thesis we develop and evaluate the performance of an autotuning method based on the Design of Experiments, a branch of statistics that is not widely studied or applied in autotuning problems, and which aids in the parsimonious production of statistically interpretable and accurate surrogate models.
We present a series of descriptions and discussions of various optimization methods, from the perspective of performance tuning. We describe heuristics from mathematical optimization, and parametric and nonparametric statistical modeling methods, describing how these surrogate models can be used to minimize an unknown function. We then discuss how the Design of Experiments enables managing the compromise between experimental budget and model quality, establishing a link with Online Learning methods, focusing on parsimony, progressive model improvement, uncertainty, and robustness, the properties that are most relevant for a method's applicability to autotuning problems.
The key contribution of this thesis is the development of a transparent and parsimonious autotuning approach based on the Design of Experiments, which we apply to diverse problems such as optimizing the configuration of GPU and CPU kernels and finding mixed-precision bit quantization policies for neural networks. We also present a series of empirical evaluations of other methods on autotuning problems from different High Performance Computing domains, such as search heuristics coordinated by a bandit algorithm to optimize the configuration of compilers for several GPU and FPGA kernels. Although some experimental scenarios eluded the detection and exploitation of search space structure, regardless of the chosen method, we demonstrate how autotuning methods based on the Design of Experiments can aid in interpretable, efficient, and effective code optimization.
La fin de la loi de Moore et de la loi de Dennard entraînent une augmentation de la complexité du matériel informatique qui implique d'adapter et d'optimiser les codes scientifiques très régulièrement. Une optimisation manuelle de code n'est pas adaptée en raison du nombre considérable de configurations, mais en se plaçant dans le cadre de l'optimisation mathématique et de l'apprentissage, il est possible d'appliquer des méthodes issues de ces domaines pour optimiser automatiquement les performances des codes scientifiques, un processus appelé autotuning. Cependant, les méthodes d'autotuning couramment utilisées sont souvent peu propices à l'analyse statistique, comme les algorithmes génétiques, ce qui rend leur résultat difficile à interpréter, ou dépendantes d'hypothèses restrictives sur l'espace de recherche, comme la descente de gradient, ce qui peut conduire à des solutions sous-optimales. Dans cette thèse, nous développons et évaluons la performance d'une méthode d'autotuning utilisant des plans d'expériences, une branche des statistiques qui a encore été peu utilisée dans ce contexte, et qui a pour objectif de produire des modèles interprétables et précis tout en restant parcimonieux sur le plan expérimental.
Cette thèse commence par une présentation des principales méthodes d'optimisation et d'apprentissage. Nous décrivons en particulier les principales heuristiques issues de l'optimisation mathématique, les méthodes de modélisation statistique paramétriques et non paramétriques ainsi que comment ces modèles peuvent être utilisés pour minimiser une fonction inconnue (surrogate optimization), puis nous expliquons en quoi les techniques de plan d'expériences permettent de contrôler le compromis entre le budget expérimental et la qualité du modèle, et enfin, nous faisons le lien avec les techniques d'apprentissage en ligne, en nous concentrant sur les propriétés les plus importantes (parcimonie, transparence, incrémentalité, confiance, robustesse) pour leur applicabilité aux problèmes d'autotuning.
La principale contribution de cette thèse est le développement d'une approche d'auto-tuning transparente et parcimonieuse basée sur les plan d'expériences. Nous appliquons cette approche à différents problèmes comme l'optimisation de la configuration de noyaux GPU et CPU, et la discrétisation de la précision numérique dans des réseaux de neurones. Nous évaluons également empiriquement d'autres méthodes (par exemple des heuristiques de recherche coordonnées par un algorithme de bandit) sur des problèmes d'optimisation de configuration de compilateurs pour des noyaux de calcul sur GPU et sur FPGA. Même s'il n'est pas possible de détecter et d'exploiter la structure de l'espace de recherche en toute généralité, nous montrons comment les méthodes d'autotuning basées sur des plans d'expériences peuvent permettre de réaliser une optimisation de code à la fois interprétable, efficace, et peu coûteuse sur le plan expérimental.
Origine : Fichiers produits par l'(les) auteur(s)