Analyse de la commutativité

Pedro Diniz (pedro@isi.edu)

Sommaire

Les machines parallèles offrent la promesse d’une augmentation significative des performances en permettant à plusieurs processeurs d’exécuter simultanément différentes parties du calcul. Les programmeurs ont traditionnellement développé des applications pour des machines parallèles en utilisant des langages explicitement parallèles. Contrairement aux langages de programmation en série, les langages explicitement parallèles présentent un modèle de programmation complexe caractérisé par des phénomènes tels que l’impasse, l’exécution non déterministe et, sur les machines à transmettre des messages, la nécessité de gérer directement le mouvement des données à travers le calcul. Les avantages évidents de programmation du paradigme de programmation impérative séquentielle ont donc inspiré le développement de techniques d’analyse et de compilateurs conçus pour paralléliser automatiquement les programmes série.

Les compilateurs de parallélisation actuels préservent la sémantique du programme série d’origine en préservant les dépendances des données. Ces compilateurs tentent d’identifier des éléments de calcul indépendants (deux éléments de calcul sont indépendants si aucun d’eux n’écrit un élément de données auquel l’autre accède), puis génèrent du code qui exécute des éléments indépendants simultanément. Une limitation importante de cette approche est la difficulté d’effectuer une analyse de dépendance suffisamment précise pour exposer des quantités substantielles de simultanéité. Alors que les chercheurs ont été en mesure de développer des algorithmes raisonnablement efficaces pour les nids de boucles qui manipulent des matrices denses à l’aide de fonctions d’accès affines, peu de progrès ont été accomplis vers une analyse automatique réussie des programmes qui manipulent des structures de données basées sur des pointeurs. Les chercheurs ont tenté de construire des systèmes totalement automatiques, mais les approches les plus prometteuses exigent que le programmeur fournisse des annotations qui spécifient des informations sur la topologie globale des structures de données manipulées. Une deuxième limitation, plus fondamentale, des approches basées sur la dépendance aux données est l’incapacité de paralléliser les calculs qui manipulent les structures de données de type graphique. Les alias intrinsèquement présents dans ces structures de données empêchent la découverte statique de morceaux de code indépendants, forçant le compilateur à générer du code série. Enfin, la préservation des dépendances de données pour les programmes qui mettent périodiquement à jour les structures de données partagées peut limiter artificiellement la quantité de simultanéité exposée, car les tâches doivent retarder les mises à jour jusqu’à ce qu’elles soient sûres que chaque mise à jour ne changera pas l’ordre relatif des lectures et des écritures dans la structure de données partagée .

L’analyse de la commutativité est un cadre d’analyse statique pour détecter les opérations de navettage. Deux opérations commutent lorsqu’elles génèrent le même résultat, quel que soit l’ordre dans lequel elles s’exécutent. L’analyse de la commutativité élimine de nombreuses limitations des approches existantes basées sur la dépendance aux données Au lieu de préserver l’ordre relatif des lectures et des écritures individuelles sur des mots de mémoire uniques, l’analyse de commutativité agrège les données et le calcul en unités de grain de grande taille. Il analyse ensuite statiquement le calcul à cette granularité pour découvrir quand les morceaux du calcul commutent, c’est-à-dire génèrent le même résultat quel que soit l’ordre dans lequel ils s’exécutent. Si toutes les opérations requises pour effectuer un trajet de calcul donné, le compilateur peut générer automatiquement du code parallèle. Bien que le programme parallèle résultant puisse violer les dépendances des données du programme série d’origine, il est toujours garanti de générer le même résultat.

Cette approche a plusieurs propriétés intéressantes. Étant donné que l’analyse de commutativité ne repose pas sur des informations sur la topologie des structures de données manipulées, un compilateur qui utilise l’analyse de commutativité n’a pas besoin d’analyser les parties du code qui construisent la structure de données. L’analyse de la commutativité convient donc aux calculs incomplets, tels que les applications qui manipulent des données persistantes (par exemple, les applications de base de données orientées objet) ou les applications qui manipulent des données géographiquement dispersées (par exemple, les calculs mobiles sur le World Wide Web). Dans ces cas, le code qui a initialement créé la structure de données peut ne pas être disponible ou peut ne plus exister. L’analyse de la commutativité est également particulièrement adaptée aux calculs qui manipulent des graphiques. Il s’agit d’un aspect important de l’analyse de commutativité, car les calculs qui manipulent ces structures de données sont intrinsèquement hors de portée de l’analyse de dépendance des données.

Nous avons adopté une approche orientée systèmes pour évaluer la capacité de l’analyse de commutativité à extraire et à exploiter des quantités importantes de parallélisme dans des applications complètes. Nous avons construit un compilateur de parallélisation qui utilise l’analyse de commutativité comme principal paradigme d’analyse. Ce compilateur prend en entrée un programme séquentiel non annoté écrit dans un sous-ensemble de C ++ et génère du code parallèle pour un multiprocesseur à mémoire partagée. En utilisant ce compilateur de parallélisation, nous parallélisons automatiquement plusieurs applications, y compris le solveur Barnes-Hut N-body, un code de simulation d’eau liquide et un code de modélisation sismique. Pour toutes ces applications, l’analyse de commutativité est capable d’exposer une quantité substantielle de simultanéité et le code parallèle généré présente de très bonnes performances. Sur 16 processeurs, la version automatiquement parallélisée de Barnes-Hut fonctionne entre 11 et 12 fois plus rapidement que la version séquentielle d’origine; pour l’application de simulation d’eau, la version parallélisée automatiquement fonctionne 7 à 8 fois plus vite que la version séquentielle d’origine; pour l’application de modélisation sismique, la version parallélisée automatiquement s’exécute environ 12 fois plus vite que la version séquentielle d’origine.

Ces résultats expérimentaux sont très encourageants. Ces applications sont de nature très dynamique – elles manipulent des structures de données sophistiquées basées sur des pointeurs ou présentent des modèles d’accès aux données très irréguliers. L’exploitation du parallélisme à gros grains dans des applications présentant ces caractéristiques a été reconnue comme un problème très difficile. Nous ne connaissons aucun autre compilateur ou technique de compilation capable d’extraire des quantités importantes de concurrence pour ces calculs. En outre, les résultats expérimentaux positifs fournissent des preuves concrètes de la signification pratique de l’analyse de commutativité en tant que technique pour les compilateurs à parallélisation automatique.


Source de la page: https://www.isi.edu/~pedro/CA/commutativity.html
Traduit par Jean-Etienne Bergemer

Publié dans Edu

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *