Toward transparent and parsimonious methods for automatic performance tuning

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 (surrogateoptimization), 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, 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'autotuning transparente et parcimonieuse basée sur les plans 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 decompilateurs 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.The end of Moore's Law and the breakdown of Dennard's scaling mean thatincreasing hardware complexity and optimizing code efficiently are indispensableto maintain the exponential performance improvements of the past decades. Handoptimizing code is incompatible with the sheer number of configurations of manycode optimization problems, but fitting these problems into the mathematicaloptimization and learning frameworks enables applying methods from these domainsto automatically optimize code for performance, a process called autotuning.Commonly used autotuning methods are either not conducive to statisticalanalysis, such as genetic algorithms, or reliant on restrictive hypotheses aboutthe target search space, such as gradient descent. In this thesis we developand evaluate the performance of an autotuning method based on the Design ofExperiments, a branch of statistics that is not widely studied or applied inautotuning problems, and which aids in the parsimonious production ofstatistically interpretable and accurate surrogate models.We present a series of descriptions and discussions of various optimizationmethods, from the perspective of performance tuning. We describe heuristicsfrom mathematical optimization and parametric and nonparametric statisticalmodeling methods, describing how these surrogate models can be used to minimizean unknown function. We then discuss how the Design of Experiments enablesmanaging 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 thatare most relevant for a method's applicability to autotuning problems.The key contribution of this thesis is the development of a transparent andparsimonious autotuning approach based on the Design of Experiments, which weapply to diverse problems such as optimizing the configuration of GPU and CPUkernels and finding mixed-precision bit quantization policies for neuralnetworks. We also present a series of empirical evaluations of other methods onautotuning problems from different High Performance Computing domains, such assearch heuristics coordinated by a bandit algorithm to optimize theconfiguration of compilers for several GPU and FPGA kernels. Although someexperimental scenarios eluded the detection and exploitation of search spacestructure, regardless of the chosen method, we demonstrate how autotuningmethods based on the Design of Experiments can aid in interpretable, efficient,and effective code optimization