Présentation des matrices de différence striées dans l'optimisation des compilateurs

Une variété de problèmes en maths et en info peut être représentée avec des formes appelées polyèdres. Des petits groupes de ces formes, connus sous le nom de sous-domaines polyédraux, sont utiles parce qu'ils prennent moins de place et nécessitent moins de temps pour être utilisés. Cet article présente un nouveau type de sous-domaine polyédral appelé Matrice de Bornes de Différence à Pas (SDBM), qui est particulièrement utile pour optimiser les compilateurs. La SDBM a des capacités puissantes et des méthodes efficaces qui la rendent adaptée pour les compilateurs de machine learning. Cet article décrit des méthodes de décision, des opérateurs de domaine et des preuves concernant la complexité des SDBM. Une étude empirique avec le cadre de compilation MLIR confirme l'utilité de ce domaine dans des applications réelles. Nous identifions aussi un type spécifique de SDBM qui apparaît souvent en pratique, montrant des algorithmes encore plus rapides pour ce type.

#Introduction et Motivation

Quand on analyse et vérifie des systèmes informatiques, différents modèles sont utilisés pour représenter comment ces systèmes fonctionnent. Les modèles numériques se concentrent sur les caractéristiques arithmétiques des variables du système et soutiennent les conceptions mathématiques de différents systèmes, comme les systèmes de timing et les modèles hybrides, qui combinent des aspects continus et discrets. Ces modèles aident à analyser les boucles et les programmes récursifs efficacement.

Beaucoup de ces modèles numériques reposent sur un type spécial de maths appelé arithmétique de Presburger, où les problèmes de décision courants sont compliqués et classés comme NP-dur. La version la plus simple de ces problèmes concerne des cas non relationnels, comme les bornes d'intervalle où une variable a une limite numérique spécifique. Des versions plus complexes impliquent des inégalités qui représentent des relations entre plusieurs variables, comme des systèmes d'inégalités connus sous le nom de systèmes UTVPI (Unité Deux Variables Par Inégalité). Ces systèmes forment ce qu'on appelle le domaine abstrait octagonal. Les systèmes UTVPI sont moins coûteux à utiliser que des formes complexes mais capturent quand même beaucoup de problèmes à multi-variables.

Les algorithmes pour les systèmes UTVPI utilisent des représentations appelées Matrices de Bornes de Différence (DBM), qui peuvent exprimer des inégalités entre des variables. Les DBM sont largement utilisés dans la vérification formelle et l'analyse statique des programmes. D'autres modèles numériques tels que les Congruences, qui se concentrent sur des combinaisons linéaires de variables entières, ont tendance à manquer les aspects d'inégalité importants.

Un type spécifique d'égalités de congruence, où certaines variables sont fixées à des valeurs spécifiques, a une faible complexité. Ce scénario est utile lorsqu'on améliore d'autres modèles abstraits. Cependant, il reste flou s'il existe des algorithmes efficaces pour combiner UTVPI avec des contraintes de congruence. Trouver un moyen de fusionner ces deux là aurait de nombreuses applications utiles dans l'analyse et l'optimisation des modèles de machine learning.

Les compilateurs modernes de machine learning utilisent souvent des formes de représentation de Presburger pour diverses opérations, comme les mises en page de données mémoire et des changements de format comme le remodelage. Les expressions affines apparaissent également lors des modifications de programme pour optimiser le matériel, y compris la vectorisation et le traitement parallèle. La plupart de ces expressions concernent des formes hyper-rectangulaires mais incluent parfois des formes plus complexes.

Certaines opérations, comme les convolutions et la normalisation, produisent des valeurs liées aux pas et tailles qui nécessitent des contraintes de congruence. Bien que les optimisations avancées des compilateurs s'appuient souvent sur des bibliothèques complètes d'arithmétique de Presburger, des cas plus simples nécessitent un modèle combinant UTVPI et congruences qui opère sur des polynômes de degré inférieur. Ce modèle pourrait également bénéficier des efforts de vérification qui utilisent actuellement des bibliothèques d'arithmétique de Presburger.

Cet article examine la combinaison d'inégalités représentées par des DBM avec des congruences à une seule variable, créant un nouveau domaine abstrait appelé Matrices de Bornes de Différence à Pas (SDBM). Il s'intéresse aussi à une version spéciale connue sous le nom de SDBM Harmonique (HSDBM), où les conditions de congruence forment un ensemble ordonné qui surgit souvent des changements de boucles dans du code haute performance.

Bien que le problème de satisfiabilité de la SDBM paraisse complexe, nous proposons un algorithme qui s'exécute dans un délai gérable. Cette complexité temporelle, qui est pratique pour les applications d'analyse de programme, nous permet de développer des algorithmes pour HSDBM aussi.

Pour finir, nous établissons une forme standard pour les systèmes de contraintes SDBM qui peuvent être calculés efficacement. Nous montrons également que deux systèmes en forme standard peuvent être traités rapidement, menant à un ensemble de solutions qui combine leurs solutions, ce qui est courant en interprétation abstraite.

#DBM, SDBM et HSDBM

Quand on parle d'ensembles avec des éléments entiers, on se concentre sur des sous-ensembles d'entiers. On définit quelques termes pour la clarté. Si un graphe n'a pas de cycles négatifs, la distance entre deux sommets peut être calculée.

