Systèmes et traitements parallèleseleuldj/Cours/Arc_Par/STP Support 2018.pdf · devant le temps de ces opérations, estimez le temps d’exécution de l’évaluation de p(x 0)

27/09/2018

1

Systèmes et traitements parallèles

Mohsine Eleuldj

Département Génie Informatique, EMI

[email protected]

Octobre 2018

2

Motivation

A l’aide d’un ordinateur classique :• La prévision météorologique du lendemain prend une semaine !• La détection d’un missile dans un espace aérien prend 12 minutes sachant

que le missile peut atteindre sa cible en 10 minutes !• La supervision d’une centrale nucléaire (détection de la température,

pression,…) prend deux secondes sachant que si un paramètre dépasse un seuil pendant une seconde, la centrale explose !

Solution : Traitement parallèle ou HPC (High Performance Computing)

• Accélération des calculs (application de calcul intensif)• Réduction du temps d’accès aux données (application traitant un ensemble

immense de données).• Réduction des temps de réponse (application temps réel).Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

27/09/2018

2

3

Objectifs et plan du cours

Objectifs• Etudier les architectures des systèmes parallèles.• Déterminer leurs performances afin de pouvoir les prévoir et les améliorer.• Apprendre à concevoir des applications parallèles.• Programmer en utilisant les standards open source OpenMP et MPI.

ContenuI. Introduction au traitement parallèleII. Pipeline et traitement vectorielIII. Réseaux d’interconnexionIV. Analyse des performances des systèmes parallèlesV. Applications parallèles (OpenMP et MPI)

Evaluation : TP (30%) + Contrôle avec documentation (70%)

Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

4

Chapitre IIntroduction au traitement parallèle

• Quelques applications parallèles

• Evolution des systèmes d’ordinateurs

• Evolution de la densité d’intégration

• Définition et niveaux de parallélisme

• Parallélisme dans un système monoprocesseur

• Classifications des ordinateurs parallèles

• Classement des superordinateurs (Top 5, juin 2018)


27/09/2018

3

5

Quelques applications parallèles

• Prévision météorologique• Réactions chimique et nucléaire (temps réel)• Activités géologique et sismique• Simulation des circuits intégrés • Moteur de recherche du Web • Exploration minière (pétrole, …) • Réalité virtuelle (simulation de vol d’avion, entertainment

industry, …) • Réalité augmentée (superposition de la réalité et d’éléments de

son, image, vidéos,…)• Génomique (Biologie à l’échelle du génome)• Big Data (données massives)Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

6

Evolution des systèmes d’ordinateurs

• Technologie de fabrication : commutation implantée par des relais électromécanique, tube à vide, transistors (1947), diodes, circuits électroniques, mémoire à tore (électromagnétisme), SSI (Small Scale Integration), MSI (Medium), LSI (Large) et VLSI (Very Large), ULSI (Ultra) et WSI (Wafer).

• Processeur : arithmétique bit à bit (additionneur à 1 bit), virgule fixe, virgule flottante, coprocesseur scientifique, multiprocesseurs, processeur multi-core, plusieurs niveaux de mémoire cache (3 à 7), GPU, GPGPU,…

• Système d’exploitation : traitement par lot, multiprogrammation, temps partagé, mémoire virtuelle, multitraitement, multithreading,...

• Langage de programmation : langage machine binaire, langage d’assemblage, Fortran (1956), Algol (1960), Cobol (1959), Pascal (1980), Fortran étendu (vectoriel), Snobol (chaîne de caractères), Lisp et Prolog (IA), C, C++ (Orienté objet), Concurrent C, Python, Java,...

• Bibliothèque (Library) : mathématique, graphique, statistique, apprentissage automatique, parallélisation (OpenMP, MPI),…


27/09/2018

4

7

Evolution de la densité d’intégration

Processeur Année Transistors Technologie

4004 1970 2,3 K 6μm

8088 1980 29 K 3μm

80286 1983 134 K 2μm

80386 1985 275 K 2μm

80486 1989 1,2 M 1μm

Pentium 1995 3,3M 350 nm

PentiumPro 1996 5,5M 250 nm

Pentium II 1997 7,5 M 180 nm

Pentium III 1999 9,5 M 130 nm

Pentium IV 2003 42 M 90 nm

i7-3770K 2008 1,4 G 22 nm


8

Intel Core i7-3770K160 mm2, 22 nm, 1,4 G transistors et 3,4 GHz


27/09/2018

5

9

Traitement parallèle

Définition du traitement parallèle : Exploitation d'événements concurrents • Concurrence : parallélisme, simultanéité et pipeline• Parallélisme : événements se produisant pendant le même intervalle de temps• Simultanéité : événements se produisant dans le même instant• Pipeline : événement se produisant pendant des intervalles de temps chevauchés

Niveaux du traitement parallèle• Travail ou programme (multiprogrammation, temps partagé, multitraitements)• Tâche ou procédure (décomposition du programme)• Inter-instruction (analyse de la dépendance des données) vectorisation• Intra-instruction (au niveau de la micro-programmation) ou du câblage

Constatation : de plus en plus le matériel remplace le logiciel • Miniaturisation et réduction du coût • Augmentation de la vitesse (temps réel)• Augmentation de la fiabilité et la tolérance au pannes


10

Parallélisme dans un monoprocesseur

• Multiplicité des unités fonctionnelles (10 UAL dans le CDC-6600)

• Parallélisme et pipeline dans le CPU (processeur)

• Pipeline entre le CPU et des E/S (canaux, DMA, E/S programmées)

• Système de hiérarchie de mémoire (mémoire virtuelle)

• Equilibrage des tâches bornées par le calcul (calcul intensif ) et celles bornées par les E/S (communications intensives)

• Multiprogrammation (chevauchement entre le CPU et les E/S)

• Temps partagé (Time sharing) : efficace pour les applications interactives temps réel

Tous ces mécanismes sont pris en charge (propres) par les systèmes d’exploitation


27/09/2018

6

11

Classification des ordinateurs parallèles

Classification structurelle• Système à mémoire distribuée (Tableau de processeurs)

• Système à mémoire partagée (Multiprocesseurs)

Classification de Flynn (1966) • SISD : Single Instruction Single Data stream (ordinateur conventionnel)

• SIMD : Single Instruction Mulitple Data stream (Cray1: ordinateur vectoriel)

• MISD : Multiple Instruction Single Data stream (peu d’implémentation)

• MIMD : Multiple Instruction Multiple Data stream (Cray 2, MPP)


12

Classification structurelleSystème à mémoire distribuée

UC : Unité de ContrôlePC : processeur de contrôleMC : mémoire de contrôleET : Elément de traitementP : processeurM : mémoire locale.

PC

MC

P

M

P

M

P

M

P

M

Réseau d’interconnexion

Exemples : Illiac IV et MPP (Massively Parallel Processors)

E/S

ET1 ET2 ET3 ETn

UC


27/09/2018

7

13

Classification structurelleSystème à mémoire partagée

Exemples : S-1, IBM370/168MP, Cray X-MP et Cray-2.

MM 1

Réseau d’interconnexion

Réseau d’interconnexionMM 2

MM n

P1 ML1Pp MLp

E/S

MM : module mémoireP : processeurML : mémoire locale


Mémoirepartagée

…..

…..

14

Classification de Flynn : SISD

Le système peut être pipeline et/ou avoir plus d'une unité fonctionnelle (une seule unité fonctionnelle pour VAX11/780 et plusieurs unités pour IBM370/168)

P : ProcesseurM : MémoireFI : Flot d'instructionsFD : Flot de données


UC P M

FI

FI FD

27/09/2018

8

15

Classification de Flynn : SIMD

Systèmes qui ont une structure de tableaux d'ordinateurs (Illiac IV et MPP)


UC

Pn MmFI

FI

FDn

P1 M1

FD1

P2

FD2

.

.

....

UC : Unité de contrôleP : ProcesseurM : MémoireFI : Flot d'instructionsFD : Flot de données

16

FI1FInFD

Classification de Flynn : MISD

Architecture ayant moins d’intention et considérée comme impraticable par certains architectes

Pn

Mm

FIn

P1

M1

FD

P2

M2...

...

UCn

UC1

UC2

.

.

.

FI2

FI1

... FI2


27/09/2018

9

17

FI2

FI1

FIn

FD2

FD1

FDn

FI2

FI1

Classification de Flynn : MIMD

Exemples : IBM 360/16 MP, Cray-2, IBM 3081/3084 et S-1

Pn

FIn

P1 DSn

P2

.

.

.

UCn

UC1

UC2

.

.

.

Mm

M1

M2

.

.

.

.

.

.


18

