Calcul distribué : une introductioncdsweb.u-strasbg.fr/meeting3/Calcul_distribue.pdf · ¾On n’a pas toujours la bibliothèque installée ¾Des bibliothèques ou des environnements

Calcul distribué : une introduction

Emmanuel JeannotLORIA – Université H. Poincaré

[email protected]

6 mai 2003 Emmanuel Jeannot - journée calcul et données distribués 2/77

Le concept de Grille

Distribution transparente de l’énergie électrique


Le concept de grille informatique (GRID)

Distribution transparente de la puissance de calcul et de stockage à travers le réseau


Plan

• Introduction• Architecture• Différentes approches des grilles de

calcul• Quelques défis scientifiques• Exemple de travaux en cours• Conclusion


Introduction• La suite du calcul parallèle: distribué et hétérogène• Grille de calcul : grande collection de ressources

distribuées (calculateurs, machines de stockage, instruments, réseaux)

• Utiliser la puissance des réseaux et des machines qui y sont connectées.

• Cibles: de plus en plus d’applications dans divers domaines.

• Objectifs :– Transparence– Efficacité– Simplicité (d’utilisation, de programmation,…)– Sécurité– Extensibilité (passage à l’échelle)– Pluridisciplinarité– …


Introduction, suiteUne des idées (long terme): louer la puissance de calcul et les capacités

mémoire sur Internet.

Très grand potentiel :Besoin de « Problem Solving Environment » (PSEs).On n’a pas toujours les ressources disponiblesLes applications ont toujours plus besoin de puissance et de mémoire.On n’a pas toujours la bibliothèque installéeDes bibliothèques ou des environnements ont besoin de rester sur place.Énormément de ressources disponibles.

➨ Utilisation de serveurs de calcul par l’intermédiaire d’une interface simple.

Difficile pour un non-spécialiste.Peu de transparence.Problèmes de sécurité et de gestion des comptes peu abordés…


Introduction, finProblèmes à résoudre:

– algorithmique ((re)distribution des données, équilibrage de charge, ordonnancement,...)– système (administration, tolérance aux pannes, sécurité, localisation de ressources, …)– logiciel (interopérabilité, ré-utilisation de code,...)– standardisation


Pourquoi maintenant?• Accroissement des besoins• On dispose d’ordinateurs très puissants• Internet et les réseaux fournissent une

connectivité « universelle »• Nouveaux modes de travail : collaboration,

calcul (simulation)• Croissance de la vitesse des réseaux

(« network exponentials ») : changement de vision (géométrie, géographie)


Network Exponentials• Performance des réseaux contre ordinateurs

– Vitesse des ordinateurs double tous les 18 mois– Vitesse des réseaux double tous les 9 mois– Différence = 1 ordre de grandeur tous les 5 ans

• 1986 à 2000– Ordinateurs : x 500– Réseaux : x 340 000

• 2001 à 2010– Ordinateurs : x 60– Réseaux : x 4 000

Moore’s Law vs. storage improvements vs. optical improvements. Graph from Scientific American (Jan-2001) by Cleo Vilett, source Vined Khoslan, Kleiner, Caufield and Perkins.


Plan• Introduction• Architecture

– Applications– Middlewares– Services-protocoles– Infrastructure– Problématique de l’intégration– Problématique de l’interopérabilité

• Différentes approches des grilles de calcul• Quelques défis scientifiques• Exemple de travaux en cours• Conclusion


Architecture logiciel

Infrastructure

Services-protocoles

Applications

Inté

grat

ion Middlewares

Interopérabilité


Applications

• Calcul scientifique• Physique des particules (LHC)• Bio-informatique• Chimie quantique• Imagerie médicale• Simulation multi-physique


Middlewares (intergiciels)

• Interface entre les applications et les services (ou les ressources)

• Permet de :– Programmer la grille – Virtualiser l’infrastructure – Exécuter des applications sur la grille

• Beaucoup de travaux dans ce domaine


Services-protocoles1. Déjà existants dans les réseaux standards :

– XML– DNS– TCP-IP– …

