Date

Jour

Titre

Intervenant
27/04/2003 jeudi

25/04/2006 mardi Définition, modélisation et réalisation d’un système distribué à grande échelle : DIRAC Vincent Garonne
20/04/2003 jeudi

18/04/2006 mardi Algorithmique pour l'allocation et la tarification des ressources dans les réseaux télécoms avec garanties de service Loubna Echabbi
13/04/2003 jeudi Entrées-sorties réseau hautes performances dans les grappes Brice Goglin
11/04/2004 mardi Approches fonctionnelles de la programmation parallèle et des méta-ordinateurs.Sémantiques, implantations et certification. Frederic Gava
6/04/2003
jeudi Infrastructures de stockage efficaces et flexibles pour grappes Renaud Lachaize
4/04/2006 mardi MPICH2:Nemesis, une implementation hautes-performances de MPI2 Guillaume Mercier
30/03/2006 jeudi Tarification des réseaux à différenciation de services Yezekael Hayel
28/03/2006 mardi Redistribution de données à travers un réseau à haut débit
Séminaire reporté à cause grève nationale.
 Frederic Wagner
23/03/2006 jeudi Introduction à l'ordonnancement pour les systèmes temps réel multiprocesseurs Joël Goossens
21/03/2006 
mardi Reporté Vincent Garonne
16/03/2006
jeudi ANNULE
9/03/2006
Plates-formes d'expérimentation à grande échelle.
Matinée de séminaire dans le cadre de l'école Grid'5000		 H.Bal
T.Friedmann
F.Malek
F.Fernandez
2/03/2006
Algorithmique distribuée dans des contextes dynamiques.
Flavien Vernier
16/02/2006
Gestion de la tolérance aux fautes et de la cohérence des données dans le service de partage de donnée pour JuxMem Sebastien Monnet
2/02/2006 Algorithmes paralleles à grain adaptatif - exemple des prefixes.
Jean-Mouis Roch
26/01/2006 Une plate-forme d'expérimentation pour ordonnanceurs sur machines hiérarchiques Samuel Thibault

25/04 : Algorithmique pour l'allocation et la tarification des ressources dans les réseaux télécoms avec garanties de service

