Une introduction à OpenMP

Franck Cappello
INRIA – LRI, Université Paris sud

Certains transparents proviennent du cours

de Marc Snir

1
 Quelques pointeurs

• Le site officiel du ‘standard’ OpenMP

(en Anglais)
– [Link]

• Les cours de l’IDRIS (en Français)

– [Link]

2
 Sommaire

• Introduction
• L’API OpenMP
– Les directives
– Bibliothèque de fonctions
– Variables d’environnement
• Un petit exemple
• Quelques difficultés
• Conclusion

3
 Multithreading en mémoire partagée (1)

• Le problème :
– On dispose de n processeurs
– Ces machines sont connectées d’un mécanisme de mémoire
partagée entre eux

 Comment utiliser cette machine à n processeurs reliés par

de la mémoire partagée ?

CPU CPU CPU CPU CPU CPU CPU

RAM (partagée)

4
 Multithreading en mémoire partagée (2)

• Une réponse : le multithreading en mémoire partagée

– Faire exécuter un processus qui va spawner des threads (flots
d’exécution) sur chaque processeur
– Effectuer des échanges de données de façon transparente via la
mémoire partagée
– Synchroniser explicitement au besoin, par exemple avec des
verrous (locks)

• Le modèle le plus simple pour l’utilisateur paraît être

d’ouvrir/fermer les sections parallèles en fonction des
besoins et de la possibilité de paralléliser

5
 Origine d’OpenMP
Propriétés requises pour un environnement de programmation parallèle :
• portable
• extensible
• efficace
• programmation de haut niveau
• facilite le parallélisme de données
• relativement simple à utiliser (pour les codes existants et les nouveaux)

Environnements existants
• Bibliothèque de Threads bas niveau
• Win32 API, Posix thread.
• Bibliothèque de passage de messages
• MPI, PVM
• Langages de haut niveau
• HPF, Fortran D, approche orienté objet
• Directives de compilateur
• Un compilateur par constructeur.
• Initiative X3H5 vers la définition d’un standard AINSI
6
 OpenMP : Introduction
OpenMP:C$OMP
uneFLUSH
API pour#pragma
écrire omp
des critical
Applications
C$OMP THREADPRIVATE(/ABC/)
Multithread (spécification de 1997)
CALL OMP_SET_NUM_THREADS(10)
C$OMP parallel do shared(a, b, c)
• Un ensemble de directives call omp_test_lock(jlok)
de compilation et une
call OMP_INIT_LOCK (ilok)
bibliothèque de fonctions C$OMP MASTER
C$OMP ATOMIC
C$OMP SINGLE• PRIVATE(X)
Facilite la création de programmes multi-thread
(MT) Fortran, setenv OMP_SCHEDULE “dynamic”
C and C++
C$OMP PARALLEL DO ORDERED
• Standardise la PRIVATE (A,laB,
pratique de C)
programmation
C$OMPdes
ORDERED
machines
C$OMP PARALLEL SMP des
REDUCTION (+: 15
A,dernières années
C$OMP
B) SECTIONS
#pragma omp parallel for private(A, B) !$OMP BARRIER
Défendu
C$OMP par -les
PARALLEL principaux constructeurs
COPYIN(/blk/) C$OMP DO lastprivate(XX)
-les vendeurs de logiciels (compilateurs entre autres)
Nthrds =-les
OMP_GET_NUM_PROCS()
vendeurs d ’applications
omp_set_lock(lck)
7
 Mode de programmation
OpenMP est utilisé « principalement » pour
paralléliser les boucles :
• Trouver les boucles les plus coûteuses en temps
• Distribuer leurs itérations sur plusieurs threads.

Eclater cette boucle vers

plusieurs threads
void main() void main()
{ {
double Res[1000]; double Res[1000];
#pragma omp parallel for
for(int i=0;i<1000;i++) { for(int i=0;i<1000;i++) {
do_huge_comp(Res[i]); do_huge_comp(Res[i]);
} }
} }
Programme Séquentiel Programme Parallèle 8
 OpenMP : Modèle d’exécution
Parallélisme Fork-Join :
Le thread Maître lance une équipe de threads selon les
besoins (région parallèle).
Le parallélisme est introduit de façon incrémentale ; le
programme séquentiel évolue vers un prog. parallèle

Thread
Maître

Régions parallèles
9
 Modèle abstrait Fork-Join !=
appels Unix fork-join
Modèle
abstrait

Implementation
possible

10
 Two-level scheduling
Compiler typically translates task into a procedure invocation

Compiler generated tasks

A shared workpile can be used to allocate