2. Mis en œuvre pour la grille– Service de prévision (NWS)– Service de stockage (IBP) – Protocole de transfert (gridFTP)– OGSA (Open Grid Services Architecture)– …


Infrastructure• Réseaux

– Wide Area Network (WAN) • Internet• backbone Gbit/s (VTHD, GEANT, TERAGRID)

– Local Area Network (LAN)– System Area Network (SAN)

• Machines de calcul– PCs– Grappes– Ordinateurs parallèles

• Instruments : fournisseurs de données– Accélérateur de particules– (radio)-télescope– Séquenceur (génome)

• Stockage – Centre de stockage– Service de stockage dans le réseau


Infrastructures en FranceR eim s

C aenRouen

Ren nes N ancy

S tras bourg

Po it ie rs

Bo rd eaux

L yon

G renob le

Tou lou se .

M on tpellie r

M arse il le

N antes

B esan çon

C lerm ont -F er rand

Lim oges

P ar is

D ijon

L il le

S oph ia

C om piè gne

O rlé ans

C or te

2 .4 Gb i t/s622 M bi t/s

155 M b i t/s

34 M bi t/s

8 M b it/s

N R D

N IO

N O C

RENATER• Ressources de calcul

– Centres de calcul nationaux (terascale)

• IDRIS, CINES, méso-centres, ressource des laboratoires, …

• Réseaux– Réseau opérationnel

RENATER– Réseau expérimental VTHD

(projet RNRT)VTHD


Problématique de l’intégration

Infrastructure

Services-protocoles

Middlewares

Applications Faire communiquer les couches entre elles :

• Spécifier les rôles à chaque niveau • Définir des APIs/interfaces standardisés (ex : gridRPC)• Optimiser le transfert des données•…

Inté

grat

ion


Problématique de l’interopérabilité

Infrastructure

Services-protocoles

Middlewares

Interopérabilité

Beaucoup d’environnements :– PSE– Portails WEB– Serveurs de calculs– …

Objectif : faire coopérer les éléments d’une même couche ensemble.

Coopération ?– Standards– Protocoles– API– Descripteurs de problème

Exemple : couplage de code


Plan• Introduction• Architecture• Différentes approches des grilles de calcul

– Portail web– Internet computing– Méta-computing– Super-calculateur virtuel– Réseaux pair à pair (peer-to-peer)

• Quelques défis scientifiques• Exemple de travaux en cours• Conclusion


Différentes approches1. Différents types d’applications2. Différents besoins pour les utilisateurs3. Différentes plate-formes cibles4. Différents modèles d’exécution

Différentes solutions

Actuellement : effort de standardisation (GGF)


Modèles de déploiement• Client-serveur

– Centralisé ou Distribué– Utilisation de caches

pour éviter la congestion– Information centralisée

• Pair-à-Pair (P2P)– Chaque pair est à la fois

client et serveur– Distribution de la charge

dans le réseau (si parité!)– Information distribuée

Client

Internet

serveur

Client

ClientClient

Client

Client

ClientClient

Client

Client

CacheProxy

serveur

Client/Serveur

Internet

serveur serveur

Client/Serveur

Client/Serveur Client/

Serveur

Client/Serveur

Client/Serveur

Client/Serveur

Client/Serveur

Client/Serveur

Zone de congestion

Zone de congestion


Différents types de GRIDCaractéristiques

des nœuds :

Les systèmes de Calcul Global ou

« Mega Computing » ou « Internet Computing »

Les systèmes Pair à Pair

Les systèmes distribués à grande échelle

Grands sitesde calcul,Clusters

• <100• Stables• Identificationindividuelle

• Confiance

• ~100 000• Volatiles• Pas d’identindividuelle

• Pas de confiance

Les Grilles de calcul ou « GRID »

2 types de grands systèmes distribués

PCWindows,Linux


Portail Web• Sans doute la première incarnation

du concept de grille

• Accès à l’information– A partir d’une adresse http– A partir d’un moteur de recherche

• Transparence lors de l’accès à l’information– On ne sait pas toujours d’où vient

l’information (ex. images de cette présentation)

Serveur Web Serveur Web

Moteur de Recherche

Serveur Web Serveur Web

