Programmation parall ele et distribu eepageperso.lif.univ-mrs.fr/~arnaud.labourel/PPD/cours1.pdf · Primitive de synchronisation utilis ee en programmation informatique pour eviter

Presentation du coursDefinitions des differents systemes

Conclusion

Programmation parallele et distribuee

Arnaud LabourelCourriel : [email protected]

Universite de Provence

26 janvier 2012

Arnaud Labourel, [email protected] Programmation parallele et distribuee


Conclusion

But du cours

Introduction aux systemesparalleles,concurrents,repartis,distribues.

Theorie et Applications.

Realisation d’une application en Java.



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.



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)



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


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

~arnaud.labourel/PPD/index.html


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



Conclusion

Systemes parallelesSystemes concurrentsSystemes distribuesSysteme repartis

Parallelisme

Definition (Petit Robert)

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



Conclusion


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)....



Conclusion


Parallelisme a differents niveaux

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

Multi-processeurs



Conclusion


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).



Conclusion


Exemple de sequencage des instructions



Conclusion


Exemple d’architecture avec pipeline



Conclusion


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)



Conclusion


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)



Conclusion


Exemple d’architecture multi-cœur



Conclusion


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



Conclusion


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



Conclusion


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



Conclusion


Loi d’Amdahl



Conclusion


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)



Conclusion


Memoire partagee

DefinitionPlusieurs processus partagent un espace memoire.

Problemes :

coherence de cache

acces concurrents



Conclusion


Coherence du cache

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



Conclusion


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.



Conclusion


Pourquoi utiliser l’exclusion mutuelle ?

Exemple de programmes executes en paralleleglobal = 0 ;

Programme 1 :global = global + 1 ;

Programme 2 :global = global + 2 ;



Conclusion


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.



Conclusion


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, [email protected] Programmation parallele et distribuee


Conclusion


Systemes distribues : terme generique

Definition (Tanenbaum)

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



Conclusion


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



Conclusion


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



Conclusion


Exemple de grappe de serveurs

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



Conclusion


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



Conclusion


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.



Conclusion


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, [email protected] Programmation parallele et distribuee


Conclusion


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)



Conclusion


Architecture 3-tiers



Conclusion


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



Conclusion


Exemple de reseau



Conclusion


Exemple de routage unicast

source

destination



Conclusion


Exemple de routage broadcast

destinations

source



Conclusion


Exemple de routage multicast

destinations

source



Conclusion


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.



Conclusion


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.



Conclusion


Exemple d’arbres couvrant



Conclusion


Plusieurs arbres couvrants possibles



Conclusion


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, [email protected] Programmation parallele et distribuee


Conclusion


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, [email protected] Programmation parallele et distribuee


Conclusion


Remarques sur la calculabilite et lacomplexite

Calculabilitedefaillancesinformation dynamique incomplete

ComplexiteCouts differents :

calcul internecommunication

Nombres de messagesNombres de “tours” (round)



Conclusion


Systemes repartis

Systeme assez heterogene

Reseau + technologie objetIntergiciel (middleware)

DCOMCorbaJava RMI



Conclusion


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.



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



Conclusion

Pour recapituler (Tentative...)

Systeme SystemeHomogene Heterogene

conception descendanteParallele Concurrent

(top-down)conception ascendante

Distribue Reparti(bottom-up)


Documents

Programmation parall ele et distribu eepageperso.lif.univ-mrs.fr/~arnaud.labourel/PPD/cours1.pdf · Primitive de synchronisation utilis ee en programmation informatique pour eviter