Liveness Analysis in Explicitly-Parallel Programs
Analyse de durées de vie dans les programmes explicitement parallèles
Résumé
In this report, we revisit scalar and array element-wise liveness analysis for
programs with parallel specifications. In earlier work on memory
allocation/contraction (register allocation or intra- and inter-array reuse
in the polyhedral model), a notion of ``time'' or a total order among the
iteration points was used to compute the liveness of values. In general, the
execution of parallel programs is not a total order, and hence the notion of
time is not applicable.
We first revise how conflicts are computed by using ideas from liveness
analysis for register allocation, studying the structure of the corresponding
conflict/interference graphs. Instead of considering the conflict between
two live ranges, we only consider the conflict between a live range
and a write. This simplifies the formulation from having four instances
involved in the test down to three, and also improves the precision of the
analysis in the general case.
Then we extend the liveness analysis to work with partial orders so
that it can be applied to many different parallel
languages/specifications with different forms of parallelism. An
important result is that the complement of the conflict graph with
partial orders is directly connected to memory reuse, even in
presence of races. However, programs with conditionals do not always define
a partial order, and our next step will be to handle such cases
with more accuracy.
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...