Exploiter les sous-expressions communes dans les CSP numériques

Résumé : Il est bien connu que la forme des équations est déterminante pour l'efficacité de la résolution de systèmes d'équations et d'inégalités sur les réels par des techniques par intervalles. Peu de transformations automatiques de ces systèmes ont pourtant été proposées jusqu'ici. L'Elimination des Sous-expressions Communes (CSE) est une technique largement utilisée en optimisation de code. En analyse par intervalles, Vu, Schichl, Sam-Haroud et Neumaier exploitent des sous-expressions communes en transformant le système d'(in)équations en un unique graphe sans circuits. Ils estiment que l'impact des sous-expressions communes sur les performances serait uniquement dû à une réduction du nombre des opérations. Cet article apporte deux contributions principales. Premièrement, en raison de propriétés liées à l'arithmétique par intervalles, nous démontrons théoriquement et expérimentalement que l'exploitation de certaines sous-expressions communes aux équations non seulement réduit le nombre d'opérations, mais aussi apporte des filtrages additionnels lors de la propagation. Deuxièmement, contrairement aux approches existantes, en nous basant sur une meilleure exploitation des opérateurs naires d'addition et multiplication, nous proposons un nouvel algorithme I-CSE qui identifie et exploite toutes les sous-expressions communes “utiles”. Nous montrons sur un échantillon de problèmes tests que I-CSE détecte plus de sous-expressions communes utiles que les approches traditionnelles et conduit généralement à d'importants gains de performance (de parfois plusieurs ordres de grandeur).
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.375-384, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00292817
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 2 juillet 2008 - 16:13:45
Dernière modification le : mercredi 11 avril 2018 - 12:12:04
Document(s) archivé(s) le : vendredi 28 mai 2010 - 20:33:42

Fichier

pages-375-384-article3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00292817, version 1

Collections

Citation

Ignacio Araya, Bertrand Neveu, Gilles Trombettoni. Exploiter les sous-expressions communes dans les CSP numériques. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.375-384, 2008. 〈inria-00292817〉

Partager

Métriques

Consultations de la notice

315

Téléchargements de fichiers

174