1 Introduction
Lors de la compilation de langages parallèles ou de la parallélisation
automatique de programmes séquentiels, des analyses statiques du code
sont nécessaires. Celles-ci font souvent appel à des calculs
polyédriques lorsqu'on s'intéresse à des langages à contrôle statique
(voir le chapitre 7 pour des exemples précis). Ce modèle
polyédrique permet l'expression des dépendances de données
[12, 22, 4, 3], des
calculs d'ordonnancement
[24, 13, 14, 7, 8]
et de placement de tâches parallèles [15, 10],
des optimisations de génération de code
[6, 18, 1], etc.
Il existe de nombreux outils de calcul polyédrique numérique, mais
nous n'en connaissons que trois qui permettent de manipuler des
expressions paramétriques. Il s'agit de PIP [11, 16], de la PolyLib [23, 5] et de
l'Omega Library [21, 17]. PIP et la PolyLib étant fortement utilisés dans la communauté de la parallélisation
automatique, nous avons réalisé la couche symbolique qui les rendra
plus agréables et accessibles. Ces développements sont regroupés dans
une bibliothèque : SPPoC pour Symbolic Parameterized Polyhedral
Calculator. À la suite de demandes de la dite communauté,
l'Omega Library est aussi intégrée dans SPPoC bien que disposant déjà
d'une interface symbolique.
PIP permet de résoudre des problèmes de programmation linéaire
paramétrée en nombres entiers. Un tel problème est la donnée d'un
polyèdre définissant le domaine de recherche, d'un autre domaine
définissant le domaine des valeurs des paramètres et d'une liste de
variables. PIP retourne le minimum lexicographique de ces variables
dans leur domaine de validité sous la forme d'un QUAST (Quasi Affine
Selection Tree).
La PolyLib , quant à elle, permet la manipulation de
polyèdres paramétrés (définition, opérations ensemblistes, application
de fonctions affines et de leur réciproque, comptage du nombre de
points, etc).
Enfin l'Omega Library qui manipule l'arithmétique de
Presburger est partiellement redondante avec PIP et la PolyLib mais
apporte d'autres fonctionnalités comme le calcul d'une fermeture
transitive de relation.
Le premier inconvénient de ces outils (du moins en ce qui concerne
PIP et la PolyLib ) est leur difficulté d'utilisation venant
principalement des structures de données de bas niveau utilisées. En
effet, les polyèdres et autres structures de données sont représentés
par des matrices de coefficients. Les variables et les paramètres sont
repérés par leur indice de ligne ou de colonne. Ces représentations,
bien qu'efficaces pour le calcul, ne sont que très peu lisibles. Le
second inconvénient (et certainement le plus important) est que les
résultats ne sont pas forcément sous leur forme la plus simple. Cela
se fait cruellement sentir quand on enchaîne plusieurs calculs. La
complexité des objets traités augmente alors rapidement, rendant
impossibles de nouveaux calculs.
1
Pour résoudre ces deux problèmes, nous avons développé une interface
unifiée à ces outils. Elle est complètement symbolique, donc
beaucoup plus utilisable, et fait des simplifications qui permettent des enchaînements de calculs jusqu'alors
impossibles.
La suite de cet article est structurée ainsi : après une présentation
succinte de l'interface utilisateur dans le chapitre 2, nous
décrivons successivement les quatre composants de SPPoC : l'interface
à PIP (chapitre 3), l'interface à la PolyLib (chapitre
4), l'interface à l'Omega Library (chapitre 5)
et le fonctionnement des simplifications symboliques
(chapitre 6). Enfin, le
chapitre 7 présente deux exemples d'applications
bénéficiant de cette interface de haut niveau.