Maintenant, le sujet de l'apprentissage automatique et de l'intelligence artificielle est extrêmement populaire, en ce moment, grâce à la puissance de calcul des ordinateurs, des idées et des algorithmes qui sont apparus depuis longtemps peuvent être mis en œuvre et considérablement améliorés. Presque tous les jours, vous pouvez lire des nouvelles sur les nouvelles réalisations dans ce domaine. De plus, l'apprentissage automatique est utilisé dans presque tous les domaines ... et le développement de compilateurs ne fait pas exception. Cependant, le domaine est assez spécifique et a ses propres caractéristiques et difficultés à créer des compilateurs intelligents. Dans le même temps, il existe de nombreuses études sur ce sujet et elles sont menées depuis longtemps tant dans le milieu académique que dans différentes entreprises.
Où exactement essayez-vous d'appliquer des méthodes d'apprentissage automatique lors de la création de compilateurs? Et pourquoi jusqu'à présent les compilateurs «intelligents» ne font-ils pas partie du quotidien du développeur?
Options d'utilisation de l'apprentissage automatique dans le développement de compilateurs
Commençons par la première question sur les utilisations spécifiques de l'apprentissage automatique. Le fait est que les compilateurs modernes sont des systèmes complexes avec un grand nombre d'optimisations qui vous permettent d'obtenir un code machine plus efficace. Cependant, certaines optimisations et autres tâches, telles que l'allocation de registres, sont NP-complete, ce qui oblige les développeurs de compilateurs à utiliser des algorithmes heuristiques. Par conséquent, la plupart des compilateurs ont un grand nombre d'indicateurs d'optimisation qui vous permettent de configurer l'heuristique utilisée. Dans LLVM, presque chaque passage a plusieurs options cachées qui peuvent affecter son fonctionnement, elles peuvent être utilisées soit en utilisant l'indicateur –mllvm lors de l'appel de clang, soit dans l'utilitaire opt. Cependant, cette variété d'indicateurs est cachée derrière les options beaucoup plus fréquemment utilisées, qui contiennent de nombreux paramètres à la fois et sont généralement appelées niveaux d'optimisation. Pour les compilateurs C / C ++, ceux-ci sont connus de la plupart des -O1, -O2, -O3 pour optimiser le runtime et -Os pour optimiser la taille du code. Mais, malheureusement, le code optimal n'est pas toujours le résultat (les experts assembleurs peuvent réécrire le code généré de la meilleure façon), beaucoup dépend du code source dans un langage de haut niveau, de l'architecture du processeur, des fonctionnalités du langage, etc.
Malgré le fait qu'aujourd'hui les processeurs modernes ont suffisamment de RAM et des performances assez élevées, il existe encore des domaines où les performances des applications, l'efficacité énergétique et la taille du code machine jouent un rôle clé. Des exemples de tels domaines comprennent le développement de logiciels pour les systèmes embarqués avec une quantité limitée de RAM, le traitement numérique du signal, les systèmes en temps réel, etc. Par conséquent, dans les cas où vous avez besoin d'obtenir du code machine hautes performances pour des systèmes suffisamment grands, la sélection des options de compilation correctes qui donnent le meilleur résultat est une tâche importante. De plus, le
problème du pire
cas d' exécution (
WCET )
n'a pas disparu lorsque les systèmes en temps réel doivent calculer et minimiser, si possible, le temps d'exécution d'une tâche spécifique sur la plate-forme. Jusqu'à présent, les programmeurs travaillant avec des systèmes avec une quantité limitée de RAM ne peuvent pas entièrement compter sur des compilateurs et optimisent souvent indépendamment le code machine généré.
Il est difficile pour une personne de prédire quelles optimisations donneront un bon résultat et qui peuvent conduire à des régressions, car pour cela, vous devez avoir une bonne compréhension des subtilités des algorithmes heuristiques utilisés, une bonne connaissance de la structure et des passages du compilateur utilisé, et connaître également pleinement le code du programme compilé, qui Le processus de développement d'applications actuel est impossible. En conséquence, l'identification des meilleures options de compilation pour un programme pour une personne devient une tâche de recherche exhaustive de diverses combinaisons d'options et de mesures des performances et des tailles de code.
De plus, il existe une limitation sous la forme d'une unité de compilation avec laquelle vous pouvez travailler et pour laquelle vous pouvez choisir des options. Donc, pour C / C ++, c'est toujours un fichier qui peut contenir beaucoup de code, qu'il serait peut-être utile d'optimiser de différentes manières, mais pour le moment ce n'est pas possible. Par conséquent, un compilateur «intelligent» qui pourrait former puis obtenir du code bien optimisé pour une variété de cas est un rêve pour certains développeurs.
Recherche et solutions existantes
Naturellement, le problème de la sélection automatisée des options de compilation intéresse les chercheurs depuis de nombreuses années. L'un des projets les plus célèbres est le développement de G. Fursin et des chercheurs de son équipe
MILEPOST GCC , qui est une version du compilateur gcc qui peut lui-même sélectionner des passes d'optimisation basées sur une formation précédente sur l'échantillon de données obtenu. Dans ce travail, nous avons utilisé un ensemble de 55 caractéristiques pour résoudre le problème et un modèle assez simple basé sur l'idée de distribuer de bonnes solutions basées sur l'algorithme K des plus proches voisins. C'est ce développement qui a montré que les passes d'optimisation de l'optimisation peuvent conduire à un code deux fois plus rapide que le code obtenu en utilisant l'option d'optimisation maximale standard -O3.
Il existe également des études de G.Pekhimenko et A.D. Brown pour TPO d'IBM (
Toronto Portable Optimizer ). Leur tâche principale était de sélectionner des valeurs sélectionnables heuristiquement pour les optimisations et l'ensemble même des transformations de code. Pour la mise en œuvre, une régression logistique a été utilisée, ce qui a permis de définir des amendes efficaces pour une formation plus rapide. Le classificateur a été construit dans Matlab. La probabilité d'utilisation a été calculée pour chaque passage, et elle a été utilisée si elle était supérieure à 50%. En raison de la caractéristique qu'ils ont essayé de réduire dans cette étude, c'était le temps de compilation statique.
A.Askhari a été engagé dans la sélection directe des options de compilation pour l'ensemble du programme afin de minimiser le temps d'exécution, le temps de compilation, la taille du code et la consommation d'énergie. Pour cela, le
cTuning Framework et le
Collective Mind Framework développé par G. Fursin et A. Lokhmotov (également développé sur
GitHub ) ont été utilisés.
Il y a aussi des études par
M. Stephenson et S. Amarasinge sur la sélection des optimisations pour certains algorithmes particulièrement importants (allocation des registres, PREFETCHING DES DONNEES, FORMATION HYPERBLOC). Pour chaque fonction, ses propres caractéristiques ont été utilisées en conséquence. Pour la solution, un algorithme génétique a été utilisé. Le test du produit développé a été effectué par l'Open Research Compiler (ORC).
Il existe également un projet
MAGEEC (Machine Guided Energy Efficient Compiler) dont les objectifs sont quelque peu différents. L'infrastructure développée utilise l'apprentissage automatique pour sélectionner les optimisations nécessaires pour générer le code avec une efficacité énergétique maximale pour les systèmes informatiques hautes performances. MAGEEC est conçu pour fonctionner avec gcc et LLVM. Ce compilateur fait partie du plus grand projet TSERO (Total Software Energy Reporting and Optimization).
Une recherche directement liée à LLVM est
LLVMTuner , un produit logiciel développé à l'Université de l'Illinois par I. Chen et W. Adwe. En 2017, un rapport a été présenté décrivant les résultats disponibles à l'époque. Dans ce travail, nous avons optimisé les cycles «chauds» individuels. Ce cadre est conçu pour la configuration automatisée de grands programmes. LLVMTuner s'exécute sur le middleware LLVM IR, utilise le profilage pour identifier les boucles actives, puis ajuste automatiquement l'heuristique à leur place. L'accent est mis sur les cycles de niveau supérieur. Les cycles sélectionnés et toutes les fonctions d'appel sont transférés vers un module séparé, qui est en outre soumis aux optimisations nécessaires. Cette solution vous permet d'obtenir des performances améliorées sur des programmes volumineux.
Problèmes existants
Cependant, il n'existe aucun compilateur largement utilisé qui ajuste indépendamment l'heuristique de l'optimisation des passes. Quel est le problème? Comme vous le savez, l'efficacité des méthodes d'apprentissage automatique et la qualité des modèles obtenus dépendent du choix correct des fonctionnalités et de la qualité des données de formation (malgré l'existence d'algorithmes moins sensibles aux données «bruyantes»). Sans connaître la structure et les algorithmes utilisés dans le compilateur, il n'est pas facile de sélectionner un ensemble complet et suffisant de caractéristiques pour la formation, bien qu'il y en ait des assez claires et logiques, par exemple, la taille du cycle, le nombre de sorties du cycle, etc. Par conséquent, il est difficile de développer une solution universelle adaptée à de nombreux compilateurs à la fois, et ce n'est pas un fait que cela est généralement possible. De plus, il est probable que cela ne soit pas nécessaire.
Le développement des compilateurs devant être efficace et réalisable dans un délai assez court, il est naturel que même les grandes entreprises développent leurs compilateurs industriels à partir de solutions toutes faites. La plupart des solutions modernes peuvent être divisées en deux catégories: s'exécuter sur des machines virtuelles, par exemple, des compilateurs JVM - JIT et des compilateurs basés sur LLVM, un système qui implémente une machine virtuelle avec des instructions de type RISC - des compilateurs statiques et dynamiques. Bien sûr, il existe encore des solutions propres aux entreprises, mais elles deviennent moins compétitives en raison du manque d'une grande communauté impliquée dans le développement des technologies qui y sont utilisées. En conséquence, de nombreuses grandes entreprises telles que Google, Apple, Adobe et ARM utilisent aujourd'hui LLVM pour développer leurs propres solutions. Bien sûr, gcc reste le principal compilateur pour C / C ++, d'autres solutions existent pour d'autres langages, mais de toute façon, si, par exemple, une solution pour LLVM est trouvée, elle couvrira déjà une bonne partie des compilateurs existants.
La collecte de caractéristiques pour la formation devient également un gros problème, car les compilateurs multi-passes transforment fortement la représentation intermédiaire, et les caractéristiques collectées au stade initial ne sont pas tout à fait pertinentes pour les optimisations ultérieures du compilateur, ces caractéristiques peuvent changer avec une forte probabilité. Caractéristiques, en outre, il est logique de collecter séparément pour différents types d'éléments: modules, cycles, blocs de base, car les optimisations sont généralement conçues pour changer un type particulier d'élément, dans LLVM, même selon ce critère, les passages sont divisés.
Mais, tout d'abord, la question se pose d'identifier les éléments pour lesquels il est nécessaire de collecter des caractéristiques. Il existe de nombreuses façons de calculer des identifiants uniques qui peuvent être enregistrés lors de toutes les optimisations, par exemple:
- Hachage frontal basé sur AST
- numéros uniques attribués dans l'analyse frontale
- Nombre 64 bits généré sur la base d'arcs dans CFG (graphique de flux de contrôle) à l'aide d'une somme de contrôle (similaire à PGO (optimisation guidée par profil) dans LLVM)
Cependant, vous devez enregistrer correctement ces identifiants lors des transformations, lorsque les éléments peuvent fusionner en un, se diviser, en créer de nouveaux et supprimer ceux d'origine, ce qui n'est pas une tâche facile.
Deuxièmement, il est difficile en principe d'évaluer les limites des cycles source, blocs de base, etc. écrits dans le code source, sur l'IR déjà converti. Par exemple, en raison de la génération en plusieurs étapes du code machine adoptée par LLVM, les informations sur les unités de base de la machine sont perdues après la génération du code sur la base des instructions machine dans AsmPrinter. Et en conséquence, des informations sur les identifiants des blocs de base et des cycles sont également perdues, pour lesquelles, par exemple, le décalage depuis le début de la fonction est mesuré.Par conséquent, avec cette méthode, ce n'est qu'au stade de la génération du code machine que le décalage peut être obtenu sous la forme du nombre d'octets selon les instructions. Cependant, aux étapes ultérieures de la génération de code machine lors de l'utilisation de fragments de machine, divers alignements peuvent y être ajoutés, ce qui modifie la taille des instructions prises en compte précédemment, et des instructions nop sont également ajoutées. De ce fait, pour les blocs de base à la fin de grandes fonctions, l'erreur de calcul peut être très importante, jusqu'à un passage complet à un autre bloc / cycle. Et bien que certaines des transformations des étapes ultérieures puissent être suivies et prises en compte, cela ne garantit pas la précision des mesures, car la taille des instructions peut varier jusqu'à l'éditeur de liens.
Comme vous pouvez le voir, même la collecte d'attributs sur la base de laquelle une formation est nécessaire est assez compliquée et prend du temps, et qui, à l'avenir, deviendra probablement l'ensemble d'entrée pour le modèle formé pour la prise de décision. Et il n'y a pas de solutions évidentes à ces problèmes, ce qui complique le travail immédiat associé à l'apprentissage automatique et attire un grand nombre de personnes en raison du manque d'ensembles de données suffisants. Eh bien, les difficultés typiques de trouver des solutions aux problèmes d'apprentissage automatique, de choisir des modèles, des méthodes, de déterminer le bon sous-ensemble d'attributs avec un grand nombre d'entre eux, etc. existent dans ce cas. Presque tous ceux qui ont rencontré l'apprentissage automatique les connaissent et, peut-être, quelque chose d'unique et spécifique pour les compilateurs n'est pas là.
Il est difficile de prédire quand les compilateurs intelligents se répandront. Les compilateurs modernes ont également d'autres problèmes qui ne seront probablement pas résolus par cette méthode et qui, à l'heure actuelle, sont probablement plus prioritaires. Cependant, les compilateurs sont déjà devenus beaucoup plus intelligents qu'ils ne l'étaient à l'aube de leur apparition, et ce processus se poursuivra, bien qu'il puisse être un peu plus lent que la plupart des développeurs ne le souhaiteraient.