Client


Punch/NetCare

PUNCH/NetCare : portail webdédié à l’architecture des ordinateurs

Utilise les cycles libres parmi 600 PCs.

http://punch.perdue.edu


l’Internet Computing• Principe

– Des millions de PC en attente…– Utilisation des cycles processeurs inutilisés

(environ 47% en moyenne dans une entreprise*) via un économiseur d’écran

• Exemples– SETI@HOME

• Recherche de signaux extra-terrestres• 4,5 millions d’utilisateurs• 55,06 Teraflop/s (à comparer aux 35,86

Teraflop/s de l’ordinateur le plus puissant au monde au Japon!)

– DECRYPTHON• Etablir la carte des 500 000 protéines du

vivant– RSA-155

• Casser des codes cryptographiques* d’après une enquête d’Omni Consulting Group


Seti@home


Méta-computing

AGENT(s)

A

S3

Client

S2 !

Requête

Réponse (C)

A, B, C

C=Op(C, A, B) S4S1 S2

C


Méta-computing• Principe

– Acheter du service de calcul sur Internet– Services = applications pré-installées sur un calculateur

• Appels bloquants ou non-bloquants: Matlab, C, Fortran, Scilab...

• Exemples– Netsolve (Univ. Tennessee)– NINF (Univ. Tsukuba)– DIET (ENS-Lyon/INRIA)


Distributed Interactive Engineering Toolbox

Hiérarchie d’agents (extensibilité)

Fonctionne sur le mode gridRPC (appel de procédure à distance sur la grille)

Utilise CORBA pour l’exécution de calculs sur les serveurs

ReD : RedirectorMA : Master AgentLA : Leader AgentSeD : Server DaemonCRD : Computational ResourceDeamon

ReD : RedirectorMA : Master AgentLA : Leader AgentSeD : Server DaemonCRD : Computational ResourceDeamon


Supercalculateur virtuel• Principe

– Agréger les ressources distribuées en un supercalculateur

– Faire exécuter ses applications sur ce supercalculateur (mpirun)

“10 GFlops, EOS data,20 Mb/sec -- pour 20 minutes”

MetacomputingDirectoryService

GRAMGRAM

Courtier deressource

Service d’information :localisation + sélection

Allocateurs deressources

de GLOBUS

ForkLSFEASYLLCondoretc.

“Quels ordinateurs ?”“Quelle vitesse ?”“Disponibilité ?”

“50 processeurs + stockagede 10:20 à 10:40 pm”

“20 Mb/sec”

• Exemples– Globus– Légion– Unicore

GRAM

GRAM = Grid Resource Information Management


The Globus Project™Making Grid computing a reality

• Close collaboration with real Grid projects in science and industry

• Development and promotion of standard Grid protocols to enable interoperability and shared infrastructure

• Development and promotion of standard Grid software APIs and SDKs (System Development Kit) to enable portability and code sharing

• The Globus Toolkit™: Open source, reference software base for building grid infrastructure and applications

• Global Grid Forum (GGF): Development of standard protocols and APIs for Grid computing


Vue Globus

Application

Connectivity“Talking to things”: communication (Internet) & sécurité

Resource“Partager les ressources”: négociation des accès, contrôle de l’utilisation

Collective“Coordonner les ressources”: services pour la gestion de l’infrastructure, services distribués spécifiques aux applications

InternetTransport

Application

Link

Proto

cole In

ternet

Fabric“Contrôle local”: accès et contrôle des ressources


Système Pair à Pair(Peer to Peer)

• Applications dédiées– Napster, Gnutella, Freenet, – KaZaA, Music-city,– Jabber,

• Projets de recherche– Globe (Tann.), Cx (Javalin), Farsite, – OceanStore (USA), XtremWeb (LRI),– Pastry, Tapestry/Plaxton, CAN,

Chord, • Autres projets

– Cosm, Wos, peer2peer.org, – JXTA (sun), PtPTL (intel),

Toutes les ressources (PC) sont égales, les opérations se font à parité, de pair à pair.

PC volontaireParticipant à la mise enrelation entre Pair

Client

VolontaireInternet

req.

