Benjamin COHEN BOULAKIA
27, rue des Girondins,
F-92 210 Saint-Cloud.
Né le 31 Aout 1976
au Blanc-Mesnil (93).
Nationalité Française,
Célibataire.
Depuis novembre 2002, Doctorant au laboratoire PRiSM à l'Université de Versailles, où je suis actuellement A.T.E.R., j'ai commencé ma thèse sous la direction de William Jalby, professeur responsable de l'équipe «Architecture et Parallèlisme» et suis actuellement co-encadré par Dominique Barth, professeur responsable de l'équipe «Algorithmique, Combinatoire Analytique et Applications», et Johanne Cohen, chargée de recherche du CNRS au sein du laboratoire LORIA de l'université de Nancy I. Mes travaux portent sur des méthodes d'optimisation combinatoire pour la résolution de problèmes d'ordonnancement de code sous contrainte de registres issus de la compilation.
Mon activité d'enseignement a débuté en 2000 lorsque j'ai participé aux tutorats d'initiation à la bureautique dispensés aux étudiants en première année de DEUG, expérience que j'ai eu l'occasion d'approfondir en organisant cette activité conjointement avec Claude Timsit, ainsi que par des enseignements similaires en DEUG AES. J'ai par la suite diversifié mes activités en enseignant des matières comme le système d'exploitation, la compilation, la programmation en C ou en JAVA, ce à divers niveaux et filières, du DEUG jusqu'à la maîtrise d'informatique, ainsi que dans des filières non informaticiennes, comme par exemple la licence SPI (Sciences Pour l'Ingénieur).
| Année | 00 - 01 | 01 - 02 | 02 - 03 | 03 - 04 | 04 - 05 | total |
|---|---|---|---|---|---|---|
| compilation (Maîtrise) | 24 | 24 | ||||
| Systèmes d'Exploitation (Licence) | 38 | 38 | 76 | |||
| Langage C (Licence) | 36 | 36 | ||||
| Encadrement de projet (Licence) | 20 | 20 | ||||
| JAVA Avancé (2ème année DEUG) | 30 | 30 | ||||
| Bureautique (1ère année DEUG) | 48 | 48 | ||||
| Tutorats Bureautique (1ère année DEUG) | 12 | 12 | 12 | 36 | ||
| Total | 12 | 60 | 66 | 58 | 74 | 270 |
Du fait de ma formation à la fois technique (IUT) et théorique (DEA), je suis ouvert à tout type d'enseignement, ainsi qu'à la prise de responsabilités dans l'organisation de ces enseignements.
Ce module optionnel, après un rappel en théorie des langages, aborde des notions théoriques (pré-processeur, analyseur lexical et syntaxique…) et techniques (code assembleur, utilisation de Lex et YACC) de compilation. Ce module a donné lieu à un projet de contrôle continu dont j'ai assuré l'évaluation et la correction.
Il s'agit d'une matière axée sur la programmation système. Ce module accueillant essentiellement des étudiants sans aucune expérience de la programmation en C, une première partie de ce module consiste donc en l'apprentissage de ce langage. Par la suite, les primitives systèmes sont abordées. Ce module a donné lieu à plusieurs projets de contrôle continu, pour lesquels j'ai participé à l'élaboration des sujets, ainsi qu'à la correction.
Le but de ce module est d'enseigner la programmation en langage C à des étudiants de 2ème et 3ème année de licence de Sciences Pour l'Ingénieur. Il s'agit d'une filière non informatique, dans laquelle les étudiants ont une connaissance assez succincte de la programmation. J'ai, dans le cadre de cet enseignement apparu lors de la réforme LMD, participé à l'adaptation des supports d'enseignement issus des modules de licence d'informatique, ainsi qu'à la conception et la correction du projet de contrôle continu associé.
Ce module est un module d'encadrement de projet en groupe de 6-8 étudiants. J'ai, dans le cadre de ce module, rédigé deux sujets complémentaires, l'un à caractère technique, et l'autre d'approche plus théorique, et encadré les étudiants pendant la réalisation de ce projet.
Module optionnel de deuxième année de DEUG, ces travaux pratiques s'adressent essentiellement aux étudiants envisageant sérieusement une poursuite d'études en licence d'informatique. C'est un module essentiellement axé sur le développement d'un projet en JAVA. J'ai, dans ce module, participé à la rédaction du sujet de projet et des supports d'enseignements, ainsi qu'à la correction et l'organisation des présentations.
Il s'agit d'un enseignement abordant la conception de feuilles de calcul sous Excel. Cet enseignement s'adresse à des étudiant ayant très souvent une faible maîtrise de l'outil informatique. Dans le cadre de cet enseignement, j'ai participé à la rédaction des sujets d'examens, ainsi qu'à leur correction.
Cet enseignement n'est pas un module obligatoire, mais un tutorat destiné aux étudiants arrivant à l'université. Il a pour but de familiariser l'étudiant avec les ressources informatiques mises à sa disposition.
Participant au départ comme simple tuteur, j'ai peu à peu accru mon activité dans ce domaine, jusqu'en 2002 où, sous la direction de Claude Timsit, j'ai été chargé de l'organisation des tutorats, et notamment de la formation des tuteurs.
Je me suis, dans le cadre de ma thèse, interessé à l'algorithmique et l'optimisation conbinatoire appliqués à différents domaines. Mon activité de recherche s'est tout d'abord orientée vers l'optimisation dans les réseaux, dans la continuité de mon stage de DEA, effectué sous la direction de Pascal Berthomé du LRI (Paris XI). Le problème que nous avons abordé, dans le cadre du projet RNRT ROCOCO, concerne le dimensionnement de réseau à moindre coût satisfaisant une matrice de demande fournie. La particularité abordée vient du fait que les coûts d'établissement d'une liaison suivent une fonction en escalier. Dans un intervalle, c'est-à-dire entre deux capacité données, le coût est fixe. Nous nous sommes interessé dans ce cadre à l'obtention de bornes inférieures du coût minimal de satisfaction de l'ensemble des demandes. Ces travaux ont fait l'objet d'une présentation au 4ème congres de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'03).
Par la suite, je me suis tourné vers des problèmes d'optimisation liés à la compilation. La complexité des architecture matérielles augmentant sans cesse, l'optimisation de code dans le domaine du calcul haute performance est un problème de plus en plus important. La production de code optimisé selon certains critères (performances, consommation de ressources matérielles) est un champ d'application important pour l'optimisation combinatoire. Dans ce cadre, le type de problème abordé concerne l'ordonnancement de calculs arithmétiques. La particularité que nous traitons est la présence dans ces calculs de certaines valeurs redondantes.
On considère un programme constitué d'un ensemble d'instructions, consommant et produisant des valeurs. Chaque valeur doit être stockée dans un registre, ceux-ci étant en nombre limités. Les valeurs produites par certaines instructions étant consommées par d'autres instructions induisent des dépendances entre instructions. la réalisation d'un programme est donc un ordonnancement de ces instructions qui respecte ces contraintes de précédence. Parmis les ordonnancements existant, on peut recherche l'optimal selon plusieurs critères, notamment la minimisation du nombre de registres, ou du temps total d'ordonnancement.
L'approche classique consiste à modéliser ces dépendances par un graphe. Si l'on ne considère aucune relation particulière entre les instructions, on considère le cas le plus général, un DAG, correspondant en compilation à un bloc de base. Dans ce cas, la plupart des problèmes d'optimisation considérés sont NP-Difficiles. Si l'on considère une expression arithmétique utilisant des opérateurs binaires, on a affaire à un arbre binaire, pour lequel la plupart des problèmes d'optimisations sont résolu en temps polynomial. Notre travail consiste à considérer un cas intermédiaire : une expression arithmétique, dont certaines valeurs de base apparaissent plusieurs fois.
Nous considérons donc des DAGs orientés vers la racine, dans lesquels les seuls sommets de degré sortant supérieur à 1 sont les feuilles qui représentent les valeurs initiales présentes plusieurs fois. La structure interne du DAG resta un arbre binaire. Nous appelons de tels DAGs des DAGs arithmétiques. Bien que proche des problèmes d'optimisation sur les arbres binaires, cette catégorie de problèmes est complexe. Dans ce cadre, nous abordons plusieurs problèmes : optimisation du nombre de registres utilisés, minimisation de la taille de l'ordonnancement sous contrainte de registres.
Cette partie s'effectue dans le cadre d'une collaboration avec Johanne Cohen, du LORIA.
Le problème considéré consiste à déterminer un ordonnancement utilisant un nombre minimum de registres. Ce problème est conjecturé NP-Complet, même dans les cas les plus simples. Il a été modélisé sous forme de problème de parcours de graphe. Il s'agit donc de déterminer un ordre de parcours du DAG tel que l'ordonnancement induit soit de consommation minimale en registres. Nous cherchons d'un part à prouver la NP-Complétude de ce problème, d'autre part à proposer une méthode de résolution exploitable.
Nous étudiant actuellement un sous-ensemble de problèmes : le cas où les feuilles ont un degré inférieur ou égal à 2. Nous avons conçu une heuristique, s'appuyant sur la notion de graphe d'interférence associé aux feuilles. Ce graphe modélise toutes les interférences possibles entre les feuilles au sein de l'ordonnancement. Ainsi, la taille d'une clique maximale dans ce graphe d'interférence indique le plus grand nombre de feuille potentiellement en conflit pour l'occupation d'un registre. Nous pouvons alors effectuer dans le parcours un choix qui permettra d'éviter autant que possible ces interférences.
Dans ce cas, on considère r registres disponibles, et l'on désire ordonnancer le DAG arithmétique en utilisant au plus ces r registres. Lorsqu'une valeur est chargée dans un registre, la conserver dans ce registre pour la ou les opérations suivantes réduit la taille de l'ordonnancement mais provoque une hausse locale de la consommation en registres. Il peut donc être nécessaire de la libérer, afin de respecter la contrainte de consommation en registres. Le problème que nous abordons consiste alors à déterminer l'ordonnancement de taille minimale sous contrainte de registres. Ce problème est complexe, du fait qu'il tient compte à la fois du choix de l'ordonnancement, et des possibilités de "mutualisation" du chargement des variables utilisées plusieurs fois.
C'est la raison pour laquelle ce problème est subdivisé en deux sous-problèmes :
Le premier problème a été résolu, et a fait l'objet d'une présentation lors du 6ème congres de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'05). Le deuxième problème est actuellement l'objet d'une étude, il est conjecturé NP-Difficile.
Le problème général a par ailleurs été traité par une méthode de Branch&Cut, qui a donné lieu à un stage de Maîtrise, co-encadré avec Edith Naudin.