psar

L’unité d’enseignement « Projet SAR » relève de la spécialité SAR du master d’informatique. L’objectif est de pratiquer les domaines couverts par la spécialité : conception, vérification et réalisation d’applications et systèmes répartis.

Le travail demandé comporte une grosse part de développement logiciel, aussi il faudra utiliser un gestionnaire de versions concurrentes. Pour cela, la Plateforme Pédagogique et Technique d’Informatique de notre université met à votre disposition un serveur Subversion, dont vous devez lire attentivement la documentation. Tous les systèmes d’exploitation offrent un client Subversion en ligne de commande, vous pouvez aussi installer une version graphique si vous le désirez. Le serveur Subversion de la PPTI doit être utilisé pour que vos encadrants puissent suivre et tester votre travail. Les exceptions à son utilisation doivent faire l’objet d’un accord préalable avec les encadrants.

Les soutenances, de tous devant tous, auront lieu les après-midi des 12 et 13 mai ; réservez dès à présent ces dates.

Prenez connaissance des projets contenus dans la liste ci-dessous, puis contacter les responsables des projets qui vous intéressent, en cliquant sur leur nom. Vous pouvez ainsi poser des questions complémentaires et prendre éventuellement rendez-vous. Lorsqu’un encadrant vous aura donné son accord, vous signalerez votre candidature au responsable de l’UE en vous déclarant dans le menu à gauche du texte de présentation du projet. Vous ne pouvez pas candidater à plusieurs projets simultanément.

Liste chronologique des 24 sujets proposés
les sujets sur fond coloré sont déjà attribués
L

Pour passer du mode abrégé au mode étendu, cliquer sur le bouton ci-dessus.
Pour être prévenu des stages annoncés tardivement, utiliser le fil RSS: il est spécifique à cette rubrique.
Pour ne lister que les stages associés à un mot-clé, cliquer sur une occurrence des mot-clés apparaissant en mode étendu sous le titre des stages.

1. Gestion de tas réparti


Site :Gestion de tas réparti
Lieu :UPMC
Encadrant : Pierre Sens
Dates :du 01/02/2014 au 10/05/2014

Description

L’objectif est de concevoir un gestionnaire de tas réparti entre des processus situés sur des machines différentes. Voir le document pdf joint.


Sujet Projet Tas Réparti

2. Etudes sur la dissémination d’information dans les réseaux sociaux


Site :Equipe Regal
Lieu :LIP6
Encadrant : Pierre Sens, Ruijing Hu,
Dates :31/01/2014 au 12/05/2014

Description

Nombre d’étudiants : 1 ou 2

Contexte :

Le but de ce projet est d’étudier les performances d’un algorithme pour la dissémination d’information lorsque celui-ci est déployé sur des réseaux présentant des caractéristiques structurelles variées.

Mots-clés : dissémination d’information, graphes, Internet, réseaux sociaux, clustering.

Présentation :

La dissémination d’information de type broadcast, dans laquelle un nœud du réseau tente de transmettre une information à tous les autres nœuds, est une problématique essentielle pour beaucoup d’applications réparties. La performance de ce protocole dépend bien sûr de la structure du réseau sur lequel il est déployé. Le but du projet est de comprendre comment la densité locale des réseaux influe sur l’efficacité de cet algorithme. Pour ce faire, nous proposons de calculer différentes métriques liées à la performance des protocoles de diffusions (comme la latence ou la complexité en message) lorsque ceux-ci sont déployés sur des réseaux présentant des structures différentes (par exemple un sous-ensemble du réseau Internet ou d’un réseau social issu de Flickr). On se concentrera en particulier sur la densité locale, propriété capturée généralement par la notion de clustering.

Déroulement :

Dans un premier temps, l’étudiant se familiarisera avec une bibliothèque C permettant la représentation de grands graphes. Ceci permettra l’analyse de la structure de différents réseaux (Internet, Flickr) à travers le calcul d’un ensemble de caractéristiques statistiques liées à la topologie, en particulier la distribution des degrés et le coefficient de clustering. Dans un second temps, l’étudiant calculera les performances de l’algorithme de diffusion de type flooding sur ces réseaux. On pourra par exemple calculer la latence et la complexité de messages observées en moyenne lorsqu’une source tente de propager une information à l’ensemble des nœuds du réseau.

Pré-requis : bon niveau en C et en algorithmique sur les graphes.


3. Mutualisation entre machines virtuelles de la mémoire inutilisée. Grp1


Site :LIP6 Regal
Lieu :UMPC, 4 place Jussieu 75005 PARIS
Encadrant : Julien Sopena (Julien.Sopena@lip6.fr), Sébastien Monnet (Sebastien.Monnet@lip6.fr) et Maxime Lorrillere (Maxime.Lorrillere@lip6.fr).
Dates :01/02/2014 au 10/05/2014

Description

Mutualisation entre machines virtuelles de la mémoire inutilisée.

Nombre de groupes : 1 ou 2

Pitch : Si la généralisation de la virtualisation a permis d’offrir une grande flexibilité aux applications modernes, elle s’accompagne d’une fragmentation de la mémoire. Ce projet PSAR vise à développer une solution permettant, en mode utilisateur, de partager entre deux machines virtuelles la mémoire inutilisée au travers d’un cache réparti. Le but étant de comparer les performances obtenues avec celles des solutions noyau existantes.

Mots-clés : cache réparti, programmation système, programmation noyau, virtualisation.

Contexte : La virtualisation est aujourd’hui omniprésente dans les systèmes distribués : elle permet en effet de fournir dynamicité et sécurité. Cependant cette flexibilité se fait au prix d’une importante fragmentation de la mémoire. Or le bon dimensionnement des machines virtuelles (VMs) reste une tâche ardue et les administrateurs surdimensionnent souvent la mémoire allouée à chaque VM, générant ainsi un énorme gâchis de ressources.

L’utilisation de la mémoire libre par le système d’exploitation pour faire du cache règle partiellement le problème : les applications effectuant des Entrées/Sorties en sont bénéficiaires, mais si une VM utilise peu son disque, le cache sera vide ou inutile. De plus, même avec du cache, une application intensive en Entrées/Sorties se trouve fortement ralentie par le moindre accès au disque, alors que de la mémoire libre est peut être disponible sur une autre VM.

Une solution consiste alors à utiliser la mémoire inutilisée d’autres machines en réseau : la latence d’un réseau local est beaucoup plus faible qu’un accès disque, il est donc intéressant de disposer d’un second niveau de cache, réparti en réseau. Si des solutions de cache réparti en espace utilisateur existent déjà (Memcached), elles sont loin d’être transparentes et nécessitent de lourdes modifications des applications pour en profiter.

Objectifs : L’idée de ce projet est de concevoir et d’implémenter un cache réparti transparent pour les applications. Des solutions noyau existent, mais elles induisent un surcoût lié aux changements de contexte. Ce projet vise à développer une solution s’exécutant en mode utilisateur. Plusieurs approches système sont envisageables : surcharge des fonctions d’Entrée/Sortie Posix, réalisation d’un système de fichier utilisateur (FUSE), ...

Déroulement du projet :

  • Développement des primitives pour capturer les accès au système de fichiers (Posix ou FUSE) ;
  • Développement d’un cache local en espace utilisateur. Pour cela, il faut contourner le page cache du noyau (O_DIRECT) et implanter une stratégie de cache efficace ;
  • Test de performances du cache local en espace utilisateur comparé au page cache du noyau ;
  • Développement du cache réparti : les données évincées du cache local sont envoyées dans un cache "distant" en réseau (sockets Posix ou MPI) ;
  • Test de performances du cache réparti comparé au cache local et au page cache du noyau.

Les étudiants pourront avoir accès, le cas échéant, à la plateforme Grid’5000 pour réaliser l’étude de performance.

Pré-requis : Bon niveau en C et en programmation système, notions en noyau.


PSAR-Mutualisation_entre_machines_virtuelles_de_la_mémoire_inutilisée.pdf -