Classement des superordinateurs(http://www.top500.org/lists/2018/06)

Kilo =103, Méga =106, Giga =109, Tera = 10 12, Peta = 1015

Rang Système Constructeur Nombre de cores

Performance(Pflops)

Puissance(KW)

1 SummitIBM,United States

2 282 544 122 8 806

2SunwayTaihuLight

Sunway,China

10 649 600 93 15 371

3 SierraIBM,United States

1 572 480 72 ?

4 Tiahe-2ANUDT,China

4 981 760 61 18 482

5 ABCIFujitsu,Japan

391 680 19 1 649


27/09/2018

10

19

A propos de Summit d’IBM

supercomputer now running at the Department of Energy’s (DOE) Oak Ridge National Laboratory (ORNL), captured the number one spot with a performance of 122.3 petaflopson High Performance Linpack (HPL), the benchmark used to rank the TOP500 list. Summit has 4,356 nodes, each one equipped with two 22-core Power9CPUs, and six NVIDIA Tesla V100 GPUs. The nodes are linked together with a Mellanox dual-rail EDR InfiniBand network.

Exercice :• Quel est le nombre de CPU et de GPU ?• Quel est le nombre de cores dans un GPU ?• Dessiner une architecture de ce superordinateur.


20

Principe général de la parallélisation

Diviser-pour-régner de parallélisation• Décomposition du problème en plusieurs sous-problèmes (processus, threads,

tâches,…)• Répartition (allocation) des sous-problèmes sur les différents cores ou

processeurs selon le modèle maître/esclave, arborescent,...• Possibilité de partage de la mémoire (mémoire partagée) ou échange de

messages (mémoire distribuée) au cours du traitement• Combinaison des résultats des sous-problèmes afin de résoudre le problème

de départ

Alternance entre le traitement séquentiel et parallèle

Exemples : Fork/Join et mapReduce


27/09/2018

11

21

Exercice Exemple de parallélisation

Considérons l’évaluation du polynôme p(x) en un point donné.

p(x) = a4x4 + a3x3 + a2x2 + a1x + a0

Sur 3 systèmes différents : 1, 2 et 4 processeurs. Supposons qu’une addition et

une multiplication prennent 1 et 4τ (τ : cycle d’horloge).

a) En supposons que le temps de communication (transfert) est négligeable devant le temps de ces opérations, estimez le temps d’exécution de l’évaluation de p(x0) sur les 3 systèmes.

b) Avez-vous choisi le meilleur algorithme dans le cas d’un seul processeur ?

c) En supposons que les processeurs sont interconnectés à l’aide d’un bus et

qu’une communication prend 1 10τ, estimer le temps d’exécution.

d) Généraliser ces résultats pour un polynôme de degré n.

Problématiques : décomposition, affectation (équilibre des charges), communication, analyse de la complexité des l’algorithmes, ….


22

Chapitre IIPipeline et traitement vectoriel

• Pipeline• Principe du pipeline• Exemples du pipeline unidimensionnel

• Exécution d’un programme• Addition des nombres en virgule flottante

• Ordinateur pipeline• Pipeline bidimensionnel (Produit matriciel)

• Traitement vectoriel• Ordinateurs vectoriels• Cray-1• Vectorisation


27/09/2018

12

23

Principe du pipeline

Hypothèses : Ei : étage i (1≤ i ≤ k), T : tampon et H : horloge

Temps(Ei) = τi, Temps(T) = τ0 et τ = max{1 ≤ i ≤ k, τi} + τ0

n tâches, T1 et Tk : temps sans et avec pipeline de k étages

Tk = τ0 + kτ + (n - 1)τ = (k + n - 1)τ + τ0

Supposons que T1 = nkτ Rendement = T1/Tk = nkτ/ [(k + n - 1) τ + τ0] ≈ nk/(k+n - 1)

Concept : chaîne de montagne dans une usineObjectif : amélioration des performances

E1 E2 Ektâches T T TT T

H

…

H H H H


24

Exemple : Exécution d’un programme

• Exécution d'une instruction.• CI : Chercher l'instruction de la mémoire• DI : Décoder l'instruction• CO : Chercher les opérandes• EO : Exécuter l'opération

• Problème :• conflit d’accès à la mémoire• branchement et interruption

• Avantage : exécution de la même instruction plusieurs fois (traitement vectoriel)

• Ordinateurs pipeline : IBM3838, CRAY-1, CYBER-205.

CI DI CO EOProgramme(instructions)


27/09/2018

13

25

Exemple : Addition des nombres représentés en virgule flottante

Entrée : deux nombres en virgules flottante normalisée.

A = a x 2p et B = b x 2q

a et b : matisses et p et q : exposants.

On veut calculer :

A + B = c x 2r = d x 2s où r = max(p.q) et 0,1 ≤ d < 1.

Exemple : A = 0,101 x 28 et B = 0,1101 x 29

A + B = 0,101 x 28 + 0,1101 x 29

= 0,0101 x 29 + 0,1101 x 29 -- réduction au même exposant

= 1,0010 x 29 -- addition des matisses

= 0,1001 x 210 --normalisation


26

Algorithme de calcul de l’addition

1. Déterminer r = max(p,q) et t = | p – q |

2. Décaler à droite la mantisse associée au plus petit exposant par t bits

3. Additionner les mantisses pour obtenir c

4. Normaliser le résultat :

si c < 1 alors u = 0

si c > 1 alors u = 1

5. Le résultat final est :

d = c << u et s = r + u


27/09/2018

14

27

Additionneur pipeline

A=a x 2p

p

a

Soustracteur

d’exposants

Décaleur

droiteSélecteur

de fraction

Compteur

de zéros

Additionneur

d’

exposants

Additionneur

de

fraction Décaleur

gauche

B=b x 2q

q

b

E1 E2 E3 E4

r=max(p,q)

t=| p – q |

Fraction avec min(p,q)

Autre fraction

s

d

C=A+B=d x 2sc

cc

u

d


28

Accélération de l’additionneur pipeline

Hypothèses :τ0 = 10 ns, τ1 = 90 ns, τ2 = 70 ns, τ3 = 60 ns et τ4 = 40 nsla période du pipeline P ≥ 90 + 10 = 100 ns = 10-7sla fréquence f = 1/P = 107 Hz = 10 Mhz

après initialisation, exécution d'une opération toutes les 100 ns

T1 = (90 + 70 + 60 + 40) * n = 260 * nT4 = 410 + 100 * (n - 1) = 310 + 100 * n

Accélération = T4 / T1 ≈ 260/100 = 2,6 < 4

Exercice : Pouvez-vous réduire le temps en fusionnant E3 et E4 ?


27/09/2018

15

29

Exemples de UAL pipeline

Ordinateur Nombre d’étages

Star-100 4

TI-ASC 8

Cray-1 14

Cyber 20 26


30

Ordinateurs pipeline

Chevauchement du traitement de données dans :

- UAL

- UC

- Processeur d'E/S

- Hiérarchie de la mémoire

La performance peut se dégrader de façon significative à cause de la dépendance des données conflit des ressources partagées.


27/09/2018

16

31

Pipeline bidimensionnel

Exemple : Produit matricielC = A * B où A et B sont 2 matrices d’ordre nsoient τ : temps d’exécution d’une multiplication

t(n) : temps d’exécution du produit matriciel

Algorithme classique (SISD)nombre de multiplications = n3

si n = 103 et τ = 1 µs t(n) = 103 s ≈ 16 mn

Réseau systolique (MISD)nombre de cellules de base = 3n²-3n+1multiplication est complétée après 3n-2 périodessi n = 103 et une période =τ

≈ 3 M processeurs et t(n) ≈ 3 ms


32

Elément de base du produit matriciel

a

a

b

c

b

d

M d = a * b + c


27/09/2018

17

Réseau systolique du produit matriciel

M M M

M M M M

M M M M M

M M M M

M M M

t5 c13 c12 c11

c21

c31

t6 c21 c22

c32

t7 c33

b33

b23

b13

0

0

t2

0 0 a31 a32 a33 0 a21 a22 a23 0

t1

0

b32

b22

b12

0

a11 a12 a13 0 0

t0

0

0

b31

b21

b11

33Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

34

Ordinateurs vectoriels

Un superordinateur est caractérisé par :

- haute vitesse de calcul

- MP et MS grandes et rapides

- logiciels //

généralement conçu pour effectuer le calcul

- vectoriel

- ou matriciel

utilisé dans les applications scientifiques : prévision météorologique, recherche nucléaire, intelligence artificielle, …


27/09/2018

18

35

Générations des ordinateurs vectoriels

Année Machine puissance installations

1960 Star-100 50 MFlops 7 en 1978

Illiac-IV 1

1975 Cray-1 160 MFlops 60 en 1982

Cyber 200 800 MFlops

Fujitsu VP-200 500 MFlops

