Chapitre 3

Fondements de la Programmation

Parall lelelele

Parall

Plan du cours

1. Introduction

2. Mod les, Environnements et Paradigmes de Programmation

2. Mod

les, Environnements et Paradigmes de Programmation

2. Mod

lisme

des performances du parall lisme

Evaluation des performances du parall

3. 3. 3. 3. Evaluation

lisme

des performances du parall

Evaluation

parall lesleslesles

scientifiques parall

ques scientifiques

Biblioth ques

4. 4. 4. 4. Biblioth

parall

scientifiques

quesques

Biblioth

1. Introduction

(cid:1) Dans la d cennie pr c dente, le monde a v cu une des plus excitantes

p riodes dans le d veloppement des ordinateurs : les am liorations des

performances des ordinateurs ont t spectaculaires.

(cid:1) De nouveaux paradigmes de programmation, langages, techniques

dordonnancement et de partitionnement, et algorithmes sont

n cessaires pour exploiter efficacement la puissance de ces machines

sophistiqu es et pour gagner de

la puissance soit au niveau

algorithmique, soit au niveau architectural.

2. Mod

les, Environnements et Paradigmes de

2. Mod les, Environnements et Paradigmes de

les, Environnements et Paradigmes de

2. Mod

Programmation

2.1. Principales formes de parall lisme

Il existe fondamentalement deux approches pour la programmation

parall le : implicite et explicite.

Approche implicite

(cid:1)

Cette approche se traduit par les langages parall les et les compilateurs

parall liseurs.

Prendre un langage existant et laisser le compilateur faire tout le travail.

Approche id ale du point de vue de lutilisateur :

" Codes existants peuvent tourner sans rien changer ni optimiser.

" Economie dans les co ts de d veloppement.

Probl mes de cette approche :

Le plein potentiel parall le dun probl me ne peut pas toujours tre

exploit .

Pour l criture dun nouveau programme, il est conseill que le

programmeur ait une certaine connaissance sur les possibilit s de

d tection du parall lisme du compilateur afin d crire du code qui

sex cute rapidement.

=> d viation du but original de d tection automatique du parall lisme.

Approche explicite

(cid:1)

Cette approche est justifi e par le fait que lutilisateur est souvent le

meilleur juge de la fa on avec laquelle le parall lisme peut tre exploit

efficacement pour une application particuli re.

Avantages :

Les utilisateurs sont d j habitu s aux langages de base.

Pour que leurs programmes sex cutent efficacement, seulement un

ensemble limit de fonctions suppl mentaires a besoin d tre

appliqu .

Probl mes :

Le programmeur est responsable dune grande partie de leffort de

parall lisation.

" Manque de portabilit : ces langages sont destin s des classes

sp cifiques de machines.

" Manque de standardisation

d velopp es avec des

apparences diff rentes

: beaucoup dextensions ont t

fonctionnalit s similaires mais des

2.2. Les sources du parall lisme

(cid:1)

Exploiter toute la puissance de calcul dune machine parall le est

souvent difficile :

Les algorithmes et les applications ne poss dent pas tous le m me

parall lisme potentiel.

" Mettre en vidence le potentiel de parall lisme dun algorithme et

lexploiter au mieux des capacit s de la machine reste un probl me

difficile.

Probl me du choix de lalgorithme pour r soudre un probl me

donn :

Plusieurs algorithmes s quentiels possibles.

Le parall lisme extrait du meilleur algorithme s quentiel

naboutit pas forc ment au meilleur algorithme parall le.

" Chaque algorithme se pr te plus ou moins une

parall lisation.

(cid:1)

On identifie trois sources de parall lisme : parall lisme de donn es,

parall lisme de t ches (ou de contr le) et parall lisme de flux.

Parall lisme de donn es

(cid:1) Exploite comme source de parall lisme la r gularit des donn es

(cid:1) Applique en parall le un m me calcul des donn es diff rentes

Parall lisme de t ches

