Machine learning for performance modelling on colossal software configuration spaces

La soutenance de thèse d'Hugo MARTIN, équipe DiverSE, se déroulera le jeudi 16 Décembre 2021 à 10h00 en salle Métivier.

Machine Learning for Performance Modelling on Colossal Software Configuration Spaces.

(English version below)

Presque tous les systèmes logiciels d’aujourd’hui sont configurables. A l’aide d’options, il est possible de modifier le comportement de ces systèmes, d’ajouter ou d’enlever certaines capacités pour améliorer leurs performances ou les adapter à différentes situations. Chacune de ces options est liée à certains parties de code, et s’assurer du bon fonctionnement de ces parties entre elles, ou de les empêcher d’être utilisées ensemble, est un des défis durant le développement et l’utilisation de ces logiciels, connus sous le nom de Lignes de Produits Logiciel (ou SPL pour Software Product Lines). Si cela peut sembler relativement simple avec quelques options, certains logiciels assemblent des milliers d’options réparties sur des millions de lignes de code, ce qui rend la tâche autrement plus complexe. Durant la dernière décennie, les chercheurs ont commencé a utiliser des techniques d’apprentissage automatique afin de répondre aux problématiques des Lignes de Produits Logiciels. Un des problèmes clés est la prédiction des différentes propriétés de ces logiciels, comme la vitesse d’exécution d’une tâche, qui peut fortement varier selon la configuration du logiciel utilisé. Mesurer les propriétés pour chaque configuration peut être coûteux et complexe, voire impossible dans les cas les plus extrêmes. La création d’un modèle permttant de prédire les propriétés du logiciel, en s’aidant des mesures sur seulement d’une faible partie des configurations possible est une tâche dans laquelle l’apprentissage automatique excelle. Différentes solutions ont été developées, mais elles n’ont été validées que dans des cas où le nombre d’options est assez faible. Or, une part importante des SPL sont dotés de plusieurs centaines voire plusieurs milliers d’options. Sans tester les solutions d’apprentissage automatique sur des logiciels avec autant d’options, il est impossible de savoir si ces solutions sont adaptées pour de tels cas. La première contribution de cette thèse est l’application d’algorithmes d’apprentissage automatique sur une ligne de produits logiciels à une échelle jamais atteinte auparavant. Le noyau Linux, avec ses 15.000 options, dépasse complètement toutes les études de cas sur les Lignes de Produits Logiciels présentes dans la littérature, qui n’ont utilisé que des cas d’au mieux 60 options. En évaluant la précision de plusieurs algorithmes de l’état de l’art pour prédire la taille binaire du noyau Linux, nous avons pu déterminer les limites de 3 certaines techniques. Sans surprise, les algorithmes linéaires donnent de mauvais résultats en termes de précision, car ils ne peuvent pas appréhender la complexité causée par les interactions entre les options. Le modèle de performance-influence, bien que développé spécifiquement pour les SPL, ne peut pas gérer autant d’options malgré les mesures prises pour réduire l’explosion combinatoire. En fin de compte, nous avons constaté que les algorithmes basés sur les arbres, ainsi que les réseaux de neurones, étaient capables de fournir un modèle assez précis avec des ressources raisonnables en termes de temps et de mémoire. La deuxième contribution est la Feature Ranking List, une liste des options classées par importance envers leur impact sur une propriété cible d’un logiciel, générée par une amélioration de la sélection des caractéristiques basée sur les arbres de décisions. Nous avons évalué ses effets sur les modèles de prédiction de la taille des binaires du noyau Linux dans les mêmes conditions que pour la première contribution. L’effet souhaité et le plus connu de la sélection de caractéristiques en général est une accélération majeure du temps d’apprentissage, le divisant par 5 pour les Gradient Boosting Trees et de 20 pour les Random Forests. De manière plus inattendue, nous constatons également une amélioration notable de la précision pour la plupart des algorithmes précédemment considérés. La Feature Ranking List est lisible par l’homme, et lorsqu’elle a été présentée à des experts, elle a été jugée assez juste. Cependant, il y a une grande divergence lorsqu’on la confronte à la documentation, principalement en raison du très faible nombre d’options explicitement documentées comme ayant un impact sur la taille du noyau Linux. La troisième contribution est l’amélioration de la spécialisation automatisée des performances et son évaluation sur différents SPL dont Linux. La spécialisation des performances est un processus qui consiste à ajouter des contraintes sur un SPL afin de répondre à un certain seuil de performance défini par l’utilisateur, pour l’aider lors de la configuration du logiciel. Il est possible d’automatiser ce processus en utilisant l’apprentissage automatique, et plus précisément des arbres de décisions classifieurs qui prédisent si une configuration est acceptable ou non par rapport au seuil de performance, à partir desquels nous pouvons extraire des règles, ensuite appliquées comme contraintes sur la SPL cible. Les améliorations portent sur deux aspects. Le premier est l’application de la sélection des options basée sur la Feature Ranking List, qui a permis d’améliorer à la fois la précision et le temps d’apprentissage, même sur des SPL avec seulement quelques options. La seconde est la prise en compte des arbres de décisions régresseurs, qui produisent un modèle similaire pour l’extraction de règles, mais avec l’avantage d’être conscient de la 4 performance, alors que cette dimension est réduite à un simple booléen dans un processus de classification. Nous avons développé une nouvelle technique, basée sur les arbres de décisions régresseurs, où nous simulons un écart dans la distribution de la performance pour rendre l’algorithme conscient du seuil en ce qui concerne la fonction de perte. En fin de compte, les trois techniques ont leurs propres forces et faiblesses, avec leurs propres cas d’utilisation, et doivent être considérées comme complémentaires. La dernière contribution ouvre la porte à une utilisation plus durable de l’apprentissage automatique pour les lignes de produits logiciels. Dans ce domaine, peu voire aucune attention n’a été accordée à la précision des modèles sur différentes versions d’un SPL. Nous avons donc pris un modèle très précis issu des travaux de notre deuxième contribution, l’avons évalué sur des versions ultérieures et avons observé deux problèmes majeurs. Le premier est la différence d’options, car entre deux versions, certaines options apparaissent et d’autres disparaissent, créant un décalage dans l’espace de configuration. Le second est la baisse de précision lorsque le modèle est utilisé sur une autre version que celle sur laquelle il a été entraîné. Le coût pour entraîner le premier modèle était très important, en termes de mesures de configuration et d’efforts d’entraînement, et une telle dépense n’est pas raisonnable lorsque l’on considère une nouvelle version tous les deux ou trois mois. Pour résoudre ces deux problèmes, nous avons créé Evolution-Aware Model Shifting, une technique d’apprentissage par transfert adaptée à l’échelle et au rythme d’évolution du noyau Linux. Elle exploite le modèle original mais déprécié et, pour une fraction du coût initial, l’adapte aux nouvelles versions. Nos résultats montrent une très bonne précision sur trois ans d’évolution, et une meilleure précision que l’apprentissage à partir de zéro sur le même ensemble de données.