Cray-2 2 GFlops

Cyber-205 3 GFlops

Nec 5 GFlops

2016 TaihiLight 93 PFlops

2018 Summit 122 Pflops DOE, USA


36

Ordinateur vectoriel : Cray-1 (1/2)

Premier ordinateur vectoriel moderne

période de l'horloge = 12.5 ms fréquence = 80 Mhz.cycle de la mémoire = 50 ms, bipolaire (SECDED)transfert de (4 mots) /période de l'horloge de ou vers la mémoire.= 320 M mots/sles canaux ont un taux de transfert = 80 M mots/s

4 canaux opèrent simultanément pour achever le taux maximum de transfert.

266 tampons d'instruction800 registres12 unités fonctionnelles pipeline (1 à 14 étages).

Registres adresses (A) 8 x 24 bitsRegistres scalaires (S) 8 x 64 bitsRegistres vecteurs (V) 8 x 64 x 64 bitsTampons-adresse (B) 64 x 24 bitsTampons-scalaire (T) 64 x 64 bits


27/09/2018

19

37

Ordinateur vectoriel : Cray-1 (2/2)

VL : Vector Lnghtformat d'instructions = 16 ou 32 bitsAlgorithme LRU de remplacement des tampons d'instructionP = Program counter 22 bitsNIP = Next Instruction Parcel 16 bitsCIP = Current Instruction Parcel 16 bitsLIP = Lower Instruction Parcel 16 bitsRecip Ap : Inverse approximatif d'un opérande de 64 bits en virgule flottante.Pop/17 : compter le nombre de "1" dans l'opérande/

compter le nombre de '0' précédant un "1"Nombres en virgule flottante (64 bits) et en double précision (128 bits)Dans Cray-1, une opération sur 1 vecteur ayant :

• 3 éléments s'exécutent plus rapidement en mode scalaire• 4 éléments au plus s'exécutent plus rapidement en mode vectoriel

la vitesse moyenne Cray-1 est de 24 MFlops au lieu de 160 car les logiciels n'exploitent pas efficacement (proprement) le matériel (langage, compilation,…).

4 3 3 3 3 10

g h i j k m


38

Compilation

27/09/2018

20

39

Exemples d’instructions Cray-1

Instructions indépendantesV0 V1 + V2V3 V4 and V5

Réservation de l'unité fonctionnelle V3 V1 + V2V6 V4 + V5

Réservation de l'opérande V3 V1 + V2V6 V1 * V5

Réservation de l'opérande et de l'unitéV0 V1 + V2V3 V1 + V5


40

Exemple d’une boucle Cray-1

Soient A et B deux vecteurs de longueur N. Calculer / A = 5*B + C

Programmation sur Cray-1 :

Q N div 64R N mod 64pour i = 1 à Q faire Calculer (A,64)Calculer (A,R)

Fonction Calculer(A, longueur)S0 5 initialiser le registre scalaire par une constanteS1 C charger C dans le registre scalaireVL longueur initialiser la longueur du vecteurV0 B multiplier chaque élément du vecteur par une constanteV1 S0 * V0 multiplier une constanteV2 S1 + V1 additionner une constanteA V2 sauvegarder le résultat dans A


27/09/2018

21

41

Vectorisation (1/3)

Vectorisation : ensemble de transformations apportées à un programme scalaire conduisant à de bonnes performances lorsqu'il est exécuté sur un ordinateur vectoriel.

Rôle : Compilateur ou manuellement (règles ou critères)

Exemple : vectorisation d’une boucle

pour i= 1 à 20 faireC(i) A(i) + B(i)

VL 20V1 AV2 BV3 V1 + V2C V3


42

Vectorisation (2/3)

Indépendance des donnéespour i=1 à 20 faire X(1) X(1) + 5

X(i) X(i) + 5 X(2) X(2) + 5X(3) X(3) + 5

……Dépendance des données

pour i=2 à 40 faire Y(2) Y(1) + 3Y(i) Y(i-1) + 3 Y(3) Y(2) + 3

Y(4) Y(3) + 3……

Restructuration du programmepour i=1 à 20 faire pour j=2 à 40 faire

pour j=2 à 40 faire pour i = 1 à 20 faireZ(i,j) Z(i,j-1) + 7 Z(i,j+1) Z(i,j) + 7


27/09/2018

22

43

Vectorisation (3/3)

Eclatement de la bouclepour i=1 à 100 faire pour i=1 à 100 faire

A(i) A(i) + 2 A(i) A(i)+2B(i+1) B(i) + 1 pour i=1 à 100 faire

B(i+1) B(i)+1

Instruction conditionnellepour i=1 à 100 faire pour i=1 à 100 faire

si (A(i) > 0) alors S(i) A(i) > 0B(i) = C(i) * 5 si S(I) alors B(i) = C(i) * 5

Exemples : ACTUS (1979) et VECTRAN (1975)


44

Vectorisation assistée

Vectorisation automatique (compilateur) n'est pas encore une solution satisfaisante pour optimiser la performance d'un ordinateur vectoriel car :• réalisation d'un compilateur vectoriel est complexe• algorithmes sophistiqués

Vectorisation assistée : • compilateur détecte les zones du programmes requérant le plus de temps

d'exécution.• utilisateur peut intervenir pour restructurer le code du module.

Outils :• bibliothèque de sous-programmes vectorisés (écrits par l'utilisateur ou par

le constructeur). Par exemple : opérations matricielles, équations d'algèbre linéaire, valeurs propres, traitement du signal (TFR), …

• Expérience de l'utilisateur (architecture, compilateur, bibliothèque).


27/09/2018

23

Chapitre IIIRéseaux d’interconnexion

• Introduction

• Classifications

• Topologies statiques

• Topologies dynamiques

• Application aux algorithmes parallèles

• Sommes partielles

• Produit matriciel


Introduction aux réseaux d’interconnexions

A1

Réseau d’interconnexionA2

An

A i : Téléphone, Processeur, Module mémoire, Ordinateur, Capteurs, …

Exemples : Réseau local, Internet, Réseau d’interconnexion d’un multiprocesseurs,…

A1

A2

Am


27/09/2018

24

Classifications des réseaux d’interconnexion

• Topologie : statique ou dynamique (reconfigurable)

• Commutation : par circuit (TCP/IP) ou par paquet (UDP/IP)

• Contrôle : centralisé ou distribué

• Mode d’opération : synchrone ou asynchrone


Topologies statiques (1/2)

Les connexions entre les éléments de traitement sont statiques (figés une fois pour toutes) : Bus, Anneau, Etoile, Graphe complet, Matrice, Cube, Hypercube,…


a) bus

c) Etoile d) Graphe complet e) Matrice

b) Anneau

27/09/2018

25

Topologies statiques (2/2) : Hypercube


a) dim 0 b) dim 1 c) dim 2

d) dim 3 e) dim 4

Mesures des réseaux statiques

Définition :

• dimension(réseau) : longueur maximale pour lier 2 nœuds

• connexions(réseau) : nombre de liens du réseau

Exercice : Remplir le tableau suivant


Réseau d’interconnexion dimension connexion

Bus

Anneau

Etoile

Graphe complet

Matrice

hypercube

27/09/2018

26

Topologies dynamiques

Les connexions entre les éléments de traitement sont dynamiques (modifiables ou programmables) : réseau Baseline nxn

n/2 x n/2

n/2 x n/2

0123

n-1n-2n-3n-4

.

.

.

.

0123

n-2n-3n-4

.

.

.

.

état 0

état 1


Programmation du réseau Baseline n=8

0 1 2 3 4 5 6 71 7 3 5 0 4 6 2Permutation = ( )

01

23

45

67

01

23

45

67


27/09/2018

27

Exercice : Réseau Baseline

Considérons un réseau Baseline nxn.

a) Quel est le nombre des étages d’un réseau baseline nxn ?

b) Quel est le nombre total des cellules de base ?

c) Peut-on programmer n’importe quelle permutation ?

d) Comment peut on implémenter le contrôle ?

e) Décrire un algorithme décentralisé pour le réseau Baseline.

f) Décrire un algorithme décentralisé de routage pour l’hypercube.


Calcul des sommes partielles

Problème : Calcul de S(k) = Σ0≤i≤k a(i) pour k = 0,1,...,n-1

54

Solution 2 : Calcul non répétitif → (n – 1) additionsS(0) a(0)pour k = 1 à n-1 faire

S(k) S(k-1) + a(k)

Solution 1 : calcul direct → n(n- 1)/2 additionspour k = 0 à n-1 faire

somme a(0)pour i = 1 à k faire

somme somme + a(i)S(k) somme


27/09/2018

28

S(0)

S(1)

S(2)

S(3)

S(4)

S(5)