(cid:1) Consiste appliquer des calculs diff rents sur des donn es diff rentes

en m me temps afin de g n rer du parall lisme

Parall lisme de flux

(cid:1) Correspond la technique du travail la cha ne

(cid:1) Chaque donn e subit une s quence de traitement r alis e en mode

pipeline en exploitant une r gularit des donn es

Remarque :

Lorsquon combine plus quun mode, on parle de parall lisme mixte.

2.3. Grain (ou granularit ) et degr de parall lisme

(cid:1)

Ces deux param tres sont importants tudier lorsquon parall lise une

application.

parall lisation.

Ils ont une grande

lefficacit de

influence sur

Grain de parall lisme

(cid:1)

Taille moyenne des t ches l mentaires qui ont guid la parall lisation

(en nombre dinstructions, temps dex cution, &).

Le choix du grain de parall lisme est fortement li larchitecture sous-

jacente.

Ce param tre a g n ralement une grande influence sur le param tre du

degr de parall lisme.

Niveau de parall lisation Mode

Programmes

Gros grain

Sous-Programmes

Instructions

Grain fin

Expressions

Op rateurs

MIMD

SIMD

Degr de parall lisme

(cid:1)

Cest la mesure du nombre de sous-t ches ex cut es simultan ment

dans un programme parall le.

=> indication du nombre de processeurs que lon pourra utiliser.

Il peut fortement varier dans les diff rentes parties du programme

=> on consid re souvent le degr maximal, moyen et minimal

Ces degr s peuvent tre valu s statiquement la compilation, ou

dynamiquement lors de lex cution.

Remarque :

(cid:1)

Bien que lex cution dun programme avec un nombre de processeurs

gal au degr maximal de parall lisme soit, en principe, la plus rapide,

cela ne signifie pas

le nombre optimal de

forc ment que cest

processeurs!

2.4. Mod les dabstraction

(cid:1)

L tude de mod les th oriques pour le calcul parall le est de donner

des cadres de travail permettant de d crire et danalyser des

algorithmes.

(cid:1) Ces mod les id als sont utilis s pour d terminer des bornes de

performances et des estimations de complexit .

(cid:1) Pas de mod le unique.

(cid:1) Diff rents aspects consid rer :

Architecture

Logiciel

Algorithmes

(cid:1) De nombreux mod les dabstraction existent pour des architectures

parall les m moire partag e et m moire distribu e.

Le mod le PRAM

Caract ristiques

(cid:1)

PRAM (Parallel Random Access Machine) est un mod le de machine

utilis pour mod liser des machines parall les id alis es.

(cid:1) Machine constitu e dune infinit de processeurs qui ex cutent tous le

m me calcul en mode synchrone.

(cid:1)

Tous les processeurs partagent la m me m moire globale.

Prend en compte lacc s concurrent aux donn es.

(cid:1) M me co t pour toutes les instructions (lecture, criture, traitement, &).

Avantages

(cid:1)

Simplicit

Probl mes

(cid:1)

Difficilement portable sur machines m moire distribu e.

(cid:1) Mod le de co t peu r aliste (dur e dun acc s = dur e dun calcul).

(cid:1)

Les surco ts dus aux communications et aux synchronisations sont

n glig s.

Variations sur les PRAM

(cid:1)

Lacc s la m moire commune peut seffectuer de diverses mani res.

4 variantes sont possibles selon quun seul processeur ou plusieurs

peuvent lire ou crire dans la m me case m moire :

Lecture Exclusive (Exclusive Read, ER) : un seul processeur peut lire

dans une case m moire un instant donn .

Lecture Concurrente (Concurrent Read, CR) : plusieurs processeurs

peuvent lire simultan ment le contenu de la m me case m moire.

Ecriture Exclusive (Exclusive Write, EW) : un seul processeur peut

crire dans une case m moire un instant donn .

Ecriture Concurrente (Concurrent Write, CW) : plusieurs processeurs

