Informations générales

Les stages effectués au Centre de recherche en informatique de MINES ParisTech sont réalisés sous la responsabilité d’un chercheur ou ingénieur permanent du centre.
L’accent est mis sur la qualité du travail réalisé, l’autonomie des stagiaires, voire leur pro-activité, dans un cadre qui favorise les échanges informels.
Les propositions de stage ci-dessous sont disponibles à tout moment.</p>

Liste des offres de stage

Les offres de stage sont classées selon les catégories suivantes :

Offres de stage


Stage « Efficient Data Structures for Points-to Analysis »

Points-to analysis is crucial to analyze, transform. optimize and compile C programs. Many different kinds of points-to analyses have been introduced but they all depend on efficient data structures to minimize their space and time complexities. For the time being, only simple and crude analyses are performed in production compiler because of the potential cost of more accurate analyses.
In her PhD, Amira Mensi has implemented in PIPS an interprocedural bottom-up points-to analysis to reduce the points-to graph size to the locally visible pointers. However, the underlying data structure she uses is correct but not efficient, neither in space nor in time. The goal of the internship is to analyze the deficiencies of the current implementation by obtaining traces for the many test cases accumulated by Amira, to design several alternative data structures, to select the best one and to integrate it in the current implementation using a new API for points-to graphs.
PIPS is programmed in C and managed with SVN. It already contains many program analyses and transformation and is designed to be extensible. This makes adding new transformations pretty easy, once the framework is understood. This internship requires a good C programmer, with an interest in abstract interpretation and code optimization, ready to interact with other PIPS developers over Internet. The subject is extensible and could lead to a PhD position.

Personne à contacter : Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : francois.irigoin–at–mines-paristech.fr


Stage « Generation of Distributed Code: a Small Step Approach to Prove Correctness » :

Code distribution is crucial for many embedded systems and large scale scientific applications. Standard techniques are based, in practice, on the MPI library or on ad'hoc development tools. In both cases, programmers must tackle alone all the issues linked to distributed programming: memory consistency, deadlock, efficiency. Several attempts have been made in research to ease distributed programming using either directives or new programming languages, but compiler technology is not used much because the parallel constructs are either macros or syntactic sugar for a run-time library.

In her PhD, Dounia Khaldi has proposed to generate distributed code directly from a mapping of the statement on the target architecture and from a data dependence graph. It turns out that her heuristic is not robust. The goal of the internship is to explore small-step approaches, classical with compilers and their many passes. Instead of looking for a one-shot transformation from shared to distributed memory code, the intern should look for succession of small transformations, i.e. compiler passes, leading from an initial mapped code for a shared memory machine to a final distributed code. Hopefully, many of the necessary transformations are already implemented in our PIPS framework, but new ones will have to be added.

PIPS is programmed in C. It already contains lots of program analyses and transformation and is designed to be extensible. This makes adding new transformations pretty easy, once the framework is understood.

This internship requires a good C programmer, with an interest in computer architecture and code distributionion, ready to interact with other PIPS developers over Internet. The subject is very ambitious and can lead to a PhD position.

Personne à contacter :

Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : francois.irigoin--at--mines-paristech.fr



Stage « 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 : francois.irigoin--at--mines-paristech.fr



Stage « 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 : francois.irigoin--at--mines-paristech.fr



Stage « 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 : francois.irigoin--at--mines-paristech.fr



Stage « 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 : francois.irigoin--at--mines-paristech.fr


Stage « 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 : francois.irigoin--at--mines-paristech.fr


Stage « 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 : francois.irigoin--at--mines-paristech.fr

Stage « 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 : francois.irigoin--at--mines-paristech.fr


Stage « 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 : francois.irigoin--at--mines-paristech.fr


Stage « 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 : francois.irigoin--at--mines-paristech.fr


Stage 8 « 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 : francois.irigoin--at--mines-paristech.fr


Stage « 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 <a href="https://www.petaqcd.org/" target=_blank>PetaQCD </a> 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.

Prérequis :
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 : claude.tadonki--at--mines-paristech.fr
Web : http://www.omegacomputer.com/staff/tadonki/

Stage « Représentations intermédiaires parallèles pour LLVM et GCC » :

Sujet :
Application de la méthodologie SPIRE, développée au CRI et permettant l'extension des représentations intermédiaires de compilateurs, aux plateformes LLVM et GCC.

