Giuseppe Castagna: Proposition de stage M2

Proposition de stage M2

TITRE: Programmation fonctionnelle pour Cartes Graphiques.

Le but de ce stage est de définir des analyses statiques, des optimisation et/ou des languages fonctionnels dédies à la programmation des GPUs. Deux pistes de recherche seront possibles selon la préparation et les préférences du stagiaire. Une première piste consiste en la définition d'une syntaxe fonctionnelle pour la bibliothèque Boost::MPL. Cette bibliothèque fournit un ensemble de fonctions et de structures de données méta-programmées en C++. Parmi ces fonctionnalités, une large place est laissée à l'émulation d'un langage fonctionnel résolu à la compilation. Ainsi du code comme :

template<class X,class N> 
struct exp : if_< equal_to<int_<0>,N>
                 , int_<1>
                 , times<X, exp<X, minus<N,int_<1> > >
                 > {};

réalise le même calcul que le code OCaml suivant

let rec exp x n = match n with
                   | 0 -> 1
                   | n -> x * exp x (n-1);;

Néanmoins, pour du code complexe, l'intention est perdue sous la couche syntaxique plutôt lourde des templates C++. En outre, certains programmes MPL peuvent conduire à des erreurs de compilations assez inextricables. On aimerait donc pouvoir débugger ces méta-fonctions en OCaml puis les porter en C++. Le but du stage sera donc la définition d'un langage fonctionnel dédié, destiné à être compilé en C++. Plus précisément on demandera la réalisation d' un outil de parsing permettant, à partir de code source écrit dans un (sous) ensemble de OCaml, de générer le code C++ équivalent utilisant MPL. Ce parseur sera écris en OCaml pour les plus courageux ou en C++ grâce à la bibliothèque Boost::Spirit.

Une deuxième piste de recherche, plus théorique, consistera dans la définition de systèmes de types et/ou d'autres analyses statiques pour les bibliothèques Boost::MPL et/ou QUAFF afin d'éviter un grand nombre de contrôles à l'exécution. Ce travail pourra être couplé avec une recherche plus axée sur l'optimisation. En particulier on demandera d'étudier des équivalences sémantiques/observationnelles du parallélisme afin d'en déduire des optimisations du code compilé.

Stage en collaboration avec Véronique Benzaken et Joël Falcou du Laboratoire de Recherche en Informatique de Paris XI.

Rémunération possible

Pré-requis

Bonne connaissance de la programmation fonctionnelle
Bon niveau en C++. Notion de base sur le parsing (piste 1)
Connaissance théorie des types, théorie de la concurrence, équivalences observationnelles (piste2)

Références

[1] Falcou, J., Sérot, J., Chateau, T., and Lapresté, J. T. 2006. QUAFF: efficient C++ design for parallel skeletons. Parallel Comput. 32, 7 (Sep. 2006), 604-615. DOI
[2] THE BOOST MPL LIBRARY

Contacts

Giuseppe Castagna

: Laboratoire PPS, Université Paris 7.
Véronique Benzaken

: Laboratoire LRI, Université Paris Sud.
Joël Falcou

: Laboratoire LRI, Université Paris Sud.