peuvent crire simultan ment dans la m me case m moire => Dans

ce cas, les procs peuvent poss der des informations diff rentes, ce qui

entra ne un conflit entre eux!

(cid:1)

Plusieurs mod les ont t propos s pour r soudre ce probl me :

" Mod le commun : toutes les critures concurrentes enregistrent la

m me valeur.

" Mod le arbitraire : une seule valeur choisie arbitrairement est

enregistr e.

" Mod le prioritaire.

" Max, (min) : la valeur crite par le processeur ayant lindex le plus

grand (petit) est enregistr e. Les autres valeurs sont ignor es.

etc.

CREW et CRCW sont les variantes les plus importantes

Le mod le par passage de messages

(cid:1)

Un algorithme con u pour un syst me passage de message consiste

en une collection de programmes locaux sex cutant sur les diff rentes

unit s de calcul dans un syst me distribu .

Le passage de message dans un syst me distribu peut tre mod lis en

utilisant un graphe de communication.

Le graphe de communication peut tre direct

unidirectionnelles) ou non direct (communications bidirectionnelles).

Le syst me peut op rer en mode synchrone ou asynchrone.

La communication et la synchronisation sont explicites.

Exemples de librairies de passage de messages :

" MPI (Message Passing Interface)

PVM (Parallel Virtual Machine)