Sujet PSAR (Sopena,Monnet,Lorrillere) : Mutualisation entre machines virtuelles de la mémoire inutilisée.


4. Vers une plate-forme efficace de développement d’applications réparties.


Site :Vers une plate-forme efficace de développement d’applications réparties.
Lieu :UMPC 4 place Jussieu 75005 PARIS
Encadrant : Julien Sopena (julien.sopena@lip6.fr), Jonathan Lejeune (jonathan.lejeune@lip6.fr)
Dates :01/02/2014 au 10/05/2014
Mots-clés : Parcours SAR, aussi pour STL

Description

Vers une plate-forme efficace de développement d’applications réparties.

Pitch : Le but de ce PSAR est d’implémenter une couche logicielle permettant d’exécuter de façon transparente le même code sur le simulateur omnet++ et sur une infrastructure réelle en utilisant l’API MPI. L’intérêt d’un tel projet est de simplifier le développement d’applications réparties en utilisant un simulateur et l’ensemble des outils graphiques associés, pour développer un code pouvant s’exécuter directement sur un cloud ou une grille de calcul réels.

En cas de succès (solution fonctionnelle) l’impact du projet sera important. En effet, cette plate-forme répond à un besoin réel dans le domaine des applications réparties. Elle pourra entre autres être mis-en-oeuvre dans des projets de recherche au LIP6 ou être utilisée dans le cadre de TP d’UEs du Master SAR.

Mots-clés : programmation répartie, simulation à événements discrets, MPI, grille de calcul.

Contexte : Les simulateurs de plate-formes réparties permettent de décrire un réseau (lien, topologie, latence ...) et les noeuds qui le constituent (machines, routeurs ...) afin d’y simuler l’exécution d’applications réparties. Dans ce projet nous nous intéressons au simulateur à événements discrets comme omnet++. L’utilisation d’un tel simulateur présente plusieurs avantages :

  • en supprimant l’indéterminisme lié au réseau, il peut reproduire les mêmes séquences d’exécution, ce qui simplifie énormément les phases de débogage ;
  • il permet de simuler un nombre relativement grand de machines, diminuant ainsi le coût matériel du développement ;
  • il peut, aux prix d’une simplification du modèle, simuler de longues périodes d’expérimentation en un cours laps de temps.
  • son interface graphique permet un large éventail de fonctionnalités : configuration du réseaux, affichage des messages, monitoring, courbes, ...

L’inconvénient actuel d’un tel simulateur, est qu’il demande généralement l’écriture de code spécifique. Il est ainsi impossible de déployer directement le code testé sur le simulateur directement dans un réseau réel. Or les modifications nécessaires touchent le plus souvent à des parties critiques du code, ce qui peut entraîner l’insertion de bugs dans le code testé sur le simulateur.

Objectifs : L’idée du projet est de se baser sur les primitives de l’API MPI (Message Passing Interface) comme interface commune au simulateur et au monde réel. En effet, la couche MPI, largement répandue dans l’industrie et utilisée dans l’UE Algorithmique Répartie (AR-MI048), permet aux applications de s’abstraire de la couche réseau de l’application.

En réalisant une implémentation de l’interface MPI pour omnet++, le projet permettra à un code écrit pour MPI de s’exécuter sur le simulateur. Ainsi, un même code pourra être compilé pour fonctionner sur le simulateur ou pour s’exécuter dans un environnement réel.

Déroulement du projet :

  1. Familiarisation avec MPI et le simulateur omnet++.
  2. Développement des primitives de bases MPI (send, receive, broadcast, ...) dans le simulateur omnet++.
  3. Configuration automatique du réseau simulé par omnet++ en fonction des fichiers de description du déploiement MPI.
  4. Test d’exécution d’une petite application répartie sur le simulateur et dans un environnement réel.

Les étudiants participants au projet pourront avoir accès, le cas échéant, à la plate-forme Grid5000 pour tester leur code.

Pré-requis : bon niveau en C/C++, notions de programmation objet, notions de réseau.


PSAR-Vers_une_plateforme_efficace_de_developpement_d_applications_reparties.pdf -

Sujet du PSAR 2014 (Sopena/Lejeune) : Vers une plate-forme efficace de développement d’applications réparties.


5. Abstraction GAL via une transformation de modèle


Site :Trac-Abstraction GAL via une transformation de modèle
Lieu :LIP6
Encadrant : Yann Thierry-Mieg

Description

cf pdf


6. Editeur Xtext et Transformation Divine


Site :Trac-Editeur Xtext et Transformation Divine
Lieu :LIP6
Encadrant : Yann Thierry-Mieg

Description

cf pdf


7. Editeur Xtext et Transformation Promela


Site :Trac- Editeur Xtext et Transformation Promela
Lieu :LIP6
Encadrant : Yann Thierry-Mieg

Description

cd pdf


8. floatOS : Driver OS pour la prise en charge des exceptions mathématiques dans le calcul en virgule flottante


Site :Trac-floatOS
Lieu :Jussieu
Encadrant : B. Folliot stage pour 2-4 étudiants
Dates :standard

Description

PSAR 2014

floatOS : Driver OS pour la prise en charge des exceptions mathématiques dans le calcul en virgule flottante

Stage pour 2-4 étudiants

Dans sa première version, la norme IEEE 754 décrit cette gestion alternative des exceptions de calcul d’une façon très (et probablement trop) proche du matériel, spécifiant juste l’installation d’un vecteur système (exception handler trap). Dans sa version courante (IEEE 754-2008), la norme spécifie ce qu’elle appelle des attributs de gestion alternative qui peuvent être activés pour des blocs d’instructions écrites dans un langage haut niveau. Ces attributs de gestion alternative forment une API très informelle pour la gestion des exceptions de calcul IEEE 754.

Problème : Bien que spécifié depuis 28 ans et important pour certains codes en virgule flottante, le support pour la gestion « non-defaut » des exceptions IEEE 754 est quasi inexistant à l’heure actuelle. Aucun système d’exploitation ni langage de programmation ne spécifie de support portable pour une telle gestion alternative des exceptions IEEE 754 [3,4,5,6,7]. Cette absence de support s’explique par une multitude de réalisations matérielles très variées entre les différente architectures et la nécessité d’un support vertical très profond, faisant intervenir à la fois le matériel, le système d’exploitation et les langages de programmation (et leur compilateur).

But du projet : Le but du projet est la réalisation d’un prototype d’un tel support pour la gestion alternative des exceptions IEEE 754 à tous les niveaux, pour un choix de processeur et système restreint (la prise en compte multi-OS, multi-processeur serait trop complexe dans un premier temps). On cible un support pour : un processeur Intel avec gestion du calcul en virgule flottante sur l’unité x87 (legacy 32 bits) ou l’unité SSE/AVX (64 bits), le système d’exploitation Linux et une API de gestion d’exceptions IEEE 754 pour le langage C.

Etapes : Le projet commencera par une phase de défrichage de l’existant (méthodes non portables à séquences assembleur, etc.), continuera avec une expérimentation avec les chamanismes matériels prévus à la fois par les unité x87 et SSE/AVX des processeurs Intel, proposera une API portable et utile à l’utilisateur de calcul en virgule flottante et terminera par une implémentation (prototypée) de cette implémentation.

Support OS : La réalisation se fera au sein de VMKit [9]. VMKit est une architecture de développement de machines virtuelles de haut niveau. Cette architecture offre une couche commune pour le runtime (GC, threads, ...) et pour l’exécution des instructions. VMkit est basée sur la machine LLVM [2] qui utilise le GC de Boehm et les threads POSIX. VMkit a été utilisée pour développer une JVM (J3) [3] et une machine .NET (N3) [4] montrant ainsi son adaptation au monde objet. Elle servira ici de support de « driver OS » pour le calcul en virgule flottante de calculs scientifiques.

Bibliographie

Références bibliographiques

