55
Programmation parallèle et distribuée Philippe M ARQUET [email protected] Laboratoire d’informatique fondamentale de Lille Université des sciences et technologies de Lille Master informatique de Lille février 2008 ppd/intro – p. 1/48

Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Embed Size (px)

Citation preview

Page 1: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Programmation parallèle et distribuée

Philippe MARQUET

[email protected]

Laboratoire d’informatique fondamentale de LilleUniversité des sciences et technologies de Lille

Master informatique de Lillefévrier 2008

ppd/intro – p. 1/48

Page 2: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Création février 2008

Cette présentation reprend en partie l’introduction du cours Outils pourle calcul scientifique à haute performance que je donne avec PierreBOULET aux étudiants de l’école doctorale SPI. Ce dernier est lui-mêmeen partie bâti sur une ancienne version d’un cours de Programmationparallèle donné en maîtrise d’informatique. Voirhttp://www.lifl.fr/west/courses/cshp/ ethttp://www.lifl.fr/~marquet/pp/

Ce cours est diffusé sous la licence GNU Free Documentation License,http://www.gnu.org/copyleft/fdl.html

La dernière version de ce cours est accessible à partir dehttp://www.lifl.fr/~marquet/ens/ppd/

$Id: intro.tex,v 1.4 2012/01/18 10:08:29 marquet Exp $

ppd/intro – p. 2/48

Page 3: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Table des matières

Calcul haute performance et parallélismeTaxinomie des architectures de machinesModèles de programmation parallèlePerformanceParadigmes de programmation parallèleConception d’applications

ppd/intro – p. 3/48

Page 4: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Calcul haute performance et parallélisme

ppd/intro – p. 4/48

Page 5: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Motivation pour la haute performance

« Grand Challenge »:problème fondamentalgrands impacts sur l’industrie, la science ou la sociétésolution par l’utilisation du calcul haute performanceutilisation/définition des prochaines générations de machines/langages pourle calcul haute performance

Besoins importantsen puissance de calculen mémoire

Ordres de grandeur : (G : giga, T : téra), P : péta, E : exa1 PetaByte : vidéo de 2300 ans, 1 milliard de livres...Race to Exascale

US, Europe, China, Japan and Russia announced they will have anexascale system by 2020

Dept. of Energy plan :100 PetaFlops en 2016–20171 ExaFlops in 2018–2020

ppd/intro – p. 5/48

Page 6: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Exemples de « Grand Challenges »

Simulations de dynamique desfluides

conception d’avionshypersoniques, aérodynamismeautomobile, sous-marins furtifsprévision météorologiques àcours et long terme, climatiquesprospection pétrolière...

Calculs de structuresélectroniques et conception denouveaux matériaux

catalyse chimiqueagents immunitairessuperconducteurs

Calculs pour comprendre lanature fondamentale de lamatière

chromodynamique quantiquethéorie de la matière condensée...

Calculs symboliques dont :reconnaissance de la parolevision par ordinateurcompréhension du langagenaturelraisonnement automatiqueoutils pour concevoir, construire etsimuler des systèmes complexes

ppd/intro – p. 6/48

Page 7: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Calcul haute performance ?

Calcul haute performance =algorithme efficacecalcul de solutions approchéesetc.

+ Parallélisme

ppd/intro – p. 7/48

Page 8: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Calcul haute performance ?

Calcul haute performance =algorithme efficacecalcul de solutions approchéesetc.

+ ParallélismeParallélisme ?

ppd/intro – p. 7/48

Page 9: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Calcul haute performance ?

Calcul haute performance =algorithme efficacecalcul de solutions approchéesetc.

+ ParallélismeParallélisme =

programmation séquentielleun seul flot d’exécutionune instruction exécutée à la foisun processeur

programmation parallèleplusieurs flots d’exécutionplusieurs instructions exécutées simultanémentplusieurs processeurs

ppd/intro – p. 7/48

Page 10: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Parallélisme, pourquoi ?

Puissance de calculCoûtConsommation

ppd/intro – p. 8/48

Page 11: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Parallélisme, pourquoi ?

Puissance de calculvitesse des processeurs augmentelimitations, principalement technologiquesapplications encore plus demandeuses en puissance de calculsolution : exécuter plusieurs opérations en même temps

au sein d’un processeurpar duplication des éléments de calcul

CoûtConsommation

ppd/intro – p. 8/48

Page 12: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Parallélisme, pourquoi ?

Puissance de calculCoût