S(6)

S(7)

ET0

ET1

ET2

ET3

ET4

ET5

ET6

ET7

Calcul MIMD des sommes partielles

t3

a0

a0+a1

a0+…+a2

a0+…+a3

a0+…+a4

a0+…+a5

a0+…+a6

a0+…+a7

t1

a0

a0+a1

a1+a2

a2+a3

a3+a4

a4+a5

a5+a6

a6+a7

t2

a0

a0+a1

a0+…+a2

a0+…+a3

a2+…+a5

a3+…+a6

a1+…+a4

a4+…+a7

t0

a1

a2

a3

a4

a5

a6

a7

a0


Exercice : Algorithmes des sommes partielles

Considérons le calcul des sommes partielles sur un système MIMD composé de p ET est reliés par un réseau d’interconnexion Baseline.

a) Trouver la complexité des solutions 1 et 2 sur un SISD.

b) Trouver la complexité de la solution MIMD.

c) En supposons que n=p=8 :

• Quelles sont les permutations qu’il faut réaliser pour effectuer ce traitement

• Quel est la programmation du réseau pour chaque permutation ?


27/09/2018

29

Produit matriciel

Solution 2 : SIMD (n pour i = 1 à n faire

Par pour k = 1 à n faire cik = 0pour j = 1 à n faire

Par pour k = 1 à n faire cik = cik + aij*bjk

Solution 1 : SISDpour i = 1 à n faire

pour j = 1 à n fairecij = 0pour k = 1 à n faire cij = cij + aik*bkj

Problème : Produit matriciel de deux matrices d’ordre n


Produit matriciel (n=3)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

M2 M3M1

.

.

.

a11

a21

a31

b11

b21

b31

c11

c21

c31

a12

a22

a32

b12

b22

b32

c12

c22

c32

a13

a23

a33

b13

b23

b33

c13

c23

c33

A

B

C

i j En parallèle

1 c11=0, c12=0, c13=0

1 c11+=a11b11, c12+=a11b12, c13+=a11b13

2 c11+=a12b21, c12+=a12b22, c13+=a12b23

3 c11+=a13b31, c12+=a13b32, c13+=a13b33

2 c21=0, c22=0, c23=0

1 c21+=a21b11, c22+=a21b12, c23+=a21b13

2 c21+=a22b21, c22+=a22b21, c23+=a22b23

3 c21+=a23b31, c22+=a23b32, c23+=a23b33

3 c31=0, c32=0, c33=0

1 c31+=a31b11, c32+=a31b12, c33+=a31b13

2 c31+=a32b21, c32+=a32b22, c33+=a32b23

3 c31+=a33b31, c32+=a33b32, c33+=a33b3358Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

27/09/2018

30

Exercice : Réseau d’interconnexion du produit matriciel

Considérons le calcul du produit matriciel sur un système MIMD composé de 3 ET et un bus comme réseau d’interconnexion.

a) Proposer un réseau d’interconnexion pour les relier.

b) Comment allez-vous programmer ce réseau ?


60

Chapitre IVAnalyse des performances des systèmes parallèles

• Eléments de performance des système parallèles

• Mesures de performance

• Complexité des algorithmes

• Equilibre des charges

• Granularité

• Ordonnancement

• Extensibilité

• Communication bloquante

• Sources d’interblocage


27/09/2018

31

61

Motivation

? amélioration de la performance

Programme séquentiel+

Parallélisation(OpenMP, MPI,…)

programme parallèle


62

Eléments de performancedes systèmes parallèles

• Taille de l’exemplaire (entrée du programme)

• Complexité des algorithmes (logarithmique, polynomial, exponentiel,…)

• Architecture (mémoire partagée, distribuée)

• Processeurs (nombre, fréquence, nombre de cores, GPU, GPGPU,…)

• Mémoire (temps d ’accès, cache, niveaux de caches,…)

• Langage (C, Java, Fortran,…)

• Paradigmes de programmation (procédural, fonctionnel, orienté objet,…)

• Compilateur (optimisation, vectorisation, …)

• Système d ’exploitation (Linux, Windows,…)

• Protocole de communication (Ethernet, TCP/IP, ATM…)

• Parallélisation (équilibre des charges, Granularité, Ordonnancement, communication bloquante ou non, exclusion mutuelle,…)

• Bibliothèques (MPI, OpenMP,…) Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

27/09/2018

32

63

Mesures de performance

• Soit t(n,p) le temps d’exécution d’un problème de taille n en utilisant un système composé de p processeurs

• Performance

P = 1/t(n,p)

• Accélération (Speed up)

A = t(n,1)/t(n,p)

• Efficacité

E = A/p

En général 1 ≤ A ≤ p et E ≤ 1

si A > p alors il s’agit d’une sur-accélération


64

Exemple : Calcul de l’accélération

… … …… … …… … …… … …… … …… … …… … …… … …… … …t(n,1) = cn2

En négligeant les temps de communication

t(n,9) = t(n/3,1) = cn2/9

A = t(n,1)/t(n,9) = 9 et E = A/9 = 1

… … …… … …… … …… … …… … …… … …… … …… … …… … …

n

Considérons une matrice d’ordre n et supposons que le traitement d’un élément prend c secondes (exemple : traitement d’image)

Soit t(n,p) le temps d’exécution d’une matrice d’ordre n en utilisant p processeurs

n


27/09/2018

33

65

Exercice : Evaluation des performances

Reprenons l’exemple précédent.

a) Comment pouvez augmenter l’accélération et l’efficacité ?

b) En pratique, quelle hypothèse faut-il revoir ?


66

Degré moyen de parallélisme

• Degré de parallélismeD(t) = nombre de processeurs utilisés pendant l’instant t

avec m processeurs (D(t) ≤ m)

−=

2

112)(

1 t

tdttD

ttD

• Degré moyen de parallélisme

où t1 et t2 les temps de début et fin de l ’exécution

=−

=2

112)(

1 t

tt

tDtt

D• D(t) est une fonction discrèteSystèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

27/09/2018

34

67

Exemple :Calcul du degré moyen de parallélisme

8 9 10 11 127654

123456789

10

temps

processeurs

D = (1 + 4 + 8 + 6 + 5 + 3 + 4 + 1) / 8 = 4


68

Exercice : Choix du nombre de processeurs

Reprenons l’exécution de l’exemple précédent.

a) Quel est le nombre de processeurs qui minimise le temps d’exécution ?

b) Qu’arrive-t-il si on augmente le nombre de processeurs (plus que 8) ?

c) Qu’arrive-t-il si on réduit le nombre de processeurs (moins que 8) ?


27/09/2018

35

69

Complexité des algorithmes

• Notion d ’ordreO(f(n)) = {t:N > R*/ (∃c ∈ R+)(n0 ∈ N)( ∀n> n0 ) [t(n)<cf(n)]}

t(n) est de l’ordre de f(n)

• Soit t(n) le temps d ’exécution d’un algorithme sur un exemplaire de taille nt(n) ∈O(log n) algorithme est logarithmique t(n) ∈O(n) linéairet(n) ∈O(n2) quadratiquet(n) ∈O(p(n)), où p polynôme polynomialt(n) ∈O(f(n)), où f exponentielle exponentiel

• Classes des problèmes : P, NP, NP-complet• Problèmes indécidables : Exemple du problème d’arrêt


70

Exemple : Algorithmes des sommes partielles

Algorithme 1pour i = 0 à (n – 1) faire

S(i) a(0)pour j = 1 à i faire

S(i) S(i) + a(j)

Algorithme 2S(0) a(0)pour i = 1 à n-1 faire

S(i) S(i-1) + a(i)

Soit a un vecteur de n éléments, les sommes partielles S(i) (0 ≤ i < n) sont définis par :

=

=i

j

