Programmation parall ele et distribu eepageperso.lif.univ-mrs.fr/~arnaud.labourel/PPD/cours1.pdf ·...

Preview:

Citation preview

Presentation du coursDefinitions des differents systemes

Conclusion

Programmation parallele et distribuee

Arnaud LabourelCourriel : arnaud.labourel@lif.univ-mrs.fr

Universite de Provence

26 janvier 2012

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

But du cours

Introduction aux systemesparalleles,concurrents,repartis,distribues.

Theorie et Applications.

Realisation d’une application en Java.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Introduction

Ce cours s’appuie sur :

cours Systeme

cours Reseaux

Java

Sources :

Cours de E. Goubault

Y. Robert et A. Legrand Algorithmique Parallele.

A. Tanenbaum : Distributed Systems.

Brian Goetz et al : Java Concurrency in Practice.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Horaires

Cours : jeudi de 8h30 a 10h30(10 seances, debute le 26 janvier)

TD : jeudi de 10h30 a 12h30(10 seances, debute le 2 fevrier)

TP :groupe 1 : mardi de 14h a 16h

(10 seances, debute le 31 janvier)groupe 2 : mardi de 16h a 18h

(10 seances, debute le 31 janvier)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Fonctionnement

Page web :http://pageperso.lif.univ-mrs.fr/

~arnaud.labourel/PPD/index.html

Partiel mi-mars

Projet en deuxieme moitie du semestre

Evaluation :3 max(Ex , 2Ex+Pa

3 )+TP

4

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Plan du cours

1 Introduction et termes2 Threads Java 1.53 Machines PRAM4 Exclusion Mutuelle5 Threads Java 1.5 – Synchronisation Avancee6 Java RMI7 Replication8 Algorithmes et Problemes Fondamentaux

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Parallelisme

Definition (Petit Robert)

Inform. Technique d’accroissement des performances desordinateurs utilisant plusieurs processeurs fonctionnantsimultanement.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Systemes Paralleles

Decouper un gros probleme en de nombreux petits

problemes :

Super calculateurs pour le calcul scientifique

Stations multiprocesseursGrilles

SETI@Homefolding@homedefi cryptographiques (distributed.net)....

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Parallelisme a differents niveaux

A l’interieur du processeurinstructions en parallele (pipeline)multi-cœurs

Multi-processeurs

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Le parallelisme au sein du processeur

L’execution d’une instruction (multiplication par ex.)necessite plusieurs cycles d’horloge.

⇒ On execute en parallele les instructions independantespour gagner du temps.

Un processeur possede plusieurs Unites Arithmetique etLogiques

Les instructions peuvent etre rearrangees afin d’ameliorerle rendement (out of order execution).

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de sequencage des instructions

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple d’architecture avec pipeline

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Multi-cœur

CœurUnite executant les instructions dans un processeur

Multi-cœur : plusieurs unites executant des instructionsen parallele.

Multi-cœur (tous sur un meme circuit) 6=multi-processeur (circuits differents)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Processeur multi-cœur

Un tres grande partie des processeurs actuels sontmulti-cœurs (generalement de 2 a 8 cœurs).

Encore plus de cœurs dans l’avenir

prototype tera-scale (80 cœurs) d’Intel

processeurs multi-cœurs pour les appareils mobiles(smartphones, tablettes)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple d’architecture multi-cœur

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Le parallelisme multiprocesseurs

Un concept ancien : premier ordinateurmulti-processeur en 1962, premier ordinateurmulti-processeur parallele en 1969.

Similaire au multi-cœur a l’exception de la memoirecache qui n’est pas partagee

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Quelques exemples de multiprocesseurs

Serveurs :plusieurs sockets pour accueillir des processeurs.Supercalculateurs :

Le plus puissant : Computer K88,128 processeurs 8-cœurs (2GHz)

Le deuxieme : Tianhe-1A14 336 processeurs7 168 processeurs graphiques

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Les problemes poses par la multiplicationdes processeurs

Probleme d’optimisation

Une tres grande partie des programmes actuels n’utilisepas la puissance des multi-cœurs.

Limite theorique : loi d’Amdahl

Rendement =1

(1− s) + sN

s : proportion d’activite parallelisableN : nombre de processeurs

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Loi d’Amdahl

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Systemes Concurrents

DefinitionElements situes dans un meme espace de ressources.

Systeme multitachetous les systemes actuelssauf si les ressources sont limitees

Probleme de partage des ressourcesmemoire partageeexclusion mutuelleprocessus leger (thread)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Memoire partagee

DefinitionPlusieurs processus partagent un espace memoire.

Problemes :

coherence de cache

acces concurrents

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Coherence du cache

Les caches des differents processeurs peuvent contenirles memes donnees qui seraient modifiees de maniereindependante.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exclusion mutuelle

DefinitionPrimitive de synchronisation utilisee en programmationinformatique pour eviter que des ressources partageesd’un systeme ne soient utilisees en meme temps.

Methodes d’exclusion mutuelle vues au chapitre 4 ducours.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Pourquoi utiliser l’exclusion mutuelle ?

Exemple de programmes executes en paralleleglobal = 0 ;

Programme 1 :global = global + 1 ;

Programme 2 :global = global + 2 ;

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Pourquoi utiliser l’exclusion mutuelle ?

Exemple d’execution :Programme 1 Programme 2R1 ← 0

R2 ← 0R1 ← R1 + 1 (1)

R2 ← R2 + 2 (2)global ← R1 (1)

global ← R2 (2)