[1] Institute of Electrical and Electronics Engineers (IEEE), IEEE Standard for Binary Floating-Point Arithmetic, IEEE Std 754-1985, IEEE, New York, NY, USA, 1985.

[2] IEEE Computer Society, IEEE Standard for Floating-Point Arithmetic, IEEE Std 754-2008, IEEE, New York, NY, USA, 2008.

[3] William Kahan, Branch Cuts for Complex Elementary Functions, or Much Ado About Nothing’s Sign Bit in The State of the Art in Numerical Analysis, (eds. Iserles and Powell), Clarendon Press, Oxford, 1987.

[4] William Kahan, How JAVA’s Floating-Point Hurts Everyone Everywhere, document électronique disponible à l’adresse http://www.cs.berkeley.edu/ wkahan/...

[5] William Kahan, A Demonstration of Presubstitution for Infinity/Infinity, document électronique disponible à l’adresse http://www.cs.berkeley.edu/ wkahan/...

[6] Back to the Future of Undebuggable Floating-Point Software in Science and Engineering, document électronique disponible à l’adresse http://www.cs.berkeley.edu/ wkahan/...

[7] William Kahan, Desperately Needed Remedies for the Undebuggability of Large Floating-Point Computations in Science and Engineering, séminaire Math-Infos, UPMC, Paris, Septembre 2013, cf. http://www-polsys.lip6.fr/ safey/se...

[8] O. Kupriianova, Ch. Lauter, The libieee754 compliance library for the IEEE 754-2008 Standard, 15th GAMM - IMACS International Symposion on Scientific Computing, Computer Arithmetic and Validated Numerics, Novosibirsk, Russie, septembre 2012

— -

[9] N. Geoffray, G. Thomas, C. Clément, B. Folliot et G. Muller. VMKit : a Substrate for Virtual Machines. Proc. of the ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE 2010), Pittsburgh, PA, pp. 51-61, Mars 2010.

[10] site de LLVM (Low Level Virtual Machine) : http://llvm.org

[11] N. Geoffray, G. Thomas, C. Clément et Bertil Folliot. A Lazy Developer Approach : Building a JVM with Third Party Software. In Conference of the Principles and Practives of Programming in Java, 2008.

[12] site VMkit : http://vmkit.llvm.org/


9. VVMPad : Machine virtuelle virtuelle pour la programmation flexible de PinPad


Site :Trac-VVMPad : Machine virtuelle virtuelle pour la programmation flexible de PinPad
Lieu :Jussieu
Encadrant : B. Folliot
Dates :standard

Description

PSAR 2014

MIT&0Pad

VVMPad : Machine virtuelle virtuelle pour la programmation flexible de PinPad

Mouse-Ink-Track-&0ther-Pad

Nombre d’étudiants : 3-4

Encadrant : Bertil Folliot, LIP6-INRIA/Equipe REGAL – UPMC (Paris VI)/CNRS, Sorbonnes Universités bertil.folliot@lip6.fr http://pagesperso-systeme.lip6.fr/B... (old)

Contexte (mots-clefs) : machines virtuelles virtuelles [VVM], flexibilité, interopérabilité, adaptabilité dynamique de logiciels ; accessoires multipads.

Application : logiciel d’interface d’adaptation dynamique pour : MousePad/TrackPad/InkPad/...FuturePad – driverOS – bibliothèque de programmation – utilisateur Environnement de programmation : VMKit [VMKit], Linux, C/C++ (– à discuter)

Sujet

Les TrackPads (TP) évolués actuels permettent non seulement de remplacer efficacement la classique « souris », mais ajoutent en plus de nombreuses fonctionalités supplémentaires. Par exemple, en fonction du nombre de doigts posé sur le TP, on peut : sélectionner/glisser/déplacer/zoomer/lancer des applications, etc.

La souris reste néanmoins l’accessoire le plus utilisé, sans doute à cause de l’intuitivité et de la facilité de son utilisation : deux clicks (gauche, droit) et une molette (haut, bas). L’un n’empêchant pas l’autre, on trouve souvent sur une même machine, à la fois un trackpad et une souris. Récemment, la MagicMouse (MM) [Apple] a remplacé par une surface lisse unique (l’équivalent d’un « TouchPad », voir figure-gauche), la surface physique classique. Les boutons et la molette sont simulés (deviennent donc virtuels ; on « clique » à droite ou à gauche en touchant la surface avec l’index ou le majeur, ou on déplace le majeure sur la surface de la MagicMouse pour faire tourner (virtuellement) la mollette, exactement comme on le ferait avec la molette mécanique d’une souris classique). De plus, le TP est traditionnellement réservé aux ordinateurs portables, et n’est pas accessibles aux ordinateurs de bureaux. Un autre produit récent, le Magictrackpad (MTP) [Apple2] remédie à ce défaut en permettant de rajouter un équivalent MM/TP à un ordinateur de bureau (voir figure-milieu), ou à un portable d’ailleurs2.

Cette nouvelle interface de communication homme–machine permet de combiner les avantages de la MM (souris virtuel) et du TP. Il existe cependant des inconvénients à ces récentes nouveautés : la MM ne permet pas de se déplacer dans tous les sens (de faire un cercle sur la surface du MM avec l’anulaire par exemple) et la MTP est sur un support fixe et ne peut pas être manipulé comme une souris (i.e. On ne peut pas faire « glisser » le MTP). En plus, il existe de nombreux autres accessoires de communications complémentaires en fonction de l’utilisation que l’on souhaite avoir : - InkPad : pour écrire avec un stylo numérique (qui, virtuellement, à l’aide d’un logiciel de reconnaissance de caractères, permet de transférer l’écriture manuscrite ou les schémas sur un ordinateur). - ScanPad : qui scanne et qui (avec l’InkPad) prend des notes directement sur le document scanné. - iPad : tablette tactile qui permet de prendre des notes directement sur un texte contenu dans la tablette (très pratique pour les notes sur polycopié de cours par exemple...) - otherPad pour surfer sur le web, téléphoner, visionner, etc ; et ce, sans compter les nouveautés qui ne cessent d’apparaître...

Tous ces accessoires n’étant quasiment jamais interopérable, flexible ou dynamiquement adaptable et n’étant que peu programmable par l’utilisateur. Cela induit un nombre important de matériels, de manipulations, de langages, d’applications et d’interfaces inutiles.

But

Le but de ce stage est de concevoir, de prototyper et d’évaluer la Mit&0Pad d’un point de vue logiciel (système, on ne fera pas d’architecture physique matériel). La définition de la Mit&0Pad étant un assemblage de souris, trackpad, magicpad, inkpad, epad, otherPad... C-a-d, la réunion d’un écran tactile qui fait aussi trackpad (et autres) et qui bouge (comme une souris).

Les avantages, en dehors de l’aspect financier, sont multiples : extrême facilité d’utilisation, double/triple interfaces en surface (p.ex pointage grossier en déplacant la Mit&0Pad, puis pointage fin avec l’index sur la Mit&0Pad, puis µpointage avec le stylo), adaptabilité en fonction des besoins de l’utilisateur (interface de programmation Mit&0Pad/user), intégration à la volée de nouveaux mécanismes de communications.

Plan de travail

Compte-tenu de l’ampleur des travaux à effectuer il serait souhaitable qu’un groupe de (X=) 3 stagiaires soudés travaille sur ce sujet.

o. Si intéressé, article à écrire pour la conférence internationale Laval Virtual (deadline 11/12/13) [Laval] (papier de 4 pages, format IEEE3). i. Etats de l’art sur les divers périphériques à intégrer (magicmouse, magicpad, inkpad, epad, otherpad...) (→ X rapports bibliographiques) [xyz]. ii. Conception simplifiée de la Mit&0Pad (architecture virtuelle). iii. Conception de l’interface logiciel Mit&0Pad → OS driver/user. iii’. Conception de l’interface d’adaptabilité/interopérabilité/programmabilité de la Mit&0Pad (user → Mit&0Pad). iv. Protypage (en C/C++), dans le cadre de VMKit [VMKit], des 2 points précédents. v. Evaluation simplifiée (micros-benchmarks [µBench]).

