La grille est souvent présentée comme le prochain eldorado du calcul
scientifique. Grâce à elle, accéder à la puissance des plus grosses machines
depuis son ordinateur personnel sera un jeu d'enfant. Les ordinateurs du
monde entier s'uniront pour vendre leurs services au plus offrant.

Malheureusement, la réalité actuelle est un peu différente. L'utilisation de
cette plate-forme se heurte encore à de très nombreux problèmes.
Contrairement aux systèmes parallèles qui l'ont précédés, les capacités de
la grille sont dynamiques, hétérogènes et même non-dédiées.

En amont de tout problème d'ordonnancement se pose alors le problème de
l'obtention d'informations pertinentes, récentes et précises sur l'état
actuel du système, et sur les performances que l'on peut escompter dans les
heures ou minutes à venir.

L'exposé présentera divers outils complémentaires pour résoudre ce problème.
Le premier outil est NWS, développé à l'université de Santa Barbara,
Californie, qui constitue un ensemble cohérent pour mesurer les
disponibilités de la plate-forme en terme de charge processeur et mémoire,
ainsi que de bande passante entre machines.

Le second outil est FAST, développé par nos soins, dont l'objectif est de
prédire les besoins des routines à ordonnancer en terme d'espace mémoire, de
temps de calcul et de volume de communication. La méthode principale de FAST
pour cela est l'étalonnage préalable.

Le troisième outil est ALNEM, également développé à l'ENS-Lyon, dont
l'objectif est de cartographier le réseau pour repérer les points de
contention afin de pouvoir prédire les débits de flux concurrents.

Enfin, et si le temps nous le permet, nous présenterons DIET, également
développé à l'ENS-Lyon. Il s'agit d'une plate-forme de Grid computing
complète permettant de déclarer des serveurs de calcul, vers lesquels les
requêtes des clients sont ordonnancés par un agent. Évidement, DIET repose
sur les différents outils présentés ici pour obtenir les connaissances
nécessaires sur le système.

Les grilles de PC (Desktop Grids) proposent l'exploitation massive des ressources vacantes au sein des réseaux et sur Internet pour l'exécution d'applications parallèles de grande taille. Dans ce modèle, chaque ressource est potentiellement mise à disposition pour l'ensemble des participants. Nous présenterons les problématiques et les différentes approches méthodologiques pour l'étude des systèmes de calcul à large échelle, ainsi que les principes d'architecture de base des systèmes de calcul global (SETI@Home, distributed.net, BOINC) et applications pair-à-pair (Napster, Gnuttella).

La seconde partie de l'exposé présentera XtremWeb une plate-forme pour l'étude expérimentale du calcul global pair-à-pair. L'environnement XtremWeb est une plate-forme généraliste, sécurisée et tolérante aux défaillances pour l'exécution d'applications
parallèles. Le projet poursuit deux objectifs : fournir un environnement de calcul haute-performance, pour la production, à destination des institutions académiques ou industrielles et une plate-forme logicielle d'expérimentation et de recherche. L'exposé présentera les choix de conception et de réalisation d'XtremWeb ainsi qu'une courte étude de performance basée sur des applications issues du monde réel et un déploiement multi-site.

Cette plate-forme a permis de mener à bien une étude plus spécifique sur l'exécution d'applications parallèles communicantes à travers MPICH-V. MPICH-V est une implémentation de la librairie MPICH tolérante à la volatilité des noeuds de calcul fondée sur un checkpoint non coordonné et le log pessimiste des messages.

La troisième partie de l'exposé s'intéressera à l'exécution d'applications de type WorkFlow (graphe de tâches) sur les grilles de PC. Nous cherchons d'abord à caractériser les périodes de disponibilité et l'activité des ressources présentes dans les Desktop Grid. Pour cela une méthodologie de mesures basées sur une application de prise de trace est exécutée sur trois déploiements de plate-forme différentes (Entropia à l'UCSD, XtremWeb à l'U-PSUD et Boinc sur Internet). A partir de ce recueil de traces, nous envisageons une modélisation du temps d'exécution d'un graphe de tâche ainsi que l'élaboration d'un simulateur.

Cet expose, compose' de deux parties, abordera la problematique
du tri parallele sur clusters afin de garantir des proprietes
d'equilibrage des charges et des garanties sur les temps d'execution. Nous
commencons par une discussion sur une famille d'algorithmes concus pour le
cas homogene puis nous interessons au cas ou les processeurs ont des
vitesses differentes. Apres une discussion sur l'equilibrage des donnees
sur chacun des processeurs, nous examinerons une techniaue de distribution
des donnees pour que les processeurs terminent en meme temps.

La deuxieme partie sera consacree au developpement d'un gestionnaire SQL
qui utilise des arbres de radicaux comme structure de base (et pas des
B-arbres). Cette deuxieme partie fait reference a notre travail dans le
cadre du projet Grid-Explorer dans lequel nous avons propose de deployer
un service SQL sur la grille. Notre travail est pour l'instant situe tres
en amont d'une integration des gestionnaires habituels (Oracle, MySql etc)
dans la grille. Nous developpons une version multithreadee des operations
de base de gestion des arbres de radicaux (union, intersection,
multiplication par une constante...). De nombreuses sources de
parallelisme seront montres ainsi que les applications potentielles de ce
gestionnaire en Data mining, notamment pour la decouverte de regles
d'association.

Enfin, les deux parties seront re-connectees en remarquant par exemple que
l'operation de jointure des bases de donnees peut s'implementer par un
tri.