Are mapped by runtime to
tasks (= function pointer+arguments) to
threads
User/system threads

Team typically consists of fixed number of

Are scheduled by OS to threads; OpenMP also supports requests to
change team size
Machine processors
OS may support gang scheduling and affinity scheduling; one may be
able to get a set of (mostly) dedicated processors

11
 Implémentation possible
Le maître Le thread Le thread maître Le thread
exécute le maître exécute des taches de maître
code insère des la pile. Si elle est vide, il exécute le
séquentiel taches dans attend la terminaison code
la pile de par les autres threads séquentiel
taches

Un environnement possible d’exécution

Les threads esclaves exécutent la boucle : {prendre tâche dans la pile; exécuter la tâche}

12
 OpenMP : détails de syntaxe
• La plupart des constructeurs OpenMP sont des directives en
commentaires (ou pramas).
– C et C++ :
#pragma omp construct [clause [clause]…]
– Fortran :
C$OMP construct [clause [clause]…]
!$OMP construct [clause [clause]…]
*$OMP construct [clause [clause]…]
• Un programme OpenMP peut être compilé par un
compilateur non OpenMP
• Les compilateurs OpenMP offrent généralement la
possibilité de compiler un programme sans interpréter les
directives OpenMP (permet la comparaison rapide entre
parallélisation automatique et parallélisation par directives)
13
 OpenMP : blocks de base