Projet :
La plupart des grandes plateformes de compilation comme LLVM, GCC ou PIPS ont été conçues dans l'optique de la génération de code pour des langages impératifs séquentiels. Avec la multiplication des architectures multicoeurs, des langages explicitement parallèles de type X10, Habanero-Java… et des extensions parallèles type OpenMP et MPI, il convient d'envisager d'étendre l'architecture de ces plateformes pour être à même de traiter les spécificités de ces langages.
Afin de pouvoir réutiliser autant que possible l'investissement logiciel lourd auquel correspondent ces compilateurs, la méthodologie SPIRE d'extension "légère" de représentation intermédiaire, une structure de données centrale dans ces systèmes, a été proposée au CRI et validée, en partie, dans le cas de la plateforme de compilation PIPS.

Descriptif :

L'objet du stage de niveau Master 2 Recherche, de quelques mois, est, en partant du système SPIRE développé par le CRI :

  • d'étudier en détail les représentations intermédiaires (RI) des compilateurs LLVM et GCC ;
  • d'analyser les extensions parallèles des RIs déjà introduites dans la littérature ;
  • de tester la capacité de la méthodologie SPIRE à étendre ces RIs séquentielles au monde parallèle ;
  • et d'implémenter dans au moins une de ces plateformes ces RI étendues pour en tester expérimentalement la pertinence.

Exigences :
Une bonne connaissance de la programmation en C, des systèmes de compilation et des méthodes de spécification formelle est nécessaire.

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

Stage « Multithreading sous Matlab » :

Sujet :
Multithreading sous Matlab (Stage Master Recherche 2012/2013)

