Parcours de polyèdre paramétré avec l'élimination de Fourier-Motzkin

Marc Le Fur 1
1 PAMPA - Models and Tools for Programming Distributed Parallel Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Résumé : Ce rapport présente deux algorithmes calculant une structure de contrôle dont l'exécution énumère les vecteurs entiers d'un polyèdre paramétré dans un certain contexte. Les algorithmes reprennent la méthode des projections successives, basée sur l'élimination par paires de Fourier-Motzkin, définie par Ancourt et Irigoin dans le cas non paramétré. La politique de suppression des contraintes redondantes générées par l'élimination par paires est revue afin de réduire le temps de synthèse des parcours pour des polyèdres de complexité géométrique supérieure et améliorer le temps d'exécution des parcours produits. Les algorithmes présentés servent de base à la génération de code dans le prototype de compilateur Pandore développé à l'IRISA ; une comparaison entre ces algorithmes et celui défini par Ancourt et Irigoin est donnée sur la classe des polyèdres manipulés par le compilateur Pandore.
Type de document :
Rapport
[Rapport de recherche] RR-2358, INRIA. 1994
Liste complète des métadonnées

https://hal.inria.fr/inria-00074319
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:03:10
Dernière modification le : mercredi 16 mai 2018 - 11:23:04
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:08:22

Fichiers

Identifiants

  • HAL Id : inria-00074319, version 1

Citation

Marc Le Fur. Parcours de polyèdre paramétré avec l'élimination de Fourier-Motzkin. [Rapport de recherche] RR-2358, INRIA. 1994. 〈inria-00074319〉

Partager

Métriques

Consultations de la notice

125

Téléchargements de fichiers

186