VolontaireApplicationProvider


Système Pair à Pair :Un exemple Gnutella

PC

PC

PC

PC

PCPC

Diffusion

DiffusionDiffusion

Table des voisins :@IP a@IP b @IP z

Objectif : partager des ressources (fichiers audio/vidéo)- Spécifications du protocole ouvertes (permet d’écrire des clients)- Système totalement distribué PC

PC PC

Table des voisins :@IP 1@IP 2 @IP x

PCRessource

- Diffusion de la requête aux voisins directs, propagation par inondation- Durée de vie de la requête, évitement de boucles- Transfert du résultat par requête HTTP (avec possibilité d’inversion)


NAPSTER• Entre le client/serveur et le P2P

– Accès à des données via un site unique contenant un index

• Stockage de données• Partage des données

– Données « inaltérables »– Copies multiples sans aucun

contrôle• Limites de l’approche

– Plutôt du client/serveur que réellement P2P

– Serveur « attaquable »• Par les tribunaux…• Ou par d’autres…

Utilisateur B Napster(Client + Serveur)

Serveur NapsterAssociation musique-IP

Utilisateur A Napster(Client + Serveur)


Rationalisation des systèmes P2PCaractéristiques fondamentales

• Extensibilité : jusqu’à 100 k voir 1 M machines• Hétérogénéité : différents matériels et OS• Dynamicité : nombre de clients et de serveurs évolue constamment• Disponibilité : le propriétaire d’une ressource doit pouvoir définir une

politique de partage de sa ressource• Tolérance aux pannes : le système (et peut être les applications) doivent

supporter l ’existence d’éléments défaillants• Utilisabilité : malgré les propriétés précédentes, le système doit rester

facilement programmable et maintenable• Sécurité : le système doit être sécurisé pour les participants, les serveurs

et l’application. Un comportement malicieux ne doit pas pouvoir corrompre l’application. Un agent externe ne doit pas pouvoir se faire passer pour un serveur.


Une plate-forme de recherche opensource pour étudier :• Le Calcul Global (extensibilité ,organisation des serveur,…)• Le Calcul Pair à Pair (volatilité, communication inter-nœud, sécurité)• Fusion des systèmes de Calcul Global et Pair à Pair

Plate-forme de Recherche (étudier de nouveaux mécanismes)Plate-forme de Production (identifier les problèmes des utilisateurs)

Les requêtes peuvent être relativesà des données ou des calculs Acceptation concerne des

calculs ou des données

System CGP2P

Mon PCrequête

résultat

un PCaccepte

fournit

PC

PCPC

PC

PC

PC

PC PC

PC

Un autre PC

accepte

fournit

CommunicationsPotentielles pour lesApplications parallèles


Plan• Introduction• Architecture• Différentes approches des grilles de calcul• Quelques défis scientifiques

– Pour les applications– Algorithmes pour les middlewares– Services optimisés

• Exemple de travaux en cours• Conclusion


Programmer la grille• Programmer un ordinateur parallèle : (très)

difficile• Grille (hétérogène, distribuée) : plus

compliquée qu’un ordinateur parallèle.• Problèmes encore plus difficiles que pour le

parallélisme.• Jonction de plusieurs communautés :

parallélisme, systèmes distribués, réseaux, etc.


Recherche en calcul distribué

Infrastructure

Services-protocoles

Modèles algorithmiques de programmation, couplage de code, ...Applications

Middlewares Algorithmes pour middlewares,…

Nouveaux services optimisés,…

Distribuée, hétérogène,…


Modèles algorithmiques

• Utiles pour concevoir et prédire la performance d’algorithmes.

• Existe pour les machines séquentielles.• Plusieurs modèles en parallélisme (PRAM, passage

de messages, BSP, PRO, …).


Vers une algorithmique des grilles de calcul

• Programmer une grille de calcul comme un calculateur parallèle virtuel

• Repenser l’algorithmique parallèle– Essentiellement conçu pour des architectures parallèles régulières

et à configuration statique• Caractéristiques des grilles informatiques

– Unité de calcul hétérogène– Non-prédictibilité des performances des réseaux– Aspect dynamique des ressources de calcul

