Sujet de stage

Langage et reconnaissance d'algorithmes pour le métacalcul

DEA Informatiques USTL, 2001-2002

Tuteurs du Stage

Serge Petiton et Xavier Redon, Laboratoire d'Informatique Fondamentale de Lille (LIFL)
Équipe d'Accueil

Méthodologies et Algorithmiques Parallèles (MAP) du LIFL.
Introduction

Le calcul scientifique intensif parallèle est de plus en plus effectué selon un modèle de programmation parallèle à gros grain de type SPMD (Single Program Multiple Data). Néanmoins, le MPDM ( Multiple Programs Multiple Data) ou le MSPMD (Multiple SPMD) sont désormais possibles sur de nombreuses machines mais sont encore peu utilisés car plus durs à mettre en oeuvre. Cette programmation peut être asynchrone et à gros grains. Les réseaux de machines hétérogènes peuvent alors être utilisés pour obtenir la puissance de calcul nécessaire à de nombreuses applications. Ces environnements de metacalcul (metacomputing) existent sous plusieurs formes. Une forme assez proche du fonctionnement du Web est celle dite pair à pair ( peer to peer, P2P). Chaque machine est alors à la fois serveur et worker. Il est envisageable que chaque machine soit elle-même parallèle. Les calculs distribués et parallèles sont donc à prendre en compte dans ce type de programmation. Dans la cadre d'un programme du ministère de la recherche (ACI GRID), nous travaillons en relation avec plusieurs laboratoires de recherche sur la programmation de tels réseaux de machines. La programmation pour ces systèmes pair à pair et l'évaluation des performances sont délicates. Nous utilisons des langages permettant d'exprimer des graphes de tâches (de composants logiciels) et souhaitons pouvoir reconnaitre ensuite automatiquement certaines méthodes à ce niveau.
La reconnaissance des méthodes de calcul peut se faire en utilisant les travaux menés en collaboration avec Paul Feautrier et Denis Barthou de l'université de Versailles. Il s'agit d'une méthode basée sur la construction d'un graphe d'équivalence. Deux algorithmes comparés sont déclarés équivalents lorsque certaines conditions sont vérifiées pour tous les chemins partant de la racine de l'arbre vers ses feuilles. Pour l'instant, les algorithmes doivent être donnés sous la forme de systèmes d'équations (vous pouvez tester le prototype).
Objectif du stage

L'objectif principal du stage est d'évaluer un langage de contrôle pour programmer dans ce cadre et d'étudier l'adaptation de techniques de reconnaissances automatiques d'algorithmes aux cas des méthodes gros grains écrites à l'aide de ce langage.
En ce qui concerne la reconnaissance d'algorithmes, on se limitera dans un premier temps à adapter le prototype de comparaison d'algorithmes présenté dans l'introduction pour tester des programmes écrits avec un langage de contrôle.
Thèse

Ce travail peut être poursuivi dans le cadre d'une thèse de doctorat. Plusieurs sujets sont possibles à la suite de ce stage.
Rémunération

Dans le cadre des financements de l'ACI ``GRID'', une rémunération est prévue. Néanmoins, le montant et les modalités sont à définir après le lancement effectif de l'ACI, début janvier à priori.
This document was translated from LATEX by HEVEA.