Projet :
Matlab est un environnement de calcul et de programmation scientifique très utilisé pour la puissance de son moteur (noyau de traitement constitué de routines optimisées) et sa très grande flexibilité (prise en main aisée et utilisation assez souple).
Toutefois, dans sa version "langage de programmation", il propose un interpréteur à la place d'un compilateur. Ceci justifie sa souplesse de programmation et d'exécution interactive, mais en contre partie, il y a d'une part le surcoût sur le temps global d'exécution qui est dû au fonctionnement de l'interpréteur, et d'autre part la difficulté (voire l'impossibilité) d'utiliser directement les outils traditionnels d'analyse et d'optimisation de codes (y compris la parallélisation).
Notons toutefois qu'il existe un moyen de se raccrocher à un langage compilé tel que le C (C++ ou Fortran) via le mécanisme des fichiers "mex".
Avec l'avènement des machines multicœurs, il devient indispensable d'offrir la possibilité de paralléliser les applications dans tout environnement de programmation ou de calcul.

Descriptif :
Le but de ce stage sera donc d'étudier ce problème dans le cadre de Matlab.
En résumé, il s'agit d'étudier les mécanismes de programmation ou d'exécution multithreadée sous Matlab, en analyser les avantages et inconvénients, et procéder à des études de cas avec mesures de performances commentées.
Ce sera l'occasion pour le stagiaire, en fonction de ses capacités, de développer aussi sa propre méthodologie, tout au moins en initier une qui pourra être approfondie plus tard et étendue aux environnements similaires.

Exigences :
Le candidat devra avoir un niveau acceptable en C et connaître un peu Matlab (pas indispensable toutefois, à défaut il y aura une phase de familiarisation préalable).
De même, des notions de base de parallélisme sont importantes, surtout le modèle à mémoire partagé. L'occasion sera donnée au candidat de s'initier à la parallélisation automatique.

Personne à contacter :

Envoyer un CV et une lettre de motivation à Claude Tadonki (CRI, MINES ParisTech).
E-mail : claude.tadonki--at--mines-paristech.fr
Web : http://www.omegacomputer.com/staff/tadonki/

Stage « Modélisation de la bibliothèque MPI dans un compilateur source-à-source » :

Contexte :
PIPS est un framework de compilation source-à-source qui intègre de nombreuses transformations de programmes source-à-source ainsi que des analyses statiques et dynamiques et qui permet d'en développer rapidement de nouvelles. Par exemple, PIPS peut réaliser une analyse de préconditions qui permet de déterminer quelles sont les conditions vérifiées avant l'exécution d'une instruction. Il permet également de faire des transformations telles que l'élimination de code mort, qui détecte les instructions inutiles et les supprime, ou encore du déroulage ou de la fusion de boucles. Parmi ces transformations, une génération de code parallèle distribué au moyen de la bibliothèque MPI est en cours de développement. PIPS peut prendre en entrée du code C ou Fortran.
Cependant, le code distribué MPI n'est actuellement pas supporté par PIPS en entrée. Le code MPI généré ne peut donc pas être réanalysé et aucune nouvelle transformation ou optimisation n'est possible sur celui-ci.

Objectif :
L'objectif de ce stage est d'étudier et surtout d'implémenter les différentes possibilités de prise en charge d'une telle bibliothèque. Pour cela, le stagiaire sera amené à étudier le comportement des fonctions MPI.
Puis, il devra les intégrer dans la représentation interne de PIPS. Plusieurs solutions ont déjà été envisagées, mais le candidat est libre d'en proposer de nouvelles. Par exemple, des stubs peuvent être créés pour simuler les fonctions MPI ou des intrinsèques MPI peuvent être ajoutés à ceux déjà présents dans PIPS.
Durée : 3 à 6 mois

Prérequis :
Une bonne connaissance du langage de programmation C est exigée. Une connaissance de la bibliothèque MPI et du langage Fortran est un plus.

Référence:
PIPS : http://www.pips4u.org/
MPI : http://www.mpi-forum.org/

Personne à contacter :

Envoyer un CV et une lettre de motivation à François Irigoin (CRI, MINES ParisTech).
E-mail : francois.irigoin--at--mines-paristech.fr

Stage « Mise en oeuvre efficace d'algorithmes d'inondation sur des grandes images à niveaux de gris » :

Une image à niveaux de gris peut être considérée comme un relief topographique, lorsqu'on attribue à chaque point de l'image une altitude proportionnelle à son intensité de gris. Cette représentation reste valable quel que soit le nombre de dimensions spatiales de l'image ou encore lorsque l'information d'altitude est portée par les poids attribués aux noeuds d'un graphe (éventuellement valué).

Une inondation d'un relief produit un certain nombre de lacs de profondeur quelconque. Un tel relief image représente une nouvelle image à niveaux de gris, plus simple avec moins de vallées que le relief initial. Et bien évidemment, la surface de chaque lac est plate.

L'opération duale de l'inondation consiste à araser les pics. On l'obtient en inondant le négatif d'une image avant de reprendre le négatif du résultat; on arase ainsi les pics. On peut éviter cette double négation et construire directement les opérateurs d'arasement. Ces derniers se déduisent très simplement des algorithmes d'inondation et sont de même complexité. Nous ne nous intéresserons donc ici qu'aux algorithmes d'inondation.

Les deux opérateurs d'inondation et d'arasement sont les ingrédients de base de beaucoup d'opérateurs de filtrage et de segmentation. De nombreuses inondations sont possibles pour un relief donné ; cependant il en existe une seule si on considère la plus haute inondation possible d'une fonction f sous la contrainte d'une fonction plafond g. La fonction g est une fonction quelconque, supérieure ou égale en tout point à la fonction f (comme un seuil d'altitude non nécessairement constant).

L'opérateur d'inondation maximale prend les images f et g en entrée et produit l'image de l'inondation en sortie, laquelle est une image à niveau de gris égale à l'altitude de l'inondation en tout point inondé et au relief f partout ailleurs.

Les algorithmes classiques sont de deux types: les premiers construisent le résultat par balayages itératifs de l'image, tandis que les deuxièmes contrôlent l'inondation au moyen d'une file d'attente hiérarchique. Ces algorithmes sont très lents sur des très grandes images (2D ou 3D), l'objet de stage est donc de les accélérer. On explorera plusieurs voies :

  • Si on a recours à plusieurs coeurs ou processeurs, comment faut-il leur distribuer le travail de la manière la plus efficace ?
  • Etudier le recours à des représentations locales du relief sous forme de flèches entre chaque point et ses voisins plus hauts ou plus bas afin de limiter le nombre d'accès à la mémoire.
  • Réaliser des mises en oeuvre sur processeurs vectoriels ou graphiques. Contacts:

Personnes à contacter :

Envoyer un CV et une lettre de motivation à
Fernand Meyer (fernand.meyer--at--mines-paristech.fr) et
Claude Tadonki (claude.tadonki--at--mines-paristech.fr)

 

Stage « Mise en oeuvre efficace d'un système de localisation de texte enfoui dans des images ordinaires » :