jaiS0

)()(


27/09/2018

36

71

Equilibre des charges

Pour illustrer le concept de l’équilibre des charges, considérons le calcul des sommes partielles S(i) (0 ≤ i < 256) sur 8 processeurs numérotés p0, p1,…,p7.

Soient t(pi) le temps d’exécution du processeur pi (0 ≤ i <8)t(8) le temps d’exécution du système composé des 8 processeurst(8) = Maximum(t(p0),t(p1),…,t(p7))

Supposons qu’il n’est pas possible que les processeurs puissent communiquer (temps de communication infini)

le calcul des sommes partielles sera effectué par Algorithme 1.

=

=i

j

jaiS0

)()(


72

Charge des processus de Affectation 1

128 150 192 224 2569664320

p0 p1 p2 p3 p4 p5 p6 p7

Affectation 1p0 exécute les itérations i = 0 à 31p1 ″ i = 32 à 63

…pk ″ i = 32k à 32k+31…p7 ″ i = 224 à 255


27/09/2018

37

73

Algorithme de Affectation 1

Exercice : Soit N(k) le nombre d’additions effectuées par le processeur k. Montrer que : N(k) = 16 x (64k + 31)

N(0) = 496N(1) = 1520…N(7) = 7664

AlgorithmePar pour k=0 à 7 faire

pour i = 32k à (32k + 31) faireS(i) a(0)pour j = 1 à i faire

S(i) S(i) + a(j)

32640)(7

0

===k

kNS 40808/ =S


74

Nombre d’additions de Affectation 1

temps(Affectation 1) = t(p7) = 7664 x c où c : temps d’exécution d’une addition


27/09/2018

38

75

Charge des processus de Affectation 2

128 144 160 176 192 208 224 2402561129680644832160

p0 p1 p2 p3 p4 p5 p6 p7 p7 p6 p5 p4 p3 p2 p1 p0

Affectationp0 exécute les itérations i=0 à 15 et i=240 à 255p1 ″ i=16 à 31 et i=224 à 239…pk ″ i=16k à 16k+15 et i=(240 - 16k) à (255 - 16k)…p7 ″ i=112 à 127 et i=128 à 143


76

Algorithme de Affectation 2

AlgorithmePar pour k=0 à 7 faire

pour i=16k à 16k+15 et i=(240 - 16k) à (255 - 16k) faireS(i) a(0)pour j=1 à i faire

S(i) S(i) + a(j)

Exercice :Montrer que le nombre d’additions est indépendant de k et que

N(k) = 4080


27/09/2018

39

77

Nombre d’additions de Affectation 1 et 2

temps(Affectation 2) = t(p0) =t(p1) = ... = t(p7)Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

78

Degré moyen de parallélismede Affectation 1 et 2

t4 t5 t6 t7 t8t3t2t1t0

123456789

10

temps

processeursAffectation 1

Affectation 2

Exercice : montrez que D(Affectation 1) = 4,5 et D(Affectation 2) = 8


27/09/2018

40

79

Granularité

Granularité = taille de la tâche affectée (allouée) à un processeur (ou processus)temps d ’exécution = temps de calcul + temps de communication

Hypothèse : temps de communication d’un message de taille n est a + b * noù a est b sont deux constantes (a : latence et b : débit)

Exemple : Produit matriciel C = AB où A et B deux matrices d’ordre n.

Version 1: pour i=1 à n fairepour j=1 à n faire

C(i,j) 0pour k=1 à n faire

C(i,j) C(i,j) + A(i,k) * B(k,j)Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

80

Granularités des processeurs pour le produit matriciel

version 2 : granularité grosse Par pour i=1 à n faireprocessus : vecteur x matrice pour j=1 à n faire


C(i,j) C(i,j)+A(i,k)*B(k,j)

version 3 : granularité moyenne pour i=1 à n faireprocessus : vecteur x vecteur Par pour j=1 à n faire



version 4 : granularité fine pour i=1 à n faireprocessus : scalaire x scalaire pour j=1 à n faire

C(i,j) 0Par pour k=1 à n faire



27/09/2018

41

81

Nombre de multiplications et de communications pour le produit matriciel

Nombre de multiplications et de communications pour n=3Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

82

Ordonnancement

• Alternance entre les phases de calcul et de communication

• Congestion du réseau de communication réduit le débit

• Ordonnancement des processus de telle sorte que lorsque certains calculent les autres communiquent

Calcul

Communication

Calcul

Communication

Calcul

Calcul

p1p2

p3

p4

Exemple : 2 processeurs + 1 DMA


27/09/2018

42

83

Extensibilité (scalability)

0

20

40

60

80

100

1 2 3 4 5 6 7 8

Exercice : Déterminer le nombre optimal de processeurs pour ce temps d’exécution

processeurs

temps


84

Communication bloquante

Quand p0 envoie un message à p1, p0 ne peut continuer son exécution (traitement) que lorsqu’il reçoit un accusé de réception de p1

p0 p1

Envoyer (message)

Attendre(accusé)

Traitement

Recevoir (message)Envoyer (accusé)


27/09/2018

43

85

Interblocage

p0 p1

Envoyer (message 0)

Envoyer (message 1)

(1) Interbloquage

p0 p1

Envoyer (message 0)

Envoyer (message 1)

Recevoir (message 1)

(2) Solution

Recevoir (message 0)

Envoyer (accusé 0)

Envoyer (accusé 1)


Exercice : produit matriciel

Considérons le calcul matriciel de deux matrices d’ordre n.

a) Quelles sont les différentes manières d’effectuer ce calcul

b) Pour chaque cas trouvez :

• Le nombre des processeurs

• Le temps de calcul

• Le degré moyen de parallélisme


27/09/2018

44

Chapitre VApplications parallèles

• Environnement distribué• Installations d’OpenMP et MPI• OpenMP (Open MultiProcessing)

• Présentation d’OpenMP• Région parallèle• Synchronisation et exclusion mutuelle• Constructeurs de boucle• Clauses réduction

• MPI (Message Passing Interface)• Présentation de MPI• Communication (envoi et réception de messages)• Diffusion• Réduction

• Autres outils des applications parallèles• Multithreading en Java


88

Environnement distribué

Réseau de communication

Cray J916(6 processeurs)

Réseau local 1 Réseau local 2

P

P : poste de travail (PC, SIMD, MPP,...) sous un système d’exploitation (Unix, Linux, Windows, SunOS,…) utilisant des bibliothèque (OpenMP, MPI, …)

P P P P P P P


27/09/2018

45

Installations de OpenMP et MPI

• Unix : La majorité des éditions incluent dans leur noyau les commandes mpicc et mpirun de MPI et l’option de compilation –fopenmp d’OpenMP (https://www.ubuntu.com/download/desktop)

• Cygwin : Simulation d’un environnement UNIX sous Windows. Il faudrait installer openMP et mpi (https://cygwin.com/install.html)

• Vmware : Machine virtualisée permettant l’exécution d’applications sous des systèmes d’exploitation différents (Windows, Linux, OS,…)

• Eclipse : Utilisation de l’outil PTP (Parallel Tools Plateforme) sous Windows et Unix (https://www.youtube.com/watch?v=m9o0TGS1_80)


90

Installation des packages de CygWin

Compilateur et éditeur

g++ : gcc ++ GNU Compiler Collection

ssh : open ssl

make : devel/make the GNU version

vim : Editor/vim Vi IMproved

Biblithèques OpenMP et MPI

libopenmpi : C librairy

libopenmpi : devel librairy

openmpi : C librairy

libopenmpicxx1 : C++ librairy


27/09/2018

46

Exercice : Programme C sous Unix

// hello.c programme qui affiche ″Hello World″#include <stdio.h>void main() {

printf("Hello World!");}

Lancement de la compilation:$gcc hello.c (ou bien $gcc –o hello.exe hello.c)

Lancement de l’exécution:$./a (ou bien $./hello)

Affichage obtenu:$ Hello World!


Présentation d’OpenMP

• Historique : PVM (Parallel Virtual Machine) en 1991 et MPI-1(1994), MPICH2(2000) et OpenMP (1997)

• API (Application Programming Interface) pour les applications multithreads

• Standard composé d’un ensemble de directives au compilateur et de fonction de la bibliothèque pour les applications parallèles

• Simplifie l’écriture des multitreads pour les langages Fortran, C et C++

• Souvent utilisé dans des architectures à mémoire partagées

• Modèles d’exécution :

• SPMD (Single Programme Multiple Data) : Plusieurs threads exécutent le même programme tout en traitant partiellement ou totalement les données dépendamment de leur identificateur

• Constructeur et clauses associées aux directive (for, reduce,…)


27/09/2018

47

Architecture d’OpenMP


Modèle de programmation : Fork/Join


• Un thread maître (en rouge) peut créer un ensemble de threads : bifurquer (Fork)

• Plusieurs threads peuvent se ramener au thread maître : se joindre (Join)

• Alternance entre des régions séquentielles et des régions parallèles

• Le parallélisme peut être imbriqué (nested) : un thread peut créer d’autres threads

Séquentielle Parallèle Séquentielle Parallèle Séquentielle

Fork Join Fork Join

Fork Join

27/09/2018

48

Région parallèle


• Création des threads de la région parallèle grâce à la directive au compilateur :#pragma omp parallel

• Exemple de de création de 3 threads dans la région parallèle :double A[100]; // variable partagéeomp_set_threads_num(3); // initialisation du nb de threads#pragma omp parallel // directive de la région parallèle{ // début de la région parallèle

int ID = omp_get_thread_num(); // identification du threadcalculer(ID,A); // appel de la fonction

} // fin de la région parallèle

• Chaque thread exécute le bloc de la région parallèle et appelle la fonction calculer avec son numéro ou rang (ID = 0,1 et 2) qui est une variable privée.

• La directive peut inclure une clause : #pragma omp parallel num_threads(3)

Exercice


Ecrire le programme helloOMP.c qui reprend hello.c (exercice précédent).

1. Ajouter la directive de la création de la région parallèle (sans la directive d’initialisation du nombre de threads) et afficher le numéro du thread après le message. Compiler le programme ($gcc –fopenmp helloOMP.c) et l’exécuter.

2. Quel est le nombre total des threads générés ? Est-il le même que pour vos camarades ?

3. Quelle est la configuration matérielle de votre système ? Quel est le contenu des variables de l’environnement système ($env)

4. Qu’arrive-t-il après la commande ($export OMP_NUM_THREADS=3)?

5. Refaire une autre exécution. Que pouvez-vous constater par rapport à l’affichage de la première exécution ?

27/09/2018

49

Calcul séquentiel de Π


Considérons le calcul séquentiel de Π par intégration numérique :

où n est le nombre de pas

Algorithme séquentieln nombre de paspas 1/n, somme 0pour i=0 à (n – 1) faire

x (i + 0,5)*passomme somme + 4/(1 + x*x)

pi pas * sommeimprimer(pi)

1

4

2

Programme séquentiel de Π


/* fichier piSéquentiel.c version séquentielle du calcul de Pi par intégration* numérique de la fonction f(x) = 4/(1 + x*x) entre 0 et 1 */#include <stdio.h>#define N = 1000; // nombre de points à évaluermain (){

int i;double pas, x, pi, somme = 0.0;pas = 1.0/(double) N; // distance entre deux abscissesfor (i = 0; i < N; i++){ // considérer n points

x = (i + 0.5)*pas; // calculer l’abscisse à évaluersomme += 4.0/(1.0 + x*x);// accumuler les ordonnées dans somme

}pi = pas * somme; // trouver une approximation de piprintf("Pi=%20.19f ",pi);

}