(communications

2.5. Paradigmes de programmation parall le

(cid:1)

La conception des applications parall les se base sur ladoption de

paradigmes de programmation bien d finis.

Le choix du paradigme ad quat est d termin par les ressources de

calcul parall les disponibles et par le type du parall lisme inh rent dans

le probl me.

Quelques paradigmes reconnus.

Un programme = combinaison de plusieurs paradigmes.

Le paradigme Parall lisme de phases

: de multiples processus r alisent chacun un calcul

(cid:1)

Programme = suite d tapes

tape = 2 phases : calcul + interaction

Calcul

ind pendant

Interaction entre les processus :

Inconv nients :

synchronisation

communication bloquante, etc.

Pas de recouvrement entre linteraction et le calcul.

N cessit et difficult de maintenir l quilibrage de charge entre les

processus.

Le paradigme Diviser pour Parall liser

(cid:1)

D couverte dynamique dun arbre de calculs.

Un processus parent divise le travail entre ses fils.

Les processus fils combinent leurs r sultats vers leur p re.

Division et regroupement r cursifs.

Sch ma algorithmique :

(cid:1)

R duction du probl me des

instances

plus

petites.

ind pendantes

R solution parall le r cursive des

appliquant

sous-instances,

r cursivement la m me technique

chacune des sous-instances.

Construction de

la solution du

probl me initial partir des solutions

de chacune des sous-instances.

Le paradigme Ma tre/esclaves

(cid:1)

Un processus ma tre = coordinateur

ex cute le code s quentiel

initie des processus esclaves

transmet du travail ces processus

esclaves

attend les r sultats des esclaves

it ration de lassignation de travail

Paradigme simple

(cid:1)

(cid:1) Ma tre = goulot d tranglement

(cid:1)

Paradigme non-extensible

(cid:1) Des processus esclaves

" attendent du travail du ma tre

" ex cutent le travail

retournent le r sultat au ma tre

des performances du //smesmesmesme

Evaluation des performances du //

3. 3. 3. 3. Evaluation

des performances du //

Evaluation

(cid:1)

L tude th orique des performances des algorithmes parall les permet

de conna tre par exemple

lefficacit dun programme,

le gain issu du parall lisme,

son comportement futur dans le cas de laugmentation du nombre de

processeurs,

etc.

Il existe de nombreuses m triques de performances. Les plus utilis es

sont les suivantes:

3.1. Terminologie

(cid:1)

Soit r soudre une instance dun probl me de taille n

On note par :

T1(n) le temps dex cution s quentiel sur un seul processeur

Tp(n) le temps dex cution parall le sur p processeurs

3.2. Acc l ration

On d finit le facteur dacc l ration, qui permet de mesurer le gain en temps d la

parall lisation (ou le taux dutilisation des processeurs), par le rapport :

Sp(n) = T1(n) / Tp(n) => 1<Sp(n)dp : normal . Plus Sp est proche de p,

Sp(n)<1 : on ralentit ! (mauvaise parall lisation)

Sp(n)>p : acc l ration super-lin aire : analyser et

meilleur est lalgorithme parall le.

Sp(n)

Acc l ration super-

lin aire

justifier

Sp(n)=p

Acc l ration

id ale

Acc l ration

normale

ralentissement

Super-lin aire :

Ce nest pas magique, et ce nest pas normal

on doit analyser le ph nom ne et lexpliquer

corriger une erreur ou exploiter une optimisation

Exemples dexplications :

(cid:1) On ne fait plus les bonnes op rations (r sultat faux)

(cid:1)

lalgorithme s quentiel nest pas le m me que lalgorithme utilis pour

la parall lisation, et quil est moins efficace.

Les donn es tiennent dans le cache total des p processeurs

(cid:1)

(cid:1) On a modifi lalgorithme de d part et on converge plus vite (exp de

lalgorithme g n tique optimis )

(cid:1) On cherche une solution dans un arbre et on stoppe le programme

3.3. Efficacit

(cid:1)

On d finit lefficacit , qui est quivalent un rendement, dun algorithme

parall le par le rapport :

Ep(n) = Sp(n) / p

=> 0 (=0%)< Ep(n) <= 1 (=100%)

Ep(n)>1 (cid:2)(cid:2)(cid:2)(cid:2) acc l ration super-lin aire

Elle permet de mesurer le taux moyen dutilisation des processeurs.

Plus lefficacit est proche de 1, plus lalgorithme a de bonnes qualit s

parall les.

Exemple (Multiplication de matrices)

Algorithme A

Temps en s quentiel = 10 mns

Nb procs = 10

Temps en // = 2 mns

Acc l ration = 10/2 = 5 (lapplication

va 5 fois plus vite)

Efficacit = 5/10 = 0.5

Algorithme B

Temps en s quentiel = 10 mns

Nb procs = 3

Temps en // = 4 mns

Acc l ration = 10/4 = 2.5 < 5

Efficacit = (5/2)/3 = 0.8 > 0.5

Remarque

(cid:1)

Lutilisateur sint resse surtout lacc l ration obtenue.

Lacheteur de la machine sint resse beaucoup lefficacit .

Le d veloppeur sint resse aux deux.

Choix de la r f rence s quentielle :

A quels programme et ex cution s quentielle se comparer ?

(cid:1) M me programme lanc sur un seul processeur ?

(cid:1) M me algorithme implant en s quentiel ?

(cid:1) Meilleur algorithme s quentiel connu ?

(cid:1)

Compilation s quentielle avec le m me compilateur ?

Compilation avec le meilleur compilateur s quentiel ?

Optimisations s quentielles autoris es par la parall lisation ?

Optimisations s quentielles maximales ?

Ex cution sur un seul processeur de la machine parall le ?

Ex cution sur la meilleure machine s quentielle ?

Tous les choix sont plausibles :

(cid:1)

Chaque choix de r f rence s quentielle correspond :

Un point de vue diff rent,

Une pr occupation diff rente,

Un objectif danalyse diff rent

Limportant est de faire le choix correspondant sa probl matique

Exemple de choix :

(cid:1)

Utilisateur final : SON programme s quentiel sur SA machine s quentielle

: m me algorithme sur un processeur de la machine

Parall liseur

parall le

3.4. Sources de perte de performances

(cid:1) Sous-optimisation s quentielle

Aspects s quentiels

(cid:1) Fraction s quentielle

(cid:1) Surco t des op rations de gestion du parall lisme

(cid:1) Surco t d aux communications

(cid:1) D s quilibre de charge

(cid:1) ES s quentielles/s quentialis es

(cid:1) Sous-optimisation des outils et langages parall les

Algorithmique et

programmation

parall le

Environnement de

d veloppement

Remarque

(cid:1)

Lapproche pr c dente est raisonnable pour les machines parall les

m moire partag e. Cependant, sur des machines parall les

m moire distribu e, elle est insuffisante.

Une autre d finition du facteur dacc l ration a t propos e par

Gustafson qui est bas e sur la loi dAmdahl.

3.5. Scalabilit des architectures parall les

(cid:1)

Une architecture // est dite scalable si elle peut tre tendue (resp.

r duite) un syst me plus large (resp. petit) avec une augmentation