On décrit formellement les Matrices de Bornes de Différence (DBM), qui sont des systèmes de contraintes impliquant des variables et des inégalités. Tous les bornes supérieures et inférieures pour les variables n'ont pas besoin d'être présentes dans une DBM. Quand il n'y a pas de bornes de variable présentes, on l'appelle sans bornes de variable (VBF) ; sinon, il a des bornes de variable. La satisfiabilité des contraintes de DBM peut être déterminée dans un délai raisonnable.

Ensuite, on introduit la SDBM. Une SDBM Stridée maintient la structure d'une DBM mais ajoute des contraintes de congruence spécifiques. Une SDBM Harmonique (HSDBM) désigne une SDBM où les conditions de congruence sont arrangées de manière à ce que chacune divise la suivante.

Pour simplifier le problème de satisfiabilité de la SDBM, nous montrons qu'il peut être réduit à la vérification de systèmes SDBM plus simples, où toutes les contraintes de congruence ont un reste de zéro. Cette approche réduit la complexité de recherche de solutions.

Nous fournissons des méthodes pour convertir les SDBM en une forme plus simple. Quand une solution existe, la SDBM peut être manipulée sans changer ses propriétés. Le processus de conversion des SDBM en SDBM simples est efficace et garantit que les solutions restent valides.

Dans le cas des HSDBM, nous montrons que les opérations de fermeture de chemin et de resserrement de PGCD suffisent à confirmer la satisfiabilité. Nous pouvons effectuer des projections des ensembles de solutions, menant à des solutions qui respectent à la fois les inégalités et les conditions de congruence.

#Satisfiabilité des HSDBM dans le Temps

Pour les HSDBM, nous supposons que le système est simple et effectue des opérations pour garantir que tous les composants sont proches et valides. Les projections des ensembles de solutions permettent une analyse plus poussée des bornes et des congruences. En utilisant des résultats précédents, nous pouvons déterminer des solutions basées sur des variables projetées.

Lorsqu'on vérifie si un HSDBM est valide, la fermeture de chemin et le resserrement de PGCD suffisent à établir si une solution existe. Grâce à des méthodes comme SolveHSDBM, qui rassemble des étapes de fermeture de chemin et de resserrement, nous confirmons si nos systèmes sont satisfaisables.

#Satisfiabilité des SDBM dans le Temps

Le problème de déterminer la satisfiabilité des SDBM est difficile et actuellement considéré comme NP-dur, ce qui signifie qu'aucun algorithme en temps polynomial n'est connu. Cependant, nous proposons une approche qui fonctionne efficacement dans la taille des contraintes. L'algorithme SDBM se concentre sur les valeurs des contraintes de congruence, qui tendent à être plus petites par rapport aux bornes fixées par les inégalités.

En transformant le problème SDBM en une forme plus gérable, nous pouvons trouver des solutions efficacement. La méthode proposée implique d'identifier des solutions entières aux contraintes d'inégalité et d'ajuster soigneusement les bornes des variables.

Pour optimiser notre approche, nous discutons de la manière de resserrer les bornes pour éviter l'apparition de solutions superflues. La technique de resserrement de PGCD garantit que les valeurs restent alignées avec les propriétés nécessaires, tandis que la fermeture de chemin maintient l'intégrité du système de contraintes.

Enfin, nous effectuons une normalisation sur les systèmes HSDBM, garantissant que les inégalités sont aussi serrées que possible. Cette étape garantit que toutes les bornes reflètent véritablement les solutions disponibles dans le système, améliorant ainsi l'analyse globale.

#Applications à la Validation de Traduction

Nous explorons aussi l'application de nos méthodes dans la validation des traductions, notamment avec les modèles de machine learning. Les cadres pour traiter ces modèles sont configurés pour utiliser notre SDBM proposé tout au long du processus de compilation.

Nous analysons plusieurs modèles de machine learning, les convertissant en représentations adaptées pour un traitement ultérieur. Pendant ce processus, nous vérifions à quel point les représentations SDBM tiennent bien dans des scénarios pratiques, veillant à ce que les opérations et transformations soutiennent de manière cohérente les exigences du modèle.

Les résultats démontrent que SDBM peut représenter avec précision beaucoup des expressions et structures couramment rencontrées dans des environnements de machine learning. Les études montrent une forte compatibilité de SDBM avec différents modèles, soulignant son potentiel à travers différentes étapes du traitement des modèles.

#Étude Empirique

Une partie importante de l'enquête implique l'analyse de l'efficacité de SDBM dans des applications réelles. Nous instrumentons plusieurs compilateurs établis utilisant SDBM pour évaluer sa prévalence et son adéquation dans des environnements pratiques.

Ces compilateurs couvrent un large éventail d'utilisations, du machine learning à la conception matérielle. Nous nous concentrons sur combien d'expressions et d'ensembles peuvent être représentés dans le cadre SDBM et quantifions cela en termes de taux de réussite pendant la compilation.

Nos découvertes révèlent que la plupart des expressions affines dans ces tests peuvent effectivement être représentées via SDBM. Cela suggère que SDBM est capable de gérer une vaste gamme de constructions trouvées dans les infrastructures des compilateurs. Malgré certaines limitations dans les cas particuliers, les résultats indiquent une haute adéquation pour une utilisation de bout en bout dans de nombreux scénarios computationnels.

Dans l'ensemble, la SDBM et la HSDBM démontrent un potentiel significatif pour améliorer l'efficacité et l'exactitude des processus d'interprétation abstraite, notamment dans le domaine des optimisations de compilateurs et de machine learning. La recherche établit les bases pour une future exploration visant à rendre les compilateurs plus efficaces en utilisant ces nouvelles représentations.