Informations générales pour tous les stages :
1. Indemnité de stage :
L'estimation est la suivante :
- aucune indemnité, si le stage dure moins de 2 mois ;
- environ 400 euros entre 2 et 6 mois.
2. Lieu :
Centre de recherche en informatique - CRI
MINES ParisTech
35 rue Saint-Honoré
77305 Fontainebleau CedexUn bus privé gratuit est disponible quotidiennement depuis Paris, sauf durant les vacances scolaires, pendant lesquelles les transports en commun RATP doivent être utilisés.
Offres de stage :
- Coarse grain loop parallelization (Stage master recherche)
- Coarse grain loop fusion (Stage master recherche)
- Analyse sémantique des tableaux, des structures et des pointeurs (Stage master recherche)
- Analyse statique des paramètres fonctionnels et des pointeurs vers des fonctions (Stage master recherche)
- Coarse grain approach for loop invariant code motion (Stage master recherche)
- Détection des variables non initialisées d'un programme C (Stage master recherche)
- Détection des débordements de tableaux d'un programme C (Stage master recherche)
- Linéarisation de tableaux et test de dépendance
- Régénération de code source C
- Gestion des dépendances de contrôle dans l'élimination de code mort
- Parallèlisation des réductions par sections critiques
- Ordonnancement optimal et vectorisation des calculs de l'opérateur de Dirac (Stage Master recherche)
- Inférence de types et rates (Master II)
Description :
| Stage 1 « Coarse grain loop parallelization » : |  |
Loop parallellization is crucial for GPU's and multicore processors. Standard techniques are based on dependence graphs linking definition and usage of variable values. The graph arcs contain additional information about the relationship between loop iterations creating these arcs. This information is used to decide if the loop can be parallelized and how it should be parallelized.
The coarse grain approach does not use graphs but summaries of the loop body effects on memory. Each loop can be parallelized, regardless of its body control structure and procedure calls. Coarse grain parallelizations has already been implemented in PIPS, our automatic code analysis and transformation framework, but it should be reimplemented in a simpler way, using additional transformer information and integrating, as far as possible, auxiliary transformations such as array section privatization (this includes scalar and array privatization) and invariant code motion.
PIPS is programmed in C. It already contains lots of program analyses and transformation and is designed to be extensible. This makes adding new transformation pretty easy, once the framework is understood.
This internship requires a good C programmer, with an interest in computer architecture and code optimization, ready to interact with other PIPS developers over Internet.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 2 « Coarse grain loop fusion » : | |
Loop fusion is crucial for GPU's and multicore processors with a memory hierarchy because it improves locality, sometimes dramatically. Standard techniques are based on dependence graphs linking definition and usage of variable values. The graph arcs contain additional information about the relationship between loop iterations creating these arcs. This information is used to decide if two loops can be fused and how.
The coarse grain approach does not use graphs but summaries of the loops body effects on memory. Two loops can be fused if the memory areas they write do no impact the memory area they would have read before or written after. Bascially, the Bernstein conditions must be checked for different sets of iterations and this can be performed without building a graph. Loop fusion has already been implemented in PIPS, our automatic code analysis and transformation framework, using the standard graph-based technique, but it should be reimplemented in a simpler way, using additional transformer information, allowing shifting, prologue and epilogue when the iteration sets are different, and integrating, as far as possible, auxiliary transformations such as array section privatization (this includes scalar and array privatization) and invariant code motion. Non adjacent loops should also be tackled.
PIPS is programmed in C. It already contains lots of program analyses and transformation and is designed to be extensible. This makes adding new transformation pretty easy, once the framework is understood.
This internship requires a good C programmer, with an interest in computer architecture and code optimization, ready to interact with other PIPS developers over Internet.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 3 «Analyse sémantique des tableaux, des structures et des pointeurs» : | |
L'utilisation de structures et de pointeurs est traditionnelle dans de nombreux domaines, mais encore limitée pour les applications nécessitant de grandes puissances de calcul comme le calcul scientifique ou le multimédia. Cette utilisation nécessite des extensions des analyses statiques de tels codes, que la multiplicité et la complexification des architectures matérielles rendent plus nécessaires que jamais: multicore, GPU, multiprocesseur hétérogène, accélérateur FPGA,...
L'objectif du stage est d'abord de faire un tour rapide des analyses existantes dans PIPS et de proposer une ou plusieurs solutions pour effectuer les extensions nécessaires afin de couvrir les accès à des éléments de tableaux constants, les champs des structures et, si possible, les pointeurs. Ensuite, une ou plusieurs de ces extensions seront implantées en C dans le framework de compilation source-a-source PIPS.
Ce stage peut éventuellement se prolonger par une thèse dans le domaine de la compilation.Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 4 « Analyse statique des paramètres fonctionnels et des pointeurs vers des fonctions » : | |
L'utilisation de paramètres fonctionnels et de pointeurs vers des fonctions permet d'écrire des codes élégants et puissants, mais elle rend les analyses statiques de tels codes plus délicates alors que la multiplicité et la complexification des architectures matérielles les rendent plus nécessaires que jamais: multicore, GPU, multiprocesseur hétérogène, accélérateur FPGA,...
L'objectif du stage est d'abord de faire un tour rapide de la bibliographie et de proposer plusieurs solutions plus ou moins précises. Ensuite, une ou plusieurs de ces solutions seront implantées en C dans le framework de compilation source-a-source PIPS.
Ce stage peut éventuellement se prolonger par une thèse dans le domaine de la compilation.Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 5 « Coarse grain approach for loop invariant code motion » : | |
Loop invariant code motion is a standard code optimization technique. We currently use a technique based on dependence graphs linking definition and usage of variable values. The graph arcs contain additional information about the relationship between loop iterations creating these arcs. The Allen & Kennedy algorithm is slightly modified to hoist the invariant code through loop distribution. This is described in Julien Zory's PhD dissertation, available on line, and implemented in PIPS, our automatic code analysis and transformation framework.
The coarse grain approach does not use graphs but summaries of the loop body effects on memory and of each of its components. It is possible to decide independently for each statement if it can be moved out of the loop because its result is iteration independent. It is still unclear how efficient this approach can be in practice. It is simpler but can only move one statement of the loop body, not a set of statements as is possible with the A&K based algorithm. Experiments will be carried out to check the effectiveness of the coarse grain approach.
PIPS is programmed in C. It already contains lots of program analyses and transformation and is designed to be extensible. This makes adding new transformation pretty easy, once the framework is understood.
This internship requires a good C programmer, with an interest in computer architecture and code optimization, ready to interact with other PIPS developers.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 6 « Détection des variables non initialisées d'un programme C » : | |
La rétro-ingénierie, la maintenance et l'optimisation de codes nécessitent l'application de nombreuses analyses statiques ou dynamiques qui permettent de mieux comprendre, vérifier, améliorer et optimiser les instructions.
Parmi ces analyses, la détection des variables non initialisées avant leur utilisation permet d'éviter des erreurs lors de l'exécution du programme. Elle permet également de valider les analyses ultérieures portant sur les accès aux variables du programme, en lecture et écriture, telles que le calcul des dépendances.
La phase d'analyse dynamique de détection des variables non initialisées avant leur utilisation est déjà intégrée dans notre framework de compilation source-a-source PIPS pour des programmes en Fortran.L'objectif de ce stage est d'implanter cette analyse pour les programmes C.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 7 « Détection des débordements de tableaux d'un programme C » : | |
La rétro-ingénierie et la maintenance de codes nécessitent l'application de nombreuses analyses statiques ou dynamiques qui permettent de mieux comprendre et de vérifier les programmes.
Parmi ces analyses, la détection des débordements de tableaux est essentielle. Elle permet d'éviter des erreurs lors de l'exécution du programme, mais aussi de valider les résultats des analyses qui caractérisent l'ensemble des éléments de tableaux référencés par des instructions. La phase d'analyse dynamique de détection des débordements de tableaux est déjà intégrée dans notre framework de compilation source-a-source PIPS pour des programmes en Fortran.L'objectif de ce stage est d'implanter cette analyse pour les programmes C.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 8 « Linéarisation de tableaux et test de dépendance » : | |
PIPS est un framework de compilation source-a-source qui intègre de nombreuses transformations de programmes source-a-source ainsi que des analyses statiques et dynamiques et qui permet d'en développer rapidement de nouvelles.
Une des optimisations clés est la parallélisation automatique de boucles. Mais les programmeurs C ainsi que les générateurs automatiques de code C ont tendance à linéariser leurs tableaux, c'est-à-dire à remplacer les tableaux multidimensionnels par des tableaux monodimensionnels. Les expressions d'indices qui en résultent ne sont généralement pas affines et les tests de dépendance échouent. L'objectif de ce stage est de développer un nouveau test de dépendance permettant de linéariser, dans le vrai sens du terme, les polynomes qui résultent d'une linéarisation de tableaux. Un minimum de connaissance en algèbre linéaire permettra d'aborder le sujet plus facilement.Ce stage est plutôt orienté ingénieur, mais il peut éventuellement se prolonger par une thèse dans le domaine de la compilation.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 9 « Régénération de code source C » : | |
PIPS est un framework de compilation source-a-source qui intègre de nombreuses transformations de programmes source-a-source ainsi que des analyses statiques et dynamiques et qui permet d'en développer rapidement de nouvelles.
Les analyses et transformations sont appliquées à une représentation interne du programme, mais une fois les analyses ou transformations réalisées, il faut montrer le résultat en respectant au mieux le style initial du code source. L'objectif de ce stage est de raffiner cette phase de restitution pour les programmes C. Au-delà des problèmes d'indentation qui peuvent être traités en interne ou en externe via, par exemple, indent, il faudrait aussi reconnaître les graphes de contrôle qui peuvent être représentés par la construction switch, regénérer les includes, et ajouter des commentaires Doxygen en fonction des résultats d'analyse de PIPS.
Ce stage est plutôt conçu comme un stage ingénieur, mais il peut éventuellement se prolonger par une thèse dans le domaine de la compilation.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 10 « Gestion des dépendances de contrôle dans l'élimination de code mort » : | |
PIPS est un framework de compilation source-a-source qui intègre de nombreuses transformations de programmes source-a-source ainsi que des analyses statiques et dynamiques et qui permet d'en développer rapidement de nouvelles.
L'élimination de code mort consiste à retirer d'un programme toutes les instructions et les variables qui n'ont pas d'impact sur le résultat. Cette transformation s'appuie sur les use-def chains, mais elle doit aussi prendre en compte les dépendances de contrôle. Elle est particulierement utile pour traiter du code généré automatiquement par un outil ou un compilateur de langage DSL. L'implantation qui est disponible dans PIPS prend correctement en compte les dépendances de données, mais les dépendances de contrôle le sont imparfaitement.
Le but du stage est de compléter cette implantation, voire d'introduire une nouvelle analyse, une analyse de continuation. La continuation consiste à déterminer si un statement peut provoquer un arrêt ou une boucle infinie, ou bien si l'éxecution doit nécessairement passer au statement suivant. L'information de continuation reste à raffiner puisqu'on ne pourra pas toujours déterminer s'il y a continuation nécessaire ou continuation possible.
Ce stage est plutôt conçu comme un stage ingénieur, mais il peut éventuellement se prolonger par une thèse dans le domaine de la compilation.
Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 11 « Parallèlisation des réductions par sections critiques » : | |
PIPS est un framework de compilation source-a-source qui intègre de nombreuses transformations de programmes source-a-source ainsi que des analyses statiques et dynamiques et qui permet d'en développer rapidement de nouvelles.
La détection des réductions est implantée dans PIPS, mais elle est exploitée en générant les directives OpenMP spécifiques. Dans certains cas, il est plus efficace de ne pas distribuer une grosse boucle de calcul en une boucle de calcul parallèle et une boucle de réduction. Pour des raisons de localités, il vaut mieux éxécuter en parallèle la boucle initiale et protéger par une section critique la mise à jour de la variable de réduction.L'objet premier de ce stage est de générer les sections critiques nécessaires à l'éxécution parallèle des réductions. L'objectif second est de vérifier que cette technique permet de traiter efficacement les réductions avant ou après une parallèlisation dite CoarseGrain.
Ce stage est plutôt conçu comme un stage ingénieur, mais il peut éventuellement se prolonger par une thèse dans le domaine de la compilation.Personne à contacter :
Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : irigoin--at--mines-paristech.fr
| Stage 12 « Ordonnancement optimal et vectorisation des calculs de l'opérateur de Dirac » : | |
La Chromodynamique Quantique sur Réseaux (Lattice Quantum ChromoDynamics ou LQCD en anglais) étudie le mécanisme de la formation de la matière à travers l'interaction des particules fondamentales de l'univers sous les contraintes de confinement (naissance de l'univers juste après le Big Bang). Un axe très prépondérant de cette étude repose sur d'intenses simulations (de type Monte Carlo), dont le principal ingrédient est l'opérateur de Dirac. Du point de vue informatique, la mise en œuvre de cet opérateur expose des patterns d'accès mémoire assez spéciaux ainsi qu'un schéma de calcul pouvant contenir des redondances. L’évaluation de l'opérateur de Dirac étant très répétée, sa mise en œuvre optimisée (suivant l'architecture cible) est devenue le principal cheval de bataille dans la recherche en LQCD (voir le projet PetaQCD financé par l'Agence Nationale de le Recherche).
L'étude d'une mise en œuvre efficace de l'opérateur de Dirac se fait à deux niveaux. Le niveau macroscopique, dans lequel le réseaux global est subdivisé en sous-réseaux géométriquement identiques, il faut donc trouver le bon partitionnement et gérer efficacement les communications entre les sous-réseaux. Le niveau microscopique, dans lequel on réorganise les calculs de base de l'opérateur proprement dit de manière à réduire les redondances tout en limitant la perte d'efficacité mémoire (défaut de caches). Cette réorganisation peut se faire par des approches algébriques (factorisations et simplifications en algèbre linéaire) et/ou par une réécriture des instructions de manière à utiliser plus efficacement les possibilités de l'architecture cible (pipeline d'instructions, vectorisation). Le travail ici consistera à transformer le corps de la boucle principale de l'opérateur de Dirac, de manière à réduire au mieux les défauts de cache. On pourra utiliser un modèle analytique (à déterminer) ou un outil approprié pour mesurer l'efficacité mémoire. La vectorisation explicite du code sera ensuite envisagée.
Un minimum de connaissance en algèbre linéaire et optimisation de code facilitera l'entrée en matière pour ce sujet. De plus, un intérêt pour l'adéquation application/code/architecture sera utile pour entretenir un bon degré de motivation et d'enthousiasme. Il n'est pas nécessaire d'avoir des connaissances en physique des particules, mais un minimum de culture sur le sujet sera acquis en chemin. Ce stage, qui pourra être mené aussi bien sous un angle recherche que sous un angle programmation, pourra servir de point de départ pour une thèse en calcul haute performance (pour la QCD).
Personne à contacter :
Envoyer un CV et une lettre de motivation à Claude Tadonki (CRI, MINES ParisTech).
E-mail : tadonki--at--mines-paristech.fr
Web : http://www.omegacomputer.com/staff/tadonki/
| Stage 13 « Inférence de types et rates » : | |
1. Sujet :
Développement d'un algorithme de d'inférence de type et de "rate" (fréquence de signal) dans le langage Faust de traitement du signal audio.
2. Projet :
Le langage Faust, développé au Grame (Lyon), permet de spécifier de manière fonctionnelle des opérations de traitement du signal ; il est particulièrement adapté aux applications audio et musicales.
Dans une nouvelle version à venir, élaborée dans le cadre du projet ANR Astree en collaboration avec le CRI (MINES ParisTech), Faust a fait l'objet d'une extension vectorielle qui propose l'ajout (1) de nouvelles primitives permettant de manipuler des valeurs vectorielles et (2) de signaux de "rates" (nombre d'échantillons par seconde) différents. Cette extension a logiquement conduit à enrichir la sémantique statique du noyau du langage Faust, dont une spécification formelle a été proposée récemment (Jouvelot, P., and Orlarey, Y. Dependent Types for Multirate Faust. SMC’10, Barcelone, Aug.10).3. Descriptif :
L'objet du stage de niveau Master 2 Recherche, de quelques mois, avec prolongation en thèse possible, est, en partant du système de typage développé par le CRI et Grame :En fonction du temps disponible, une preuve informatique, en Coq, de l'ensemble de ce processus pourra être envisagée.
- de proposer un algorithme d'inférence de types et de rates ;
- de l'implémenter dans un prototype fondé sur un langage fonctionnel comme Caml;
- et d'en prouver la correction par rapport à la sémantique statique.
4. Exigences :
Une bonne connaissance de la programmation fonctionnelle, des systèmes de typage et des méthodes de preuves est nécessaire. Un intérêt pour la musique ou les traitements audio est un plus.5. Personne à contacter
Envoyer un CV et une lettre de motivation à Pierre Jouvelot (CRI, MINES ParisTech).
E-mail : pierre.jouvelot--at--mines-paristech.fr
Web : http://www.cri.mines-paristech.fr/~pj