Les constructeurs OpenMP s’appliquent à des blocs structurés.
Un bloc structuré : un bloc de code avec un seul point d’entrée (au début
du bloc) et un seul point de sortie (à la fin du bloc).
if(conv(res(id))goto 30
!$OMP PARALLEL !$OMP PARALLEL
10 wrk(id) = garbage(id) 10 wrk(id) = garbage(id)
res(id) = wrk(id)**2 30 res(id)=wrk(id)**2
if(conv(res(id)) goto 10 if(conv(res(id))goto 20
!$OMP END PARALLEL go to 10
print *,id !$OMP END PARALLEL
if(not_DONE) goto 30
20 print *, id

Un bloc structuré Un bloc non structuré

14
 L ’API OpenMP
• Les constructeurs OpenMP :
– Les régions parallèles
– La distribution du calcul
– L’environnement de données
– La synchronisation

• Bibliothèque de fonctions
• Variables d’environnement

15
 Les régions parallèles
Les threads sont créés avec la directive “omp parallel”.
!$OMP PARALLEL [CLAUSE[[,] CLAUSE]...]
…
!$OMP END PARALLEL
Par exemple, pour créer région Parallèle à 4 threads :
Chaque thread double A[1000];
exécute de omp_set_num_threads(4);
manière #pragma omp parallel
redondante le {
code à
int ID = omp_thread_num();
l’intérieur du
fonc(ID,A);
bloc structuré
} Tous les threads attendent ici les autres
threads avant de continuer (barrier)

Chaque thread appelle fonc(ID,A) avec ID différent 16

 Les régions parallèles
double A[1000];
Tous les threads exécutent le omp_set_num_threads(4);
même code.
#pragma omp parallel
{
int ID = omp_thread_num();
double A[1000]; fonc(ID, A);
}
omp_set_num_threads(4) printf(“fin\n”);

Une seule
copie de A fonc(0,A) fonc(1,A) fonc(2,A) fonc(3,A)
est partagée
entre tous les
threads.
Tous les threads attendent ici les autres
printf(“fin\n”); threads avant de continuer (barrier)

17
 Distribution du calcul
Les constructeurs“for” pour C et C++ et “do” pour Fortran
distribuent les itérations de la boucle sur les différents threads de
l’équipe
!$OMP DO [CLAUSE[[,]CLAUSE]...]
boucle DO
!$OMP ENDO
Exemple de code for(i=0;I<N;i++) { a[i] = a[i] + b[i] ; }
séquentiel

Constructeur
OpenMP pour #pragma omp parallel
région parallèle #pragma omp for
et distribution
for(i=0;I<N;i++) { a[i] = a[i] + b[i] ; }
du calcul

Par défaut, il y a une barrier à la fin de la

boucle. La clause “nowait” élimine la barrière 18
Distribution des itérations sur les threads
!$OMP DO
SCHEDULE(type[,CHUNK])
• La clause schedule définit comment les iterations de la boucle sont placées sur
les threads
– schedule(static [,chunk])
– distribue des blocs d ’itérations de taille “chunk” sur chaque thread.
– schedule(dynamic[,chunk])
– Chaque thread collecte dynamiquement “chunk” iterations dans
une queue jusqu’à ce que toutes les itérations soient exécutées.
– schedule(guided[,chunk])
– Les threads collectent dynamiquement des blocs d ’itérations. La
taille des blocs diminue selon une fonction exponentielle jusqu ’à
la taille chunk.
– schedule(runtime)
– Le mode de distribution et la taille des blocs sont définis par la
variable d ’environnement OMP_SCHEDULE.
19
 Distribution du calcul
Le constructeur Sections attribue à chaque thread un
bloc structuré différent. Programmation MPMD.
!$OMP SECTION [CLAUSE[[,] CLAUSE]...]

#pragma omp parallel

#pragma omp sections
{
X_calculation();
#pragma omp section
y_calculation();
#pragma omp section
z_calculation();
}
Par défaut, il y a une « barrier » à la fin du bloc
“section”. La clause “nowait” élimine la barrière 20
 Portée des constructeurs OpenMP
La portée (champ d ’application) des constructeurs OpenMP
s’étend au delà des frontières de fichiers sources.

titi.f
toto.f
subroutine tata
C$OMP PARALLEL
+ external omp_get_thread_num
call tata
integer iam, omp_get_thread_num
C$OMP END PARALLEL
iam = omp_get_thread_num()
C$OMP CRITICAL
Portée Portée print*,’De la part de ‘, iam
Statique Dynamique des C$OMP END CRITICAL
des régions Directives orphelines
régions parallèles return
parallèles peuvent apparaître à
end l’extérieur des
régions parallèles

21
 Environnement de données
Modèle de programmation à mémoire partagée :
La plupart des variables sont partagées par défaut

Les variables globales sont partagées par les threads

Fortran: blocs COMMON, variables SAVE et MODULE
C: variables de fichier, static
Tout n’est pas partagé
Les variables de la pile des fonctions appelées à l’intérieur d’une section
parallèle sont privées

!$OMP PARALLEL [CLAUSE[[,] CLAUSE]...]

!$OMP DO [CLAUSE[[,]CLAUSE]...]
!$OMP SECTION [CLAUSE[[,] CLAUSE]...]
22
 Environnement de données
attributs par défaut
program tri subroutine toto
common /input/ A(10) real temp(10)
integer index(10)
call input …………
!$OMP PARALLEL
call toto(index)
!$OMP END PARALLEL
print*, index(1)
A, index

A, et index sont
partagés par tous les temp temp temp
threads.
temp est local à
chaque thread A, index
23
 Environnement de données
Changer l’attribut de stockage
• Les clauses suivantes modifient l’attribut de stockage :
• SHARED
• PRIVATE
• FIRSTPRIVATE
• THREADPRIVATE
• Une valeur privée à l’intérieur d’une boucle parallèle
peut être transmise à une valeur globale à la fin de la
boucle :
• LASTPRIVATE
• l’attribut par défaut peut être chargé :
• DEFAULT (PRIVATE | SHARED | NONE)
toutes les clauses s’appliquent aux régions parallèles et aux constructeurs de
distribution du calcul sauf “shared” qui concerne seulement les régions parallèles
24
 Réduction
!$OMP PARALLEL REDUCTION({opér., intr.}:liste)
!$OMP DO REDUCTION ({opér., intr.}:liste)

• La clause “reduction” permet de réaliser une opération de

réduction sur une variable:
• reduction (op : liste) op : +, -, *, max, min, or, etc.
• Les variables dans la liste doivent être des scalaires partagés à
l’intérieur d’une région parallèle.
• Utilisable dans les directives “parallel” et de distribution
de calcul :
• Une copie locale de chaque variable dans la liste est attribuée à
chaque thread et initialisée selon l’opération à réaliser (0 pour “+”)
• Les réductions intermédiaires sur chaque thread sont “visibles” en
local
• Les copies locales sont réduites dans une seule variable globale à la
fin de la section. 25
 Exemple de réduction

#include <omp.h>
#define NUM_THREADS 2
void main ()
{
int i;
double ZZ, func(), res=0.0;
omp_set_num_threads(NUM_THREADS)
#pragma omp parallel for reduction(+:res) private(ZZ)
for (i=0; i< 1000; i++){
ZZ = func(I);
res = res + ZZ;
}
}

26
Trace d’une matrice (1)
 Calcul de la trace d’une matrice An

 Rappel : la trace d’une matrice est la somme des éléments de sa diagonale

(matrice nécessairement carrée)

& n #
 Mathématiquement, on sait que : Trace( A) = $ ' Ak , k !
% k =1 "
 Immédiatement, on voit facilement que le problème peut être parallélisé en
calculant la somme des éléments diagonaux sur plusieurs processeurs puis
en utilisant une réduction pour calculer la trace globale

20/01/09 27
 Trace d’une matrice (2)
#include <stdio.h> printf("La trace de A est : %f \n",
#include <omp.h> traceA);
}
void main(int argc, char ** argv) {
int me, np, root=0;
int N; /* On suppose que N = m*np */
double A[N][N];
double traceA = 0;

/* Initialisation de A */
/* … */
#pragma omp parallel default(shared)
#pragma omp for reduction(+:trace) {
for (i=0; i<N; i++) {
traceA += A[i][i]
}
}

20/01/09 28
subroutine jacobi
(n,m,dx,dy,alpha,omega,u,f,tol,maxit)
... Un exemple
!$omp parallel
!$omp do
do j=1,m
do i=1,n
uold(i,j) = u(i,j)
enddo
enddo
!$omp enddo
* Compute stencil, residual, & update
!$omp do private(resid) reduction(+:error)
do j = 2,m-1
do i = 2,n-1
resid = (ax*(uold(i-1,j) + uold(i+1,j))
& + ay*(uold(i,j-1) + uold(i,j+1))
& + b * uold(i,j) - f(i,j))/b
* Update solution
u(i,j) = uold(i,j) - omega * resid
* Accumulate residual error
error = error + resid*resid
end do
enddo
!$omp enddo
!$omp end parallel
29
 Synchronisation

OpenMP possède les constructeurs suivants

pour les opérations de synchronisation
• atomic
• critical section
• barrier
• flush
• ordered
• single Pas vraiment des opérations
de synchronisation
• master

30
 Synchronisation

• Atomic est un cas spécial de section critique qui peut

être utilisé pour certaines opérations simples.
• Elle s’applique seulement dans le cadre d’une mise à
jour d’une case mémoire

!$OMP PARALLEL PRIVATE(B)

B = DOIT(I)
!$OMP ATOMIC
X=X+B
!$OMP END PARALLEL

31
 Synchronisation

Un seul thread à la fois peut entrer dans une

section critique (critical)

!$OMP PARALLEL DO PRIVATE(B)

!$OMP& SHARED(RES)
DO 100 I=1,NITERS
B = DOIT(I)
!$OMP CRITICAL
CALL COMBINE (B, RES)
!$OMP END CRITICAL
100 CONTINUE
!$OMP END PARALLEL DO

32
 Synchronisation
BARRIER tous les thread attendent que les autres threads arrivent
au même point d ’exécution avant de continuer

#pragma omp parallel shared (A, B, C) private(id)

{
id=omp_get_thread_num();
Barrière implicite à la
A[id] = big_calc1(id);
fin de la construction
#pragma omp barrier
omp for
#pragma omp for
for(i=0;i<N;i++){C[i]=big_calc3(I,A);}
#pragma omp for nowait
for(i=0;i<N;i++){ B[i]=big_calc2(C, i); }
A[id] = big_calc3(id);
} Pas de barrière
implicit barrier at the end
of a parallel region implicite nowait
33
 Synchronisation : flush
• Exemple d’utilisation de flush (consistance mémoire)

!$OMP PARALLEL SECTIONS ICOUNT = 0

A=B+C !$OMP PARALLEL SECTIONS
!$OMP SECTION A=B+C
B=A+C ICOUNT = 1
!$OMP SECTION !$OMP FLUSH ICOUNT
C=B+A !$OMP SECTION
!$OMP END PARALLEL SECTIONS 1000 CONTINUE
!$OMP FLUSH ICOUNT
IF(ICOUNT .LT. 1) GO TO 1000
B=A+C
ICOUNT = 2
!$OMP FLUSH ICOUNT
!$OMP SECTION
2000 CONTINUE
!$OMP FLUSH ICOUNT
IF(ICOUNT .LT. 2) GO TO 2000
C=B+A
!$OMP END PARALLEL SECTIONS
34
 Synchronisation : SINGLE / MASTER

• Ces directives permettent d’assurer que le code n’est

exécute que par un seul thread

• Dans le cas de SINGLE, c’est le premier thread qui atteint

la zone considérée qui procède à l’exécution

• Dans le cas de MASTER, c’est toujours le thread maître

(de rang 0) qui exécute la tache

35
 Coût des synchronisations
mesures sur IBM SP3 NH1(SDSC), compilateur IBM

36
 Balance : taille de régions parallèles
VS nombre de synchronisations
Problème Augmenter la taille de la ou des régions
de performance parallèles :
-> plus de code « scallable »
-> moins de « fork & join »
mais plus de variables partagées

Augmentation du nombre de
synchronisations dans la région -Baisse de performance
parallèle OU
-Développement plus long
Utilisation de variables
supplémentaires
Etude au cas par cas (pas d’outils)
37
 Problèmes d’extensibilité
• Mode de programmation (grain)
J. Levesque (ACTC IBM), présentation a SCIComp 2K

Comparison of OpenMP Techniques

12
3-D Finite Difference Code
Limite de l ’extensibilité 10
Nighthawk 1
de l ’approche « loop level
8
parallelization » par rapport

Y-Axis
DO
à l ’approche SPMD. 6
SPMD

0
1 2 3 4 5 6 7 8
X-Axis

• Limite Architecture/Système
De nombreux programmes OpenMP n’étaient pas
extensibles sur l ’Origin 2000 (migration de pages) 38
 Fonctions de bibliothèque
Fonctions relatives aux verrous
– omp_init_lock(), omp_set_lock(), omp_unset_lock(),
omp_test_lock()
Fonctions de l’environnent d’exécution
• Modifier/vérifier le nombre de threads
– omp_set_num_threads(), omp_get_num_threads(),
omp_get_thread_num(), omp_get_max_threads()
• Autoriser ou pas l’imbrication des régions parallèles et l’ajustement
dynamique du nombre de threads dans les régions parallèles
– omp_set_nested(), omp_set_dynamic(), omp_get_nested(),
omp_get_dynamic()
• Tester si le programme est actuellement dans une région parallèle
– omp_in_parallel()
• Combien y a t-il de processeurs dans le système
– omp_num_procs()

39
 Variables d’environnement
Contrôler comment les itérations de boucle sont ordonnancées.
OMP_SCHEDULE “schedule[, chunk_size]”
Positionner le nombre de threads par défaut.
OMP_NUM_THREADS int_literal
Indiquer si le programme peut utiliser un nombre variable de
threads selon la région parallèle
OMP_DYNAMIC TRUE || FALSE
Indiquer si les régions parallèles imbriquées vont créer de
nouvelles équipes de threads ou si les régions imbriquées seront
sérialisées
OMP_NESTED TRUE || FALSE

40
 Conclusion
• Modèle de programmation parallèle simple,
portable.
• Attention aux performances
• OpenMP3 : orienté tâche
• Recherche : introduction des directives de
distribution de données (entre autres)

41
Une difficulté : éviter le false sharing
do j=1,10...
omp parallel do schedule(static)
Hypothèses : 2 threads
do i=1,10 u(10,10)
uold(j,i) = u(j,i) u(x,y) -> 64 bits float
omp end parallel
32 Octets
8 octets
3,1 3,2 3,3 3,4
2,7 2,8 2,9 2,10
uold 2,3 2,4 2,5 2,6
1,9 1,10 2,1 2,2 Faux partage
en mémoire
1,5 1,6 1,7 1,8
1,1 1,2 1,3 1,4 ligne de cache
1) redimensionner les tableaux u et uold (calculs non pertinents)
2) utiliser un chunk de 4 (moins de parallélisme)
42
Le parallélisme imbriqué
 La notion de parallélisme imbriqué fait référence à la
