View
21
Download
0
Category
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