(diminution) lin aire en sa performance (co t).

La scalabilit est utilis e comme une mesure de la capacit du syst me

fournir des performances augment es

taille est

augment e, par exemple.

lorsque sa

Autrement dit, la scalabilit est une r flexion de la capacit du syst me

utiliser efficacement laugmentation des ressources de calcul.

(cid:1)

En pratique, la scalabilit dun syst me peut tre exprim e en

diff rentes formes, incluant la vitesse, lefficacit , la taille , les

applications, la g n ration et lh t rog n it .

Dans un syst me fortement (resp. faiblement) scalable, la taille du

probl me

(resp.

exponentiellement) en fonction de p pour maintenir une efficacit fixe.

lin airement

augmente

n cessite

quelle

ques Scientifiques Parall lesleslesles

4. Biblioth ques Scientifiques Parall

4. Biblioth

ques Scientifiques Parall

4. Biblioth

4.1. Motivation

(cid:1)

Calcul scientifique calcul num rique

Alg bre lin aire dense ou creuse

R solution lin aire directe ou it rative

R solution non-lin aire

Calcul de valeurs et de vecteurs propres

Transform es de Fourier rapides &

(cid:1)

R duction du temps de d veloppement

Ind pendance vis- -vis de limplantation

S quentielle, ou

Parall le

4.2. Portabilit et efficacit

(cid:1) G n ricit (ind pendance vis- -vis du type des donn es)

(cid:1)

Ind pendance vis- -vis de la repr sentation des donn es

(cid:1)

Choix du meilleur algorithme num rique

Assurance de la stabilit num rique

(cid:1) Optimisation fonction de larchitecture de la machine

(cid:1) Optimisation fonction des param tres (nombre de colonnes/lignes)

4.3. Biblioth ques monoprocesseurs (s quentielles)

BLAS (Basic Linear Algebra Subroutines)

Elle est divis e en trois sections:

(cid:1)

BLAS 1 : vecteur/vecteur

BLAS 2 : matrice/vecteur

BLAS 3 : matrice/matrice

BLAS niveau 1 :

Premi re biblioth que de calcul scientifique

(cid:1)

(cid:1) Op rations de type z= x+y ( scalaire, x, y et z vecteurs)

(cid:1)

(cid:1) Grand succ s

(cid:1) O(n) op rations sur O(n) l ments

Traitement l ment par l ment des l ments des vecteurs

BLAS niveau 2 :

(cid:1) Motiv s par :

" Diminution du nombre dacc s m moire

Augmentation du grain de calcul

Prise en compte des unit s vectorielles pipelines

(cid:1) Op ration entre matrices et vecteurs

" Op rations de type z= y+ Ax (A matrice)

" O(n2) op rations sur O(n2) l ments

BLAS niveau 3 :

(cid:1) Motiv s par :

" Utilisation maximale des hi rarchies m moire

" Minimisation des mouvements de donn es entre les m moires

" Meilleure utilisation des caches

(cid:1) Op ration entre matrices et matrice

" Op rations de type C= C+ AB (A, B, C matrices)

" O(n3) op rations sur O(n2) l ments

LAPACK (Linear Algebra PACKage) :

(cid:1)

R solution de syst mes lin aires

