Liveness Analysis in Explicitly-Parallel Programs

Alain Darte 1 Alexandre Isoard 1 Tomofumi Yuki 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Dans ce rapport, nous revisitons l'analyse de durée de vie (vivacité) des scalaires et des éléments de tableaux pour des programmes comportant des spécifications parallèles. Les précédents travaux sur l'allocation/contraction mémoire (allocation de registres ou réutilisation de tableaux dans le modèle polyédrique) utilisaient une notion de ``temps'' ou d'ordre total entre les itérations pour calculer la vivacité des valeurs. En général, l'exécution de programmes parallèles n'est pas un ordre total, et donc la notion de temps est mal définie. Nous révisons tout d'abord le calcul des conflits entre éléments mémoire en utilisant des idées provenant de l'analyse de durée de vie pour l'allocation de registres. Plutôt que de considérer le conflit entre deux intervalles de vie, nous considérons le conflit entre un intervalle de vie et une écriture. Ceci simplifie la formulation en n'impliquant plus, dans le test, que trois instances au lieu de quatre, et également améliore la précision de l'analyse dans le cas général. Nous étendons ensuite l'analyse de vivacité pour prendre en compte des ordres partiels de sorte qu'elle puisse s'appliquer à différents langages ou spécifications parallèles, avec des formes différentes d'expression du parallélisme. Un résultat important est que le complémentaire du graphe de conflits, dans le cas des ordres partiels, est directement lié à la formulation de la réutilisation mémoire, même en cas d'accès concurrents (races). Néanmoins, les programmes comportant des conditionnelles ne définissent pas toujours d'ordre partiel, et l'étape suivante sera de traiter ces cas avec plus de précision.
Type de document :
Rapport
[Research Report] RR-8839, CNRS; Inria; ENS Lyon. 2016, pp.25
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01251579
Contributeur : Alain Darte <>
Soumis le : mercredi 6 janvier 2016 - 14:00:00
Dernière modification le : mardi 16 janvier 2018 - 15:42:37
Document(s) archivé(s) le : jeudi 7 avril 2016 - 16:01:13

Fichier

RR-8839.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01251579, version 1

Collections

Citation

Alain Darte, Alexandre Isoard, Tomofumi Yuki. Liveness Analysis in Explicitly-Parallel Programs. [Research Report] RR-8839, CNRS; Inria; ENS Lyon. 2016, pp.25. 〈hal-01251579〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

87