Titre                      :    Parallélisation MPI d’un algorithme d’optimisation sur un cluster de calcul
                                  Projet Technique 

Équipe                   :    Dolphin (CRIStALUMR CNRS 9189, Inria Lille-Nord Europe)
Encadrants             :    Bilel Derbel et Arnaud Liefooghe
Contact                  :    bilel.derbel [at] univ-lille1.fr



1. Contexte et problématique

Plusieurs plateformes de calcul parallèle et distribué offrent de nos jours une puissance de calcul grandissante et à la portée d’un public large et diversifié. En effet, plusieurs systèmes distribués dédiés aux calculs, tels que les grappes (cluster) et les grilles de calcul (ensemble de grappes géographiquement distantes) jouissent d’une attention particulière des constructeurs d’équipement et des chercheurs, et plusieurs bibliothèques de programmation leur sont aujourd’hui complètement dédiées. Ces bibliothèques de calcul parallèle et distribué permettent aux ingénieurs de concevoir des algorithmes parallèles dans des modèles abstraits; mais qui pourront par la suite être implémentés de façon réaliste et efficace. Elles offrent aussi aux développeurs une prise en main rapide de l’environnement de calcul et une grande flexibilité lors de la mise en place d’une parallèlisation donnée.

De ce fait, plusieurs domaines d’applications ont de plus en plus recours à ces moyens de calculs et aux bibliothèques qui leurs sont dédiées pour mettre en pratique leurs solutions et tirer profit de la puissance de calcul disponible. Dans ce projet, nous nous intéressons à des méthodes d’optimisation combinatoire relativement gourmandes en temps CPU. Notre objectif est de pouvoir déployer les calculs qui leur sont sous-jacent de façon parallèle en utilisant MPI (Message passing Interface), une bibliothèque de calcul haute performance dédiée aux modèles de calculs distribués par échange de message [1]. Le travail comporte ainsi deux aspects complémentaires, à savoir (i) la conception même d’un algorithme applicatif parallèle par échange de messages et (ii) son implémentation effective et sa a mise en pratique à l’aide de MPI. Ces deux points ne sont pas indépendants dans la mesure où l’expérimentation avec MPI pourra conduire à des modifications/améliorations de l’algorithme conçu au préalable (et ainsi de suite).


2. Travail à réaliser

Dans ce projet, nous considérons comme domaine d’application cible à notre parallélisation avec MPI l’optimisation combinatoire multi-objectif [2]. En toute généralité, l’optimisation combinatoire multi-objectif a pour but de trouver un ensemble de solutions optimisant plusieurs objectifs de façon simultanée, c’est à dire plusieurs fonctions de coûts fournies au préalable. L’ensemble de solutions recherchées est généralement de grande taille et nécessite donc un effort de calcul conséquent. En s’inspirant du paradigme informatique “diviser pour règner”, l’idée que nous voulons mettre en place consiste à partager le calcul de cet ensemble de façon coopérative entre différents processus parallèles; chaque processus communicant avec les autres et calculant uniquement une partie (ou un sous ensemble) de l’ensemble global recherché.

Ainsi, le travail se déroulera suivant le plan détaillé ci-dessous :
0. Cerner les bases du domaine d’application visé (l’optimisation multi-objectif) et se familiariser avec MPI (10% du projet)
1. Concevoir des méthodes de parallélisation dans le modèle d’échanges de messages (20% du projet)
2. Implémenter et déployer les algorithmes parallèles conçus dans le point 1 sur un cluster de calcul en utilisant la bibliothèque de calcul MPI (25% du projet)
3. Expérimenter la solution ainsi déployée et étudier son efficacité parallèle (20% du projet)
4. En fonction des performances observées, revenir au point 1 afin d’affiner la conception ou d’en étendre le champs d’applicabilité pour des ressources de calcul massivement parallèle et/ou à très large échelle (e.g. multi-cluster, multi-core, etc) (15% du projet)
5. Packaging des différents développements et documentation (10% du projet)

Les différents développements sont à réaliser dans le cadre de la plate-forme nationale de calcul Grid’5000 [3]. Cette plateforme est constituée de plusieurs sites (dont le site de Lille au CRI) offrant plusieurs grappes agrégeant pas moins de 7000 coeurs de calculs. En fonction de la motivation, des centres d’intérêts de l’étudiant(e) et de l’avancement du projet, des déploiements à très large échelle sont envisageables.


3. Le candidat idéal

Il/elle devra
— avoir un esprit critique, être motivé(e) et intéressé(e) par les systèmes distribués, la programmation parallèle et les algorithmes en général
— maitriser un des langages de programmation suivants : c, c++, fortran


4. Bibliographie

[1] OpenMPI: Open Source High Performance Computing. http://www.open-mpi.org/
[2] E-G. Talbi. Metaheuristics: from design to implementation. Wiley, 2009
[3] GRID’5000. https://www.grid5000.fr/