27/09/2018

50

Exercice : Précision du calcul et optimisation


1. Comment pourriez-vous améliorer la précision de la valeur obtenue de Pi ?

2. Déterminer n pour que le calcul produit la valeur Pi avec 11 chiffres corrects après la virgule sachant que Pi25 = 3,141592653589793238462643.

3. Ecrire une version récursive de ce calcul. Faire attention à la granularité des threads.

4. Pi peut être calculé à partir de :

Comparer la précision de ce calcul par rapport au précédent.

5. En prenant n=109, estimer le temps d’exécution en utilisant la fonction clock() qui retourne le nombre de cycles d’horloge et la constante CLOCKS_PER_SEC de la bibliothèque <time.h>.

Exercice : Calcul parallèle de Π


1. Ecrire le programme piOMP.c qui est une version parallèle de piSéquentiel.c en utilisant la directive de création de la région parallèle et les fonctions de la bibliothèque (runtime library routines) :

int omp_get_num_threads(); // retourne le numéro du thread

int omp_get_thread_num(); // retourne le nombre de threads

Faire attention aux variables partagées par les threads ainsi qu’à leurs variables privées.

2. Estimer le temps d’exécution en utilisant la fonction de la bibliothèque :

double omp_get_wtime(); // retourne le temps en secondes

3. Estimer le temps d’exécution en variant le nombre de threads (1,2,…,16).

27/09/2018

51

Répartition du traitement aux threads


pour i=0 à N-1 faire calcul // algorithme séquentiel

Région parallèle // répartition R1nb nombre de threadsk numéro du threaddébut k*N/nbfin (k+1)*N/nbsi k=N-1 alors fin Npour i=début à fin-1 faire calcul

Région parallèle // répartition R2nb nombre de threadsk numéro du threadpour i=k à (N-1) pas=nb faire calcul

Exemple: N=14 et nb=3Itération Thread(R1) Thread(R2)

0 0 01 0 12 0 23 0 04 1 15 1 26 1 07 1 18 1 29 2 010 2 111 2 212 2 013 2 1

Exercice : Calcul parallèle de Π


1. Reprendre le programme piOMP.c et écrire une version où les tâches sont explicitement réparties aux threads.

2. Comparer le temps d’exécution de cette version avec la précédente.

27/09/2018

52

Synchronisation : Exclusion mutuelle


Impose des contrainte d’ordre afin de protéger l’accès aux variables partagéesPlusieurs types : critical, atomic,…La directive #pragma omp critical permet une exclusion mutuelle : un seul

thread à la fois peut entrer dans la région critique

float res;#pragma omp parallel{ float B; int i, id, nthrds;

id = omp_get_thread_num();nthrds = omp_get_num_threads();for (i=id; i<niters; i+nthrds){

B = big_job(i);#pragma omp critical

consume (B, res);}

}

Exercice : Exclusion mutuelle


Reprendre le programme piOpenMP et ajouter la directive afin de garantir un accès en exclusion mutuelle à la variable partagée somme.

27/09/2018

53

Constructeur de partage de traitement d’une boucle (loop worksharing construct)


for (i=0; i<N; i++) a[i] = a[i] + b[i]; // séquentiel

#pragma omp parallel // région parallèle{ int id, i, Nthrds, istart, iend;

id = omp_get_thread_num();Nthrds = omp_get_num_threads();istart = id * N / Nthrds;iend = (id+1) * N / Nthrds;if (id == Nthrds-1) iend = N;for (i=istart; i<iend ;i++) a[i]=a[i]+b[i];

}

#pragma omp parallel // région parallèle et constructeur#pragma omp // de boucle{ for(i=0; i<N; i++) { a[i] = a[i] + b[i];}

Clause de réduction


Clause de réduction : reduction (op : list)Inside a parallel or a work-sharing construct:– A local copy of each list variable is made and initialized depending on the

“op” (e.g. 0 for “+”).– Compiler finds standard reduction expressions containing “op” and uses

them to update the local copy.– Local copies are reduced into a single value and combined with the original

global value.The variables in “list” must be shared in the enclosingparallel region.

double ave=0.0, A[MAX]; int i;#pragma omp parallel for reduction (+:ave)

for (i=0;i< MAX; i++) { ave + = A[i]; }ave = ave/MAX;

Opérateurs dans C : +, *, -, &, |, ^, && et ||

27/09/2018

54

Programme OpenMP du calcul de Π


#include <stdio.h>#include <omp.h>static long N = 100000000; // nombre d'étapesint main(){

int i; double x, pi, somme = 0.0, pas, start_time, run_time;start_time = omp_get_wtime();pas = 1.0/(double) N;#pragma omp parallel for reduction (+:somme)for (i=0; i<N; i++){

x = (i + 0.5)*pas;somme += 4.0/(1.0 + x*x);

}pi = pas * somme;run_time = omp_get_wtime() - start_time;printf("Pi=%f temps écoulé=%f",pi, run_time);

}

Exercice :Comparaison des temps d’exécutions


Comparer les temps d’exécution des différentes version du calcut de Pi.

27/09/2018

55

Présentation de MPI

• Bibliothèque standard à inclure dans un programme C (#include "mpi.h") ou Fortran (INCLUDE ’mpif.h’)

• Plusieurs implantations : MPI-1(1994), MPICH2(2000) et OpenMPI(2009)

• Autres bibliothèques : OpenMP(2010),…

• Souvent utilisée dans des architectures à mémoire distribuée

• Modèle SPMD (Single Programme Multiple Data)

• Le même programme est installé dans chaque processeur (ou machine)

• Des instances multiples du programme traitent partiellement ou totalement les données

• Chaque instance a un identificateur unique par rapport à un communicateur

• L’instance exécute la partie du programme selon son identificateur

• Le traitement inclut le transferts de messages et la combinaison des résultats (Reduce)


Schéma général d’un programme MPI

rang identificateur du processus en cours par rapport à un communicateur

si (rang = identificateur_spécifique) alors

faire un traitement

sinon

faire un autre traitement

110

p0

p1

p2

p3

Communicateur


27/09/2018

56

Quelques commandes Unix

$pwd

$ls -l

$hostname

$mpirun -n 1 hostname (ou mpiexec -np 1 hostname)

$mpirun -n 7 hostname

$mpirun hostname

$mpirun -n 5 hello

$mpirun -n 12 hello

$mpirun -machinefile machine.txt -n 4 hostname


Quelques fonctions MPI (1/2)

112

int MPI_Init(int *argc, char ***argv)int MPI_Finalize()int MPI_Comm_rank(MPI_Comm comm, int *rank)int MPI_Comm_size(MPI_Comm comm, int *size)int MPI_Send(const void *buf, int count, MPI_Datatype datatype, int dest, int tag,

MPI_Comm comm)int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag,

MPI_Comm comm, MPI_Status *status)int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm)int MPI_Comm_group(MPI_Comm comm, MPI_Group *group)int MPI_Group_incl(MPI_Group group, int n, const int ranks[], MPI_Group *newgroup)int MPI_Comm_create(MPI_Comm comm, MPI_Group group,MPI_Comm *newcomm)int MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm)