Références

[Laval] http://www.laval-virtual.org/ [VMKit] http://vmkit.llvm.org/ (la distrib. public chez LLVM) http://pagesperso-systeme.lip6.fr/N... (travaux de thèse) [papier VMKit] ACM SIGPLAN/SIGOPS Int. Conf. on Virtual Execution Environment (VEE), Pittsburgh (PA), USA, pp. 51-61, 2001 : http://llvm.org/pubs/2010-03-VEE-VM... [VVM] http://vvm.lip6.fr/publications/98A... (papier fondateur) http://pagesperso-systeme.lip6.fr/B... (old) http://vvm.lip6.fr/publications/ (very old !) [Apple] http://www.apple.com/fr/magicmouse/ [Apple2] http://www.apple.com/fr/magictrackpad/


10. Fée (proj. Sorbonne@Univ.) : metacloud & very-very-big-data


Site :Trac-Fée (proj. Sorbonne@Univ.) : metacloud & very-very-big-data
Lieu :Jussieu
Encadrant : B.Folliot en coopération avec le Muséum d'Histoire Naturelle
Dates :standard

Description

PSAR 2014 B. Folliot Stage pour 2-4 étudiants

Lors des journées Convergence@Sorbonne Universités (9 octobre 2013, à l’Université Pierre & Marie Curie), il est apparu qu’il y avait un manque flagrant de coopération et de collaboration des différentes branches scientifiques liées aux Sciences de l’Environnement. Pourtant, chaque branche récolte des données partielles, complémentaires aux autres branches ou pouvant être obtenues à partir des données récoltées par d’autres. Cela induit un travail parfois inutile (redondant), peut biaiser les résultats, et rend difficile une vision à plus ou moins long terme de la gestion de ces données pour les sciences participatives sont aujourd’hui un succès scientifique et médiatique. Plus de 10 000 observateurs déposent chaque année des données. Ce succès a généré une forte attente, aussi bien de la part des participants que du grand public, d’outils et méthodes d’analyse et de traitement des données permettant de simuler des scénarios ou réaliser des prévisions variées en exploitant les données collectées par tous les observateurs.

La satisfaction de cette attente légitime est confrontée à trois problèmes. L’analyse de données en écologie a atteint un tel niveau de complexité qu’elle est très difficilement accessible au plus grand nombre. Compte tenu de la diversité des demandes, la mise à disposition des outils d’analyses requiert d’importantes ressources de calcul et de stockage pour réaliser efficacement les analyses (simulations, prévisions) attendues et partager toutes les données dérivées générées. Enfin, l’hétérogénéité des sites, des formats, ainsi que des bases de données où sont enregistrées les données collectées rend difficile l’accès à ces mêmes données et ne facilite pas les collaborations entre observateurs.

Ce projet vise à automatiser et unifier les consultations des données des sciences participatives. D’un point de vue utilisateur, le projet vise à termes à proposer des services d’analyse et de prédiction. D’un point de vue système, le projet vise d’une part à développer des modules flexibles d’extraction de données accessible via un « portail » de consultation et de restitution des données ; d’autre part la définition de modèles de fédération et de coopération de clouds capables de répondre efficacement aux besoins (gestion de gros volumes de données, simulations à grande échelle, etc) d’un service des données des sciences participatives.


11. Interface Shell pour les services dans CosyVerif


Site :Trac-Interface Shell pour les services dans CosyVerif
Lieu :LIP6, UPMC
Encadrant : Fabrice Kordon, Alban Linard et Francis Hulin-Hubard

Description

Introduction

Cosyverif est un environnement open source pour la vérification formelle de logiciels complexes (répartis, temps-réel, etc.) qui est conçu comme une plate-forme d’intégration de composants logiciels hébergés dans une machine virtuelle ou sur une machine physique. Le projet est développé conjointement par trois laboratoires d’Île de France : le LIP6 (UPMC), le LIPN et le LSV (ENS de Cachan).

Basé sur une approche client/serveur, Cosyverif est composé d’une interface utilisateur, Coloane, et du serveur, qui est constitué de la plateforme d’intégration (alligator) interfaçant des outils (programmes de vérification, etc) développés et intégrés par les laboratoires contributeurs. Le projet présenté se situe dans ce cadre.

Vous serez encadrés par les ingénieurs de développement du projet, en association avec un enseignant travaillant au LIP6. Le résultat de votre travail devra respecter des critères de qualité précis en vue de son intégration dans la plateforme Cosyverif dont vous deviendrez ainsi un contributeur.

Travail à effectuer

Actuellement, chaque outil (binaire obtenu à partir de programmes C, C++ OCaml, ou bien scripts Python par exemple) est enrobé par une classe Java permettant de l’intégrer dans la plateforme. L’écriture de cette classe peut rebuter certains développeurs. Le but de ce stage est de mettre en place une interface en shell pur pour les services de la plateforme CosyVerif. Il faudra pour cela définir une interface pour le script shell d’enrobage, et implémenter sa liaison avec le langage Java.


12. Big-OS : un système d’exploitation pour les grands volumes de données


Site :Trac-Big-OS : un système d’exploitation pour les grands volumes de données
Lieu :LIP6
Encadrant : Gaël Thomas

Description

L’essor de l’informatique en nuage a permis aux administrations et entreprises de stocker d’énormes jeux de données. Aujourd’hui, l’un des goulots d’étranglement majeurs pour les performances de traitement de ces données est le système d’exploitation de chaque machine. Les systèmes actuels ne peuvent pas gérer efficacement les applications intensives en données car ils ne disposent pas d’une vue unifiée des ressources utilisées, ce qui les empêche de déterminer des stratégies efficaces pour le placement des tâches/données sur les ressources matérielles. Une meilleure gestion des ressources permettrait une forte réduction du nombre de machines nécessaires aux traitements des données.

Le but du projet PSAR est d’implémenter des sondes dans le noyau Linux de façon à identifier les ressources physiques et logicielles les plus sollicitées par les processus. Les informations remontées par ses sondes permettront ensuite de commencer à définir des stratégies de placement des tâches de des données prenant en compte à la fois la topologie de la machine et l’utilisation effectives des ressources par les tâches.

Les développements seront effectués sous Linux et il est donc demandé au candidat d’avoir un très bon niveau de programmation en C et des connaissances solides en système d’exploitation.

Bibliographie

Lokesh Gidra, Gaël Thomas, Julien Sopena, and Marc Shapiro. A study of the scalability of stop-the-world garbage collectors on multicores. In Proceedings of the conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’13, Houston, USA, March 2013.

Mohammad Dashti, Alexandra Fedorova, Justin Funston, Fabien Gaud, Renaud Lachaize, Baptiste Lepers, Vivien Quéma, and Mark Roth. Traffic Management : A Holistic Approach to Memory Placement on NUMA Systems. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’13, Houston, USA, March 2013.


13. Intégration de nouveaux services dans CosyVerif


Site :Trac-Intégration de nouveaux services dans CosyVerif
Lieu :LIP6, UPMC
Encadrant : Fabrice Kordon, Alban Linard et Francis Hulin-Hubard

Description

Introduction

Cosyverif est un environnement open source pour la vérification formelle de logiciels complexes (répartis, temps-réel, etc.) qui est conçu comme une plate-forme d’intégration de composants logiciels hébergés dans une machine virtuelle ou sur une machine physique. Le projet est développé conjointement par trois laboratoires d’Île de France : le LIP6 (UPMC), le LIPN et le LSV (ENS de Cachan).

Basé sur une approche client/serveur, Cosyverif est composé d’une interface utilisateur, Coloane, et du serveur, qui est constitué de la plateforme d’intégration (alligator) interfaçant des outils (programmes de vérification, etc) développés et intégrés par les laboratoires contributeurs. Le projet présenté se situe dans ce cadre.