excellent rapport coût/performance nécessaireaccroissement de la puissance d’un élément de calcul⇒ explosion des coûts : coût marginal prohibitifgrande puissance de calcul : faire coopérer de nombreux élémentsde calculs de « faible » puissance et de moindre coût

Consommation

ppd/intro – p. 8/48

Page 13: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Modèle pour le parallélisme

Programmation séquentiellemodèle unique (von Neumann)

Programmation parallèlepas de modèle uniquedifférents aspects à considérer

architecturelogicielalgorithmes

Le parallélisme est orthogonal à l’informatique

ppd/intro – p. 9/48

Page 14: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Différents aspects du parallélisme

ArchitectureLogicielAlgorithmes

ppd/intro – p. 10/48

Page 15: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Différents aspects du parallélisme

Architecture

comment organiser et implanter de multiples processeursUnité de contrôle unique / multiples

moins de flexibilité / trop de libertéMémoire partagée / distribuée

bande passante d’une mémoire partagéeréseau d’accès à la mémoire

Systèmes distribuéstopologie du réseau d’interconnexionsurcoût des communications

LogicielAlgorithmes

ppd/intro – p. 10/48

Page 16: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Différents aspects du parallélisme

ArchitectureLogiciel

Approche de la programmation parallèleCorrection d’un programme parallèleImplémentationOutils spécifiques

Algorithmes

ppd/intro – p. 10/48

Page 17: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Différents aspects du parallélisme

ArchitectureLogiciel

Algorithmes

repenser en parallèle → gain de performance

ppd/intro – p. 10/48

Page 18: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Implications du parallélisme

Nouveaux conceptsconcurrencecommunicationsynchronisation

Facteurs de performanceallocation deprocesseurs/ordonnancementdistribution des donnéesgranularitératio communications/calculéquilibre (dynamique) de lachargeextensibilité

Problèmes spécifiquesnon-déterminismecorrection/justesseinterblocageterminaison

Dimension algorithmiquepensée/raisonnement parallèlemeilleur algorithme séquentielvs meilleur algorithmeparallèle

ppd/intro – p. 11/48

Page 19: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Taxinomie des architectures de machines

ppd/intro – p. 12/48

Page 20: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Modèle von Neumann

John VON NEUMANN (1946)grandes lignes pour construire une machine électroniqueappliquées jusqu’à nos jours

Modèle procéduralune séquence d’opérations peut décrire tous les problèmes

Différents blocs fonctionnels :mémoire : données et instructionsunité de contrôle : charge les instructions depuis la mémoireALU : exécute les instructionsI/O : transferts de données

ALU

Unité de contrôle

Mémoire

(programme)(données)

entréessorties

Séquencement des instructions inhibe le parallélisme

ppd/intro – p. 13/48

Page 21: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Développements architecturaux

Règle généraleextraction du parallélisme

Plusieurs aspectsfonctions du processeurhiérarchie du système mémoireinterface processeur/mémoiresystèmes multiprocesseurs

ppd/intro – p. 14/48

Page 22: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Classification de Flynn

Machine parallèle :plusieurs processeursclassification selon l’agencement des processeursnombreuses méthodes de classification

Michael J. FLYNN (1972)flux d’instructions : séquence d’instructions exécutées par la machineflux de données : séquence des données appelées par le flux d’instructionsinsuffissant pour classer finement les architectures parallèles

S Single I InstructionM Multiple D Data

}

