SPPoC : manipulation automatique de polyèdres pour la compilation

Pierre Boulet & Xavier Redon

Le modèle polyèdrique est très souvent utilisé pour l'analyse et la transformation de programme dans les compilateurs paralléliseurs. Les prototypes de recherche dans ce domaine utilisent donc souvent des outils comme PIP (résolution paramétrique de problèmes linéaires), la PolyLib (bibliothèque de manipulation de polyèdres) ou Omega (bibliothèque et interface de manipulation de formules de Presburger). Les deux principaux problèmes de ces outils sont leur manque de convivialité et des modules de simplification trop primitifs. Le manque de simplification fait que l'enchaînement de calculs conduit à des résultats incompréhensibles ou qui n'aboutissent pas pour des problèmes de mémoire ou de temps. La bibliothèque SPPoC (Symbolic Parameterized Polyhedral Calculator) résoud ces problèmes grâce à son interface totalement symbolique et à des modules de simplification des résultats plus poussés. Elle permet aussi d'unifier différents outils. La présentation de SPPoC est illustrée par deux applications : une application de génération de code et une application d'estimation de volume de communications.

The polyhedral model is quite popular in the field of parallelizing compilers. So, research prototypes tend to use tools like PIP (parametric integer programming solver), the PolyLib (library for polyhedra manipulation) or Omega (library and calculator for Presburger formulas). The two main drawbacks of these tools are a poor human-computer interface and a lack of aggressive simplification. This last deficiency leads to sequences of computations which give too complex results or even that cannot be completed due to memory exhaustion or time constraints. The SPPoC (Symbolic Parameterized Polyhedral Calculator) library brings a solution to these problems due to its completely symbolic interface and to its advanced simplification modules. It also allows the unification of different tools. We present two applications which use SPPoC : a code generator and a communication volume estimator.

• Introduction
• Interface utilisateur
  • Choix d'implémentation
  • Interface de programmation
  • Utilisation interactive
• Programmation linéaire en nombres entiers paramétrée
  • PIP
  • Limitations de PIP
  • Interface à PIP
• Opérations sur les polyèdres
  • Construction des polyèdres
  • Opérations ensemblistes
  • Opérations sur les polyèdres paramétriques
• Opérations sur les relations en nombres entiers
  • Construction des relations
  • Opérations ensemblistes
  • Opérations spécifiques
• Simplifications symboliques
  • Présentation générale de l'implémentation
  • Expressions arithmétiques
  • Systèmes de contraintes
  • Calculs avec les QUAST
• Exemples d'utilisation
  • Génération de code
  • Estimation de volumes de communications
• Conclusion
• References
• Description de l'interface de programmation
  • Module Term
  • Module Form
  • Module Expr
  • Module Ineq
  • Module System
  • Module Quast
  • Module Modulo
  • Module NewPar
  • Module EQuast
  • Module Question
  • Module PIP
  • Modules d'interface à la PolyLib

This document was translated from L^AT_EX by H^EV^EA and H^AC^HA.