Abstract :

Variability is the blessing and the curse of today software development. On one hand, it allows for fast and cheap development, while offering efficient customization to precisely meet the needs of a user. On the other hand, the increase in complexity of the systems due to the sheer amount of possible configurations makes it hard or even impossible for users to correctly utilize them, for developers to properly test them, or for experts to precisely grasp their functioning. Machine Learning is a research domain that grew in accessibility and variety of usages over the last decades. It attracted interest from researchers from the Software Engineering domain for its ability to handle the complexity of Software Product Lines on problems they were tackling such as performance prediction or optimization. However, all studies presenting learning-based solutions in the SPL domain failed to explore the scalability of their techniques on systems with colossal configuration space (> 1000 options). In this thesis, we focus on the Linux Kernel. With more than 15.000 options, it is very representative of the complexity of systems with colossal configuration spaces. We first apply various learning techniques to predict the kernel binary size, and report that most of the techniques fail to produce accurate results. In particular, performance-influence model, a learning technique tailored for SPL problem, does not even work on such large dataset. Among the tested techniques, only Tree-based algorithms and Neural Networks are able to produce an accurate model in an acceptable time. To mitigate the problems created by colossal configuration spaces on learning techniques, we propose a feature selection technique leveraging Random Forest, enhanced toward better stability. We show that by using the feature selection, the training time can be greatly reduced, and the accuracy can be improved. This Tree-based feature selection technique is also completely automated and does not rely on prior knowledge on the system. Performance specialization is a technique that constrains the configuration space of a software system to meet a given performance criterion. It is possible to automate the specialization process by leveraging Decision Trees. While only Decision Tree Classifier has been used for this task, we explore the usage of Decision Tree Regressor, as well as a 7 novel hybrid approach. We test and compare the different approaches on a wide range of systems, as well as on Linux to ensure the scalability on colossal configuration spaces. In most cases, including Linux, we report at least 90% accuracy, and each approach having their own particular strength compared to the others. At last, we also leverage the Treebased feature selection, whose most notorious effect is the reduction of the training time of Decision Trees on Linux, downing from one minute to a second or less. The last contribution explores the sustainability of a performance model across versions of a configurable system. We reused the model trained on the 4.13 version of Linux from our first contribution, and measured its accuracy on six later versions up to 5.8, spanning over three years. We show that a model is quickly outdated and unusable as is. To preserve the accuracy of the model over versions, we use transfer learning with the help of Tree-based algorithms to maintain it at a reduced cost. We tackle the problem of heterogeneity of the configuration space, that is evolving with each version. We show that the transfer approach allows for an acceptable accuracy at low cost, and vastly outperforms a learning from scratch approach using the same budget. Overall, this thesis focuses on the problems of systems with colossal configuration spaces such as Linux, and show that Tree-based algorithms are a valid solution, versatile enough to answer a wide range of problem, and accurate enough to be considered.