Vous serez encadrés par les ingénieurs de développement du projet, en association avec un enseignant travaillant au LIP6. Le résultat de votre travail devra respecter des critères de qualité précis en vue de son intégration dans la plateforme Cosyverif dont vous deviendrez ainsi un contributeur.

Travail à effectuer

Nous vous proposons d’intégrer deux nouveaux services dans la plateforme Cosyverif.

Le premier service est un service de placement automatique. Les objets manipulés dans la plateforme sont des graphes. En utilisant l’outil Graphviz, vous écrirez un outil de placement automatique des éléments du graphe.

Le second service est un service d’import/export avec le format standard PNML. Ce format d’échange permettra aux outils intégrés dans la plateforme de participer à un concours international de vérification, le Model Checking Contest.


14. Allocation de ressources pour les services dans CosyVerif


Site :Trac-Allocation de ressources pour les services dans CosyVerif
Lieu :LIP6, UPMC
Encadrant : Fabrice Kordon, Alban Linard et Francis Hulin-Hubard

Description

Introduction

Cosyverif est un environnement open source pour la vérification formelle de logiciels complexes (répartis, temps-réel, etc.) qui est conçu comme une plate-forme d’intégration de composants logiciels hébergés dans une machine virtuelle ou sur une machine physique. Le projet est développé conjointement par trois laboratoires d’Île de France : le LIP6 (UPMC), le LIPN et le LSV (ENS de Cachan).

Basé sur une approche client/serveur, Cosyverif est composé d’une interface utilisateur, Coloane, et du serveur, qui est constitué de la plateforme d’intégration (alligator) interfaçant des outils (programmes de vérification, etc) développés et intégrés par les laboratoires contributeurs. Le projet présenté se situe dans ce cadre.

Vous serez encadrés par les ingénieurs de développement du projet, en association avec un enseignant travaillant au LIP6. Le résultat de votre travail devra respecter des critères de qualité précis en vue de son intégration dans la plateforme Cosyverif dont vous deviendrez ainsi un contributeur.

Travail à effectuer

Le but de ce stage est de mettre en place une gestion de ressources dans la plateforme. Celle-ci permet d’exécuter à distance des outils de vérification formelle, généralement très gourmands en temps et mémoire, sur des machines dédiées.

Actuellement, tous les utilisateurs sont anonymes et peuvent lancer de longs calculs, utilisant beaucoup de mémoire ou de disque. Afin de limiter les ressources fournies à chaque utilisateur, et donc fournir une meilleure qualité de service, nous souhaitons mettre en place un système de gestion fine des ressources (temps, mémoire, disque, ...).

Le travail du stage consiste tout d’abord en un état de l’art des systèmes de gestion des ressources, puis en l’implémentation de la solution choisie.


15. Mise à jour des scripts de build CosyVerif


Site :Trac-Mise à jour des scripts de build CosyVerif
Lieu :LIP6, UPMC
Encadrant : Fabrice Kordon, Alban Linard et Francis Hulin-Hubard

Description

Introduction

Cosyverif est un environnement open source pour la vérification formelle de logiciels complexes (répartis, temps-réel, etc.) qui est conçu comme une plate-forme d’intégration de composants logiciels hébergés dans une machine virtuelle ou sur une machine physique. Le projet est développé conjointement par trois laboratoires d’Île de France : le LIP6 (UPMC), le LIPN et le LSV (ENS de Cachan).

Basé sur une approche client/serveur, Cosyverif est composé d’une interface utilisateur, Coloane, et du serveur, qui est constitué de la plateforme d’intégration (alligator) interfaçant des outils (programmes de vérification, etc) développés et intégrés par les laboratoires contributeurs. Le projet présenté se situe dans ce cadre.

Vous serez encadrés par les ingénieurs de développement du projet, en association avec un enseignant travaillant au LIP6. Le résultat de votre travail devra respecter des critères de qualité précis en vue de son intégration dans la plateforme Cosyverif dont vous deviendrez ainsi un contributeur.

Travail à effectuer

Les outils intégrés dans la plateforme nécessitent que nous puissions les compiler depuis leurs sources. Pour ceci, nous disposons d’un serveur d’intégration continue (Jenkins), s’appuyant sur des machines de différentes architectures (Linux ou MacOS, en 32 ou 64 bits). Malheureusement, ce serveur n’est pas exploitable car les scripts de build des outils ne sont pas toujours bien faits (ou bien sont inexistants). Le but de ce stage est de mettre à jour les scripts de build des outils de la plateforme.

Le stagiaire apprendra l’utilisation de différents systèmes de build (autotools, CMake, ocamlbuild, ...).


16. Authentification dans CosyVerif


Site :Trac-Authentification dans CosyVerif
Lieu :LIP6, UPMC
Encadrant : Fabrice Kordon, Alban Linard et Francis Hulin-Hubard

Description

Itroduction

Cosyverif est un environnement open source pour la vérification formelle de logiciels complexes (répartis, temps-réel, etc.) qui est conçu comme une plate-forme d’intégration de composants logiciels hébergés dans une machine virtuelle ou sur une machine physique. Le projet est développé conjointement par trois laboratoires d’Île de France : le LIP6 (UPMC), le LIPN et le LSV (ENS de Cachan).

Basé sur une approche client/serveur, Cosyverif est composé d’une interface utilisateur, Coloane, et du serveur, qui est constitué de la plateforme d’intégration (alligator) interfaçant des outils (programmes de vérification, etc) développés et intégrés par les laboratoires contributeurs. Le projet présenté se situe dans ce cadre.

Vous serez encadrés par les ingénieurs de développement du projet, en association avec un enseignant travaillant au LIP6. Le résultat de votre travail devra respecter des critères de qualité précis en vue de son intégration dans la plateforme Cosyverif dont vous deviendrez ainsi un contributeur.

Travail à effectuer

Le but de ce stage est de réaliser un système d’authentification dans la plateforme. Celle-ci permet d’exécuter à distance des outils de vérification formelle, généralement très gourmands en temps et mémoire, sur des machines dédiées.

Actuellement, tous les utilisateurs sont anonymes et peuvent lancer de longs calculs. Afin de limiter les ressources fournies à chaque utilisateur, et donc fournir une meilleure qualité de service, nous souhaitons mettre en place un système d’authentification. Celui-ci comprendra la création de comptes utilisateurs, leur gestion, et la liaison avec le serveur exécutant les outils.

Le travail du stage consiste tout d’abord en un état de l’art des systèmes d’authentification, puis en l’implémentation de la solution choisie.


17. programmation sous iOS, le Balezator


Site :Trac-programmation sois iOS, le Balezator
Lieu :UPMC (2 étudiants)
Encadrant : Fabrice Kordon et Thomas Baspeyras

Description

Le Balezator — Projet de programmation sous iOS

Projet de programmation sous iOS v2014

Le Balezator

Application de pédagogie musicale

Client : Thomas Baspeyras
Courriel : antichambre (arobase) orbite (point) info
Enseignant : Fabrice Kordon
Courriel : fabrice (point) kordon (arobase) lip6 (point) fr

But

Produire une application de pédagogie musicale de niveau publiable. Il existe deux prototypes ayant déjà permis de défricher les spécifications souhaitées et le portage sur iPhone/iPad. Le travail demandé est susceptible d'intéresser deux programmeurs :

  • Produire un module sonore permettant de jouer un son en fonction d'une note, sur une empreinte mémoire légère et adaptable à divers instruments.
  • Intégrer le module sonore, le travail effectué sur le prototype l'année dernière et les fonctions manquantes afin de finaliser une application complète

Historique

L'apprentissage de la musique présente des aspects ludiques, et quelques aspects fastidieux. L'une des nécessités les plus ennuyeuses est de devoir mémoriser l'emplacement des notes sur l'instrument ou sur la portée. Pour combler mes lacunes de guitariste amateur, j'ai écrit pour mon propre usage une application javascript : le Balezator.

