Exploiter les sous-expressions communes dans les CSP numériques - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

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).
Fichier principal
Vignette du fichier
pages-375-384-article3.pdf (346.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00292817 , version 1 (02-07-2008)

Identifiants

  • HAL Id : inria-00292817 , version 1

Citer

Ignacio Araya, Bertrand Neveu, Gilles Trombettoni. Exploiter les sous-expressions communes dans les CSP numériques. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.375-384. ⟨inria-00292817⟩
96 Consultations
158 Téléchargements

Partager

Gmail Facebook X LinkedIn More