Les OCR (Optical Character Recognition) commerciaux sont de plus en plus performants mais leur utilisation est encore restreinte aux documents numérisés ou aux images prises dans des conditions d'acquisition maîtrisées (support plat, sans effet de perspective, le document occupant la presque totalité de l'image,..). Ils ne sont pas capables de gérer la diversité de styles, les déformations liées à la perspective ou la complexité de l'environnement. La localisation du texte enfoui est une étape nécessaire pour étendre les conditions d'utilisation des OCR existants.

Le CMM (Centre de Morphologie Mathématique) de l'Ecole des Mines de Paris a développé un système de localisation de texte enfoui pour des images tout venant. Ce système a remporté la première place dans la catégorie « localisation de texte » lors de la campagne d'évaluation d'algorithmes de traitement d'images ImagEval. Aucune contrainte temps réel n'était considérée à cette occasion.

Aujourd'hui nous envisageons de porter ces algorithmes sur des dispositifs portables, type smartphone. Pour cela, un travail important de simplification et d'optimisation des algorithmes est nécessaire. Il s'agit de trouver un compromis qualité/performance satisfaisant. En effet, la puissance traitement des systèmes mobiles est modérée, de même que l'approvisionnement en énergie (généralement de modestes batteries). A partir du système mobile, on devrait donc être capable d'acquérir une image avec ses contraintes (résolution et environnement) et d'en extraire les informations textuelles dans un délai acceptable à l'échelle de l'utilisateur. Le texte deviendrait accessible aux personnes malvoyantes ou illettrées (ou ne parlant pas la langue du pays où elles se trouvent) en combinant ce système soit à un module de restitution orale ou à un module de traduction, respectivement. On peut bien sûr imaginer un télétraitement de cette phase dans une approche du type Cloud Computing, mais nous ne l'aborderons pas dans ce stage.

Exigences :
Le candidat retenu pour ce stage aura pour tâche principale d'accélérer un module critique de l'application développée par le CMM, de manière à répondre à l'exigence du compromis qualité/performance mentionné précédemment. Le travail se fera sur des processeurs multi-coeurs standards, très probablement en C. Toutefois, si le candidat a des compétences dans la programmation des systèmes mobiles et si le temps le permet, il pourra étendre sa contribution dans ce contexte-là.

Personnes à contacter :

Envoyer un CV et une lettre de motivation à
Beatriz Marcotegui (beatriz.marcotegui--at--mines-paristech.fr) et
Claude Tadonki (claude.tadonki--at--mines-paristech.fr)

 

Stage « Reconstruction d'images à grande échelle sur GPU » :

Description du stage :
Dans le contexte de la simulation de forage, la reconstruction d'une vue principale à partir de vues partielles est une opération importante et récurrente. En plus de la complexité fondamentale de l'algorithme considéré, il faut ajouter celle liée à la résolution des images traités. Comme la plupart des modules de traitement d'images, l'accélération à l'aide de GPUs est devenu un recours naturel. Toutefois, sachant que le principal goulot d'étranglement en ce concerne les GPUs c'est la mémoire et les échanges avec le CPU, la considération des scénaris à grande-échelle (taille et/ou résolution) à performance quasi-constante est un défi technique à étudier. Le but du présent stage est d'explorer les possibilités de mise en oeuvre efficace de la reconstruction d'images à grande échelle sur les GPUs de dernière génération.
Le travail débutera par le déploiement et le profilage du module existant, suivi d'une extension pour la prise en compte des résolutions élevées. La mise au point pourra se faire sur les GPUs disponibles, le passage au GPU Pascal par exemple se fera par la suite.

Exigences :

Le candidat devrait avoir un bon niveau en programmation C et quelques notions de traitement d'images. Des bases en programmation GPU seraient un plus.

Personnes à contacter :

Envoyer un CV et une lettre de motivation à
Claude Tadonki (claude.tadonki--at--mines-paristech.fr) et
Olivier Stab (olivier.stab--at--mines-paristech.fr)

Stage « Maude in Dedukti » :

Context : Dedukti is a type-checker for the lambda-Pi calculus modulo, a type system characterized by two features: dependent types and a conversion rule generated by beta-reduction and rewriting modulo a given set of rewrite rules Preliminary experiments have shown that the reduction algorithm (a modi cation of the virtual machine of Matita that takes into account rewrite rules) behaves well on simple examples coming from Rewriting Logic and has comparable results to Maude.

