Skip to Main content Skip to Navigation
Conference papers

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).
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00292817
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, July 2, 2008 - 4:13:45 PM
Last modification on : Wednesday, February 3, 2021 - 7:54:26 AM
Long-term archiving on: : Friday, May 28, 2010 - 8:33:42 PM

File

pages-375-384-article3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00292817, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

399

Files downloads

256