Sujets d'approfondissement pour le cours

"modèle polyédrique"

 

Les propositions suivantes sont des classées par thèmes. Pour chaque sujet j'ai  indiqué un article de référence, et j'ai suggéré une direction de recherche pour l'approfondissement. Bien sûr, cette direction peut être modifiée par l'étudiant selon ses motivations. Lorsqu'un seul article est mentionné, cela signifie que les références susceptibles d'être intéressantes pour ce thème sont toutes présentes dans l'article.

Il n'y a, à priori, pas de consignes précise pour la forme du rapport. Je conseille un rapport entre 7 et 15 pages dactylographiées (i.e. pas écris à la main, je n'ai aucune contrainte sur le traitement de texte). Pas plus de 20 pages (en général, il est plus difficile de faire court que long). Les rapports doivent impérativement être rendus une semaine avant la soutenance pour permettre aux relecteurs de lire (pour ceux qui passent en Janvier, le rapport doit être rendu fin décembre pour qu'il n'y ait pas trop d'écart entre les temps de préparation). La présentation dure approximativement  1/2h (pas plus d'une heure) qui est suivie d'un débat (questions puis discussion). Deux relecteurs notent la présentation et l'exposé, (pensez que si vous passer plus tard, il y a une semaine ou vous aurez un rapport à relire). Un point intermédiaire sera fait le 19 Novembre, les exposés commencant le 3 décembre. Je suggère que  les orateurs du 3 décembre passent me voir apres le cours  du 12 novembre pour faire leut point avant. N'hesitez pas a poser des questions par mail, je le lirai probablement du canada dans la semaine du 2 au 10 Novembre.

Voici des fiches de notations pour le rapport et la présentation

  Affectation des sujets

Andrianarisoa Ny Haingo : Polylib, Chernikova: aspect d'implémentation (3)

Arnaud Alexis : Génération de code dans le modèle polyédrique (4)

Bernardi Vincent : polyèdres paramétrés et polynômes d'Ehrhart (1 et/ou 2)

Eyraud Lionel : optimisation mémoire pour systèmes intégrés (8)

Goglin Brice : Transformations de boucles pour FPGA (9)

Laganier Julien : Ordonnancement sous contraintes de ressources (7)

Riffault Olivier : Ordonnancement cyclique hiérarchique (6)

Vernois Antoine : Génération de code "à la Omega" (5)

 

Calendrier

lundi 5 Novembre : Pas de cours

lundi 12 Novembre : cours 5

lundi 19 Novembre : point intermédiaire sur chaque projet (chacun passe 15 minute avec moi pour présenter ou il en est des lectures, expliquer ce qu'il a compris et propose un plan pour le rapport)

lundi 27 Novembre cours 6, rapport rendus par Andrianarisoa Ny Haingo et Bernardi Vincent (lecteurs: Brice Goglin et Lionel Eyraud)

Lundi 3 décembre :  présentations Andrianarisoa Ny Haingo et Bernardi Vincent rapports rendus Laganier Julien et Riffault Olivier, Arnaud Alexis  (lecteurs Andrianarisoa Ny Haingo et Bernardi Vincent et Vernois Antoine)

lundi 10 décembre : présentations Arnaud Alexis, Laganier Julien et Riffault Olivier rapports rendus  Vernois Antoine, Brice Goglin et Lionel Eyraud (lecteurs Laganier Julien,   Riffault Olivier, Arnaud Alexis)

lundi 17 décembre : présentations Brice Goglin et Lionel Eyraud et Vernois Antoine

lundi 7 Janvier :

 

Fondements du modèle polyédrique

  1. polyèdres paramétrés et polynômes d'Ehrhart. Cet article présente un résumé des travaux de Philippe Clauss et Vincent Loechner sur les polyèdres paramétrés et les polynômes d'Ehrhart permettant de compter les points dans un polyèdre paramétré. En plus de la présentation technique de ces outils, on pourra essayer de réfléchir à leurs applications dans le domaine de la compilation de boucle.
  2. Z-polyèdres et LBL les Z-polyèdres ont été étudiés à Rennes puis implémentés dans la Polylib les LBL sont proposés par Teich et Thiele. On présentera ces travaux et comme ci dessus, on pourra essayer de réfléchir à leur applications dans le domaine de la compilation de boucle.
  3. Polylib, Chernikova: aspect d'implémentation. l'algorithme de chernikova permet de passer de la représentation implicite à la représentation paramétriques des polyèdres. On présentera cet algorithme puis on étudiera les implémentations de bibliothèques de calcul sur les polyèdres: Polylib (disponible en .http://www.irisa.fr/cosi/HOMEPAGE/Risset/Polylib/), Omega (http://www.cs.umd.edu/projects/omega/), on pourra envisager une démo....

Aspect compilation

  1.  Génération de code dans le modèle polyédrique. Les travaux les plus récents dans ce domaine sont ceux de Rajopadhye et Quilleré. On expliquera les problèmes et les techniques de génération de code dans le modèle polyédrique, on montrera le liens avec le problème de la réutilisation de mémoire. On peut aussi envisager une démo avec LoopGen
  2. Génération de code "à la Omega". L'équipe de rice utilise l'outil Omega (un peu plus puissant que la Polylib) pour compiler du HPF (High Performance Fortran). On expliquera la technique exposée ici et on pourra réfléchir sur les avantages de l'approche américaine sur l'approche européenne basée sur Polylib et Pip.
  3. Ordonnancement cyclique hiérarchique. L'ordonnancement cyclique hiérarchique permet d'ordonnancer un système d'équations récurrentes structurées. On étudiera cette structuration et cet ordonnancement puis on réfléchira à d'autres méthodes pour l'ordonnancement hiérarchique pour systèmes intégrés. On pourra aussi comparer les techniques d'ordonnancement cyclique en se basant sur cette étude.
  4. Ordonnancement sous contraintes de ressources. Deux techniques permettent de limiter les ressource disponibles lors d'une parallélisation automatique: le partitionnement permet d'exécuter N processeur virtuels sur N/p processeurs physique et l'ordonnancement sous contrainte de ressource permet de limiter les ressources utilisées à chaque itérations les approches de Feautrier et Fimmel pourront être comparées.

Aspects matériels

  1. Optimisation de la mémoire pour systèmes intégrés. Les transformations de fusion de boucles et d'alignement de boucles peuvent être utilisées pour optimiser la mémoire dans les systèmes intégrés (system on chip, SoC). On présentera ces techniques et on pourra réflechir à une utilisation plus poussée des techniques de transformations de boucle (combinaison de fusion et alignement, pavage de boucle, etc.). On pourra aussi présenter la problématique générale de conception de SoC.
  2. Transformation de boucle pour FPGA. Les outils de resynchronisation (retiming) pour circuits synchrones ouvrent de nouvelles perspectives pour les transformations de boucle appliquées au FPGA. Steven Derrien propose d'optimiser la conception d'architectures régulières pour augmenter la fréquence de fonctionnement sur un circuit FPGA.  On étudiera cette technique et on pourra aussi essayer de regrouper les travaux sur les transformation de boucles pour FPGA.