{

SISD MISD

SIMD MIMD

ppd/intro – p. 15/48

Page 23: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Classification de Flynn — MIMD

MIMDn PE et n flux d’instructions

flux d’instructions indépendantsflux de données indépendants

Multiples configurationsmémoire (données) propremémoire partagée

Tendance actuelleprocesseurs banalisésarchitecture de la machine =réseau

Difficulté de programmation

Réseau d’interconnexion

M1 M2 M3 M4 M5

P1 P2 P3 P4 P5

M : mémoireP : processeurC : contrôle

C

C1 C2 C3 C4 C5

ppd/intro – p. 16/48

Page 24: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Mémoire partagée / mémoire

distribuée

Réseau d’interconnexion

P1 P2 P3 P4 P5

Mémoire partagée

cache cache cache cache cache

Réseau d’interconnexion

P1 P2 P3 P4 P5

M1 M2 M3 M4 M5

Machine MIMD à mémoirepartagéePC bi-processeur, multi-cœurCray CX-1000-SM : 4 octo-cœurIntel Xeon 7500

Machine MIMD à mémoiredistribuéeStations de travail + EthernetCray XK6 : 24 blades de 4 nœuds de16-core AMD Opteron 6200

ppd/intro – p. 17/48

Page 25: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

MIMD à mémoire distribuée

Réseau d’interconnexion

P1 P2 P3 P4 P5

M1 M2 M3 M4 M5

MIMD à passage de messagesun ensemble de « nœuds »un réseau

Nœudunité de calculmémoire localegestion de la communicationentre les nœuds

Mém. locale

CPU

Co−processeur

Interfaceréseaux

Mémoire et messagesmémoire locale accessible par lesprocessus locauxcommunication par le réseaumessage : (données, référencede processus)attention portée sur la diminutiondes communicationspasse par une bonnedécomposition des données

ppd/intro – p. 18/48

Page 26: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Modèles de programmation parallèle

ppd/intro – p. 19/48

Page 27: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Modèle de fonctionnement et modèle

de programmation

Modèle de fonctionnement des machines parallèles/distribuéeslié à l’architecture de la machinecomment sont exécutées les instructions élémentaires

Modèle de programmation parallèlelié à l’expression de l’algorithmequelles sont les « entités » parallèles du programmecomment sont exprimées leurs interactions

Passer du modèle de programmation au modèle d’exécution :compilateur, support d’exécutionde immédiat à ... travail ardu de recherche en informatique

Programmeur ne se préoccupe pas du modèle de fonctionnement

ppd/intro – p. 20/48

Page 28: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Multiplicité des modèles de

programmation

Deux grandes approches du parallélisme :Parallélisme de tâches (task or control parallelism)

décomposition d’une tâche en sous-tâchesvariables partagées entre les tâches, oucommunications par messages entre les tâchesmise en œuvre :

tâche ↔ processeurParallélisme de données (data parallelism)

structures homogènes« tableaux »affectation de « tableaux »mise en œuvre :

donnée « élémentaire » ↔ processeurCombinaison des modèles !

ppd/intro – p. 21/48

Page 29: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Modèles de programmation à

parallélisme de tâches

Un ensemble de tâches : processus ou threadchaque tâche travaille mémoire locale/privée+ synchronisation entre les tâchescommunication par messages

opération coopérative : un émetteur un récepteurou mémoire partagée

mécanisme de protection des accès à cette mémoireBibliothèque de fonctions

parfois directives/extension de langageProcessus communicants

PVM parallel virtual machineMPI message passing interface

Processus (légers, threads)interface POSIX pthreads

standard OpenMP

ppd/intro – p. 22/48

Page 30: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Modèles de programmation à

parallélisme de données

Manipulation de structures homogènes≡ tableauxhaut niveau d’expression du parallélismedécoupage des structuresdistribution des structures sur les processeurstravail sur la structure localerestructuration des structures : communications

Langages à parallélisme de donnéesFortran 95 (norme Fortran)

manipulation de tableauxHPF High Performance Fortran

extension de Fortran 95 pour machines à mémoire distribuéedistribution des tableaux sur des processeurs

DPCE Data-Parallel C Extension

ppd/intro – p. 23/48

Page 31: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Modèles de fonctionnement vs

modèles de programmation

Modèle de fonctionnement est lié à l’architecture de la machineTrois grandes classes :

SISD — Simple Instruction, Simple DonnéeMIMD — Multiples Instructions, Multiples DonnéesSIMD — Simple Instruction, Multiples Données

Modèle de programmation est lié à la traduction de l’algorithmeDeux principaux modèles :

parallélisme de tâches (→֒ SISD, MIMD)parallélisme de données (→֒ SISD, MIMD, SIMD)

ppd/intro – p. 24/48

Page 32: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Performance

ppd/intro – p. 25/48

Page 33: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Performance ?

Comment caractériser les performances d’un système ?d’un système pour une (classe d’)application donnéebenchmark

Rapport entre performance et coûtQuelle métrique pour la performance ?Théorèmes et lois

ppd/intro – p. 26/48

Page 34: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Benchmark

Programmme de test des performancesmesure + prédiction des performancesdécouverte des points faibles et forts

Macro benchmarkapplications ou applications synthétiquesmesure les performances globales

Micro benchmarknoyau de procéduresmesure des aspects spécifiques (CPU, mémoire, I/O...)

Nombreux benchmarks disponiblesmacro : PARKBENCH, SPEC (→ SPECint...), Splashmicro : STREAM, LINPACK

LINPACKnoyau d’algèbre linéaireclassement TOP-500, http://www.top500.org

ppd/intro – p. 27/48

Page 35: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Performance ? À quel coût ?

Temps entre le début et la fin de l’applicationutilisateur : minimiser ce tempsminimise le coût d’une exécution

heures CPU payantesRapporter le coût d’exécution au coût de développement

utilisation de paralléliseur automatiquecode peu stable ( 6= code de production)

Débit d’une machinenombre de jobs exécutés en une unité de tempsmulti-processing

partitionner une machine multiprocesseurspartition statique/dynamique

réduire le coût : améliorer le débit

ppd/intro – p. 28/48

Page 36: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Métriques

Temps d’exécutionen secondes : wallclock time ou elapsed timeen temps CPU

Nombre d’instructionsnombre d’instructions exécutées par la machinepas seulement dépendant du programme

compilateur, optimisationsarchitecture du processeur : RISC, CISC

vitesse en MIPS, millions d’instructions/secondeNombre d’opérations (flottantes)

nombre d’opérations nécessaires à la production du résultatadd, sub, mul= une opérationdiv, sqrt = 9 opérationssin, exp= 17 opérationsFlop, Mflop, Gflopvitesse en Mflop/s, Gflop/s (Mflops, Gflops !)

ppd/intro – p. 29/48

Page 37: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Facteur d’accélération

Un algorithmeexécution sur p processeurs en un temps tp

exécution sur 1 processeur en un temps t1

Accélération (speedup)

Sp =t1

tp

t1 temps du meilleur algorithme séquentielet non temps de l’algorithme parallèle exécuté sur 1 processeurÉtude de l’accélération

1 ≤ Sp ≤ p

Code séquentiel : Sp = 1

Code « purement » parallèle : Sp = p

ppd/intro – p. 30/48

Page 38: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Loi d’Amdahl

G. M. Amdahl (1967)Trouver une borne à l’accélération

pour un problème donnépour une taille de problème donnée

Identifier la partie parallélisable du codecharge de travail fixe W (par exemple en Mflop)distribution de cette charge entre P processeursdécomposition de la charge

W = αW partie séquentielle+ (1 −α)W partie parallélisable

Accélération

Sp =t1

tp=

W

αW + (1 −α)(W/p)=

p

1 + (p − 1)α→

1

α

quand p → ∞

ppd/intro – p. 31/48

Page 39: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Illustration de la loi d’Amdahl

Accélération pour p processeurs

Sp =p

1 + (p − 1)α

α pourcentage de code séquentielIllustration

p\α 50% 10% 1%

10 1.82 5.26 9.17100 1.98 9.17 50.25

1000 1.99 9.91 90.9910000 1.99 9.91 99.02

ppd/intro – p. 32/48

Page 40: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Implications de la loi d’Amdahl

Sp →1

α

quand p → ∞

Accélération limitée par la partie séquentiellelimite indépendante du nombre de processeurs

p\α 50% 10% 1%

∞ 2 10 100Bonne accélération : diminuer la partie séquentielle

optimiser cette partie séquentiellene pas focaliser sur la partie parallèle

ppd/intro – p. 33/48

Page 41: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Loi de Gustafson

Loi Amdahl = accélération à travail constantJohn Gustafson (1988)

parallélisme : problème de plus grande taillemeilleure précision du résultat...

Charge de travail augmente avec la taille de la machine p

W ′ = αW partie séquentielle+ (1 −α)pW partie parallèle

W charge de travail du problème originelsur un processeur : temps d’exécution de W ′ = proportionnel à W ′

sur p processeurs : par définition, temps d’exécution proportionnel à W

Accélération à temps constant

S′p =

t1

tp=

αW + (1 −α)pW

W= α + (1 −α)p

ppd/intro – p. 34/48

Page 42: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Implication de la loi de Gustafson

S′p = α + (1 −α)p

Accélération à temps constant linéaire en p

Problème extensiblepartie séquentielle n’est plus un problèmepartie séquentielle αW doit rester constanteproblèmes extensibles juqu’à un certain degré

ppd/intro – p. 35/48

Page 43: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Paradigmes de programmation parallèle

ppd/intro – p. 36/48

Page 44: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Paradigme de programmation

parallèle

Structure d’algorithmesPour exécution sur une machine parallèleQuelques paradigmes reconnusUn programme = combinaison de plusieurs des paradigmes

ppd/intro – p. 37/48

Page 45: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

« Parallélisme de phases »

Programme = suite d’étapesÉtape = 2 phases

calculinteraction

Calculde multiples processusréalisent chacunun calcul indépendant

Interaction entre les processussynchronisationcommunication bloquante, etc.

Inconvénients :pas de recouvrement en l’interaction et le calculnécessité et difficulté de maintenir l’équilibre de charge entre les processus

ppd/intro – p. 38/48

Page 46: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Itérations parallèles

Cas particulier du parallélisme de phasesItérations parallèles synchronesparfor p=0 to P-1

for i=0 to N

x[p] = f (p, i, x)

rendez-vous ()

Les étapes sont des itérations d’une boucleItérations parallèles asynchronesparfor p=0 to P-1

for i=0 to N

x[p] = f (p, i, x)

Itérations indépendantesUtilisation de x[p] produit au temps i-1 par un processus autre que p ?

ppd/intro – p. 39/48

Page 47: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Diviser pour régner

Découverte dynamique d’un arbre de calculsUn processus parent divise le travail entre ses filsLes processus fils combinent leur résultat vers leur pèreDivision et regroupement récursifsGestion des fils :

création dynamique et terminaison, ouutilisation d’un pool de processus

ppd/intro – p. 40/48

Page 48: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Pipeline

De multiple processus forment un pipeline virtuelUn flot de données parcourt le pipelineRecouvrement entre les calculs des différents processusRecouvrement possible des communications entre les processus parles calculsÉquilibre du pipeline

ppd/intro – p. 41/48

Page 49: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Maître/esclaves

Ferme de processus ou maître/esclaveUn processus maître = coordinateur

exécute le code séquentielinitie des processus esclavestransmet du travail à ces processus esclavesattend les résultats des esclavesitération de l’assignation de travail

Des processus esclavesattend du travail du maîtreexécute le travailretourne le résultat au maître

Paradigme simpleMaître = goulot d’étranglementParadigme non-extensible

ppd/intro – p. 42/48

Page 50: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Pool de travail

Pool de travail = structure de données globale/partagéeMultiples processusProcessus « libre »

prend un travail dans le poolproduit zéro, un, ou plusieurs nouveaux travaux dans le pool

Fin du programme quand le pool est videImplantation en mémoire partagée plus naturelle et plus facileÉquilibre de la charge de travailProblème du dimensionnement des travaux

trop petit : surcoût d’accès au pooltrop grand : non équilibrage de la chargevariable : diminution en fonction de la somme des travaux restants

ppd/intro – p. 43/48

Page 51: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Conception d’applications

ppd/intro – p. 44/48

Page 52: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

À la découverte du parallélisme

Où est le parallélisme dans l’application ?étude des dépendances entre les données

Découpage en tâches élémentairesparfois évidentpeut nécessiter des transformations du programmepeut aller jusqu’à des transformations de l’algorithme

Partitionnement des donnéesrecherche des données « proches »but : minimiser les communications

ppd/intro – p. 45/48

Page 53: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Choix du modèle de programmation

Une affaire de compromisefficacitéfacilité de programmationcontrôle fin du comportement du programmemaintenance du codeexpertise de l’utilisateurcompilateurs de la machine cible

Mixage de plusieurs modèlesprototypage en parallélisme de données puis optimisation avec passage demessagesparallélisme de données avec utilisation de bibliothèques de passage demessagesensemble de tâches data-parallèles

ppd/intro – p. 46/48

Page 54: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Choix de la granularité

Maximiser le degré de parallélisme et minimiser le volume decommunication sont contradictoiresIl ne sert pas forcément à grand chose d’avoir un parallélisme trop fin

une bonne approche est un découpage fin suivi d’un regroupementInfluence de la hiérarchie mémoire

parallélisme au niveau des instructionseffets de cachealignement des tableaux en mémoirecalcul « out of core » pour les très gros volumes de données

ppd/intro – p. 47/48

Page 55: Programmation parallèle et distribuée - CRIStALmarquet/cnl/ppd/intro.pdf · chromodynamique quantique théorie de la matière condensée... Calculs symboliques dont : ... Modèle

Équilibrage de charge

Statiqueen général : trouver la distribution de données la plus adaptéeoptimiser les communications

Dynamiquedans le cas où le calcul dépend des donnéesdans le cas d’une machine hétérogène ou non-dédiée

ppd/intro – p. 48/48