Le principe est simple : le Balezator indique une case sur une corde de la guitare (point d'interrogation sur la pastille jaune, visible sur la copie d'écran ci-dessus), et l'on doit identifier la note correspondante à l'aide des boutons C (do), C# Db, D (ré), etc. C'est bête, mais efficace.

Le même principe peut être appliqué à d'autres problèmes de mémorisation. Le Balezator se décline donc, pour l'apprentissage des accords :

Pour la basse :

Ou pour l'apprentissage du solfège :

Le Balezator réside sur mon site personnel (http://www.orbite.info/balezator). Au départ, cette mise en ligne devait seulement me servir à utiliser l'application n'importe où... C'est rapidement devenu la page la plus visitée du site. Depuis que le Balezator est connu sur les forums d'apprentis guitaristes et d'apprentis bassistes, je reçois de temps en temps des courriels me demandant des fonctions nouvelles, ou s'il existe une version pour iPhone ou autre plateforme mobile.

En 2013 un projet de portage du Balezator sur iPhone a été soumis à un étudiant. Une application prototype a été produite, qui a permis de dégrossir l'architecture du projet, de compiler un prototype semi-fonctionnel et de réévaluer les besoins pédagogiques :

Le Balezator pour iOS : bientôt sur vos mobiles !

Le Balezator pour iOS doit faire mieux que son ancêtre javascript sur les points suivants :

  • L'audition des notes demandées par l'application et proposées par l'utilisateur
  • L'adaptation à différentes tailles d'interface graphique (iPhone, iPad)
  • La persistance des préférences
  • La persistance et la présentation des taux de réussite de l'utilisateur
  • L'inclusion d'une mini-documentation pédagogique
  • La localisation linguistique de l'interface et de la documentation

De plus le projet 2014 doit faire mieux que le prototype 2013 sur les points suivants :

  • L'exercice de mémorisation des notes visualisées sur le manche en désignant leur nom doit être complété par l'exercice réciproque : désigner la note sur le manche en fonction du nom proposé
  • Le module sonore est entièrement à construire
  • L'application résultante doit être entièrement fonctionnelle, au delà du stade de prototype

Lot 1 : Le module sonore

Le problème de l'audition des notes est que les fonctions audio standard d'iOS sont bien adaptées à la stricte reproduction d'un contenu pré-enregistré, moins à une reproduction « synthétique ». Or, il ne serait pas de bon goût d'enregistrer toutes les notes à reproduire, ni du point de vue informatique (lourde occupation mémoire), ni du point de vue de la prise de son (des dizaines de prises). Il s'agit plutôt d'émuler un synthétiseur type lecteur d'échantillon, c'est à dire de pouvoir au moins lire les échantillons sonores à une vitesse variable selon la hauteur de la note souhaitée, et mieux, de pouvoir en moduler l'amplitude pour en contrôler la durée (enveloppe ADSR).

En outre le module sonore doit être polyphonique (car après le Balezator des notes viendra sûrement celui des intervalles puis celui des accords), et adaptable à d'autres sonorités d'instrument.

Enfin, il serait souhaitable, chaque fois que cela a un sens, de prendre appui sur la norme Musical Instrument Digital Interface. Le MIDI est un protocole de communication élaboré par les fabricants d'instruments électroniques au début des années 1980, rustique, bien conçu, remarquablement standardisé et encore abondamment en usage aujourd'hui. Le MIDI fournit par exemple une numérotation standard des notes.

Il est à noter que des bibliothèques et des applications ont (bien sûr) déjà été écrites dans des buts similaires. Certaines sont open source, et constituent probablement un excellent point de départ pour ne pas réinventer l'eau tiède.

Lot 2 : Programmation de l'application

Le prototype produit en 2013 implémentait une architecture modulaire, une interface graphique adaptée (manche de guitare et clavier des notes), et le cœur de l'application (proposer des notes aléatoirement et attendre la réponse de l'utilisateur). Le projet 2014 implique de refondre une spécification en tenant compte du prototype existant et des demandes nouvelles (principalement : pouvoir effectuer l'exercice dans les deux sens), puis de programmer une application complète intégrant le module sonore, les spécifications nouvelles et les spécifications initiales non implémentées (localisation, préférences, scores persistants, documentation utilisateur).

Conclusion

Ce projet ne nécessite pas de compétences musicales — c'est le client qui les apporte — mais elles sont les bienvenues ! L'accent est mis sur la capacité de mener le projet à son terme dans un cadre collaboratif (programmeur du module sonore, programmeur de l'application, client, enseignant) ; des capacités de communication et de travail en équipe sont souhaitées.

Bibliographie

le site du Balezator


18. Programmation haut-niveau des architectures hybrides CPU-GPU


Site :Trac-Programmation haut-niveau des architectures hybrides CPU-GPU
Encadrant : FORTIN, Pierre (Pierre.Fortin@lip6.fr) SAID, Issam (Issam.Said@lip6.fr)

Description

Nombre d’étudiants demandé : 2

Description générale :

En géophysique moderne, les méthodes d’imagerie sismique reposent souvent sur la méthode des différences finies pour la modélisation de la propagation des ondes dans le sous-sol. Ce type d’algorithme, relativement simple, est parfaitement adapté aux architectures massivement parallèles et est un très bon sujet d’étude pour le calcul haute performance.

Dans le cadre d’un projet de recherche avec la société TOTAL, nous nous intéressons à l’accélération de certains modèles de propagation d’ondes sur la nouvelle architecture APU (Accelerated Processing Unit, ou Fusion) de la société AMD. Cette architecture permet d’associer sur une même puce un processeur CPU et un processeur GPU (Graphics Processing Unit). Ceci permet au CPU et au GPU d’accéder à une même mémoire physique, et d’éviter ainsi les transferts de données via le bus PCI qui pénalisent les performances de nombreuses applications sur GPU : les toutes dernières consoles de jeux (Sony PlayStation 4 et Microsoft Xbox One) sont ainsi basées sur ces nouveaux APU.

Il existe deux paradigmes principaux pour la programmation des GPU :
- une programmation "bas-niveau" (langages OpenCL et CUDA) qui permet d’obtenir des performances maximales, au prix d’un important effort de développement ;
- une programmation "haut-niveau" via des directives de compilation (#pragma en C/C++, voir par exemple OpenACC ou la dernière version d’OpenMP) qui permet de réduire considérablement les temps de développement, et de procéder de façon incrémentale, mais implique parfois des baisses de performance.

Nous avons déjà développé un code optimisé pour ces APU grâce à un langage bas-niveau (OpenCL). Nous souhaiterions désormais comparer cette approche avec l’utilisation de directives de compilation.

Travail à effectuer :

A partir de notre code d’imagerie sismique en C/C++ (stencils de différences finies pour la propagation des ondes), vous devrez utiliser ces directives de compilation afin d’exploiter au mieux la puissance de calcul de ces nouvelles architectures APU.

Plus précisément, après une prise en main de ce paradigme de programmation haut-niveau, vous devrez déployer le code fourni sur APU à l’aide de directives de compilation : on utilisera pour cela l’implémentation OpenACC de la société CAPS-Entreprise qui permet d’exploiter pleinement les APU. Les performances de ce code seront alors comparées à notre code optimisé en OpenCL.

Diverses améliorations pourront alors être envisagées pour s’approcher au mieux des performances du code OpenCL : on prendra d’abord en compte le placement des données afin de tirer parti de la mémoire des APU, puis on pourra s’intéresser à l’optimisation des noyaux de calcul (toujours via des directives de compilation, comme les directives HMPPCG développées par CAPS Entreprise).

Aucune connaissance préalable des GPU et de leur programmation n’est nécessaire.

Bibliographie

Fusion APU (AMD) : http://www.amd.com/us/products/tech...

Fusion APU (Wikipedia) : http://en.wikipedia.org/wiki/AMD_Ac...

OpenACC : http://www.openacc-standard.org/

CAPS Entreprise : http://www.caps-entreprise.com/


19. Implémentation d’un algorithme de détection des contraintes de dépendances entre les features : Application aux distributions d’eclipse


Site :Trac-Implémentation d’un algorithme de détection des contraintes de dépendances entre les features : Application aux distributions d’eclipse
Encadrant : Ziadi Tewfik

Description

Contexte et Objectif

Dans le cadre de nos travaux de recherche au LIP6, nous avons implémenté un environnement, intégré à Eclipse, permettant l’analyse de code source de de plusieurs variantes d’extraire les fragment de code communs et variables entre toutes ces variantes. Ces fragments sont appelés features.

L’objectif de ce projet est d’étendre cet environnement en implémentant un algorithme permettant de détecter les contraintes de dépendances entre ces features. Cet algorithme doit être par la suite validée sur une étude de cas qui concernes les différentes distributions d’Eclipse.

Apports de projet

  • Les lignes de Produits Logiciels
  • Développement Java avec Eclipse

20. Manipulation de modèles comportementaux pour les lignes de produits


Site :Trac-Manipulation de modèles comportementaux pour les lignes de produits
Encadrant : Ziadi Tewfik

Description

Contexte et Objectif

L’ingénierie des lignes de produits logiciels (LdP) est une approche récente du génie logiciel qui est une transposition des chaînes de production au monde du logiciel. Le principe est de minimiser les coûts de construction de logiciels dans un domaine d’application particulier en ne développant plus chaque logiciel séparément, mais plutôt en le concevant à partir d’éléments réutilisables. Le principe de l’approche LdP réside dans la conception d’une architecture permettant de définir plusieurs logiciels à la fois. Les membres d’une ligne de produits sont caractérisés par leurs points communs, mais aussi par leurs déférences (variabilité). La gestion de cette variabilité est l’une des activités clé des lignes de produits. Une autre activité dans l’ingénierie des LdP concerne la construction d’un produit logiciel (on parle aussi de dérivation de produit) qui consiste en partie à figer certains choix vis-à-vis de la variabilité définie dans la ligne de produits pour générer un produit spécifique.

Plusieurs outils et environnements (comme le plugin Eclipse FeatureIDE[http://wwwiti.cs.uni-magdeburg.de/i...]) ont été proposés ces dernières années pour la manipulation des LdPs. L’idée de base de ces travaux consiste à : 1) proposer des mécanismes pour la spécification de la variabilité. 2) automatiser la dérivation de produits en utilisant les transformations de programmes.

Dans ce projet nous nous intéressons aux modèles de lignes de produits logiciels ou la variabilité est spécifiée dans des modèles comportementaux (automates, diagrammes de séquence)

Travail demandé

  • Implémentation en utilisant les technologies autours de Xtext d’un mini DSL (domain specific language) pour spécifier textuellement les modèles comportementaux (MC).
  • Implémentation des outils pour parser et visualiser les MC.
  • Implémentation d’un algorithme de dérivation pour els MC.
  • Intégration dans l’environnement FeatureIDE.

21. Mutualisation entre machines virtuelles de la mémoire inutilisée - Grp2


Site :LIP6 Regal
Lieu :UMPC, 4 place Jussieu 75005 PARIS
Encadrant : Sopena Julien, Monnet Sébastien
Dates :01/02/2014 au 10/05/2014
Mots-clés : Parcours SAR, aussi pour STL

Description

Mutualisation entre machines virtuelles de la mémoire inutilisée.

Pitch : Si la généralisation de la virtualisation a permis d’offrir une grande flexibilité aux applications modernes, elle s’accompagne d’une fragmentation de la mémoire. Ce projet PSAR vise à développer une solution permettant, en mode utilisateur, de partager entre deux machines virtuelles la mémoire inutilisée au travers d’un cache réparti. Le but étant de comparer les performances obtenues avec celles des solutions noyau existantes.

Mots-clés : cache réparti, programmation système, programmation noyau, virtualisation.

Contexte : La virtualisation est aujourd’hui omniprésente dans les systèmes distribués : elle permet en effet de fournir dynamicité et sécurité. Cependant cette flexibilité se fait au prix d’une importante fragmentation de la mémoire. Or le bon dimensionnement des machines virtuelles (VMs) reste une tâche ardue et les administrateurs surdimensionnent souvent la mémoire allouée à chaque VM, générant ainsi un énorme gâchis de ressources.

L’utilisation de la mémoire libre par le système d’exploitation pour faire du cache règle partiellement le problème : les applications effectuant des Entrées/Sorties en sont bénéficiaires, mais si une VM utilise peu son disque, le cache sera vide ou inutile. De plus, même avec du cache, une application intensive en Entrées/Sorties se trouve fortement ralentie par le moindre accès au disque, alors que de la mémoire libre est peut être disponible sur une autre VM.

Une solution consiste alors à utiliser la mémoire inutilisée d’autres machines en réseau : la latence d’un réseau local est beaucoup plus faible qu’un accès disque, il est donc intéressant de disposer d’un second niveau de cache, réparti en réseau. Si des solutions de cache réparti en espace utilisateur existent déjà (Memcached), elles sont loin d’être transparentes et nécessitent de lourdes modifications des applications pour en profiter.

Objectifs : L’idée de ce projet est de concevoir et d’implémenter un cache réparti transparent pour les applications. Des solutions noyau existent, mais elles induisent un surcoût lié aux changements de contexte. Ce projet vise à développer une solution s’exécutant en mode utilisateur. Plusieurs approches système sont envisageables : surcharge des fonctions d’Entrée/Sortie Posix, réalisation d’un système de fichier utilisateur (FUSE), ...

Déroulement du projet :

Développement des primitives pour capturer les accès au système de fichiers (Posix ou FUSE) ; Développement d’un cache local en espace utilisateur. Pour cela, il faut contourner le page cache du noyau (O_DIRECT) et implanter une stratégie de cache efficace ; Test de performances du cache local en espace utilisateur comparé au page cache du noyau ; Développement du cache réparti : les données évincées du cache local sont envoyées dans un cache "distant" en réseau (sockets Posix ou MPI) ; Test de performances du cache réparti comparé au cache local et au page cache du noyau.

Les étudiants pourront avoir accès, le cas échéant, à la plateforme Grid’5000 pour réaliser l’étude de performance.

Pré-requis : Bon niveau en C et en programmation système, notions en noyau.


22. Temps-réel en multi-cœurs : problème de la contention mémoire - Grp1


Site :LIP6 Regal
Lieu :UMPC, 4 place Jussieu 75005 PARIS
Encadrant : Julien Sopena (Julien.Sopena@lip6.fr), Antoine Blin (Antoine.Blin@lip6.fr)
Dates :01/02/2014 au 10/05/2014
Mots-clés : Parcours SAR, aussi pour STL

Description

Pitch : L’arrivée de processeurs multi-cœurs au sein des architectures matérielles embarquées amène de nouvelles problématiques en termes de sureté de fonctionnement. Ce projet PSAR vise à développer une plate-forme de tests permettant d’évaluer les problèmes de contention mémoire pour des applications temps-réel s’executant sur des processeurs multi-cœurs.

Mots-clés : virtualisation, multi-cœur mémoire, noyau, architecture des ordinateurs.

Contexte : Historiquement, les architectures logicielles du monde automobile ont été développées pour interagir avec les véhicules en respectant des contraintes de temps réel, d’embarquabilité et de minimisation des coûts. Plus récemment, des systèmes multimédia basés sur Linux et Androïd ont été intégrés au sein des véhicules sur des calculateurs différents des systèmes temps réel.

L’utilisation de processeurs multi-cœurs est une solution potentiellement intéressante pour diminuer les coûts. En utilisant la virtualisation sur de telles architectures, il est possible d’exécuter des systèmes d’exploitation temps réels en parallèle de systèmes multimédia sur un même processeur. L’hyperviseur doit alors assurer un isolement spatial et temporel entre les différents systèmes pour garantir le respect des contraintes de sûreté et de sécurité.

Les hyperviseurs développés pour des architectures embarquées, attribuent, de manière exclusive, un ou plusieurs cœurs à chaque OS virtualisé. La mémoire, quant à elle, est divisée en plages attribuées statiquement à chaque système d’exploitation virtualisé, les mécanismes de protection mémoire étant utilisés pour assurer l’isolation. Si ces solutions assurent le partitionnement de la mémoire et du CPU, des ressources telles que les bus et certains caches restent partagées. Un cœur qui effectue un grand nombre d’accès mémoires peut provoquer de la contention sur les bus et de la pollution au sein des caches partagés impactant ainsi les autres cœurs.

Objectifs : L’objectif de ce projet est de développer une plate-forme de tests chargés d’évaluer . Il s’agira notamment de pouvoir solliciter les différents éléements du système mémoire (Caches et BUS) d’une architecture multi-cœurs et de mesurer les ralentissements engendré sur les tâches exécutées.

Pré-requis : Connaissances Noyau, Bon niveau en C et en architecture.


23. Temps-réel en multi-cœurs : problème de la contention mémoire - Grp2


Site :LIP6 Regal
Lieu :UMPC, 4 place Jussieu 75005 PARIS
Encadrant : Julien Sopena (Julien.Sopena@lip6.fr), Antoine Blin (Antoine.Blin@lip6.fr)
Dates :01/02/2014 au 10/05/2014
Mots-clés : Parcours SAR, aussi pour STL

Description

Pitch : L’arrivée de processeurs multi-cœurs au sein des architectures matérielles embarquées amène de nouvelles problématiques en termes de sureté de fonctionnement. Ce projet PSAR vise à développer une plate-forme de tests permettant d’évaluer les problèmes de contention mémoire pour des applications temps-réel s’executant sur des processeurs multi-cœurs.

Mots-clés : virtualisation, multi-cœur mémoire, noyau, architecture des ordinateurs.

Contexte : Historiquement, les architectures logicielles du monde automobile ont été développées pour interagir avec les véhicules en respectant des contraintes de temps réel, d’embarquabilité et de minimisation des coûts. Plus récemment, des systèmes multimédia basés sur Linux et Androïd ont été intégrés au sein des véhicules sur des calculateurs différents des systèmes temps réel.

L’utilisation de processeurs multi-cœurs est une solution potentiellement intéressante pour diminuer les coûts. En utilisant la virtualisation sur de telles architectures, il est possible d’exécuter des systèmes d’exploitation temps réels en parallèle de systèmes multimédia sur un même processeur. L’hyperviseur doit alors assurer un isolement spatial et temporel entre les différents systèmes pour garantir le respect des contraintes de sûreté et de sécurité.

Les hyperviseurs développés pour des architectures embarquées, attribuent, de manière exclusive, un ou plusieurs cœurs à chaque OS virtualisé. La mémoire, quant à elle, est divisée en plages attribuées statiquement à chaque système d’exploitation virtualisé, les mécanismes de protection mémoire étant utilisés pour assurer l’isolation. Si ces solutions assurent le partitionnement de la mémoire et du CPU, des ressources telles que les bus et certains caches restent partagées. Un cœur qui effectue un grand nombre d’accès mémoires peut provoquer de la contention sur les bus et de la pollution au sein des caches partagés impactant ainsi les autres cœurs.

Objectifs : L’objectif de ce projet est de développer une plate-forme de tests chargés d’évaluer. Il s’agira notamment de pouvoir solliciter les différents éléments du système mémoire (Caches et BUS) d’une architecture multi-cœurs et de mesurer les ralentissements engendrés sur les tâches exécutées.

Pré-requis : Connaissances Noyau, Bon niveau en C et en architecture.


24. UnlockSat : vers un solveur SAT parallèle coopératif sur multi-coeurs.


Site :LIP6 Regal
Lieu :UMPC, 4 place Jussieu 75005 PARIS
Encadrant : Julien Sopena (Julien.Sopena@lip6.fr), Souheib Baarir (Souheib.Baarir@lip6.fr) et Julia Lawall (Julia.Lawall@lip6.fr).
Dates :01/02/2014 au 10/05/2014
Mots-clés : Parcours SAR, aussi pour STL

Description

UnlockSat : vers un solveur SAT parallèle coopératif sur multi-coeurs.

Pitch : La résolution de problèmes SAT se prête bien aux nouvelles architectures multi-coeurs, car ces problèmes se décomposent naturellement en sous-problèmes indépendants. Cependant pour obtenir de bonnes performances un solveur parallèle nécessite un mécanisme de partage d’information pour éviter aux différents threads de faire les mêmes erreurs. L’objet de ce stage est de réduire les coûts de synchronisation induit par ce mécanisme de partage, en travaillant tant sur l’implémentation de la synchronisation que sur les informations partagées.

Contexte : Avec l’intégration toujours plus grande, des systèmes informatiques dans des applications critiques (métro, voitures, centrales-nucléaires, blocs opératoires, etc), assurer la correction des programmes devient une nécessité. Si l’utilisation systématique de tests permet d’améliorer grandement la qualité des codes, elle ne peut réellement garantir leur correction. A l’inverse, les techniques dites de model-checking, qui vérifient la validité du workflow applicatif par rapport à une propriété donnée, permettent de garantir la validité des programmes. Parmis les techniques utilisées dans l’industrie, celles bassées sur la théorie de la satisfiabilité booléenne (SAT) tant à s’imposer, notament dans l’aéronotique.

La résolution de promblème SAT sur des modèles toujours plus complexes pose des problèmes de temps de calcul. L’utilisation d’architectures multi-coeurs a très vite semblé prometteuse car le problème se prête très bien à la parallélisation. En effet, en fixant la valeur de l’une des variables booléennes propositionnelles u on obtient deux nouveaux problèmes disjoints : l’un associé à la valeur u=vrai, l’autre découlant de u=faux. Ces deux nouveaux problèmes plus petits (puisque contenant une variable de moins) peuvent alors se résoudre indépendamment.

Cependant, les approches parallèles souffrent d’un problème de partage de l’information. En effet, l’isolation des threads de traîtement dans les parallélisations dites non collaboratives empêche le partage des connaissances. Ces derniers se retrouvent à faire les mêmes "erreurs". À l’opposé dans les approches dite collaboratives, le surcoût de synchronisation engendrée par le partage des structures de données limite l’intérêt de la parallélisation.

L’idée du projet UnlockSat, dans lequel s’inscrit ce stage, est de réaliser un solveur SAT parralèle colaboratif de façon à pouvoir bénéficier des techniques d’apprentissage de clause (clauses-learning) et ainsi à pouvoir concurrencer les solutions séquentielles ou des portfolios (différents solveurs en parallèle).

Objectif : Dans le cadre de ce projet, une permière version d’un solveur multi-threadé à été rélasier. Se basant sur le solveur séquentiel Glucose, elle a été pensée de façon à pouvoir intégrer les derniers algorithme de la littérature mais aussi de façon à limiter l’impact de la synchronisation. Si les résultats brutes se montrent très prometteurs (le prototype se classerai 3ème au dernier concourt international SAT Competition 2013 dans la catégorie Hard-Combinatorial Problems), ces premiers travaux ont aussi été l’occasion de mettre en évidence l’importance du partage des clauses. En effet, les bonnes performances obtenues avec les 8 coeurs de la compétition, ne se maintiennent pas, dès lors que l’on utilise les 40 coeurs de la machine de test.

L’objectif de ce stage est d’intégrer au prototype existant des mécanismes permettant de limiter le coût lié à la synchronisation. Plusieurs approches pourront être mis-en-oeuvre :

  • utilisation de structure wait-free ;
  • retardement du partage des clauses ;
  • selection dynamique des clauses partagées.

Pré-requis : Bon niveau en C++.