R solution des moindres carr s

Valeurs propres, valeurs singuli res

Factorisation de matrices LU, Cholesky, QR, &

Alg bre lin aire de haut niveau

Travail sur des matrices denses ou des matrices bandes : pas de prise

en compte de matrices creuses g n rales

Con ue pour

parall les m moire partag e.

Utilise des algorithmes par blocs pour utiliser au mieux la hi rarchie

m moire.

Implant e au dessus des BLAS 3.

les machines vectorielles. Etendue aux machines

4.4. Biblioth ques parall les

(cid:1)

Equilibrage de la charge de calcul

Recouvrement des acc s aux donn es distantes par des calculs

N cessit de versions parall les des biblioth ques de calcul num rique

Prise en compte de la localit des donn es

Bonne r partition des donn es

Versions parall les des algorithmes

Proposer une biblioth que parall le

Parall liser chacune des fonctions de la biblioth que

Quel algorithme parall le ?

Quelle r partition des donn es ?

Jusqu de nouvelles m thodes num riques

(cid:1) Mod le de programmation SPMD dutilisation des biblioth ques

BLACS (Basic Linear Algebra Communication Subroutines)

(cid:1)

Bibilioth que de communications

Communications sp cialis es

change de vecteurs/matrices

Lignes/colonnes de matrices : blocs de matrices

Diffusion et r duction

Contexte de la communication : isoler les communications de la

biblioth que et dautres communications.

BLACS :

Portabilit (versions PVM et MPI)

Efficacit (versions optimis es pour nombres de machines)

Ce nest pas une biblioth que g n rale de communications

PBLAS (Parallel BLAS)

(cid:1)

Ce sont les BLAS parall les

Interface aussi proche que possible de celle des BLAS

Implant e au dessus de BLAS + BLACS

BLAS : calculs locaux

BLACS : communications

Consid r e comme un noyau pour dautres biblioth ques num riques

parall les

ScaLAPACK (Scalable LAPACK)

(cid:1)

La r f rence en terme dalg bre lin aire dense pour machines

m moire distribu e.

Cest une biblioth que domaine public

Implant e au dessus de LAPACK, PBLAS et BLACS

Dautres biblioth ques sont implant es au dessus de ScaLAPACK

Succ s de ScaLAPACK

(cid:1)

Extensibilit

Garantir les performances quand le nombre de processeurs

augmente

quilibrage de la charge via des distributions cycliques 2D

quilibrage de charge pour des petits blocs (grain de

distribution)

Faible co t de communication pour des gros blocs (diminution

du nombre de messages)

Taille de blocs qui soit le bon compromis entre quilibrage de

la charge et la latence des communications

(cid:1)

Strat gie dun succ s

Code source (Fortran 77 et C), donc portabilit

Structure hi rarchique (BLAS, BLACS, &)

volution continue des biblioth ques de base

" Meilleurs algorithmes

" Optimisation pour la majorit des machines (assembleur)

" Rejaillit de suite sur ScaLAPACK

IBM PESSL

(cid:1)

PESSL : Parallel Engineering and Scientific Subroutines Library

Biblioth que math matique dIBM : calcul num rique haute performance

sur IBM SP et clusters dIBM RS/6000

Alg bre lin aire, FFT, g n ration de nombres al atoires, &

Fondements du Parall lisme

Formes

Sources

Granularit

Mod les

Paradigmes

Performances

Biblioth ques

"Implicite

"Explicite

"Donn es

"T ches

"Flux

"Grosse

"Moyenne

"Fine

"PRAM

"Passage

de msgs

"//me de phases

"diviser pour //er

"ma tre/esclaves

"Acc l ration

"Efficacit

"Scalabilit

"BLAS

"LAPACK

--------------

"BLACS

"PBLAS

"ScaLAPACK

"PESSL

Parallélisme en programmation : Approches implicites et explicites

Parallélisme en programmation : Approches implicites et explicites