• Problèmes et défis– Politique d’ordonnancement des calculs– Équilibrage dynamique par redistribution intensive des données– Recouvrement calcul/communication


Application : couplage de code• Une application = un assemblage de plusieurs

codes de calcul

Mécanique des structures

Thermique

Optique

Dynamique

Conceptionde

Satellite

Application de couplage

Grappe de PC

SAN

SAN

Grappe de PC

LAN

WAN

SupercomputerVisualisation


Couplage de codeSimulation multi-physique utilisation de codes parallèles• distribués (car parfois propriétaires)• de différentes naturesProblèmes :• Interaction efficace• Transfert des données• Réutilisation du codeUne solution : approche par composants parallèles• Encapsulation du code• Communication par des interfaces


Algorithmes pour les middlewares Problème de l’ordonnancement

✬ Mauvaise allocation des ressources ⇒ mauvaises performances

Allocation :• ressources disponibles,• charge,• taille des données,• localisation des données,• le temps de calcul,• …

Métrique :• optimiser les besoins de l’application• optimiser les besoins de chaque client• régime permanent


Algorithmes pour les middlewares Problème de la persistance et de la redistributionBesoin de stocker et de redistribuer les données pour éviter des transferts inutiles.

Redistribution de données entre grappes = problème de décomposition d’un graphe bipartie valué.

832

1

43

=

2

2+

2

1

+


C=A*B ?A sur S1B sur S2

Serveur 2B

Bande passantevitesse

C=A*B sur S1

C=A*BReception de B par serveur 2

OK ! Prêt à recevoir B

Envoie B sur Serveur 1

B

Serveur 1AB

Redistribution : principe

AGENT

Contrôle

Données


Standardisation des services : OGSA


Service : évaluation de la performance

Important de connaître la performance fourniepar les ressources :– État de l’infrastructure.– Goulot d’étranglement.– Ajout de nouvelles ressources.– …


Service de prédiction de la performance

Prédire : optimiser les décisions

Plusieurs approches :– Statistique (Network Weather Service : NWS)– Stochastique– Simulation

Besoin de modèles fiables


NWSService distribué :

- supervision périodique- prédiction dynamique

Utilise des senseurs deperformance

Prédictions suivant modèles statistiques


Service de sécurité

Besoin :– transactions sûres,– authentification des utilisateurs,– autorisations personnalisées.

Problème : différentes législations


Sécurité dans les réseaux Pair à Pair

Êtes-vous prêt à laisser exécuter n’importe quoi sur votre PC ?

Solution : technique du sandbox (isolation du code de calcul)

Calcul

SandboxSystème


Autres problèmes/services

• Découverte de ressources– hardware et software

• Visualisation de données– Passage à l’échelle

• Services aux utilisateurs– Outils pour le support et

les utilisateurs finaux.

• Tolérance aux pannes– Serveurs ou agents

• Check-pointing– E/S parallèles rapides– Garbage collection


Problème des données• Taille importante des données (cf. datagrid)

• Besoin :– Écriture et lecture à distance.– Traitement à distance (filtres …).– Publication (données accessibles par les

autres utilisateurs).– Découverte d’informations.– Nommage global.

Transparence!


IBP : Internet BackplaneProtocol

Service de stockage anonyme distribué.

Serveur IBP de stockage sur le réseau (dépôts)

Client IBP récupère une clé après le stockage de ses données sur n serveurs

Clé : permet à tous client de récupérer les données stockées.


Plan• Introduction• Architecture• Différentes approches des grilles de calcul• Quelques défis scientifiques• Exemple de travaux en cours

– AdOC : réalisation d’un service de compression dynamique et adaptatif (Jeannot, Knutsson, Bjorkman)

• Conclusion


AdOC : IntroductionUne partie des performances des supports d’exécution

dépend de leurs capacités à transmettre efficacement de grandes quantités de données

Transmettre des donnés :– de grande taille (quelques MO → X GO/TO),– aussi rapidement que possible,– sur des réseaux standards,– en gérant l’hétérogénéité,– pour des applications et des middlewares de type grid (mais

pas seulement).


Idée « naïve »

