CLooG est un plugin à la PolyLib qui fournit un logiciel et une bibliothèque
qui génère des boucles pour parcourir les points entiers d'un polyèdre.
C'est à dire qui trouve le code ou le pseudo code où chaque point d'un ou
plusieurs polyèdres paramétrés ou union de polyèdres paramétrés est atteint.
Bien que l'utilisateur ait le contrôle total sur la qualité et la forme du code
généré, CLooG a été conçu pour éviter la surcharge de contrôle et produire un
code particulièrement efficace. Le cœur du processus de génération de code
est l'algorithme de Quilleré et al. [4] étendu et amélioré par
les travaux présentés dans [2]. Cette technique
génère les niveaux de boucles en projetant les polyèdres sur la dimension
correspondante, puis en séparant les projetés en polyèdres disjoints. On trie
ensuite ces polyèdres de manière à respecter l'ordre lexicographique.
On génère enfin récursivement les nids de boucles qui parcourent chaque polyèdre.
Domaines à parcourir
Code optimisé en taille
Code optimisé en gardes
for (i=1;i<=8;i++) {
for (j=i-1;j<=7;j++) {
S1 ;
}
if ((i<=6)&&(i>=2)) {
for (j=0;j<=4;j++) {
S2 ;
}
}
}
for (j=0;j<=7;j++) {
S1(i=1) ;
}
for (i=2;i<=5;i++) {
for (j=0;j<=i-2;j++) {
S2 ;
}
for (j=i-1;j<=4;j++) {
S1 ;
S2 ;
}
for (j=5;j<=7;j++) {
S1 ;
}
}
for (j=0;j<=4;j++) {
S2(i=6) ;
}
for (j=5;j<=7;j++) {
S1(i=6) ;
}
for (i=7;i<=8;i++) {
for (j=i-1;j<=7;j++) {
S1 ;
}
}
Ce générateur fait partie de Chunky, un outil de recherche dédié à l'amélioration
de la localité des données. Il a aussi été conçu pour être la partie finale de
paralléliseurs automatiques tels que PAF. Il est donc particulièrement orienté
'code compilable' et permet d'effectuer simplement des transformations de
programmes.
CLooG 1.0 sera la fusion de la version de recherche de CLooG
et de la version
GMP-snprintf de CLooG 0.12.1 par Sven Verdoolaege.
La version actuelle est encore pour l'évaluation et il n'y a pas de garantie
que la compatibilité ascendante sera respectée. De nombreux rapports d'expérience
sont nécessaires pour geler l'interface de la bibliothèque et la forme du
fichier d'entrée. Vous êtes donc invités et encouragés à
m'envoyer des messages
pour me signaler des bugs, mais aussi me faire part de vos souhaits, critiques,
commentaires, suggestions ou simplement me faire part d'expériences réussies.
Besoins
Pour installer CLooG, il est d'abord nécessaire d'installer la PolyLib version
5.0 ou supérieure. Vous avez seulement besoin de la version 32 ou 64 bits.
La PolyLib peut être téléchargée librement à partir de
http://icps.u-strasbg.fr/PolyLib/
ou http://www.irisa.fr/polylib/.
Une fois téléchargée et décompressée, vous pouvez la compiler en utilisant les
commandes suivantes :
./configure
make
Et en tant que super-utilisateur : make install
CLooG fait une utilisation intensive d'opérations polyèdriques, et c'est la
PolyLib qui se charge de ce travail. La PolyLib est une bibliothèque libre
écrite en C pour manipuler des polyèdres. Cette bibliothèque manipule des
objets tels que les vecteurs, les matrices, les treillis, les polyèdres, les
Z-polyèdres, les unions de polyèdres et bien d'autres structures intermédiaires.
Elle fournit des fonctions pour toutes les opérations importantes sur ces
structures [5].
0.12.1 -> 0.12.2 : Nouvelle option -cpp pour un code pseudo-compilable
(d'après une idée de Armin Größlinger de la LooPo Team, voir manuel),
traduction automatique des structures de données
vers des fichiers d'entrée pour LoopGen et Omega
CodeGen. Amélioration du support des strides.
Quelques corrections mineures.
0.12 -> 0.12.1 : Choix par configure de la version 32 ou 64 bits (64 bits
par défaut si la PolyLib64 est présente, 32 sinon), merci à
Sven Verdoolaege ! Optimisations par pattern matching :
jusqu'à deux fois plus rapide sur les CLooG benchmarks.
Quelques corrections mineures.
0.11.1 -> 0.12 : Meilleure gestion mémoire, support des strides,
diverses améliorations.
0.11 -> 0.11.1 : Ajout de l'option -block, modifications internes.
0.10.7 -> 0.11 : Modifications de l'API (lire la section 3.4 du
manuel), correction d'un bug sur les polyèdres vides.
0.10.6 -> 0.10.7 : Génération de pseudo-code FORTRAN 90,
améliorations et corrections mineures.
0.10.5 -> 0.10.6 : Support des domaines infinis (voir les exemples
infiniteX.cloog), améliorations mineures.
0.10.4 -> 0.10.5 : Utilisation mémoire réduite, liens depuis C++ facilités,
modifications mineures.
0.10.3 -> 0.10.4 : Correction de bugs mineurs.
0.10.2 -> 0.10.3 : Améliorations et changement d'API mineures, nécessite
une désinstallation de toute version précedente pour
mise à jour des headers.
0.10.1 -> 0.10.2 : Résolution du bug de propagation de constantes
négatives, et améliorations mineures.
0.10 -> 0.10.1 : Résolution de quelques problèmes de compilation.
Le manuel de CLooG [3] présente brièvement l'algorithme
de Quilleré et al. [4] et d'autres informations utiles
pour comprendre le fonctionnement du générateur. Il montre en détail comment
écrire les fichiers d'entrés pour le logiciel et comment choisir ses options
grâce à de nombreux exemples. Il présente la bibliothèque, ses structures de
données,et ses différentes fonctions. Il explique comment compiler, installer
et désinstaller le logiciel et la blibliothèque. Enfin il présente les travaux
en cours. Une copie de ce document est fournie dans le sous répertoire /doc
dans la distribution standard. Il serait fair play de référencer ce rapport
technique [3] ou mieux, l'article présentant les améliorations
apportées à l'algorithme de Quilleré et al. dans CLooG [2]
dans toute publication qui résulterait de l'utilisation de CLooG ou de sa
bibliothèque.
Mailing-list de la PolyLib:
Les annonces sur CLooG sont envoyées sur la mailing-list de la PolyLib
(en anglais). Pour rejoindre la liste, envoyez un mail à
sympa@u-strasbg.fr
avec le message suivant:
SUB PolyLib prénom nom organisation.
On vous demandera alors de confirmer votre inscription en répondant au message
que vous recevrez. Un forum pour la communauté
Polylib
a aussi été créé. vous pouvez
vous inscrire
au groupe pour avoir un contact complet avec le monde de la Polylib.
Les CLooG-Benchs sont un ensemble de problèmes réels de génération de code
tirés de divers programmes. Ces problèmes se veulent représentatifs du travail
de génération de code dans le modèle polyédrique. Nous avons choisi
d'énumérer les spécifications de regénération de toutes les parties à contrôle
statique de plusieurs benchmarks bien connus (le travail d'extraction a été
effectué par WRAP-IT).
Les problèmes vont du très
simple avec quelques instructions sans boucles, au plus compliqué avec plus
d'un millier d'instructions inclues dans plusieurs niveaux de boucles. Le
but de cette bibliothèque de problèmes est de permettre l'évaluation d'outils
de génération de code tels que CLooG.
La génération de code pour parcourir les Z-polyèdres est un problème bien connu.
Il a d'abord été résolu par Ancourt et Irigoin [1].
Il utilisèrent l'élimination de Fourier-Motzkin pour calculer les bornes des
boucles. Plusieurs générateurs descendent de cette technique :
Pour des situations complexes, la meilleure solution est celle de Quilleré et
al. [4]. Cette technique
génère les niveaux de boucles en projetant les polyèdres sur la dimension
correspondante, puis en séparant les projetés en polyèdres disjoints. Ensuite
on trie ces polyèdres de manière à respecter l'ordre lexicographique. Enfin
on génère récursivement les nids de boucles qui parcourent chaque polyèdre.
Les générateurs utilisant cette technique sont :
[1]
C. Ancourt and F. Irigoin. Scanning polyhedra with do loops. In 3rd ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming,
pages 39-50, june 1991.
[bibtex]
[2]
C. Bastoul.
Efficient code generation for automatic parallelization and optimization.
ISPDC'03 IEEE International Symposium on Parallel and Distributed Computing,
pages 23-30, Ljubljana, october 2003.
[pdf]
[bibtex]
[3]
C. Bastoul. Generating loops for scanning polyhedra.
Technical Report 2002/23, PRiSM, Versailles University, 2002.
[postscript]
[bibtex]
[Accueil]
[Télécharger CLooG]
[Documentation]
[CLooG-Benchs]
[Liens sur la Génération de Code]
[Références]