possibilité d’ouvrir une région parallèle à l’intérieur d’une
région déjà parallèle

 Immédiatement, on peut voir les applications dans le cas de la

parallélisation des nids de boucles, par exemple pour procéder
‘par blocs’

 Toutefois, la plupart des compilateurs sérialisent les régions

imbriquées, par manque de support au point de vue du système
d’exploitation (en pratique, seules les NEC SX5 et les Compaq
ES-40 permettent une telle approche)

20/01/09 43
 Problèmes de Binding
SDSC Blue Horizon
A study on 1 node (SMP 8 procs)
Each OpenMP thread performs an independent matrix inversion

Results for OMP_NUM_THREADS=8

Without binding, threads migrate in about 15% of the runs
With thread binding turned on there was no migration
-> P=0.9876 probability overall results slowed by 25%
for 144 nodes
Slowdown occurs with/without binding

Results for OMP_NUM_THREADS=7

12.5% reduction in computational power
No threads showed a slowdown

44
 OpenMP2
• Pas une transformation mais une amélioration
• Utilisation possible des constructeurs
Workshare,Where et Forall de Fortran 90.
• Accepte les notations tableaux de Fortran 90
• Ajout de la clause NUM_THREAD à la directive
PARALLEL
• La clause REDUCTION est étendue aux tableaux
• Routines de prise de temps (OMP_GET_WTIME)
• La spécification suggère le principe d’affinité des
threads (deux régions parallèles successives devraient
utiliser les mêmes threads avec les même numéro)
45