InternetInternet

Ne marche pas si :

Tcomp( )+Tsend( )+Tuncomp( )>Tsend( )


A quoi faut-il s’adapter?

• La vitesse du réseau,• la charge courante du réseau,• la vitesse CPU actuelle de l’émetteur et

du récepteur,• le type de donnée (ASCII, exe, .gz,

etc.),• la taille des données.


AdOCAdaptive On-line Compression Algorithm.

Travail type « proof of concept » basé sur deux idées :

1. recouvrement Compression/communication,

2. adaptation dynamique du niveau de compression.


Implantation d’AdOCUn algorithme/bibliothèque de niveau

utilisateur

1. Multithreading : recouvrement compression/communication

2. File d’attente où sont stockées les données compressées (supervision du changement de taille)


Compression Dynamique Adaptative

Paquets compressésà différents niveauxDonnée à transmettre

RéseauThread decompression adaptatif

Thread d’envoi des paquets

File d’attente∆ taille de la file

En cours d’intégration dans omniORB.

Compression basée sur la zlib


Expériences

Deux fichiers de test:– Oilpann.hb : matrice creuse ASCII

(Harwell-Boeing format)– Bin.tar : tarball de binaires

65/77

Évolution du niveau compression et de la taille de la file d’attente

66/77

Temps de transfert moyens: ASCII

FTP niv=1 niv=9 scp scp -C

01

23

45

67

89

1011

1213

1415

1617

Tm

/Tad

oc

100 Mbps 10 mbps Internet ADSL 56Kbps

Networks

67/77

Temps de transfert moyens : binaires

FTP niv=1 niv=9 scp scp -C

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

100 Mbps 10 Mbps Internet ADSL 56Kbps

Tm

/Tad

oc

Networks


Bibliothèque AdOCBibliothèque qui implante l’algorithme AdOC :1. Recepteur multithreadé2. File d’attente optimisée (« zerocopy »)3. API : sendFile/recvFile +

adoc_read/adoc_write + setMaxLevel/setMinLevel

4. Thread-safe5. Opensource (LGPL) :

http://www.loria.fr/~ejeannot/adoc


Utilisation dans NetSolve

AGENT(s)

A

S3

Client

A, B, C

Réponse (C)

S2 !

Requête

Op(C, A, B) S4S1 S2

C


Intégrer AdOC dans NetSolve

Multiplication de matrice à distance sur Internet

0

500

1000

1500

2000

2500

0 200 400 600 800 1000 1200

Taille de la matrice

Tem

ps

NetSolveNetSolve + AdOC340%


AdOC :Conclusion/travaux futurs• AdOC : bibliothèque et algorithme de

compression adaptative.• Service pour les middlewares.• Permet d’accroître les performances• Travaux futurs :

– Ajouter des algorithmes de compression très rapides,

– ajouter des algorithmes de compression plus efficaces,

– faire des tests sur des réseaux plus rapides (XGbps).


Plan

• Introduction• Architecture• Différentes approches des grilles de

calcul• Quelques défis scientifiques• Exemple de travaux en cours• Conclusion


Conclusion

Gros besoin pour les scientifiques et les industriels.Mais, utilisation transparente des ressources sur Internet

loin d’être atteinte!


Conclusion

Plusieurs approches en fonction des besoins et de l’infrastructure cible.

Effort de standardisation (GGF)

Succès de certains middlewares

Réalisation de nouveaux services


Conclusion

Bien identifier ce qui est technologique Les effets de modes et les buz-words…

De ce qui est plus fondamentalLes nouveaux concepts…


Vers de nouveaux systèmes d’exploitation Grid-aware ?

• Conception de systèmes d’exploitation GRID-aware– Actuellement : essentiellement middleware– Gestion des ressources = rôle de l’OS !


Remerciements

Certains transparents ont été emprunté à :– T. Priol– F. Capello– Globus Team– M. Cosnard– …

Documents

Calcul distribué : une introductioncdsweb.u-strasbg.fr/meeting3/Calcul_distribue.pdf · ¾On n’a pas toujours la bibliothèque installée ¾Des bibliothèques ou des environnements