Au final, global est egal a 2 au lieu de 3 qui est leresultat attendu.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Processus leger

DefinitionEnsemble d’instructions a executer se partageant lememe espoir memoire, chacun ayant une pile d’appeldistincte.

Utilite :

Separer les differentes fonctionnalites d’unprocessus : gestions des peripheriques, calculslourds.

Gains par rapport a l’utilisation de processusdistincts : commutation de contexte moins couteux.Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Systemes distribues : terme generique

Definition (Tanenbaum)

Un systeme distribue est une collection d’ordinateursindependants qui apparait comme un seul systeme pourses utilisateurs.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de systemes distribues

Grille informatique : infrastructure virtuelleconstituee d’un ensemble de ressourcesinformatiques :

heterogenesdelocalisees

Grappe de serveurs : plusieurs ordinateurs enreseau qui vont apparaıtre comme un seulordinateur ayant plus de capacite :

homogeneslocalises

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de grilles informatiques

Projets de calcul distribue :SETI@home : recherche de signe de vieextra-terrestre

5,2 millions de participantspuissance comparable au meilleur super-calculateuractuel

Folding@home : etude du repliement des proteines

4.51 millions de participants400 000 maximum en meme tempsplus puissant que le meilleur super-calculateur actuel

Distributed.net : challenge de dechiffrage de code

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de grappe de serveurs

Super-calculateurs virtuels :System X (grappe de 1100 serveurs)Duplication de serveurs :

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Systemes distribues

Terme generique mais aussi :

Reseauparadigme client/serveursystemes n-tiers

(auto)Gestion de reseauxroutagearbre couvrantelectiongestion des defaillances

Systemes concurrentsprincipe du decoupage d’un probleme en nombreusestaches specialisees

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Architecture client/serveur

DefinitionMode de communication entre plusieurs ordinateurs d’unreseau qui distingue un ou plusieurs clients du serveur.Chaque logiciel client peut envoyer des requetes a unserveur.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Architecture client/serveur

Caracteristiques d’un serveur :

initialement passif (en attente d’une requete) ;

a l’ecoute, pret a repondre aux requetes envoyeespar des clients

des qu’une requete lui parvient, il la traite et envoieune reponse

Caracteristiques d’un client :

initialement actif

envoie des requetes au serveur ;

il attend et recoit les reponses du serveur.Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Architecture 3-tiers

DefinitionModele d’architecture separant en trois couches :

presentation des donnees (affichage)

traitement des donnees(partie fonctionnelle, logique)

acces aux donnees persistantes(serveurs base de donnees)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Architecture 3-tiers

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Routage

DefinitionMecanisme de choix des chemins d’acheminements desdonnees d’un expediteur jusqu’a un ou plusieursdestinataires dans un reseau.

Different type de routage :

unicast : une seule destination

broadcast : toutes les machines,

multicast : un ensemble de machines

anycast : n’importe quelle machine

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de reseau

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de routage unicast

source

destination

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de routage broadcast

destinations

source

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple de routage multicast

destinations

source

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Election

Definition

Procede (algorithme) permettant d’elire un uniqueprocessus comme chef de file (leader) d’une tache.

But : choisir un chef qui prendra toutes les decisions.

Utile dans de nombreux algorithmes comme celui del’arbre couvrant.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Arbre couvrant

Definition (Theorie des graphes)

Sous-graphe connexe et acyclique contenant tous lessommets d’un graphe.

Utilite :

Eviter les cycles dans un reseau commute ethernet(Spanning Tree Protocol)

Plus generalement, faciliter le routage en le limitanta l’arbre couvrant.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Exemple d’arbres couvrant

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Plusieurs arbres couvrants possibles

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Gestion des pannes

Le probleme

Les systemes informatiques fiables doivent etre capablesde gerer des composants defectueux qui donnent desinformations conflictuelles aux differentes parties dusysteme.

Les pannes peuvent survenir pour de nombreusesraisons :

defaillance materielle

defaillance logiciel (bugs)

attaque malicieuse (DoS)Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Une analogie

Probleme des generaux byzantins

Des generaux doivent mener une attaque malgre lapresence de traitres essayant de semer la confusion parmiles generaux loyaux.But : les generaux loyaux doivent se mettre d’accord surun plan de bataille.

Toujours realisable si les traitres ne peuvent pas sefaire passer pour un autre general

Realisable si et seulement si il y a moins d’un tiersde traitres dans les autres casArnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Remarques sur la calculabilite et lacomplexite

Calculabilitedefaillancesinformation dynamique incomplete

ComplexiteCouts differents :

calcul internecommunication

Nombres de messagesNombres de “tours” (round)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Systemes repartis

Systeme assez heterogene

Reseau + technologie objetIntergiciel (middleware)

DCOMCorbaJava RMI

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Interlogiciel

DefinitionLogiciel tiers qui creant un reseau d’echanged’informations entre differentes applicationsinformatiques.

Exemple :Java RMI : interface de programmation (API) pour lelangage Java qui permet d’appeler des methodesdistantes sur un serveur.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

A Propos de ces definitions

pas de veritable consensusbeaucoup de points communs

simultaneiteproblematique du partage des ressources (au sens large)coordination

parfois tres entremeleeprogrammation concurrente sur une stationmulti-processeurs

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Presentation du coursDefinitions des differents systemes

Conclusion

Pour recapituler (Tentative...)

Systeme SystemeHomogene Heterogene

conception descendanteParallele Concurrent

(top-down)conception ascendante

Distribue Reparti(bottom-up)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr Programmation parallele et distribuee

Recommended