27/09/2018

57

Quelques fonctions MPI (2/2)

113

int MPI_Reduce(void *sendbuf, void *recvbuf, int count,

MPI_Datatype datatype, MPI_Op op, int root,MPI_Comm comm)

Int MPI_Allreduce( void *sendbuf, void *recvbuf, int count,

MPI_Datatypedatatype, MPI_Opop, MPI_Commcomm )

Opérations :

MPI_MAX : maximum MPI_MIN : minimum

MPI_SUM : sum MPI_PROD : product

MPI_LAND : logical and MPI_BAND : bit-wise and

MPI_LOR : logical or MPI_BOR : bit-wise or

MPI_LXOR: logical xor MPI_BXOR : bit-wise xor

MPI_MAXLOC : max value + location MPI_MINLOC : min value + location

Liste complète (≈360 fonctions) : https://www.open-mpi.org/doc/v1.8


Exemples de programmes

• Communication entre processus

• Calcul de Π• Sommes partielles

• Vote électronique

• Synchronisation des événements (horloge de Lamport)

• Datation des événements


27/09/2018

58

Algorithme de communication

p nombre total de processusrang identificateur du processusdest 0si (rang ≠ 0) alors

message ″Hello world du processus ″ + rangenvoyer(message,dest)

sinonécrire(″Hello world du processus 0 : nombre de processus ″,p)pour source=1 à (p-1) faire

recevoir(message,source)écrire(message)

Exemple : p=4

115

p0

p2 p3p1


Programme de communication (1/3)

/* programme helloMPI.c*/#include <stdio.h>#include <string.h>#include "mpi.h"

int main(int argc, char* argv[]){int my_rank; /* rank of process */int p; /* number of processes */int source; /* rank of sender */int dest; /* rank of receiver */int tag=0; /* tag for messages */char message[100]; /* storage for message */MPI_Status status ; /* return status for receive */


27/09/2018

59


/* start up MPI */MPI_Init(&argc, &argv);

/* find out process rank */

MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

/* find out number of processes */

MPI_Comm_size(MPI_COMM_WORLD, &p);

if (my_rank !=0){

/* create message */

sprintf(message, "Hello MPI World from process %d!", my_rank);

dest = 0;

/* use strlen+1 so that '\0' get transmitted */

MPI_Send(message, strlen(message)+1, MPI_CHAR,dest, tag,MPI_COMM_WORLD);

}117Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018


else{printf("Hello MPI World From process 0: Num processes: %d\n",p);for (source = 1; source < p; source++) {

MPI_Recv(message, 100, MPI_CHAR, source, tag,MPI_COMM_WORLD, &status);

printf("%s\n",message);}

}

/* shut down MPI */MPI_Finalize();return 0;

}


27/09/2018

60

Exercice : Programme de communication

a) Création de Exemple1.cprogramme de communication précédent

b) Compilation de Exemple1.c$mpicc -o Exemple1.exe Exemple1.c

c) Exécution de Exemple1.c$mpirun -n 5 Exemple1.exe

d) Création de Exemple2.csupprimer les appels MPI_Sendexécuter le programmeQue se passe-t-il (utiliser la commande top et supprimer les processus)?

e) Création de Exemple3.csupprimer les appels MPI_Sendsupprimer la boucle lorsque my-rank=0 (processus p0)remplacer sprintf par printf (un affichage par processus)exécuter le programme à 2 reprises. Que se passe-t-il ?


Algorithme du calcul de ΠΠΠΠCalc_pi(rank, num_procs)

si (rank = 0) alorsnum_intervals 1000pour s=1 à num_procsfaire envoyer(0,s,num_procs)

h 1/num_intervalssum0pour i = rank + 1à num_intervalspasnum_procsfaire

x=h * (i – 0,5)sum = sum + 4*racine_carrée(1 – x2)

mypi = h* sumsi (rank≠ 0) alors envoyer(rank,0,mypi)sinon

pour s=1 à num_procsfairerecevoir(pi)sum += pi

écrire(″PI=″, sum*h)120Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

27/09/2018

61

Diffusion et réduction

Calc_pi(rank, num_procs)si (rank = 0) alors

num_intervals 1000diffuser(num_intervals)h 1/num_intervalssum0pour i = rank + 1à num_intervalspasnum_procs

x=h * (i – 0,5)sum = sum + 4*racine_carrée(1 – x2)

mypi = h* sumreduce(mypi,pi,sum)si (rank = 0) alors écrire(″PI=″, pi)


Schéma du calcul de ΠΠΠΠ

Hypothèse :

num_procs = 3 (p0, p1 et p2)num_intervals =10 donc h = 0,1

p0 calcule les valeursx=0,05, x=0,35, x=0,65 et x=0,95

p1 calcule les valeursx=0,15, x=0,45 et x=0,75

p2 calcule les valeursx=0,25, x=0,55 et x=0,85

122

p0 p1 p2 p0 p1 p2 p0p1 p2 p0

1

1


27/09/2018

62

Programme du calcul de ΠΠΠΠ (1/3)

/* fichier piMPI.c */#include <mpi.h>#include <stdio.h>void calc_pi(int rank, int num_procs){

int i, num_intervals;double h, mypi, pi, sum, x;

/* set number of intervals to calculate */if (rank == 0) {

num_intervals = 1000000000;}

/* tell other tasks how many intervals */MPI_Bcast(&num_intervals, 1, MPI_INT, 0, MPI_COMM_WORLD);



124

/* now everyone does their calculation */h = 1.0 / (double) num_intervals;sum = 0.0;for (i = rank + 1; i <= num_intervals; i += num_procs) {

x = h * ((double)i - 0.5);sum += (4.0 /(1.0 - x*x));

}mypi = h * sum;

/* combine everyone's calculations */MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,MPI_COMM_WORLD);if (rank == 0) {

printf("PI is approximately %.16f\n", pi);}

}


27/09/2018

63


125

int main(int argc, char *argv[]) {int my_rank; /* rank of process */int num_procs; /* number of processes */

MPI_Init(&argc, &argv); /* start up MPI */MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); /* find out process rank */MPI_Comm_size(MPI_COMM_WORLD, &num_procs); /* number of processes */calc_pi(my_rank, num_procs); /* calculate PI */

MPI_Finalize(); /* shut down MPI */return 0;

}


Exercice : Programme du calcul de ΠΠΠΠ

a) Création de MPIPi1.cprogramme ΠΠΠΠ précédent

b) Compilation et exécution de MPIPi1.c

$mpicc -o MPIPi1.exe MPIPi1.c –lm

$mpirun -n 4 MPIPi1.exe

c) Création de MPIPi2.c

augmenter le nombre d’intervalles

d) Création de MPIPi3.c tel que Π = 4 * ∫ dx/(1 + x2)

e) Quelle est la version qui donne les meilleures précisions relativement à num_intervals réduit sachant que les 25 chiffres de ΠΠΠΠ sont :

Pi25 = 3,141592653589793238462643f) Déterminer le temps d’exécution des deux versions en utilisant MPI_Wtime()

126

0

1


27/09/2018

64

Exercice 1 : Sommes partielles

Considérez l’algorithme de la première affectation du calcul des sommes partielles :

Par pour k=0 à 7 fairepour i = 32k à (32k + 31) faire

S(i) a(0)

pour j = 1 à i faire

S(i) S(i) + a(j)

a) Traduire cet algorithme en un programme SPMD en utilisant les fonctions MPIoù a =(2,3,6,9,4,7,0,2,2,6,8,9,11,0,2,4).

b) Afficher les calculs des processus selon la forme suivante :

<numéro du processus> : S(<indice>)=<valeur calculée>

c) Modifier le programme pour qu’il puisse être exécuté avec 1,2 , 4, 8 et 16 processus.

d) Afficher le temps de traitement des processus sachant que a est un vecteur de 100 000 éléments tel que a(i)=i. Que pouvez-vous dire des temps d’exécution ?


Exercice 2 : Sommes partielles

Reprenez les mêmes questions que l’exercice précédent et cette fois-ci pour l’algorithme de la deuxième affectation du calcul des sommes partielles :

Par pour k=0 à 7 fairepour i=16k à 16k+15 et i=(240 - 16k) à (255 - 16k) faire

S(i) a(0)

pour j = 1 à i faire

S(i) S(i) + a(j)


27/09/2018

65

Fonctions MPI_Reduce