Intervenant : Vincent Garonne (http://www.lal.in2p3.fr/dyn/rubrique.php3?id_rubrique=48)

Lieu : Laboratoire ID
Heure : 15h


Nous nous sommes intéressés par des problèmes algorithmiques concernant le routage intradomaine et interdomaine en considérant une vision économique.Nous considérons d'abord   le problème d'allocation et de tarification auquel un fournisseur est confronté. Nous considérons une approche "off-line" où l'opérateur a une vision complète de son réseau et nous nous intéressons au problème d'admission des requ\^etes de service en prenant en compte leurs budgets.  Nos résultats s'appuient d'une part sur l'analyse de complexité et d'autre part sur la théorie des matrices unimodulaires. Nous considérons ensuite une approche distribuée "en ligne", nous présentons DiMA un modèle  qui permet de distribuer la décision d'admission des requetes sur les différents routeurs du réseau. Cette solution distribuée permet le passage à l'échelle, de plus elle permet une différentiation des services économiquement efficace gr\^ace à l'utilisation des enchères. Nous considérons enfin les incitations économiques qui peuvent influencer les décisions de routage interdomaine. Nos contributions consistent à proposer un premier modèle économique qui prend en compte les prix annoncés par les différents partenaires dans le choix des routes interdomaines. Nous présentons un mécanisme itérative qui permet de choisir les prix entre les différents opérateurs et analysons sa stabilité.

18/04 : Algorithmique pour l'allocation et la tarification des ressources dans les réseaux télécoms avec garanties de service

Intervenante : Loubna Echabbi (http://www.loria.fr/~echabbi/)

Lieu : Laboratoire ID
Heure : 15h

Les environnements de calculs distribués à grande échelle se différencient des machines parallèles
les ayant précédés par leurs natures intrinsèquement hétérogènes, partagées et fortement dynamiques.
Ils se déclinent en deux types de système : les grilles institutionnelles qui mutualisent les ressources
d’organismes par accord mutuel et les systèmes communautaires de calcul global.

Dans ce séminaire, nous donnerons ainsi un état de l’art de ces systèmes et détaillons ensuite chacune
de ces formes en décrivant leurs ressemblances et leurs différences. Nous observons l’avantage et l’intérêt
d’avoir un système hybride conjuguant les deux aspects. Nous proposons une implémentation d’un système
unifié DIRAC (Distributed Infrastructure With Remote Agent Control).

Cette solution est un système léger, extensible et robuste, qui offre une plate-forme transparente et uniforme
pour une seule communauté ou organisation virtuelle. DIRAC repose sur une architecture orientée service
Agents/services régulant notamment la charge et les accès aux données dans le contexte de régime
permanent et saturé (« High Throughput Computing ») générés par des simulations de Monte-carlo
et des analyses de données de la physique de hautes énergies.

Nous exposerons la démarche mise en oeuvre pour concevoir et définir ce système qui a a connecté
plus de 6.000 processeurs répartis sur une soixantaine de sites dans le monde, a supporté plus de
5.500 tâches simultanées et a stocké, transféré et dupliqué plus de 100 téra-octets de données.

Nous traiterons notamment de la difficulté d’évaluer rigoureusement des stratégies d’ordonnancement
ou de méta-ordonnancement avec une plate-forme de système distribué à grande échelle.
Nous présenterons notre modèle d’évaluation et de performances pour une plate-forme méta-ordonnancée
composée de sites autonomes. Nous décrirons ensuite notre simulateur développé basé sur Simgrid
et les travaux liés à sa validation. Cette évaluation se situe sur une plate-forme hétérogène pour des
tâches simples dans un contexte de régime permanent et saturé.

13/04 : Entrées-sorties réseau hautes performances dans les grappes

Intervenant : Brice Goglin ()

Lieu : Laboratoire ID
Heure : 15h

Je commencerai par rappeler rapidement le fonctionnement des réseaux des grappes en détaillant le problème des traduction d'adresse et de l'enregistrement mémoire. Je présenterai ensuite mes travaux de thèse qui ont consisté en l'étude des interfaces de programmation de ces réseaux dans le cadre du stockage distribué, la mise en évidence de certaines lacunes, puis des propositions pour répondre aux besoins du stockage distribué et leur intégration dans l'interface MX des réseaux Myrinet.
Je présenterai ensuite mes travaux actuels sur l'adaptation du modèle de programmation de réseaux rapides aux nouvelles architectures matérielles. Je montrerai notamment que les modèles basés sur l'OS-bypass et le zéro-copie conçus il y a une dizaine d'années ne s'appliquent plus forcément aux machines modernes. Leur remise en cause permet d'envisager un support logiciel beaucoup plus simple et proche de celui des réseaux classiques (Ethernet), avec des performances inchangées.
Je terminerai l'exposé en détaillant l'impact de la généralisation des machines hiérarchiques sur la conception des entrées-sorties. D'une part, l'augmentation du nombre de processeurs dans la machine et la saturation de leur fréquence impose de revoir la distribution de la charge de traitement des entrées-sorties. D'autre part, l'impact des contraintes NUMA sur les performances conduit à vouloir placer judicieusement les zones de mémoire intermédiaires et le traitement des entrées-sorties.

11/04 : Approches fonctionnelles de la programmation parallèle et des méta-ordinateurs.Sémantiques, implantations et certification.

Intervenant : Fréderic Gava ()


Lieu : Laboratoire ID
Heure : 15h


Certains problèmes nécessitent des performances que seules les machines massivement parallèles ou les méta-ordinateurs peuvent offrir. L’écriture d’algorithmes pour ce type de machines demeure plus difficile que pour celles strictement séquentielles et la conception de langages adaptés est un sujet de recherche actif nonobstant la fréquente utilisation de la programmation concurrente. En effet, la conception d’un langage de programmation est le résultat d’un compromis qui détermine l’équilibre entre les différentes qualités du langage telles que l’expressivité, la sûreté, la prédiction des performances, l’efficacité ou bien la simplicité de la sémantique.

Ce travail s'inscrivait dans le cadre du projet «CoordinAtion et Répartition des Applications Multiprocesseurs en objective camL» (CARAML) de l'ACI GRID dont l'objectif était le développement de bibliothèques pour le calcul haute-performance et globalisé autour du langage OCaml. Ce projet était organisé en trois phases successives : sûreté et opérations data-parallèles irrégulières mono-utilisateur ; opérations de multitraitement data-parallèle ; opérations globalisées pour la programmation de grilles de calcul.

Cet exposé est organisé en 3 parties correspondant chacune aux contributions de l’auteur dans chacune des phases du projet CARAML : une étude sémantique d’un langage fonctionnel (appelé BSML) pour la programmation BSP (Bulk-Synchronous Parallelism, un modèle qui permet la portabilité des programmes tout en offrant une prévision réaliste de leurs performances sur une grande variété d'architectures parallèles) et la certification des programmes écrits dans ce langage ; une présentation d’une primitive de composition parallèle (et qui permet aussi la programmation d’algorithmes «diviser-pour-régner» parallèles), un exemple d’application via l’utilisation et l’implantation de structures de données parallèles et une extension pour les entrées/sorties parallèles en BSML ; l’adaption du langage pour le méta-calcul.

6/04  Infrastructures de stockage efficaces et flexibles pour grappes

Intervenant : Renaud Lachaize (http://www.ics.forth.gr/~rlachaiz)

Lieu : Laboratoire ID
Heure : 10h

L'infrastructure de stockage sur laquelle repose une grappe a un impact majeur sur les performances et la disponibilités des applications.
Il constitue également l'un des éléments les plus onéreux du système informatique global, à la fois en termes de coûts directs (matériel et logiciels) et de coûts indirects (administrateurs humains).
Pour ces raisons, les systèmes de stockage sont en train d'évoluer vers des architectures plus parallèles, basées sur des composants génériques et implémentant la majorité des fonctions de manière logicielle.
La première partie de cet exposé dressera un panorama des recherches actuelles sur la problématique émergente des "briques de stockage".
Dans un second temps, je présenterai mes travaux récents sur les canevas logiciels pour systèmes de stockage répartis, avec un accent particulier sur la conception de systèmes de fichiers, les protocoles de tolérance aux pannes et le développement de services spécialisés pour certains domaines d'application.




30/03 : Tarification des réseaux à différenciation de services

Intervenant : Yezekael Hayel (http://www.irisa.fr/armor/lesmembres/Hayel/main.htm)

Lieu : Laboratoire ID
Heure : 15h
Les réseaux de communication sont en expansion permanente tant au point de vu de nouvelles applications, du nombres d'usagers et du trafic. Il existe de nombreux outils permettant la modélisation et l'étude des performances des réseaux. Des outils théoriques comme les files d'attente sont utilisés pour évaluer les performances de tels systèmes. Récemment, des concepts de la théorie des jeux ont apportés une vision
nouvelle à l'étude des réseaux.
Je propose dans mon exposé de présenter une partie de mes travaux de thèse portant sur l'étude du contrôle de congestion via un mécanisme de tarification pour les réseaux à différenciation de services. Cette étude utilise des concepts de modélisation par des files d'attente multiclasses et également la théorie des jeux.

Mots-clés: Réseaux de communication, Evaluation de performances, QoS, Théorie des jeux, Optimisation.


28/03 : Redistribution de données à travers un réseau à haut débit

Intervenant : Frédéric Wagner (http://www.loria.fr/~wagnerf/)

Lieu : Laboratoire ID
Heure : 15h

Pour utiliser au mieux les ressources distribuées (calculateurs parallèles, grappes d'ordinateurs, serveurs de calcul ou de données, ordinateur personnel, dispositifs de visualisation, etc.) et plus généralement l'infrastructure numérique il est nécessaire de mettre au point des environnements et des algorithmes qui gèrent celle-ci de manière optimisée.

Nous présentons le problème qui survient lorsque des données doivent être rapidement transférées d'un calculateur parallèle à un autre calculateur. C'est le cas lorsque le traitement fait intervenir du couplage de code ou lorsque l'on veut visualiser des données calculées par une machine parallèle.

Ce problème appelé la redistribution de données est un problème très important quand les critères de performances sont au premier plan. Pour être résolu, il nécessite surtout d'optimiser l'ordre dans lequel les données sont transférées.

Nous introduisons une modélisation de ce problème d'ordonnancement basé sur la théorie des graphes ainsi que deux algorithmes d'approximation le résolvant. Nous illustrons le développement de ces algorithmes par la transformation d'un algorithme pseudo-polynomial en algorithme polynomial.


23/03 :  Introduction à l'ordonnancement pour les systèmes temps réel multiprocesseurs

Intervenant : Joël Goossens (http://www.ulb.ac.be/di/ssd/goossens/)

Lieu : Laboratoire ID
Heure : 15h

Cet exposé aborde les techniques d'ordonnancement multiprocesseurs ; le but  est essentiellement de montrer en quoi l'ordonnancement multiprocesseur temps réel (un domaine de recherche relativement jeune) n'est pas une simple extension du cas monoprocesseur (déjà bien étudié dans la littérature).

La première partie de l'exposé constitue une introduction aux systèmes temps réel, aux techniques et problèmes d'ordonnancement classiques.

La deuxième partie de l'exposé introduit le problème plus général  de l'ordonnancement sur des plates-formes multiprocesseurs et montre en quoi l'ordonnancement multiprocesseur n'est pas une simple extension du cas monoprocesseur : absence d'algorithmes optimaux, anomalies d'ordonnancement, etc.

La troisième partie de l'exposé présente une technique par augmentation de ressources pour l'ordonnancement de tâches temps réel avec l'assignation de priorité Rate Monotonic sur des plates-formes hétérogènes multiprocesseurs (travail conjoint avec Sanjoy Baruah, Université de Caroline du Nord).

21/03

Intervenant : Vincent Garonne (http://www.lal.in2p3.fr/dyn/rubrique.php3?id_rubrique=48)

16/03 : MPICH2:Nemesis, une implementation hautes-performances de MPI2

Intervenant : Guillaume Mercier (http://dept-info.labri.u-bordeaux.fr/~mercier/main.html)
Lieu : Laboratoire ID
Heure : 15h

Jusqu'a tres recemment, les implementations du standard MPI2 n'etaient pas tres courante, quelques constructeurs seulement les proposaient avec leur materiel. Depuis quelques mois, l'univers MPI a bouge avec l'apparition de nouvelles implementations libres : MPICH2, Open MPI ou encore YAMPII. Dans cet expose, je detaillerai un sous-systeme de communication qui a ete cree et developpe pour permettre a MPICH2 d'obtenir de hautes performances. Je montrerai egalement les premiers resultats obtenus (certains publies, d'autres non) et etablierai des comparaisons entre les precedents sous-systemes de communication existants pour MPICH2, mais aussi avec les implementations concurrentes.

Présentation

9/03 : Plates-formes d'expérimentation à grande échelle

Cette matinée aura lieu à l'INRIA Rhône-Alpes.
Les invités :
- Henri Bal, présentation sur DAS3
- Timur Friedman, présentation sur PlanetLab/EuronetLab
- Fairouz Malek et Fabio Fernandez, présentation de LCG

Pour plus de détails, consulter le site de l'école Grid'5000

2/03 : Algorithmique distribuée dans des contextes dynamiques

Intervenant : Flavien Vernier (http://www.loria.fr/~vernier/)

Resumé : Avec l'évolution actuelle du calcul distribué sur grilles, de nouvelles problématiques sont apparues telles que le dynamisme des topologies. Au cours de ma thèse je me suis penché sur le problème de l'application des algorithmes itératifs d'équilibrage de charge sur des topologies dynamiques.
Je présenterai ces travaux pour un algorithme en particulier : la diffusion de premier ordre. Je l'aborderai aussi bien d'un point de vu théorique que pratique. Puis j'évoquerai mes travaux en cours sur des algorithmes de détection de convergence et d'exclusion mutuelle dans des contextes dynamiques. Je conclurai cette présentation par divers perspectives que j'envisage.

16/02 : Gestion de la tolérance aux fautes et de la cohérence des données dans le service de partage de donnée pour JuxMem

Intervenant : Sébastien Monnet (http://www.irisa.fr/paris/pages-perso/Sebastien-Monnet/)

Lieu : Laboratoire ID, 15h
Résumé :
La gestion de données à large échelle est un besoin crucial pour les
applications sur la grille de calcul. Cependant, il n'existe pas
d'approche standard pour le partage de données qui soit largement
acceptée par la communauté. Les solutions actuelles sont basées sur
des transferts explicites des données. Avec le nombre croissant
d'applications qui emploient d'importants volumes de données, nous
pensons que la gestion explicite des données devient une difficulté
majeure pour les programmeurs. Un service de partage de données pour
le calcul sur grille devrait fournir un accès transparent aux données.
Le prototype JuxMem est une illustration de ce type de service. Il
gère, de manière transparente, la localisation et le transfert des
données sans aucune intervention de l'utilisateur.

Vu l'échelle du système (plusieurs milliers de noeuds), un tel
service doit être conçu pour un environnement volatil :
les arrivées, les départs des ressources ou leur défaillance doivent
être supportés de manière transparente. En conséquence, le rôle d'un
tel service réside aussi dans l'emploi d'une stratégie de
réplication et dans l'utilisation d'un protocole de cohérence
afin de garantir la disponibilité des données.

Dans cette présentation, nous nous concentrons sur le problème de la
gestion de la cohérence de données répliquées en présence de
défaillances. Nous proposons une architecture logicielle qui découple
la gestion de la tolérance aux défaillances de celle de la
cohérence. Ceci est illustré par une étude de cas montrant comment
concevoir un protocole de cohérence s'appuyant sur des modules de
tolérance aux défaillances.

http://juxmem.gforge.inria.fr/

2/02 : Algorithmes paralleles à grain adaptatif - exemple des prefixes

Intervenant : Jean-Louis Roch (http://www-id.imag.fr/~jlroch/)

Lieu : Laboratoire ID, 16h
Résumé :
Pour l'execution sur processeurs heterogenes ou dont la vitesse (charge) peut varier en cours d'exécution, nous presentons un schéma algorithmique parallèle générique permettant d'adapter la granularité du parallélisme à la charge (variable) des processeurs. Ce schéma est basé sur le couplage récursif et dynamique d'un algorithme séquentiel optimal et d'un algorithme parallèle non optimal mais récursif et à grain fin. Il exploite  un ordonnancement dynamique de type vol de travail (Cilk, Kaapi) modifié par
Bender&Rabin pour être à utilisation maximale sur p processeurs à vitesses variables, de vitesse moyenne V.

Ce schéma est instancié sur le calcul des préfixes. En effet, toute parallélisation de ce problème entraîne nécessairement un surcoût en nombre d'opérations: alors qu'un calcul séquentiel nécessite n opérations, tout algorithme (parallèle) de profondeur d requiert au moins 2n-d opérations. Bien que l'algorithme adaptatif de préfixes proposé soit indépendant du nombre de processeurs, son temps d'exécution théorique est $\frac{2n}{V.(p+1)}  + O(log n)$, ce qui asymptotiquement optimal si les processeurs sont identiques (i.e. $V=1$) et ce quel que soit le nombre $p >= 1$ de processeurs.

Expérimentalement, cet algorithme adaptatif pour les préfixes est comparé à des algorithmes optimaux, séquentiel (p=1) et parallèles (p>1) pour un nombre fixé p de processeurs identiques sur une machine SMP octo-processeurs. Même pour des petites valeurs de $n$ (100) et de $p$ (de 1 à 8), l'algorithme adaptatif a des performances optimales dans le cas où les processeurs sont dédiées au calcul; et il est beaucoup plus rapide dans le cas général où la machine exécute concuremment d'autres processus (cas multi-utilisateurs).

References
----------
Jean-Louis Roch, Daouda Traore : Un algorithme adaptatif optimal pour le calcul parallèle des préfixes (en cours de soumission)

El-Mostafa Daoudi, Thierry Gautier, Aicha Kerfali, Rémi Revire, and Jean-Louis Roch. Algorithmes parallèles à grain adaptatif et applications. Technique et Science Informatiques, 24/5:1-20, 2005.

M. A. Bender and M. O. Rabin. "Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk." Theory of Computing Systems Special Issue on SPAA '00, 35: 289-304, 2002.
 

26/01 : Une plate-forme d'expérimentation pour ordonnanceurs sur machines hiérarchiques

Intervenant : Samuel Thibaut (http://dept-info.labri.u-bordeaux.fr/~thibault/)

Résumé :
La tendance actuelle des constructeurs est à l'HyperThreading, au multi-core
et autres technologies NUMA (Non-Uniform Memory Access), produisant ainsi
des machines très hiérarchisées. Pour pouvoir profiter le mieux possible de
telles architectures, il est nécessaire de pouvoir contrôler finement le
placement des threads et des données. De quels outils dispose-t-on pour cela ?
L'interface POSIX ne fournit absolument aucune aide ; les différents systèmes
d'exploitations existants fournissent parfois quelques primitives de placement
statique. Au final, si l'on veut contrôler vraiment l'ordonnancement, on est
obligé de modifier le noyau.

Notre réponse est basée sur un concept de bulles permettant au programmeur
de regrouper de manière hiérarchisée les différents threads de son
application. Chaque application ayant ses spécificités, un ordonnancement
générique n'obtiendrait pas de très bonnes performances. Nous fournissons donc
un ensemble d'outils pour gérer finement l'ordonnancement de l'hiérarchie de
bulles (placement, préemption, migration, priorités, ...). Le programmeur
dispose ainsi, pour ses applications multithreadées habituelles (POSIX), d'une
véritable plate-forme d'expérimentation pour développer des ordonnanceurs de
threads en espace utilisateur. Les applications envisagées vont de
l'optimisation de simulations sismiques (au sein du projet ANR NUMASIS) à
l'émulation équitable de machines virtuelles pour exécuter des algorithmes
distribués (au sein de l'ACI GRIGRID).

Présentation
Animation 1
Animation 2
Animation 3