Dans un contexte de programmation pour les grilles de calcul
(ensemble hétérogène de ressources reliées par un réseau,
accessible à une communauté d'utilisateurs), la programmation à base
de squelettes exploite le fait que de nombreuses applications utilisent
les mêmes schémas de programmation bien connus.
Cette approche de haut niveau permet ainsi de structurer aisément
les programmes parallèles en fournissant à l'utilisateur une librairie
de squelettes (routines génériques) prédéfinis.

Dans le projet Enhance, nous proposons de modéliser ces squelettes
à l'aide d'algèbres de processus. En introduisant dans ces modèles
les aspects d'incertitude propres à la programmation pour les grilles,
nous pensons pouvoir obtenir des résultats permettant de prendre
de meilleures décisions d'ordonnancement sur la grille que les approches
moins sophistiquées. De plus, les techniques développées sur les grilles
permettent d'obtenir les performances des ressources utilisées de façon
dynamique, ce qui permet un réordonnancement dynamique de l'application.

Nous illustrons ces idées sur l'exemple du squelette "Pipeline".
Nous présentons notamment un outil qui permet de générer automatiquement
un ensemble de modèles de performances pour le pipeline, puis qui
résout automatiquement tous ces modèles dans le but de fournir
à l'application des résultats significatifs pour améliorer ses performances.
Des résultats numériques illustrent l'efficacité d'une telle approche.

In this talk, the Taylor series expansions of stationary characteristics
of general-state-space Markov chains is presented.
The elements of the series are explicitely calculated and a lower bound
for the radius of convergence is established.
Applications are made to queueing systems.

Des logiciels complexes, assembles a partir de nombreux composants
preexistants, sont aujourd'hui utilises pour des emplois de plus en plus
critiques (telecommunication, ferroviaire, automobile...). Les risques
encourus, aussi bien humains qu'economiques, exigent de pouvoir mettre
en place dans ces systemes des mecanismes de tolerance aux fautes
flexibles et adaptables independamment des composants utilises. Mais la
complexification des logiciels pose probleme, car les approches
developpees jadis pour assurer la surete de fonctionnement de petits
systemes ne leur sont plus applicables.

Connues depuis longtemps, les architectures reflexives, en autorisant le
decouplage des aspects fonctionnels et non-fonctionnels d'un systeme,
visent a resoudre ce probleme. Jusqu'ici cependant, les approches
proposees s'etaient limitees a des prototypes simples, souvent realises
ex-nihilo pour experimentation. Or la tolerance aux fautes est une
propriete globale des systemes consideres, qui requiert la prise en
compte de tous les niveaux d'abstraction rencontres.

Dans notre expose, nous proposerons une extension du paradigme reflexif,
la reflexivite multi-niveaux, dont le but est d'integrer les
considerations algorithmiques de la tolerance aux fautes (validite,
observation, controle) aux contraintes architecturales rencontrees dans
les systemes complexes (abstraction, transparence, inter-operabilite).

Pour illustrer notre approche, nous presenterons le travail effectue sur
un premier prototype, qui aborde la replication de serveurs CORBA a
brins d'execution multiples ("multithreaded") sur une plate-forme
constituee de GNU/Linux et de l'ORB CORBA commercial ORBacus. Enfin,
nous terminerons par une mise en perspective de nos travaux dans le
contexte plus global de l'integration logicielle.

Pour aller plus loin :

Publications : http://www.laas.fr/~ftaiani/4-publications/
Logiciel : http://www.laas.fr/~ftaiani/7-software/
These : http://www.laas.fr/~ftaiani/3-manuscript/

L'emergence des environnements de type grille qui se caracterisent par un nombre
important de ressources qui peuvent varier dans le temps et l'espace posent de
nouveaux defis aux applications paralleles et/ou distribuees. Pour executer des
applications sur de tels types d'environnements, il est necessaire de disposer d'une infrastructure d'administration adaptee. Une telle infrastructure devrait fournir des mecanismes de bas niveau pour la decouverte et l'organisation de ressources, ainsi que des outils de haut niveau pour le deploiement et le controle a l'execution des applications.

Dans cette presentation, apres une introduction generale aux problemes d'administration, je parlerai de la maniere dont ces problemes sont abordes dans mes travaux de recherche. Je presenterai mon travail de these sur la gestion configurable de la duplication et de la coherence, ainsi que mon travail post doctoral qui porte sur l'observation de systemes a base d'evenements. Je terminerai par une reflexion sur l'administration et les pistes de recherche interessantes dans le cadre du laboratoire ID.

La reactivite aux evenements d'entrees/sorties est un facteur de
performance crucial pour les systemes multithreades distribues modernes.
Apres avoir expose les nombreuses contraintes liees a ce probleme, je
decrirai une nouvelle interface de gestion des evenements d'E/S dont
l'objectif est de fournir des mecanismes generiques permettant aux
environnements d'apprehender la detection de ces evenements de maniere
uniforme. Cette approche est fondee sur un support specifique de
l'ordonnanceur de threads, ce dernier pouvant etre vu comme un
serveur de detection d'evenements du point de vue des environnements
clients. Pour ameliorer encore la reactivite, un support systeme
supplementaire devient necessaire : les LinuxActivations. Je presenterai
d'abord le modele original (Scheduler Activations) propose par Anderson
et al., puis je detaillerai les modifications et ameliorations que nous
avons apportees a ce modele. Nous obtenons ainsi un environnement
multithreade donnant a l'application un controle total sur le niveau de
reactivite souhaite pour l'ensemble de ses E/S.

Je présenterai dans cet exposé mon projet de
programme de recherche sur le thème du placement et de
l'ordonnancement de tâches en milieu hétérogène.
Considérant que la méthodologie utilisée pour
spécifier une application est aussi importante que
l'outil de placement/ordonnancement intégré au middleware,
je propose d'en utiliser une fondée sur des motifs
parallèles. Elle devrait permettre de guider
utilisateur et outil en fournissant des éléments sur la
dépendance des tâches entre elles et avec les
données. J'aborderai alors l'intégration des approches
de programmation distribuée par passage de messages
et par appel de procédure distante. Enfin, dans une
dernière partie et dans le cadre des apports en terme
de facilité de programmation des architectures
distribuées, je donnerai quelques éléments pour une
étude systématique des environnements de développement,
en situation réelle, sur les aspects ergonomiques
et d'efficacité de travail.

Informations et contact
Web : www-sop.inria.fr/oasis/personnel/Remi.Coudarcher
E-mail : Remi.Coudarcher@sophia.inria.fr

Sur une plate-forme hétérogène, la minimisation du makespan de
l'ordonnancement d'un ensemble de tâches identiques et indépendantes est un
problème dont la complexité est intimement liée à l'architecture de la
plate-forme (étoile, chaîne, pieuvre, arbre). Après avoir rapidement
présenté quelques résultats récents à ce sujet, nous montrons que le
problème de la maximisation du débit en régime permanent d'une telle
plate-forme est en revanche polynomial et ce, quelque soit l'architecture de
la plate-forme. Nous expliquons ensuite comment en déduire un ordonnancement
asymptotiquement optimal quand le nombre de tâches à traiter devient grand.
Enfin, nous expliquons brièvement comment ce résultat peut s'interprèter
dans le cas d'une plate-forme arborescente et comment en déduire une
politique de répartition de charge distribuée et stabilisante.

La gestion des données est, depuis fort longtemps, une composante clé au sein
d'un système informatique. Dépendants de l architecture sous-jacente, les
systèmes de fichiers n ont cessé de s'adapter dans le but de proposer des
solutions permettant d exploiter le maximun des capacités des plate-formes
sur lesquel ils sont déployés (agrégation des débits, puissance d'analyse,
ressources importantes de stockage) tout en tenant compte des diverses
contraintes (hétérogénéité, tolérance aux pannes, passage à l'échelle).

Parallèlement aux considérations matérielles énoncées ci-dessus, le
développement croissant d applications scientifiques distribuées a modifié la
conception des systèmes de fichiers modernes et a imposé la prise en compte
de nouveaux paramètres (accès concurrent à grains fins, multiplicité des
accès non contigus . . .). Les méthodes courantes d'accès (open, read, write,
close, . . .) fournies par les différents systèmes de stockage sont souvent
mal adaptées à la programmation parallèle. Elles ne permettent pas, par
exemple, d accéder de manière optimale à des informations diffuses au sein
d'une même ressource. L'utilisation de librairies, qui viennent compléter
l'API Unix standard afin d améliorer les performances, s avère être la
solution mise en oeuvre dans la plus part des cas.

En 1997, le consortium MPI a définit une nouvelle interface dans le but de
définir les divers prototypes d'entrées/sorties au sein des applications
parallèles. C est sur ce standard, communément appelé MPI I/O, que nous nous
attarderons. Nous verrons les problèmes inhérents à un tel modèle et la
difficulté de mettre en place une implémentation portable et performante et
ceci même si plusieurs optimisations apparaissent peu à peu dans les nouveaux
systèmes de fichiers.

Mots clés :

Cluster, système de fichiers, Entrées/Sorties parallèles, Parallel I/O, MPI
I/O, High Performance Computing.

Dans ce séminaire je présenterai un environnement de simulation
du comportement de ressources distribuées gérées par des algorithmes
Peer-to-Peer. La plupart des environnements P2P sont évalués par
simulation logique. La bibliographie a mis à jour l'existence d'une part
de simulateurs hyper spécifiques à quelques algorithmes (Freenet, Chord)
qui arrivent à simuler des centaines de milliers de noeuds, d'autre part
des simulateurs plutôt orientés "grille" dont la structure semble
restreindre la capacité de simulation à quelques dizaines de milliers de
noeuds. Nous avons proposé au CPAD un simulateur en Java, GeSSi (Generic
Scalable Simulator), qui prétend combiner généricité et possibilité de
simuler des centaines de milliers de noeuds. Une grammaire simple permet
à l'utilisateur de spécifier les événements survenant pendant la
simulation. L'algorithme de gestion distribuée utilisé par ICluster
([Richard2003]) a permis de valider le fonctionnement du simulateur et
nous présenterons des résultats de simulation portant sur plusieurs
centaines de milliers de noeuds.

Cette thèse combine le calcul haute performance à la réalité virtuelle
par son apport de méthodes de calcul parallèle pour l'animation
d'objets 3D en synthèse d'image. Son application vise plus
particulièrement le domaine de la simulation de textiles par modèles
physiques. Les lois fondamentales de la dynamique ont en effet été
employées pour modéliser le mouvement de plusieurs objets dans un
souci de réalisme. Les modèles employés étant numériquement complexes,
le calcul d'une image en séquentiel varie de la seconde à plusieurs
minutes suivant la complexité du modèle. L'objectif a été de diminuer
ce temps par la parallélisation des algorithmes et l'exécution sur
grappes de machines multiprocesseurs afin d'obtenir des animations en
temps réel. Différentes méthodes d'intégration des équations du
mouvement ont été implantées en parallèle. Dans le cas de l'emploi de
méthodes implicites, les opérations coûteuses en calcul proviennent de
la résolution de systèmes linéaires par la méthode du Gradient
Conjugué impliquant des opérations d'algèbre linéaire de type
multiplications de matrices creuses et de vecteurs.

Ce projet de thèse a contribué à l'obtention de nouvelles structures
algorithmiques parallèles efficaces avec l'obtention d'algorithmes
asynchrones. Il a également permis de valider l'approche de
l'environnement de programmation parallèle Athapascan (projet INRIA-APACHE)
avec la mise au point d'applications avec des contraintes temps réel
mou ainsi que le contrôle dynamique de son ordonnanceur. Durant ce
projet de thèse, un couplage entre la simulation parallèle de textiles
et son affichage utilisant l'environnement de visualisation
multi-écrans Net Juggler a également été réalisé en faisant
communiquer efficacement ces deux programmes parallèles.

Mots-clés :
Programmation parallèle, simulation de textiles, modèles physiques,
couplage de programmes parallèles.

Directeur de thèse : Brigitte Plateau (ID-IMAG)

Co-encadrants : Jean-Marc Vincent (ID-IMAG) et François Faure (GRAVIR-IMAG)

Site : http://www-id.imag.fr/Laboratoire/Membres/Zara_Florence/

Expériences autour d'un gestionnaire pour grappe et évolution de la notion d'environnement d'exécution

Cette présentation sera composée de deux parties.

La première présentera les expériences autour d'une nouvelle approche de conception d'un gestionnaire de travaux pour grappes. Ce gestionnaire (OAR) repose sur une conception originale qui réduit la complexité logicielle, permet une extension aisée ainsi qu'une bonne réponse au problème du passage à l'échelle. L'architecture globale repose principalement sur deux composants de haut niveau: un outil générique d'administration d'application (Taktuk) passant à l'échelle et l'utilisation d'une base de données comme seul médium d'échange d'information entre les modules internes. Nous présenterons quelques résultats d'évaluations.

La deuxième partie, résolument spéculative, est centrée sur l'évolution de la notion d'environnement d'exécution. L'objectif est de mesurer l'apport de cette notion dans l'appréhension de la complexité des systémes distribués auxquels doit faire face les architectes systèmes. Nous illustrerons son emploi à travers différents projets en cours dans le groupe (autour de Taktuk, OAR, le successeur de Ka-deploy). Pour finir, cette partie (ou cette causerie) pourra etre percue comme une tentative de réponse/écho/complément de praticien au séminaire précédent de Denis Trystram sur la complexité "algorithitme".

Le problème de reconnaissance de repliement de protéines
connu sous le nom de "protein threading problem" est considéré
dans cet article comme un modèle de réseau de flot. Dans ce modèle
nous proposons et comparons plusieurs formulations MIP (Mixed-Integer
Programming).
Leurs propriétés permettent de découper le problème en sous-problèmes
qui peuvent être
efficacement résolus par une méthode d'élagage "branch-and-cut".
Une version parallèle de cette méthode est aussi proposée.
L'efficacité de notre approche est illustrée par des
expériences numériques sur des instances de taille très importante.

Mots clés: problème de reconnaissance de repliement de protéines,
programmation en nombres entiers, réseau de flot, CPLEX

Les infrastructures logicielles reposant sur des réseaux sans fil
en mode Ad-Hoc nécessitent des outils permettant de gérer les problèmes
de dynamicité (connexions/déconnexions volontaires ou non des entités)
et d'assurer une qualité de service résistant à ces aléas. Afin
d'assurer la continuité de service, et en particulier pour prendre des
décisions (consensus), des mécanismes de détecteurs de défaillances ont
été implantés. Ce séminaire présentera les premiers résultats concernant
leur modélisation et leur évaluation sur une plateforme composée
d'assistants personnels et de PC portables.

In this seminar, I will use recursive tilings to describe structured communication patterns such
as broadcasting. I will start with results for a torus and I will then
present several generalizations with applications to satellite networks. I will conclude with some work
in progress. The research was done over a period of more than ten years starting in
1991. The seminar is very visual; even the proofs are done almost entirely with figures.

New architectural solutions for systems based on shared memory processor clusters are presented. In the proposed architecture, processors can be dynamically switched betweenbus-based SMP clusters at program run-time. A switched processor can bring data in its cache that can be read on the fly by processors in the cluster when written into the clustermemory. This new inter-cluster data transfer paradigm is called communication on the fly. For execution in the proposed architecture, programs are structured accordingly tomacro-data flow graphs in which task composition and communication are so defined, as to eliminate re-loading of data caches during task execution. It constitutes a cache-controlled macro data flow execution model. An extended macro-data flow graph representation is presented in the paper. It enables modeling of program executioncontrol in the system including parallel task execution, data cache functioning, data bus arbiters, switching processors between clusters and multiple parallel reads of data on thefly. The proposed graph representation enables simulated symbolic execution of program graphs, based on decomposition of parallel processes onto dynamic SMP clusters and oncommunication on the fly. Simulation results for very fine-grained parallel numerical examples will be presented .

Aujourd'hui, les grappes de calculateurs sont une alternative économique
aux machines parallèle, dont une des approches pour les utiliser est
l'approche de système à image unique, comme c'est le cas pour le système
d'exploitation Kerrighed (anciennement appelé Gobelins). Dans le syst?me
Kerrighed, les ressources sont fédérées pour donner la vision d'une
machine multi-processeur à mémoire physiquement partagée. La fédération
de la ressource processeur est particuliérement importante afin de
garantir une exécution efficace des applications, en utilisant un
ordonnanceur global. Pour cela, le systéme Kerrighed offre une
architecture modulaire d'ordonnanceur global pour grappe qui permet de
fournir un ordonnanceur adaptable au type d'application en cours
d'exécution, dynamiquement configurable et utilisant efficacement les
mécanismes de fédération des ressources du système Kerrighed.

In a recent two-layer approach to survivability of networked
computing systems migratory autonomous agents have been used as a
reactionary mechanism augmenting a low-level attack recognition
scheme. This paper investigates the theoretical implications of
determining the agent traversal route as specified by such
survivability architecture. It introduces a five-step model that
transforms survivability applications into a parameterized graph
model that, together with model abstraction and representations, can
be the basis for solutions derived from scheduling algorithms. The
derivation of agent traversal paths will be transformed into the
problem of scheduling jobs with linear precedence order in machine
scheduling utilizing weak and strong modes of scheduling.

Dans les systèmes de grande taille, les fautes ont lieu de manière
quasi-continue. Il devient alors vitale de pouvoir détecter efficacement
les défaillances . Or, les environnements à large échelle induisent de
nouveaux problèmes pour détecter les fautes. Il y a deux difficultés
majeures liées à ce type d'environnement : (1) les bornes sur les délais
de transmissions ne sont pas connues (réseaux asynchrones) (2) le nombre
de sites à surveiller est très important.
Dans le modèle asynchrone, il n'est pas possible de détecter les
défaillances avec un délai de garde car il est impossible de distinguer
le cas où le processus distant est fautif de celui où la réponse est
encore en transit. Pour apporter tout de même une solution
satisfaisante, le concept détecteur de faute non fiable a été introduit
pour T.D. Chandra et S. Toueg. Un détecteur de faute est chargé
d'informer les processus corrects des fautes des autres processus
(éventuellement en commettant temporairement des erreurs ou des fausses
détections).
A partir des travaux de W. Chen, S. Toueg et M. Aguilera, nous avons
conçu, implémenté et évalué un nouveau détecteur de faute shiérarchique.
L'originalité de ce détecteur est sa capacité à adapter dynamiquement sa
qualité de détection en fonction de la charge du réseau. Sa
structucration hiérarchique permet de prendre en compte la topologie du
réseau. Nous présenterons une évaluation performances de ce détecteur.
Nous présenterons également des services utilisant notre détecteur,
notamment le service de nommage utilisé dans la plate-forme multi-agent
Darx.

Nous présenterons les mécanismes permettant de déployer une architecture
de grille sur un intranet tout en préservant les habitudes des usagers.
Par usagers, on entend les utilisateurs de moyens de calcul, les
utilisateurs de moyens bureautique et les administrateurs systèmes et
réseau. L'approche suivie est ici de déployer une environnement de
calcul à distance lorque les machines sont arrêtées électriquement et
sans utiliser leurs ressources disques. Quelques questions seront
soulevées pour faire le lien entre cette approche et les besoins de
sécurité et de performances en général associés au "grid computing".

Nous présenterons ensuite le projet de création d'entreprise associé à
cette idée (marché visé, timing et conditions de création).

Avec la généralisation de l'Internet, il est désormais possible pour les
utilisateurs de calcul numérique d'accéder aux machines les plus puissantes
disponibles de par le monde, et ce depuis leur station de travail. A grande
échelle, on parle alors de grid computing.

Une des approches possibles consiste à utiliser des serveurs de calcul, i.e.,
des machines capables de résoudre des problèmes soumis par des clients. L'un
des points cruciaux de cette approche concerne la capacité à estimer le temps
d'exécution d'une routine sur une machine donnée et les coûtsde transfert de
données entre les machines de la plate-forme d'exécution. Au cours de cet
exposé, je présenterai la bibliothèque FAST (Fast Agent System Timer) et
notamment l'extension de cette bibliothèque pour la gestion de routines
parallèles.

D'un point de vue plus algorithmique, la présence de bibliohtèques numériques
de plus en plus perfomantes sur des machines parallèles de plus en plus
puissantes, et dont le nombre de processseurs ne cesse de croître, permet
d'envisager l'exécution concurrente de calculs parallèles. Cela peut en effet
permettre d'exhiber plus de parallélisme qu'une utilisation simple du
parallélisme de tâches ou du parallélisme de données. Lorsque ces deux types de
parallélisme sont exploités de manièresimultanée, on parle alors de
parallélisme mixte. Je présenterai une validation de l'utilisation de ce
paradigme dans le cadre du grid computing, effectuée sur les algorithmes de
produits de matrices de Strassen et Winograd, ainsi qu'un algorithme
d'ordonnancement original utilisant le parallélisme mixte.

Je parlerai enfin des travaux que j'effectue actuellement au sein du
laboratoire GRAIL et donnerai quelques idées sur les thématiques de recherche
que je souhaite aborder lors de ces prochaines années.

Cet exposé en deux parties présentera deux recherches différentes
qui sont prévues pour s'intégrer dans la même plate-forme finale.
La première partie décrira la conception et l'implantation de
plusieurs modèles et outils de programmation parallèle
"d'orientation cellulaire", destinés à faciliter le développement
de systèmes de calculs distribués comme certains systèmes
multi-agents, ou neuromimétiques, ainsi que certains calculs
scientifiques à base d'équations locales. L'objectif principal est
de donner plus de confort de programmation pour de tels systèmes,
de diminuer leurs temps de développement, et de compenser les
ralentissements vis-à-vis de codes classiques en C ou C++ par
l'utilisation de plusieurs processeurs. Ces outils de développement
s'adressent essentiellement à des chercheurs en systèmes de
calculs distribués qui modifient fréquemment leurs modèles et
désirent les implanter et les tester rapidement. Une fois un
modèle au point, une implantation optimisée avec d'autres outils
de programmation est souhaitable. L'application principale de ces
outils est aujourd'hui le développement et la mise au point de
systèmes neuromimétiques d'inspiration biologique (systèmes
corticaux), destinés notamment à des mécanismes de vision pour des
robots.