Subject : The aim of this internship is to go further in this direction, by de ning a transla- tion from Rewriting Logic into Dedukti's format, and by improving the reduction algorithm of Dedukti to become competitive on the whole set of problems with respect to Maude.

Prerequisites : An advanced course on the fundations of computer science such as logic, type theory or rewrite systems. A compiler course would be a plus

Environment : The intern will be hosted by the Deducteam project-team at Inria Paris-Rocquencourt and/or the CRI at MINES ParisTech.

More information in this file.

Personnes à contacter
:

Envoyer un CV et une lettre de motivation à
Olivier Hermant(olivier.hermant--at--mines-paristech.fr)

Stage « Normalization by Completeness » :

Context : Proofs of cut elimination have took two di erent ways for a long time: syntac- tic cut reduction and proofs that this process terminates, and semantic proofs of cut admissiblity.
Recent works tend to show that some unity exist between two methods. The goal of this project is therefore to compare those two approaches, and more speci cally, to force cut admissibility to generate proofs in normal form that are reducts of the original proofs via an adequate reduction relation.
The main framework of interest of this internship will be Deduction Mod- ulo, that provides in particular a uni ed way to study axiomatic theories and axiomatic cuts.

Subject : The internship will rst focus on the study of the pair of theorems soundness/(cut- free) completeness, and on the computational content of such a cut admissibility proof. This can for instance be made through a formalization in a (construc- tive) proof-assistant of the propositional fragment, as did Hugo Herbelin for completeness with respect to Kripke structures.
The next steps will depend on the interests an results of the candidate. That could be for instance:

- carrying the initial proof (in sequent calculus, natural deduction, ...) through soundness and completeness in order to make a formal link between the original proof and the cut-free proof obtained at the very end.
- model transformations that go from Heyting algebras to (extensions of) Kripke structures, in order to compare this work to Normalization by Evaluation. This last step will take us into the world of proof normalization, while we have started by pure semantic proofs of cut admissibility

Prerequisites : At least one advanced course on the fundations of computer science such as logic or type theory. Some notions of category theory would be a plus.

Environment : The intern will be hosted by the Deducteam project-team at Inria Paris-Rocquencourt and/or the CRI at MINES ParisTech.

More information in this file.

Personnes à contacter
:

Envoyer un CV et une lettre de motivation à
Olivier Hermant(olivier.hermant--at--mines-paristech.fr)

Stage « Management of Irradiation Experiments » :

Context : In the irradiation facilities located at CERN (the European Laboratory of Particle Physics – www.cern.ch), several hundreds of objects are exposed every year to different kinds of particle beams for a large international particle-physics community. These irradiation tests are performed for various reasons, mainly for the damage testing of detector and accelerator components, materials and electronics, but also for the benchmarking of simulation codes and the calibration of dosimeters and radiation monitors.

One of these reference facilities at CERN is the Proton Irradiation Facility (IRRAD). A set of custom-made software tools are used in IRRAD:

  • - the IRRAD Data Manager (IDM) handles the data management of the experiments;
  • - the samples to be tested are positioned on remote-controlled stages supervised by a dedicated control system;
  • - Beam Profile Monitor (BPM) detectors are also used in the facility for monitoring the beam and rely on a specific data acquisition system.

The successful intern candidate will work as a "CERN Technical Student" on the development and upgrades of IDM and of the control and data acquisition systems for IRRAD. At the end of his/her stay, the student will have acquired a basic knowledge about particle physics and particle detectors (if not known already), experienced the complete lifecycle of a project from conception to production and gained knowledge of new software tools and frameworks.
The internship will be located at the CERN main campus (Geneva, Switzerland), under the academic supervision of MINES ParisTech (Paris, France).


Required computing skills : Python is a must, while the knowledge of the following other tools/frameworks/languages will be an advantage:

  • C++/C#;
  • Wed development (JavaScript, HTML, CSS, Django Framework, Semantic UI);
  • PyQt;
  • Linux.

CERN is an international institution; good English practice is a plus.


Contact information :

Send a CV and a motivation letter to Pierre Jouvelot (CRI, MINES ParisTech).
Final registration will have to be performed on the https://careers.smartrecruiters.com/CERN/tech Web site.


Email: pierre.jouvelot--at--mines-paristech.fr)
Web: http://www.cri.mines-paristech.fr/~pj </div> </blockquote>