SPPoC* : Symbolic Parameterized Polyhedral Calculator

Pierre Boulet   Xavier Redon

octobre 1999






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.

Deux outils principaux ont été développés pour effectuer ces calculs polyédriques symboliques : PIP [4, 5] et la PolyLib [8, 6]. 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 symboliques (définition, opérations ensemblistes, application de fonctions affines et de leur réciproque, comptage du nombre de points, etc).

Le principal problème de ces outils 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 une (ou plusieurs) matrices de coefficients. Les variables et 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 deuxième problème est que les résultats ne sont pas forcément sous leur forme la plus simple. Cela se fait sentir cruellement quand on enchaîne plusieurs calculs. La complexité des objets traités augmente rendant impossibles de nouveaux calculs.

Pour résoudre ces deux problèmes, nous avons développé une interface unifiée à ces deux outils. Elle est complètement symbolique, donc beaucoup plus utilisable et fait des simplifications des structures intermédiaires qui permettent des enchaînements de calculs jusqu'alors impossibles.

2   Réalisation logicielle

SPPoC est écrit en Objective Caml [7] pour les capacités de traitement symbolique de ce langage ainsi que son interfaçage simple avec le C.

2.1   Simplifications symboliques

Il comprend les manipulations avec simplification automatique d'expressions arithmétiques générales en nombres entiers ou rationnels : addition, multiplication, division euclidienne, modulo, puissances... L'algorithme de simplification tend à identifier les formes affines. En effet, ce sont de telles formes qui permettent la définition de polyèdres.

2.2   Interface à PIP

Les fonctionnalités apportées par cette interface sont : Elle est réalisée par l'appel à PIP via un tube Unix (pipe).

2.3   Interface à la PolyLib

L'interface adapte automatiquement la dimension des polyédres quand c'est nécessaire (application de fonctions et opérations sur des polyèdres de dimensions différentes). On voit ici les polyèdres de façon abstraite et l'interface est réalisée par appel direct des fonctions C de la bibliothèque.

3   Applications

3.1   Caravan

Caravan est une plateforme de développement d'outils de parallélisation automatique développée au PRiSM, à Versailles. L'interface à PIP y est utilisée pour les calculs d'analyse de dépendance et la génération de code [1].

3.2   Calcul du volume de communication

Dans [2], nous décrivons une méthode de calcul du volume de communication lors d'une assignation en HPF. Cette méthode n'a pu être implémentée avec succès que grâce aux simplifications apportées par SPPoC.

3.3   Motifs dans Array-OL

Le langage Array-OL [3] est utilisé dans le contexte du traitement du signal. Il propose un mécanisme de description de traitements parallèles sur des tableau par le biais de pavages de ces tableaux par des motifs sur lesquels seront effectués les calculs élémentaires. On détermine ici si le pavage d'un tableau par un motif recouvre totalement le tableau et s'il y a des redondances dans le calcul.

4   Conclusion

Par la mise en place d'une interface de haut niveau, nous avons facilité l'utilisation de PIP et de la PolyLib. Le gain apporté par les simplifications intermédiaires des structures de données symboliques est significatif.

En utilisant la bibliothèque Format d'affichage structuré d'Objective Caml et le système de préprocessing camlp4 nous profitons du système interactif de Caml pour l'utiliser comme une « calculatrice polyédrique ».

References

[1]
P. Boulet and P. Feautrier. Scanning polyhedra without do-loops. In PACT'98, pages 4--11. IEEE Computer Society, 1998.

[2]
P. Boulet and X. Redon. Communication pre-evaluation in HPF. In EUROPAR'98, volume 1470 of LNCS, pages 263--272. Springer Verlag, 1998.

[3]
A. Demeure, A. Lafage, E. Boutillon, D. Rozzonelli, J.-C. Dufourd, and J.-L. Marro. Array-OL : Proposition d'un formalisme tableau pour le traitement de signal multi-dimensionnel. In Gretsi, Juan-Les-Pins, France, Sept. 1995.

[4]
P. Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22:243--268, Sept. 1988.

[5]
P. Feautrier and N. Tawbi. Résolution de systèmes d'inéquations linéaires; mode d'emploi du logiciel PIP. Technical Report 90-2, Institut Blaise Pascal, Laboratoire MASI (Paris), Jan. 1990.

[6]
V. Loechner. Polylib. URL: http://icps.u-strasbg.fr/~loechner/polylib/.

[7]
projet Cristal. The caml language. URL: http://pauillac.inria.fr/caml/.

[8]
D. K. Wilde. A library for doing polyhedral operations. Publication Interne 785, IRISA, 1993.
*
URL : http://www.lifl.fr/west/sppoc/
This document was translated from LATEX by HEVEA.