La deuxième partie de l'exposé portera sur des expérimentations de
contrôle de robots à distance, à travers différents réseaux de
communication (Fast Ethernet, P2P-ATM inter-cités, et Internet),
et aux démarches algorithmiques permettant de limiter les surcoûts
de communications. Cette recherche récente se poursuit par une
distribution des différents modules d'un système de contrôle de
robot à travers une Grille de ressources informatiques. Les
objectifs étant de pouvoir utiliser un ensemble de petites
machines à la place d'une seule grosse machine performante pour
contrôler un process (comme un robot), d'accéder à un process et
de le contrôler à distance même s'il nécessite des calculs
importants. Les problèmes aborder sont ceux de l'insertion dans
une grille de ressources d'applications "interactives" traitant
des flux constants de données (provenant des capteurs du process),
avec des contraintes de temps.

A moyen terme, il est prévu de distribuer sur une grille de PCs un
contrôle de robot comportant de nombreux modules, dont des
systèmes neuromimétiques développés avec les outils décrit en
première partie.

I-Cluster est une initiative des HP Laboratories Grenoble associés au laboratoire ID-IMAG de l'INRIA Rhône-Alpes. Le but de ce programme de recherche est de développer un environnement d'exploitation des ressources de calcul inexploitées (jachères de calcul) sur un intranet.