MPI_Reduce( void* send_data, void* recv_data, int count, MPI_Datatypedatatype, MPI_Op op, int root, MPI_Comm communicator)

129

MPI_MAX - Returns the maximum element. MPI_MIN - Returns the minimum element. MPI_SUM - Sums the elements. MPI_PROD - Multiplies all elements. MPI_LAND - Performs a logicaland across the elements. MPI_LOR - Performs a logicalor across the elements. MPI_BAND - Performs a bitwiseand across the bits of the elements. MPI_BOR - Performs a bitwiseor across the bits of the elements. MPI_MAXLOC - Returns the maximum value and the rank of the process that

owns it. MPI_MINLOC - Returns the minimum value and the rank of the process thatowns it.


Exemples MPI_Reduce


27/09/2018

66

Fonction MPI_Allreduce

MPI_Allreduce( void* send_data, void* recv_data, int count, MPI_Datatypedatatype, MPI_Op op, MPI_Comm communicator)


Algorithme de vote électronique

getVote(candidateNum)candidate valeur aléatoire entre 0 et CandidatNumreturn candidate

DPoll(candidateNum)rank identificateur du processuspour i=0 à candidateNumfaire

vote[i] 0vote [getVote(candidateNum)] 1Allreduce(vote, result, Somme)pour i=0 à candidateNumfaire

afficher (rank,vote[i],result[i])

Exercice : Faire la trace pour candidatNum = 3 et proceesNum = 9132Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

27/09/2018

67

programme de vote électronique (1/2)

#include <stdio.h>#include <mpi.h>#include <stdlib.h>

// return random value between 0 and CandidateNumint getVote(int germe, int candidateNum){

int candidate;srand(germe);candidate = (rand() % (candidateNum + 1));return candidate;

}


programme de vote électronique (2/2)

Int main(int argc, char *argv[]) {const int candidateNum=3;int i, rank,

vote[candidateNum + 1], // vote du processusresult[candidateNum + 1]; // résultat du vote

MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD, &rank);for (i=0; i <= candidateNum; i++) vote[i]=0;

vote [getVote(rank, candidateNum)]=1;MPI_Allreduce(&vote, &result, candidateNum+1, MPI_INT, MPI_SUM,

MPI_COMM_WORLD);for (i=0; i <= candidateNum; i++)

printf("rank=%d vote[%d]=%d result[%d]=%d\n",rank,i,vote[i],i,result[i]);MPI_Finalize();return 0;


27/09/2018

68

Exercice : Sommes partielles

Soit l’algorithme suivants :p nombre de processeursrang identificateur du processussomme a(rang)pour i = 0 à (log(p) – 1) faire

pas 2**isi (rang < n – pas) alors

envoyer(somme, rang + pas)si (rang > pas) alors

recevoir(A, rang - pas)somme somme + A

écrire(" Somme partielle du processeur :", rang, " = " ,somme)

Faire la trace pour a =(2,3,6,9,4,7,0,2,2,6,8,9,11,0,2,4) et programmer cet algorithme en utilisant MPI.


Exercice (1/2)

a) Corriger le programme de la page suivante.

b) Quel est le résultat de son exécution ?

c) Que calcule-t-il ?

d) Expliquer le type de granularité.

e) Modifier le programme pour augmenter la granularité.

f) Estimer le temps d’exécution.


27/09/2018

69

Exercice (2/2)

main(int argc, char **argv) {int myrank, size, k, order, row, column, sum;MPI_Init (&argc, &argv);MPI_Comm_rank (MPI_COMM_WORLD, &myrank);MPI_Comm_size (MPI_COMM_WORLD, &size);

order = sqrt(size);row = myrank / order;column = myrank % order;

sum = 0;for (k=0; k<order; k++) sum = sum + (row + k) * (k - column);printf("[processus : %d]: c(%d,%d) = %d\n",myrank,row,column,sum);MPI_Finalize();


Exercice

Soient deux vecteurs a=(a0,a1,…,an-1) et b=(b0,b1,…,bn-1) avec n=2m (m ∈ N+). Nous voulons calculer le produit scalaire S = a0* b0 + a1* b1 + … + an-1* bn-1

a) Ecrire un algorithme SPMD où le processus pk lit ak et bk, calcule le produit ak * bk et l’envoie à p0 qui calcule la somme S et l’affiche.

b) Récrire l’algorithme en remplaçant les envois et réceptions par Reduce.c) Afin d’augmenter la granularité et en ayant m processeurs, réécrire l’algorithme selon

l’affectation suivante :p0 calcule le produit scalaire partiel : de l’indice 0 à l’indice 1.pk calcule le produit scalaire partiel : de l’indice 2k à l’indice 2k+1 – 1 (0 < k < m).

d) Faire la trace pour n=16 de ce dernier algorithme et déduire le degré de parallélisme sachant que le temps d’exécution est proportionnel au nombre de multiplications (temps d’addition et de transfert sont négligeables devant la multiplication).

e) Tout en ayant m processeurs, trouver une affectation qui permet l’équilibrage de charge. Calculer son degré de parallélisme en supposant que m=2i (i ∈ N+). En déduire le degré de parallélisme quand n=16.

f) Ecrire un programme SPMD de cette deuxième affectation et faire la trace pour n=16.138Systèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

27/09/2018

70

139

Synchronisation des événements


p0

p1

p2

Hypothèse : ressources partagées dans un système répartipk : processus k ( 0 ≤ k < n)eki : événement i du processus k (0 ≤ i < nk)les processus peuvent échanger des massages (envoi ou réception)

Problème : dater tous les événements avec une seule horloge logique

Exemple : k = 3 et nk = 5

e00 e01 e02 e03 e04

e14e10 e11 e12 e13

e20 e21 e22 e23 e24

140

Horloge logique de Lamport


p0

p1

p2

- initialisation de Hi à 0

- A chaque événement e su site : Hi := Hi + 1 et e est daté par Hi

- A chaque envoi de message m, la date Hi du site est envoyée avec le message

- A la réception d’un message avec la date Hj, Hi := max (Hi, Hj) + 1

1 2 3 4 8

82 3 6 7

1 2 3 4 5

1 2 3 4 8

82 3 6 7

1 2 3 4 5

27/09/2018

71

141

Représentation des événements


eki contient :j s’il envoie un message au processus jj+3 s’il reçoit un message du processus jk si l’événement n’envoie ni reçoit de message

Exemples : e00 = 1, e01= 2, e02 = 0, e03 = 5 et e04 = 4p0 = {1,2,0,5,4}p1 = {3,5,5,0,1}p2 = {1,2,0,3,1}événement = {p0,p1,p2}

142

Algorithme de datation

datation : tableau d’une dimension de l’ordre partiel d’un processusdatationPart : tableau de 2 dimensions de l’ordre partiel de tous les processusdatationTot : tableau de 2 dimensions de l’ordre total de tous les processus

Événement={ {1,2,0,5,4}{3,5,5,0,1}{1,2,0,3,1}}

k rang du processusdatationPartielle(evenement(k),k,datation)Assembler(datation,datationPart,0)si (k=0) alors

datationTotale(datationPar,datationTot)Diffuser(datationTot,0)


27/09/2018

72

143

Datation Partielle

fonction datationPartielle(processus, k, datation)H 0pour i = 0 à 4 faire

e processus(i)si (e=k) alors

H++sinon si(e < 3) alors

H++destination eenvoyer(H,destination)

sinonsource e – 3recevoir(D,source)H max(H,D) + 1

datation(i) HSystèmes et traitements parallèles, M. Eleuldj, EMI, Octobre 2018

144

Datation Partielle 2

fonction datationPartielle(processus, k, datation)H 0pour i = 0 à 4 faire

e processus(i)H++si (e < 3 et e ≠ k) alors

destination eenvoyer(H,destination)

sinonsource e – 3recevoir(D,source)si D ≥ H alors H D + 1

datation(i) H


27/09/2018

73

145

Datation Totale

fonction datationTotale(datationPart, datationTot)i0 0, i1 0, i2 0pour H=1 à 15 faire

indice positionMin(datationPart(0,i0),datationPart(1,i1), datationPart(2,i2))

si (indice=0) alorsdatationTot(0,i0) Hi0++

si (indice=1) alorsdatationTot(1,i1) Hi1++

sinondatationTot(2,i2) Hi2++


146

Multithreading en Java

public class MaTache extends Thread {

public MaTache() {

start();

}

public void run() {

System.out.println("Hello World");

}

public static void main(Stringch[] args){

MaTache t1 = new MaTache();

MaTache t2 = new MaTache();

}

}


Documents

Systèmes et traitements parallèleseleuldj/Cours/Arc_Par/STP Support 2018.pdf · devant le temps de ces opérations, estimez le temps d’exécution de l’évaluation de p(x 0)