Le caractère extrêmement dynamique des ressources disponibles pose le problème de tolérance aux fautes
dues à la disparition/apparition de machines. La migration des processus d'un noeud en panne vers un autre tente de trouver une solution à ces problèmes. Toutefois le contexte particulier du nuage I-cluster ne permet pas d'utiliser les solutions classiques comme Condor ou Mosix (disparition complète d'un noeud, impossibilité de prévoir cette disparition...).

Ce travail de thèse a pour but de fournir une solution pour pallier aux disparitons intempestives de ressources de calcul dans un intranet. Nous présentons dans ce séminaire les mécanisme de gestion de processus sous Linux, et comment nous les exploitons pour construire un module de sauvegarde/reprise du contexte d'un processus au niveau du noyau Linux en étant le moins intrusif possible au niveau de la configuration,c'est-à-dire ne pas nécessiter de modification du noyau sous-jacent, ni de recompilation/édition du programme à surveiller.

L'idée de programmer un séminaire sur le thème de la complexité
est venue naturellement après de nombreuses discussions à la Kfette
où il apparaissait que beaucoup d'entre nous avaient de l'intéret pour
le sujet mais pas toujours la même vision des choses (voire pas de
vision du tout...).
Aussi, j'essayerais de faire le tour des principales définitions et notions
élémentaires sur la complexité (classes de complexité P et NP, techniques
de réduction, problèmes NP-complets et NP-difficiles, structure de NP, etc..).
Un des objectifs est d'établir un pont entre les différentes visions
existantes.

Cette présentation sera dédiée à l'implantation
actuelle et aux récentes évolutions d'une fameuse (et non pas fumeuse)
bibliothèque
de programmation parallèle. Dans une première partie
le mécanisme de pile cactus permettant de dégénérer séquentiellement
tout en gérant efficacement le flot de donnée sera présentée.
Une seconde partie sera consacrée à l'ordonnancement dans notre
bibliothèque.
En particulier, l'utilisation de bibliothèques de partitionnement de graphes
comme Scotch ou Metis ainsi que l'ordonnancement
de programmes itératifs de type simulation de tombé de tissus ou
dynamique moléculaire y seront présentés.

Cette présentation très générale vise à introduire les réseaux
d'automates stochastiques, et à montrer l'utilité des techniques
associées pour l'évaluation de performances.
Une première partie fera un état de l'art des techniques et outils
utilisés pour l'évaluation des performances des systèmes Markoviens.
Nous introduirons dans ce contexte notre approche : les réseaux
d'automates stochastiques (SANs). Nous exposerons ensuite rapidement
les méthodes d'analyse des SANs, basées sur une algèbre tensorielle
généralisée. Enfin, pour illustrer le pouvoir de modélisation des SANs,
un exemple de modélisation d'un réseau de files d'attente ouvert
avec blocages, pertes et priorités sera exposé.

RAPPEL de la note de Joelle :

Je complète l'annonce du séminaire en précisant que l'objectif est double:
- Présentation de Zope et d'outils collaboratifs
- Lancer au sein du labo la discussion pour préciser quelles
fonctionnalités nous allons développer, qui nous font défaut ou sont mal
rendues aujourd'hui.
Il s'agit d'homogénéiser l'accès aux différents serveurs et services
existants, de le rendre indépendant du lieu de consultation. Il est
nécessaire de proposer des services conviviaux permettant d'accélérer
les tâches quotidiennes qui supposent des échanges de documents
(échanges entre personnes, échange de formats), l'établissement de
plannings, de réservations, la gestion de petites bases de données. On
devrait ainsi obtenir un système d'information plus dynamique,
présentant par un site web public une image plus proche de la vie du
laboratoire.

Le réseau Myrinet est une technologie fournissant carte d'interface et
commutateur réseau dédié aux "grappes".
J'exposerai la technologie reseau Myrinet du point de vue materiel et
logiciel avec une rapide comparaison des differentes implementation du
systeme de communication: BIP, GM, Score. J'exposerai la roadmap de Myricom
pour les evolutions futures, ainsi que celle de technologies concurrentes
(infiniband, quadrics).

I-Cluster est une initiative des HP Laboratories Grenoble associés au
laboratoire ID-IMAG de l'INRIA Rhône-Alpes. Le but de ce programme de
recherche est de développer un environnement d'exploitation des ressources
de calcul inexploitées (jachères de calcul) sur un Intranet. Plus
précisément, I-Cluster permet d'analyser en temps réel et de manière
automatique la disponibilité et la configuration des machines d'un Intranet,
ainsi que leur charge de travail. Lors de l'instanciation d'une fonction de
supercalcul par un utilisateur, I-Cluster va déterminer la configuration de
machines (cluster) la plus appropriée a l'exécution de cette fonction, puis
va allouer les machines puis y démarrer l'exécution répartie. Ce séminaire
présentera le modèle "I-Cluster Cloud" permettant la gestion distribuée des
ressources et leur diffusion dynamique au sein des machines de l'intranet.

Nous présenterons dans ce séminaire nos travaux concernant l'alignement
arborescent généralisé, c'est-à-dire la reconstruction simultannée d'une
phylogénie et d'un alignement multiple pour un jeu de séquences données.
Nous commencerons par un présentation simple de la reconstruction de
phylogénies, basées sur des caractéristiques des espèces étudiées.
Nous verrons ensuite comment reconstruire une phylogénie à partir d'un
jeu de séquences moléculaires.

Dans la deuxième partie de l'exposé nous présenterons nos travaux
concernant l'alignement arborescent généralisé. Nous présenterons en
particulier deux heuristiques, une première destinée à la construction
de petites phylogénies, la seconde adressant de grands jeux de données.
Nous finirons en présentant quelques voies en cours d'exploration
concernant l'amélioration de l'alignement multiple.

Un algorithme de gestion de ressource efficace demande de modéliser le
comportement d'une application. Traditionnellement cela consiste a
modéliser finement et séparément les calculs et les
communications. Mais plus la modélisation est fine, plus l'évaluation
de la qualité des algorithmes est complexe. Les taches malléables sont
une façon de prendre la performance d'une application parallèle dans
sa globalité en ne retenant que le nombre de processeur qu'elle
utilise et son temps d'exécution en fonction de ce nombre de
processeur.

Du point de vue d'une grappe, l'idée principale est que, pour chaque
application parallèle, on peut changer le nombre de processeur qui
l'exécute. On peut donc choisir le "bon" nombre de processeurs afin
que l'ensemble des applications finissent au plus tôt, ou que le temps
moyen d'exécution soit le plus petit possible.

L'expose présentera quelques algorithmes utiles pour l'ordonnancement
d'applications sur grappe et grille de grappe, et en montrant quelques
résultats liés aux travaux en cours.

Je voulais garder tout le mystère du titre, mais semble-t-il certains
veulent avoir un résumé. Donc que ceux qui veulent garder la surprise
ne lisent pas la suite.

Dans le paradigme maître-esclave tout le travail a faire est à
l'origine centralisé sur un processeur maître. Ce processeur distribue
via les connexions qu'il possède ce travail découpé en tâches
élémentaires identiques aux esclaves qui travaillent pour lui. Le
réseau étant hétérogène et de topologie quelconque, certains liens
sont favorisés et certains esclaves peuvent retransmettre à d'autres
esclaves situés plus loin du maître une partie du travail reçu.

Dans une première partie j'exposerais les travaux précédents sur les
arbres de processeurs à un seul niveau, ainsi que mes travaux sur les
chaînes de processeurs, pour lesquels un algorithme polynomial est
optimal. A la jonction de ces deux travaux se trouve le problème des
pieuvres pour lequel un algorithme polynomial existe aussi.

Enfin je conclurai en montrant que le problème des graphes quelconques
de processeurs est NP-dur au sens fort.

le protocole iRBP (improved RBP)

Ce séminaire a pour objectif faire une brève introduction sur le thème
de la tolérance aux pannes en systèmes repartis, et surtout, présenter
mes travaux au sein du groupe de Tolérance aux Pannes de l'École
Polytechnique Fédérale de Lausanne (EPFL - Suisse).

La première partie de la présentation expose les problèmes pour
effectuer des calculs dans un environnement distribué (très
fréquemment hétérogène) et susceptible aux pannes. Cette problématique
est présentée sur le point de vue de la sûreté de fonctionnement.
Cette façon de voir les problèmes permet d'établir les conditions et
propriétés qui doivent être respectées, afin de garantir la fiabilité
des systèmes, même sous les modèles les plus sévères de défaillances.

Cette introduction présente aussi les principales techniques pour
fournir une tolérance aux pannes. Beaucoup d'attention sera donnée aux
techniques de réplication, qui représentent le sujet le plus étudié
pour le groupe à l'EPFL. Quelques techniques normalement utilisées et
les défis pour garantir la consistance des réplicas seront présentés.

La deuxième partie de cette présentation sera plus technique, et en
fait est le coeur du travail que j'ai développé l'année dernière à
l'EPFL. Comme base, on a pris un protocole avec ordre totale 'très'
ancien (Reliable Broadcast Protocol RBP - 1985). Les caractéristiques
de ce protocole le rendent plus efficace que d'autres protocoles avec
ordre totale, mais il ne respecte pas plusieurs propriétés de
fiabilité requises aujourd'hui (comme par exemple, la propriété 'Same
View Delivery').

Nous avons restructuré ce protocole, en conservant ses bonnes
caractéristiques (par exemple, l'utilisation d'un 'token' et de
communication non-fiable), et en remplaçant quelques sous-protocoles
par des techniques 'état de l'art'. Ces changements ont rendu le
protocole bien plus fiable, car ces nouvelles techniques ont supprimé
certaines situations qui pouvaient rendre le système inconsistant. Ce
nouveau protocole, appelé 'iRBP' (improved-RBP), a atteint ses
objectifs. Le iRBP a été aussi la première implantation connue de la
technique 'two views', qui est une solution très intéressante pour
résoudre le problème du 'time-bounded buffering', c'est-à-dire le
temps pendant lequel on doit garder un message afin de le
retransmettre, si nécessaire.

The term "the Grid" was coined in the mid 1990s to denote a proposed distributed computing infrastructure for advanced science and engineering. Less than five years later, it feels as if "the Grid" is everywhere -- grid related research and development projects are popping-up all over the globe. They come in different sizes and scopes: some are small, others are international; some focus on pure computer science problems, while others are interdisciplinary. We will present our perspective of this recent wave of Grid-driven activities and how it relates to our ongoing work in the area of High Throughput distributed computing. The talk is based on our decade-long experience with the Condor high throughput computing system. We will discuss the challenges clients of Grid resources face in harnessing the power of these resources and outline the design principals and capabilities of our client tools. Our tools are designed to meet the needs of large Master Worker applications and leverage the capabilities of the Condor-G job manager.

Dans le domaine de l'optimisation combinatoire
multicritère, une solution est evaluée en fonction de
plusieurs critères d'optimalité.
Les problèmes d'optimisation multicritère ont été
largement étudiés dans le passé, et ce particulièrement dans des
domaines tels que la recherche opérationelle, la micro-économie
et plus récemment en informatique.
Les résultats existants peuvent être regroupés en trois
catégories. Dans la première on optimise un seul critère
mais une contrainte de budget est imposée sur le second.
Dans la seconde, on cherche des résultats
optimisant simultanément les divers critères d'optimalité.
Enfin, dans la troisième on cherche à
déterminer un compromis (courbe de Pareto)
entre les divers critères.

Nous aborderons ces questions du point de vue de la théorie
d'approximation et présenterons quelques applications dans
le cas des problèmes bicritères.

L'objectif de ce séminaire est de présenter nos activités autour des systémes P2P.Nous nous intéressons actuellement au problème de l'évaluation de ces systèmes. En effet, il y a relativement peu d'études qui s'intéressent à une analyse poussée de leurs comportements et de leurs performances. Plusieurs approche sont possibles :par modèlisation, par simulation et par émulation. Nous développerons chacun de ces points.

L'apparition des nouvelles plates-formes hétérogènes nous amène à réétudier des problèmes bien connus dans le cas homogène. Dans une première partie de l'exposé, nous étudierons les problèmes d'équilibrages de charges liés à la recherche d'une bonne distribution des données. Dans un premier temps, nous nous contraindrons à ne considérer que des découpages en grille. Dans un second temps, nous supprimerons la contrainte de grille afin de chercher un partitionnement libre des données.

Enfin, dans une seconde partie, nous nous interesserons au problème de l'ordonnancement et de l'allocation d'un graphe de tâches sur un réseau hétérogène. Nous établirons quelques résultats de complexité et je présenterai une nouvelle heuristique.

De plus, le domaine du calcul haute performance distribué évolue constamment, et après avoir interconnecté des stations de travail en grappes à l'aide d'un réseau rapide, les utilisateurs franchissent de plus en plus le pas suivant, c'est-à-dire l'interconnexion de grappes en grappes de grappes (ou multi-grappes) ; ce qui amène, en contrepartie, une complexité de gestion considérablement accrue.

La bibliothèque de communication Madeleine, dont la présentation fait l'objet de ce séminaire, a pour but de proposer des réponses originales à ces diverses problématiques, avec en premier plan, le souci d'offrir au programmeur d'applications le niveau de virtualisation et d'automatisation idéal permettant à la fois un temps développement très court et un potentiel d'optimisation élevé.
Depuis maintenant près d'une décennie, les configurations en grappes de stations de travail s'imposent comme la plate-forme de référence pour le calcul distribué, pour des raisons d'ordre économique, mais surtout en raison de leur considérable potentiel de puissance. Pourtant, la réalisation de ce potentiel reste une opération difficile, et dans ce contexte, la qualité de la gestion des communications au sein d'un exécutif destiné au calcul haute performance distribué est sans aucun doute un élément décisif au niveau du résultat final. Or, la conception d'un support de communication pour le calcul distribué implique l'apport de solutions à de nombreuses problématiques non triviales, à des niveaux très divers.

De plus, le domaine du calcul haute performance distribué évolue constamment, et après avoir interconnecté des stations de travail en grappes à l'aide d'un réseau rapide, les utilisateurs franchissent de plus en plus le pas suivant, c'est-à-dire l'interconnexion de grappes en grappes de grappes (ou multi-grappes) ; ce qui amène, en contrepartie, une complexité de gestion considérablement accrue.

La bibliothèque de communication Madeleine, dont la présentation fait l'objet de ce séminaire, a pour but de proposer des réponses originales à ces diverses problématiques, avec en premier plan, le souci d'offrir au programmeur d'applications le niveau de virtualisation et d'automatisation idéal permettant à la fois un temps développement très court et un potentiel d'optimisation élevé.

Dans leur présentation traditionnelle, les systèmes à mémoire distribuée virtuellement partagée (MVP, en anglais DSM) permettent à des processus de partager un espace d'adressage commun selon un modèle de cohérence fixé: cohérence séquentielle, relâchée, etc. Dans la plupart des travaux dans ce domaine, il est sous-entendu que la MVP et l'architecture sous-jacente sont données. Le programmeur doit alors adapter son application à ce cadre fixe, afin d'obtenir une exécution efficace.

Dans une première partie de cet exposé, nous présenterons une plate-forme générique d'implémentation et d'expérimentation appelée DSM-PM2, qui permet de développer et d'optimiser à la fois les applications distribuées et le(s) protocole(s) de cohérence de la MVP sous-jacente. DSM-PM2 est une plate-forme logicielle, portable sur de nombreuses architectures de grappes hautes performances. Cette plate-forme fournit les briques de base nécessaires pour implémenter et évaluer une large classe de protocoles de cohérence multithreads dans un cadre unifié. Trois modèles de cohérence sont actuellement supportés: la cohérence séquentielle, la cohérence relâchée et la cohérence Java. La plate-forme a été validée par son utilisation en tant que cible d'un système de compilation Java pour des grappes de PC, appelé Hyperion. Des études comparatives de performance ont été effectuées sur 5 applications Java multithreads en utilisant diverses variantes du protocole de cohérence, sur plusieurs architectures différentes.

Dans la deuxième partie de l'exposé, nous montrons pourquoi le passage à l'échelle des systèmes à mémoire virtuellement partagée, jusqu'ici conçus pour des grappes de petite taille, exige une remise en question des hypothèses traditionneles lorsqu'on se propose de prendre en compte des architectures de plusieurs milliers de noeuds répartis. Nous présentons une proposition d'architecture de service de partage de mémoire à grande échelle basée sur des techniques peer-to-peer.

Pour plus d'informations: - Site DSM-PM2: http://www.irisa.fr/paris/pages-perso/Gabriel-Antoniu/dsm-pm2.htm - Page personnelle de Gabriel Antoniu: http://www.irisa.fr/paris/pages-perso/Gabriel-Antoniu/

L'évolution constante des processeurs vers des architectures proposant des capacités superscalaires, de parallélisme au niveau
des instructions, de prédiction, de spéculation et la multiplication des niveaux de hiérarchie mémoire donnent de plus en plus d'importance au
travail du compilateur. Ceci se concrétise par la résolution de problèmes d'ordonnancement des instructions visant à faire apparaître un maximum de parallélisme et/ou à optimiser les accès à la mémoire. Je vous présenterai un tour d'horizon d'une partie de ces problèmes d'ordonancement faisant intervenir une transformation particulière : le décalage d'instructions. Les résultats que je présenterai abordent aussi bien les questions de complexité que de resolution pratique de ces problèmes.

La disponibilité simultanée de nombreuses ressources de calcul/stockage performantes et d'un réseau de communication mondial suffisamment efficace et stable pour véhiculer rapidement des grands volumes d'information à donner naissance aux concepts du Calcul Global et des systèmes Pair à Pair. Les systèmes SETI@home et Napster ont popularisé et crédibilisé ces concepts de façon séparée. Dans cet exposé, nous examinons la problématique de la fusion de du calcul global et des systèmes Pair à Pair à travers la présentation d'une classification des systèmes Pair à Pair, d'une plate-forme d'expérimentation (XtremWeb), d'applications en physique et bioinformatique et de problèmes scientifiques dures. Nous détaillons notamment les problèmes de l'architecture des systèmes de mise en relation et de transport, la sécurité des participants par confinement d'exécution (sandboxing) et l'exécution d'applications parallèles dans un système ou les ressources sont volatiles (MPICH-V). Nous terminons sur la nécessité d' élaborer et de mettre en oeuvre un ensemble d'outils scientifiques théoriques et expérimentaux pour conduire les nombreuses recherches que requière ce domaine nouveau.

Une introduction à ce séminaire peut être trouvée à l'adresse suivante : http://www.lri.fr/~fci/LI41.pdf

Cet expose presente un systeme de fichiers distribues pour clusters utilisant le protocole NFS.

Plutot que de concevoir "from scratch" un systeme de fichiers distribues (e.g PVFS), l'idee est de s'integrer dans l'existant: dans beaucoup d'endroits NFS est encore utilise, malgre ses defauts (coherence, gestion de la saturation)

Le serveur est modifie pour devenir un serveur de meta-donnees; les E/S lourdes (lecture, ecriture) sont assures par des processus situes sur d'autres machines

Nous presenterons les modifications apportees au modele classique du serveur NFS afin de pouvoir repartir la charge des E/S sur plusieurs machines (tout en conservant le protocole NFS pour le client).

Cette approche offre plusieurs interets: * utilisation de l'espace disque inutilise des machines * performances accrues * simplicite d'installation/d'administration