OpenMP

Françoise ROCH

ANGD Calcul Parallèle et application aux Plasmas froids

Octobre 2011
Modèle
M dèl de
d programmation
ti multi-tâches
lti tâ h
sur architecture à mémoire partagée
„ Plusieurs tâches s’exécutent en parallèle
„ La mémoire est partagée (physiquement ou
virtuellement)
i t ll t)
„ Les communications entre tâches se font
par lectures
pa ectu es et éc
écritures
tu es da
danss la
a mémoire
é o e
partagée.

Par ex. lles processeurs multicoeurs

P lti généralistes
é é li t
partagent une mémoire commune
Les tâches peuvent être attribuées à des « cores »
distincts
Modèle
M dèl de
d programmation
ti multi-tâches
lti tâ h
sur architecture à mémoire partagée
„ La librairie Pthreads : librairie de threads
POSIX, adoptée par la plupart des OS
L’é it
L’écriture d’
d’un code
d nécessite
é it un nombre
b
considérable de lignes spécifiquement dédiées
aux threads
Ex : paralléliser une boucle implique :
déclarer les structures de thread, créer les threads,
calculer les bornes de boucles, les affecter aux
threads, …

„ OpenMP : une
ne alternati
alternative
e pl
plus
s simple po
pourr le
programmeur
Programmation multi-tâches sur les
architectures UMA

CPU CPU CPU

…

cache cache cache

mémoire

La mémoire est commune

commune,
Des architectures à accès mémoire uniforme (UMA)
Un problème inhérent : les contentions mémoire
 Programmation multi-tâches sur les
architectures multicoeurs NUMA

SMT SMT SMT SMT SMT SMT SMT SMT SMT SMT SMT SMT
…

cache cache cache

mémoire mémoire mémoire

La mémoire est directement attachée aux puces multicoeurs

Des architectures à accès mémoire non uniforme NUMA
 Programmation multi-tâches sur les
architectures multicoeurs NUMA

SMT SMT T0 SMT SMT SMT SMT SMT SMT SMT SMT
T1

cache cache cache

mémoire mémoire mémoire

ACCES DISTANT
ACCES LOCAL
Caractéristiques du modèle
OpenMP
„ Gestion de « threads » transparente et portable
„ Facilité de programmation
p g
Mais
„ Problème de localité des données
„ Mémoire partagée mais non hiérarchique
„ Efficacité non garantie (impact de l’organisation
l organisation
matérielle de la machine)
„ Passage à l’échelle
l échelle limité, parallélisme modéré
OpenMP
p
(Open specifications for MultiProcessing)

„ Introduction
„ Structure d’OpenMP
p
„ portée des variables
„ Constructions de ppartage
g du travail
„ Construction task
„ Synchronisation
„ Performances
„ Conclusion
Introduction : supports
pp d’OpenMP
p
„ La p
parallélisation multi-tâches existait avant p
pour
certains compilateurs (Ex:Cray,NEC,IBM)
„ OpenMP est une API pour un modèle à mémoire
partagé
„ Spécifications pour les langages C/C++, Fortran
„ Supporté par beaucoup de systèmes et de
compilateurs
OpenMP-2 2000 , OpenMP-3 2008
Specs : [Link]
 Introduction : Modèle d’exécution
Un programme OpenMP est exécuté par un
processus unique (sur un ou plusieurs cores)

join

join

join
forrk

forrk
forrk

Thread
maître
Régions
parallèles
Introduction : les threads
Les threads accèdent aux mêmes ressources que le
processus.
Elles ont une pile (stack, pointeur de pile et pointeur
d’instructions propres)
Processus

Espace variables partagées

Piles
(variables locales)

Processus

Processus légers
Introduction : exécution d’un
programme OpenMP sur un
multicoeur
Le gestionnaire de tâches du système d’exploitation affecte
les tâches aux cores
cores.

Gestionnaire
de tâches

Cores 0 1 2 3
 OpenMP

„ Introduction
Structure d’OpenMP
„ Portée des données
„ Constructions de ppartage
g du travail
„ Construction task
„ Synchronisation
„ Performances
„ Conclusion
Structure d’OpenMP
p :
architecture logicielle

OpenMP

Runtime Compiler Environment

Library Directives variables
 Structure d’OpenMP
p : format des
directives/pragmas
S ti ll di
Sentinelle directive
ti [[clause[clause]..]
l [ l ] ]
fortran C/C++
!$OMP PARALLEL PRIVATE(a,b) #pragma omp parallel private(a,b)
!$&OMP FIRSTPRIVATE(c,d,e)
... firstprivate(c,d,e)
!$OMP END PARALLEL { …
}

La ligne est interprétée si option openmp à

ll’appel
appel du compilateur sinon commentaire
Î portabilité
Structure d’OpenMP
p : Construction
d’une région parallèle
fortran C/C++
!$USE OMP_LIB #include <omp.h>

PROGRAM example Main () {

Integer :: a, b, c Int a,b,c:

! Code sequentiel execute par le maître /* Code sequentiel execute par le maître */

!$OMP PARALLELPRIVATE(a,b) #pragma omp parallel private(a,b) \

!$OMP& SHARED(c) shared(c)
. {
! Zone
Z parallele
ll l executee
t par toutes
t t lesl threads
th d /* Zone
Z e parallele
llele executee
e e tee par ttoutes
te les
le
threads */
!$OMP END PARALLEL }

!C
Code
d sequentiel
ti l !* Code Sequentiel */

END PROGRAM example }

Clause IF de la directive PARALLEL

„ Création conditionnelle d’une région

g p
parallèle
clause IF(expression_logique)
fortran
!Code sequentiel
!$OMP PARALLEL IF(expr)
! Code p
parallele ou sequentiel
q suivant la valeur de expr
p
!!$OMP END PARALLEL
! Code sequentiel

L’expression logique sera évaluée avant le

début de la région parallèle.
Structure d’OpenMP
p :
prototypage
Il existe :
„ un module fortran 95 OMP_LIB
„ un fichier dd’inclusion
inclusion C/C++ omp.h
omp h
qui définissent les prototypes de toutes les
fonctions de la librairie OpenMP :
fortran C/C++

!$ use OMP_LIB #i l d <omp.h>

#include h
Program example
!$OMP PARALLEL PRIVATE(a,b) &
...
tmp= OMP_GET_THREAD_NUM()
!$OMP END PARALLEL
Threads OpenMP
p
„ Définition du nombre de threads
Via une variable d’environnement OMP_NUM_THREADS
Via la routine : OMP_SET_NUM_THREADS()
Via la clause NUM_THREADS()
NUM THREADS() de la directive PARALLEL
„ Les threads sont numérotées
le nombre de threads n
n’est
est pas nécessairement égale au
nombre de cores physiques
La thread de numéro 0 est la tâche maître
OMP_GET_NUM_THREADS() : nombre de threads
OMP_GET_THREAD_NUM() : numéro de la thread
OMP_GET_MAX_THREADS() : nb max de threads
Structure d’OpenMP :
Compilation et exécution
ifortt (ou
if ( icc)
i ) –openmp [Link] (INTEL)
f90 (ou cc ou CC) –openmp prog.f (SUN Studio)
gfortran –fopenmp –std=f95 prog.f (GNU)
export OMP_NUM_THREADS=2

./[Link]
/a out

# ps –eLF
USER PID PPID LWP C NLWP SZ RSS PSR
…
 OpenMP

„ IIntroduction
t d ti
„ Structure d’OpenMP
Portée des variables
„ Constructions de partage du travail
„ Construction task
„ Synchronisation
S h i ti
„ Performances
„ Conclusion
Rappel : allocation mémoire- portée des variables
„ Variables statiques et automatiques
¾ statique : emplacement en mémoire défini dès sa déclaration par le
compilateur
p
¾ automatique : emplacement mémoire attribué au lancement de l’unité de
programme où elle est déclarée (existence garantie que pendant ’exécution
de l’unité).
„ Variables globales
g
globale : déclarée au début du programme principal, elle est statique
2 cas :
¾ initialisées à la déclaration (exemple : parameter, data)
¾ non-initialisées
i iti li é à lla dé
déclaration
l ti ((exemple l : en ffortran
t lles common,
en C les variables d’unités de fichier, les variables externes ou static)
„ Variables locales
variable à portée restreinte à l’unité
l unité de programme où elle est déclarée
déclarée, 2
catégories :
¾ Variables locales automatiques
¾ Variables locales rémanentes (statiques) si elles sont :
„ a) initialisées explicitement à la déclaration
déclaration,
„ b) déclarées par une instruction de type DATA,
„ c) déclarées avec l’attribut SAVE => valeur conservée entre 2 appels
 Rappel : stockage des variables
Le processus
thread0 thread1 thread2 thread3
Noyau
y UNIX appels
pp systèmes
y
Communications entre zoneU Dans un sous programme appelé dans une
l’application et l’OS
région parallèle, les variables locales et
Code assembleur obtenu après automatiques sont privées à chacune des
compilation et édition de liens
TXT threads (mode stack).
Variables statiques
initialisées : DATA
data
Variables statiques non initialisées :
bss Variables partagées
COMMON, SAVE
Tableaux dynamiques
y q :
ALLOCATABLE heap
Leur profil n’est pas connu à
l’écriture du programme Stack du processus
Variables locales automatiques Variables
Tableaux automatiques Stack Stack Stack Stack
thread0 thread1 thread2 thread3 privées
Contextes de procédures
 Statut d’une variable
Le statut d’une variable dans une zone !$USE OMP_LIB
parallèle est : program private_var.f
¾ soit SHARED,
SHARED elle se trouve dans la
mémoire globale integer:: tmp =999
¾ soit PRIVATE, elle est dans la pile Integer :: OMP_GET_THREAD_NUM
q thread, sa valeur est
de chaque Call OMP_SET_NUM_THREADS(4)
OMP SET NUM THREADS(4)
indéfinie à l’entrée de la zone
!$OMP PARALLEL PRIVATE(tmp)
„ Déclarer le statut d’une variable print *, tmp
!$OMP PARALLEL PRIVATE(list) tmp= OMP_GET_THREAD_NUM()
!$OMP PARALLEL FIRSTPRIVATE(list)
print *, OMP_GET_THREAD_NUM(), tmp
!$OMP PARALLEL SHARED(list) ( )
!$OMP END PARALLEL
„ Déclarer un statut par défaut
Clause DEFAULT(PRIVATE|SHARED| print *, tmp
NONE)) end
Clauses de la directive PARALLEL

„ NONE
Equivalent de l’ IIMPLICIT NONE en Fortran. Toute variable
devra avoir un statut défini explicitement
„ SHARED (liste_variables)
Variables partagées entre les threads
„ PRIVATE (liste_variables)
Variables privées à chacune des threads, indéfinies en
dehors du bloc PARALLEL
„ FIRSTPRIVATE (liste_variables)
Variable initialisée avec la valeur que la variable d’origine
avait
it juste
j t avantt la
l section
ti parallèle
llèl
„ DEFAULT (PRIVATE | SHARED|NONE)

Ex !$OMP PARALLEL DEFAULT(PRIVATE) SHARED (X)

Statut d’une variable transmise par
arguments
Dans une procédure,
D éd l
les program statut
variables transmises par integer :: a=100, b
integer OMP_GET_THREAD_NUM
argument héritent du
statut défini dans l’étendue !$OMP PARALLEL PRIVATE(b)
lexicale de la région
g ((code call sub(a,b)
print *,b
contenu entre les !$OMP END PARALLEL
directives PARALLEL et end program statut
END PARALLEL).
Subroutine sub(x,y)
integer x,y,OMP_GET_THREAD_NUM
y = x + OMP_GET_THREAD_NUM()
End subroutine sub
 La directive THREADPRIVATE
program threadpriv
La directive THREADPRIVATE :
integer:: tid, x, OMP_GET_THREAD_NUM
Permet de rendre pprivé aux threads common /C1/ x
ƒ un bloc COMMON (Fortran): !$OMP THREADPRIVATE(/C1/)
les modifications apportées au
bloc par une thread ne sont plus !$OMP PARALLEL PRIVATE(tid)
visibles des autres threads.
threads tid
id = OMP_GET_THREAD_NUM()
OMP GET THREAD NUM()
„ Une variable globale, un
x= tid*10+1
descripteur de fichier ou des
variables statiques (en C) print *,"T:",tid,"dans la premiere region // x=",x
!$OMP END PARALLEL
L’instance de la variable persiste
d’une région parallèle à l’autre (sauf x=2
y
si le mode dynamic est actif )). !$OMP PARALLEL PRIVATE(tid)
L’instance de la variables dans la tid = OMP_GET_THREAD_NUM()
zone séquentielle est aussi celle de la
thread 0 print *,"T:",tid,"dans la seconde region // x=",x
!$OMP END PARALLEL
clause COPYIN : permet de
transmettre la valeur de la variable end
partagée à toutes les tâches
Allocation mémoire
ƒ L’option par défaut des compilateurs est généralement :
variables locales allouées dans la stack => privé ,
mais certaines options permettent de changer ce défaut
et il est recommandé de ne pas utiliser ces options pour
OpenMP

ƒ Une opération d’allocation ou désallocation de mémoire

sur un variable privée sera locale à chaque tâche

ƒ Si une opération d’allocation/désallocation de mémoire

p
porte sur une variable p
partagée,
g l’opération
p doit être
effectuée par une seule tâche .

ƒ En fortran ne mettre en équivalence

q que des variables de
q
même statut (SHARED ou PRIVATE), même dans le cas
d’une association par pointeur.
Allocation mémoire
Taille du “stack”
ƒ La taille du stack est limitée , différentes
variables d’environnement ou fonctions
permettent d’agir sur cette taille
ƒ La pile (stack) a une taille limite pour le shell
(variable selon les machines). (ulimit –s)(ulimit –s
unlimited),), valeurs exprimées
p en ko.
Ex: ulimit –s 65532
ƒ OpenMP :
Variable d’environnement OMP_STACKSIZE :
définit le nombre d’octets que chaque thread
OpenMP
p peut utiliser p
p pour sa stack p
privée
Quelques
q précisions
p

„ Les variables privatisées dans une région parallèle

ne peuventt être
êt re-privatisées
i ti é d dans une construction
t ti
parallèle interne à cette région.

„ En fortran: les pointeurs et les tableaux

ALLOCATABLE peuvent être PRIVATE ou SHARED
mais
i pas LASTPRIVATE nii FIRSTPRIVATE.
FIRSTPRIVATE
Quelques
q précisions
p

„ Quand un bloc common est listé dans un bloc

PRIVATE, FIRSTPRIVATE ou LASTPRIVATE,
les éléments le constituant ne peuvent pas
apparaître
pp dans d’autres clauses de pportée de
variables. Par contre, si un élément d’un bloc
common SHARED est privatisé, il n’est plus
stocké avec le bloc common

„ Un pointeur privé dans une région parallèle

sera ou deviendra
d i d fforcément
é t iindéfini
défi i à lla
sortie de la région parallèle
 OpenMP

„ IIntroduction
t d ti
„ Structure d’OpenMP
„ Portée des données
Constructions de partage du travail
„ Construction task
„ Synchronisation
S h i ti
„ Performances
„ Conclusion
Partage
g du travail
„ Répartition d’une boucle entre les threads
(boucle //)
„ Répartition de plusieurs sections de code entre
les threads,, une section de code p
par thread
(sections //)
„ Exécution d’une portion de code par un seul
Thread
„ Exécution de plusieurs occurences d’une même
procédure par différents threads (orphaning)
„ Exécution par différents threads de différentes
unités de travail provenant de constructions f95
Portée d’une région parallèle
Program portee
implicit none
!$OMP PARALLEL Subroutine sub()
call sub()
Logical :: p, OMP_IN_PARALLEL
!$OMP END PARALLEL
!$ p = OMP_IN_PARALLEL()
OMP IN PARALLEL()
End program portee
print *, “Parallel prog ? ”, p
End subroutine sub

La portée d’une région parallèle s’étend :

„ au code contenu lexicalement dans cette région
(é d statique)
(étendue i )
„ au code des sous programmes appelés

L’union des deux représente l’étendue dynamique

Partage
g du travail
„ Directives permettant de contrôler la
répartition du travail, des données et la
synchronisation des tâches au sein d’une
région parallèle :
¾ DO
¾ SECTIONS
¾ SINGLE
¾ MASTER
¾ WORKSHARE
Partage
g du travail : boucle parallèle
p
Directive DO (for en C) :
parallélisme
lléli par répartition
é titi d des ité
itérations
ti d’
d’une b
boucle.
l

„ Le mode de répartition des itérations peut être spécifié

dans la clause SCHEDULE (codé dans le programme ou
grâce à une variable d’environnement)
„ Une synchronisation globale est effectuée en fin de
construction END DO (sauf si NOWAIT)
„ Possibilité d’avoir plusieurs constructions DO dans une
région
é i parallèle.
llèl
„ Les indices de boucles sont entiers et privées.
„ Les boucles infinies et do while ne sont ppas p
parallélisables
Directives DO et PARALLEL DO
Program loop Program parallelloop
p
implicit none implicit none
integer, parameter :: n=1024 integer, parameter :: n=1024
integer :: i, j integer :: i, j
real, dimension(n, n) :: tab
!$OMP PARALLEL real, dimension(n, n) :: tab
... ! Code
C d répliqué
é li é !$OMP PARALLEL DO
!$OMP DO do j=1 n ! Boucle partagée
do j=1, n ! Boucle partagée do i=1, n ! Boucle répliquée
do i=1, n ! Boucle répliquée tab(i, j) = i*j
tab(i, j) = ii*jj end do
end do end do
end do !$OMP END PARALLEL DO
!$OMP END DO end program parallelloop
!$OMP END PARALLEL
endd program lloop

PARALLEL DO est une fusion des 2 directives

Attention : END PARALLEL DO inclut une barrière de
synchronisation
 Répartition du travail : clause SCHEDULE
0 12
4 8
!$OMP DO SCHEDULE(STATIC,taille_paquets)
( , _p q ) 1 13
2 14
Avec par défaut taille_paquets=nbre_itérations/nbre_thread 5 9 t
3 15
6 10
Ex : 16 itérations (0 à 15), 4 threads : la taille des paquets par défaut
11
est de 4 7

!$OMP DO SCHEDULE(DYNAMIC,taille_paquets) 0 1 3
2
Les paquets sont distribués aux threads libres de façon dynamique 5 6 4
7
Tous les paquets ont la même taille sauf éventuellement le dernier, 9
t
8 10
11
par défaut la taille des paquet est 1. 12 13
14 15

!$OMP DO SCHEDULE(GUIDED,taille_paquets) 0 2 4 6
Taille_paquets : taille minimale des paquets (1 par défaut) sauf le 1 3
dernier. 8 9 5 7 t
Taille des paquets maximale en début de boucle (ici 2) puis diminue 13 10 11 12
15 14
pour équilibrer la charge.
Répartition du travail : clause SCHEDULE
Ex: 24 itérations, 3 threads

1,2 3,4 5,6

1,2,..,7,8 9,10,..,16 17,18,..,24 7,8 9,10 11,12

13,14 15 16
15,16 17,18
21,22
19,20 23,24
Mode static, avec
Taille paquets=nb itérations/nb threads
Cyclique : STATIC

1,2 3,4 5,6

11,12 9,10 7,8

1,2,3,4 5,6,7,8 9,10,11,12
13,14 15,16
17,18
19,20,21 16,17,18 13,14,15
19,20
21,22 23
23 24
23,24 24 22

Glouton : DYNAMIC Glouton : GUIDED

Répartition du travail : clause SCHEDULE
Le choix du mode de répartition peut être différé
à l’exécution du code avec
SCHEDULE(RUNTIME)

Prise en compte de la variable d’environnement

d environnement
OMP_SCHEDULE

Ex :
export OMP_SCHEDULE=“DYNAMIC,400”
Reduction : pourquoi ?
Ex séquentiel : En parallele :
Do i=1,N
i=1 N !$OMP PARALLEL DO SHARED(X)
do i=1,N
X=X+a(i)
X = X + a(i)
enddo enddo
!$OMP END PARALLEL DO

Reduction : opération associative appliquée à des variables scalaires

p
partagées
g

Chaque tâche calcule un résultat partiel indépendamment des autres. Les

réductions intermédiaires sur chaque thread sont visibles en local.
P i les
Puis l tâches
tâ h se synchronisent
h i t pour mettre
tt à jour
j le
l résultat
é lt t fi
finall d
dans
une variable globale, en appliquant le même opérateur aux résultats
partiels.
Attention, p
pas de g garantie de résultats identiques
q d’une exécution à
l’autre, les valeurs intermédiaires peuvent être combinées dans un
ordre aléatoire
Reduction
Ex : !$ OMP DO REDUCTION(op:list) (op est un program reduction
opérateur ou une fonction intrinsèque )
implicit none
Les variables de la liste doivent être partagées dans la integer, parameter :: n=5
zone englobant la directive!; integer :: i, s=0, p=1, r=1
Une copiep locale de chaque
q variable de la liste est
attribuée à chaque thread et initialisée selon
l’opération (par ex 0 pour +, 1 pour * ) !$OMP PARALLEL
!$OMP DO REDUCTION(+:s)
La clause s’appliquera aux variables de la liste si les !$&REDUCTION(*:p,r)
instructions sont d’un
d un des types suivants :
do i=1,n
x = x opérateur expr s=s+1
x = expr opérateur x p=p*2
x = intrinsic (x,expr)
(x expr) r=r*3
x = intrinsic (expr,x)
end do
x est une variable scalaire, ou un tableau (version 2)
expr est une expression scalaire ne référençant pas x !$OMP END PARALLEL
intrinsic = MAX,
MAX MIN,
MIN IAND,
IAND IOR,
IOR IEOR print *,"s="
s ,s, s " , pp=",p,
p " ,rr =",rr
opérateur = +,*, .AND., .OR., .EQV., .NEQV. end program reduction
Clauses portant sur le statut des
variables
program parallel
„ SHARED ou PRIVATE implicit none
„ FIRSTPRIVATE : privatise et integer, parameter :: n=9
integer :: i, mytid
assigne la dernière valeur integer :: iter
affectée avant l’entrée
l entrée dans la integer :: OMP_GET_THREAD_NUM
OMP GET THREAD NUM
région // !$OMP PARALLEL PRIVATE (mytid)
!$OMP DO LASTPRIVATE(iter)
„ LASTPRIVATE : privatise et do i=1, n
permet de conserver,
conser er à la sortie iter = i
end do
de la construction, la valeur !$OMP END DO
calculée par la tâche exécutant rang = OMP_GET_THREAD_NUM()
la dernière itération de la boucle print *, “mytid:”
mytid: , mytid,
mytid “;iter=“
;iter= ,tter
tter
!$OMP END PARALLEL
end program parallel
Exécution ordonnée : ORDERED
Exécuter une zone
séquentiellement program parallel
implicit none
¾ Pour du débogage
integer, parameter :: n=9
¾ Pour des IOs ordonnées integer :: i,rang
integer :: OMP_GET_THREAD_NUM
!$OMP PARALLEL DEFAULT (PRIVATE)
Clause et Directive :ORDERED rang = OMP_GET_THREAD_NUM()
!$OMP DO SCHEDULE(RUNTIME) ORDERED
do i=1, n
ll’ordre
ordre d’exécution
d exécution des !$OMP ORDERED
instructions de la zone print *, “Rang:”, rang, “;itération “,i
!$OMP END ORDERED
encadrée par la directive sera end do
identique à celui d’une
d une !$OMP END DO NOWAIT
exécution séquentielle, càd !$OMP END PARALLEL
dans l’ordre des itérations end program parallel
Dépliage
p g de boucles imbriquées
q :
directive COLLAPSE
La Clause COLLAPSE(N) ( )ppermet
de spécifier un nombre de
boucle à déplier pour créer un
large espace des itérations !$OMP PARALLEL DO COLLAPSE(2)
do i=1,
i 1 N
do j=1, M
Les boucles doivent être do k=1, K
parfaitement imbriquées
p q func(i j k)
func(i,j,k)
end do
Ex. : Si les boucles en i et j end do
peuvent être parallélisées
parallélisées, et end do
si N et M sont petits, on peut !$OMP END PARALLEL DO
ainsi paralléliser sur
l’ensemble du travail
correspondant aux 2 boucles
Dépliage
p g de boucles imbriquées
q :
directive COLLAPSE

!$OMP PARALLEL DO COLLAPSE(2)

do i=1, N
Les boucles ne sont
pas parfaitement
func1(i) interdit !
imbriquées interdit do j=1, i interdit !
do k=1,, K
func(i,j,k)
Espace d’itération end do
triangulaire interdit end do
end do
!$OMP END PARALLEL DO
 Parallélisme imbriqué
q
Autoriser le parallélisme imbriqué

ƒ Via une variable d’environnement ;

Export OMP_NESTED= TRUE
ƒ Via la routine OMP_SET NESTED()

!$use OMP_LIB #include <omp.h>

call OMP_SET_NESTED(.TRUE.) omp
p_set_nested(1)
( )

Ex d’application
pp :p
parallélisation des nids de boucle,, avec un
découpage par blocs.
 Parallélisme imbriqué
q

!$OMP PARALLEL SHARED(n

SHARED(n, a
a, b) !$OMP PARALLEL SHARED(n
SHARED(n, a
a, b)
!$OMP DO !$OMP DO
do j=0,n do j=0, n
a[j] = j + 1; a[j] = j + 1;
!$OMP PARALLEL DO !$OMP DO
do i=0,n do i=0,n
b[i][j]
[ ][j] = a[j]
[j] b[i][j] = a[j]
end do
end do !$OMP END DO
!$OMP END PARALLEL DO end do
end do
!$OMP END DO !$OMP END DO
!$OMP END PARALLEL
!$OMP END PARALLEL

L’imbrication de directives de partage du travail n ’est pas

valide si on ne crée pas une nouvelle région parallèle.
 Partage du travail : SECTIONS
parallèles
program section
„ But : Répartir ll’exécution
exécution de call
ll OMP_SET_NUM_THREADS(4)
OMP SET NUM THREADS(4)
plusieurs portions de code !$OMP PARALLEL SECTIONS
indépendantes sur
différentes tâches !$OMP SECTION
call sub0()
„ Une section: une portion de
!$OMP SECTION
code exécutée par une et
call sub1()
une seule tâche
!$OMP SECTION
„ Directive SECTION au sein call sub2()
d’une construction !$OMP END PARALLEL SECTIONS
SECTIONS
0 1 2 3
sub1() sub2() sub0()
SECTIONS parallèles

„ Les directives SECTION doivent se trouver dans

l’étendue lexicale de la construction

„ Les clauses admises :

PRIVATE, FIRSTPRIVATE, LASTPRIVATE,
REDUCTION
LASTPRIVATE : valeur donnée par la thread qui
exécute la dernière section
„ END PARALLEL SECTIONS inclut une barrière
de synchronisation (NOWAIT interdit)
Ex : SECTIONS + REDUCTION
program section
Logical b
!$OMP PARALLEL SECTIONS REDUCTION(.AND. : b)
!$OMP SECTION
b = b .AND. func0()
!$OMP SECTION
b = b .AND.
AND func1()
!$OMP SECTION
b = b .AND. func2()
!$OMP END PARALLEL SECTIONS
IF (b) THEN
print(* "All
print(*, All of the functions succeeded
succeeded"))
ENDIF
 Directive WORKSHARE
ƒ destinée à permettre la parallélisation
d’instructions Fortran 95 Program workshare
q
intrinsèquement p
parallèles comme : …
¾ Les notations tableaux.
¾ Certaines fonctions intrinsèques !$OMP PARALLEL
¾ Instruction FORALL, WHERE !$OMP WORKSHARE
A(:) = B(:)
ƒ Cette directive s’applique à des somme = somme + SUM(A)
variables partagées, dans l’extension
lexicale de la construction FORALL (I=1:M) A(I)=2*B(I)
O S
WORKSHARE. !$OMP END WORKSHARE
ƒ Tout branchement vers l’extérieur est !$OMP END PARALLEL
illégal.
…
ƒ Clause possibles : PRIVATE,
FIRSTPRIVATE COPYPRIVATE,
FIRSTPRIVATE, COPYPRIVATE End program
NOWAIT

ƒ Fusion PARALLEL WORKSHARE

possible
Partage du travail : exécution exclusive
Construction SINGLE
ƒ Exécution d’une
d une portion de code par une et une seule
tâche (en général, la première qui arrive sur la
construction).
„ clause NOWAIT : permet de ne pas bloquer les autres
tâches qui par défaut attendent sa terminaison.
„ Clauses admises : PRIVATE, FIRSTPRIVATE,
„ COPYPRIVATE(var): mise à jour des copies privées de
var sur toutes les tâches (après END SINGLE)

!$OMP SINGLE [clause [clause ...] ]

...
!$OMP
$O END SINGLE
S G
Partage du travail : exécution exclusive
Construction MASTER
ƒ Exécution d’une
d une portion de code par la tâche maître seule
„ Pas de synchronisation, ni en début ni en fin
(contrairement à SINGLE)
Attention aux mises à jour de variables qui seraient utilisées
par d’autres threads
„ Pas de clause

!$OMP MASTER
...
!$OMP END MASTER
 Partage du travail : Program main
implicit none
procédures orphelines integer, parameter :: n=1025
real, dimension(n,n) :: a
real, dimension(n) :: x,y

„ Procédures appelées dans une call random_number(a)

région // et contenant des call random_number(x); y(:)=0
!$OMP PARALLEL
directives OpenMP call orphan(a,x,y,n)
Ell sontt dites
Elles dit orphelines
h li !$OMP
$ END PARALLEL
End program main
„ Attention : le contexte d’exécution Subroutine orphan(a,x,y,n)
peut être # selon le mode de implicit none
compilation
il ti ( -fopenmp
f ou pas)) Integer, intent(in) :: n
real, intent(in), dimension(n,n) :: a
des unités de programme real, intent(in), dimension(n) :: x
appelantes et appelées real, intent(out), dimension(n) :: y
„ Attention au statut des variables !$OMP DO
locales aux subroutines DO i=1,n
y(i) = SUM(a(i, : ) * x(:) )
END DO
!$OMP END DO
End subroutine orphan
 OpenMP

„ IIntroduction
t d ti
„ Structure d’OpenMP
„ Portée des données
„ Constructions de partage du travail
Construction TASK
„ Synchronisation
S h i ti
„ Performances
„ Conclusion
 Partage du travail : construction TASK
„ Une “TASK” au sens OpenMP est une unité de travail dont
ll’exécution
exécution peut être différée (ou démarrer immédiatement)
Autorise la génération dynamique de tâches

„ Permet de paralléliser des problèmes irréguliers

¾ boucles non bornées
¾ algos récursifs
réc rsifs
¾ schémas producteur/consommateur

„ Une TASK est composée de :

¾ un code à exécuter
¾ un environnement
i td
de d
données
é associé
ié
 Partage du travail : construction TASK
„ La construction TASK
définit explicitement
p une !$OMP PARALLEL
TASK OpenMP call sub()
!$OMP TASK
„ SI un thread rencontre une
construction TASK,
TASK une …
nouvelle instance de la !$OMP END TASK
TASK est créé (paquet
…
code + données associées)
!$OMP END PARALLEL
„ Le thread peut soit exécuter
la tâche, soit différer son
exécution La tâche pourra
exécution. Clauses :
Cl
être attribuée à n’importe IF, DEFAULT(PRIVATE|SHARED)
quel thread de l’équipe. PRIVATE, SHARED
FIRSTPRIVATE
UNTIED …
 Partage du travail : construction TASK
„ Par défaut les variables de TASKs orphelines sont
firstprivate
p
„ Sinon les variables sont firstprivate à moins qu’elles
héritent d’un attribut shared du contexte qui les englobe
int fib (int n) {
int x, y;
if (n < 2) return n;
#pragma omp task shared(x) Ici n est firstprivate
x = fib(n-1);
#pragma omp task shared(y)
y = fib(n-2);
#pragma omp taskwait
return x+y;
}
 Partage
g du travail : construction TASK
Remarque : le concept existait avant la construction:
Un thread qui rencontre une construction PARALLEL
¾ crée un ensemble de TASKs implicites (paquet code+données)
¾ Crée une équipe de threads
¾ Les TASKs implicites sont liées (tied) aux threads, une pour chaque
thread de l’équipe
„ A quel moment la TASK est-elle exécutée ?
L’exécution
L exécution d’une
d une TASK générée peut être affectée, par le
scheduler, à un thread de l’équipe qui a terminé son travail.
La norme 3.0 impose des règles sur l’exécution des TASK
Ex :Les TASK en attente dans la région //
//, doivent toutes être
exécutées par les threads de l’équipe qui rencontrent
¾ une BARRIER (implicite ou explicite)
¾ une directive TASKWAIT
 OpenMP

„ IIntroduction
t d ti
„ Structure d’OpenMP
„ Portée des données
„ Constructions de partage du travail
„ Construction task
S
Synchronisation
h i ti
„ Performances
„ Conclusion
Synchronisation
y

„ Synchronisation de toutes les tâches sur un

même niveau d’instruction (barrière globale)
„ Ordonnancement
Od t de
d tâches
tâ h concurrentest pour
la cohérence de variables partagées
(exclusion mutuelle)
„ Synchronisation de plusieurs tâches parmi un
ensemble ((mécanisme de verrou))
 Synchronisation
y : barrière g
globale

Program barriere
„ Par défaut à la fin des !$OMP PARALLEL &
SHARED(A,B,C) PRIVATE(tid)
constructions parallèles, tid = OMP_GET_THREAD_NUM()
A(tid) = big_calcul_1(tid);
big calcul 1(tid);
en l’absence
l’ b d
du !$OMP BARRIER Barrière
NOWAIT !$OMP DO
DO i=1, n
explicite
C(i) = big_calcul_2(i,
big calcul 2(i A)
„ Directive BARRIER ENDDO
!$OMP END DO
Barrière
Impose explicitement !$OMP DO implicite
une barrière de DO ii=11, n
B(i) = big_calcul_3(i, C)
synchronisation: chaque END DO
!$OMP END DO NOWAIT
tâche attend la fin de A(tid) = big_calcul_4(tid)
big calcul 4(tid)
!$OMP END PARALLEL
toutes les autres End program barriere
Pas de
barrière
 Synchronisation
y
Il peut être nécessaire d’introduire une synchronisation entre
tâches concurrentes pour éviter que celles-ci modifient la valeur
d’une variable dans un ordre quelconque

Ex : Espace partagé
fruit cerise
pomme
2 threads
th d ontt un
espace de couleur jaune
rouge
mémoire partagé

fruit = pomme fruit = cerise

couleur = jjaune couleur = rouge
g

Thread 1 Thread 2
 Synchronisation
y : régions
g critiques
Integer,dimension(n) :: a=1
„ Directive CRITICAL somme = 0
DO j=1,n
Ell s’applique
Elle ’ li sur une somme = somme + a(i)
(i)
END DO
portion de code …
Les tâches exécutent la
Integer somme = 0
région critique dans un Integre dimension(n) :: a=1
ordre non-déterministe, !$OMP PARALLEL DEFAULT(SHARED) &
& PRIVATE(i,,j,somme_partielle)
une à la fois somme_partielle = 0
!$OMP DO
Garantit aux threads un DO j=1,n
accès en exclusion somme_partielle = somme_partielle + a(i)
END DO
mutuelle !$OMP END DO
Son étendue est dynamique !$OMP CRITICAL
somme = somme+somme_partielle
!$OMP END CRITICAL
!$OMP END PARALLEL
….
 Synchronisation : mise à jour atomique
La directive ATOMIC s’applique seulement dans le cadre de la mise à
jour dd’un
un emplacement mémoire

Une variable partagée est lue ou modifiée

en mémoire ppar un seul thread à la fois Program atomic
implicit none
Agit sur l’instruction qui suit integer :: count, rang
immédiatement si elle est de la forme : integer :: OMP_GET_THREAD_NUM
!$OMP PARALLEL PRIVATE(rang)
PRIVATE( )
¾ x = x (op) exp
!$OMP ATOMIC
¾ ou x = exp (op) x count = count + 1
¾ ou x = f(x,exp)
( ) g _ _
rang=OMP_GET_THREAD_NUM() _ ()
¾ ou x = f(exp,x) print *, “rang : ”, rang, “count:”, count
!$OMP END PARALLEL
op : +, -, *, /, .AND., .OR., .EQV., .NEQV.
print *, “count:”, count
f : MAX,, MIN,, IAND,, IOR,, IEOR End program atomic
 directive FLUSH
Program anneau
Les valeurs des variables implicit none
partagées peuvent rester integer :: rang, nb_taches, synch=0
integer :: OMP_GET_NUM_THREADS
OMP GET NUM THREADS
temporairement dans des integer :: OMP_GET_THREAD_NUM
registres pour des raisons !$OMP PARALLEL PRIVATE(rang,nb_taches)
rang=OMP_GET_THREAD_NUM()
de performances nb taches=OMP
nb_taches OMP_GET_NUM_THREADS()
GET NUM THREADS()
La directive FLUSH garantit if (rang == 0) then ; do
!$OMP FLUSH(synch)
que chaque thread a accès if(synch == nb_taches-1) exit
aux valeurs des variables end do
else ; do
partagées modifiées par les !$OMP FLUSH(synch)
autres threads . if(synch == rang-1) exit
end do
end if
print *, “Rang: “,rang,”synch = “,synch
synch=rang
!OMP FLUSH(synch)
!$OMP END PARALLEL
end program anneau
 directive FLUSH
Program anneau
implicit none
nb_taches = 4 integer :: rang, nb_taches, synch=0
integer :: OMP_GET_NUM_THREADS
OMP GET NUM THREADS
T=0 integer :: OMP_GET_THREAD_NUM
!$OMP PARALLEL PRIVATE(rang,nb_taches)
synch=0 rang=OMP_GET_THREAD_NUM()
nb taches=OMP
nb_taches OMP_GET_NUM_THREADS()
GET NUM THREADS()
if (rang == 0) then ; do
T=3 T=1 !$OMP FLUSH(synch)
if(synch == nb_taches-1) exit
synch=3 synch
y synch=1 end do
else ; do
!$OMP FLUSH(synch)
if(synch == rang-1) exit
end do
end if
synch=2
print *, “Rang: “,rang,”synch = “,synch
synch=rang
T=2 !OMP FLUSH(synch)
!$OMP END PARALLEL
end program anneau
Performances et p
partage
g du travail
„ Minimiser le nombre de régions parallèles
„ Eviter de sortir d’un région
g p
parallèle p
pour la
recréer immédiatement
!$OMP PARALLEL
...
!$OMP DO !$OMP PARALLEL
do i=1, N ...
func1(i) Surcoût inutile !$OMP DO
end do do i=1, N
!$OMP END DO func1(i)
end do
!$OMP END PARALLEL Ici, une construction !$OMP END DO
!$OMP PARALLEL PARALLEL suffit !$OMP DO
do j=1
j=1, M
!$OMP DO func2(j)
do j=1, M end do
func2(j) !$OMP END DO
end do
!$OMP END DO !$OMP ENDPARALLEL
!$OMP END PARALLEL
Performances et p
partage
g du travail
„ Introduire un PARALLEL DO dans les boucles
capables d’exécuter des itérations en //
„ Si il y a des dépendances entre itérations
itérations, essayer de
les supprimer en modifiant l’algorithme
„ S’il reste des itérations dépendantes, introduire des
constructions CRITICAL autour des variables
concernées par les dépendances.
„ Si possible, regrouper dans une unique région
parallèle plusieurs structures DO.
DO
„ Dans la mesure du possible, paralléliser la boucle la
plus externe
„ Adapter le nombre de tâches à la taille du problème à
traiter afin de minimiser les surcoûts de gestion des
tâches par le système
„ Utiliser SCHEDULE(RUNTIME) si besoin
„ ATOMIC REDUCTION+ performant que CRITICAL
Performances : les effets du False
Sharing
La mise en cohérence des caches et les effets négatifs
d « false
du f l sharing
h i » peuventt avoiri un fort
f t impact
i t sur
les performances
Mémoire
partagée

Caches

Ligne de cache
Cores

Une opération de chargement d’une ligne de cache

partagée invalide les autres copies de cette ligne.
Performances sur architectures
multicoeurs : le false-sharing
ƒ L’utilisation des structures en mémoire partagée peut induire une
di i ti de
diminution d performance
f ett une forte
f t limitation
li it ti de
d la
l scalabilité.
l bilité

¾ Pour des raisons de performance, utilisation du cache

¾ Si plusieurs processeurs manipulent des données différentes
mais adjacentes en mémoire, la mise à jour d’éléments
individuels peut provoquer un chargement complet d’une ligne
de cache, pour que les caches soient en cohérence avec la
mémoire

„ Le False sharing dégrade les performances lorsque toutes les

conditions suivantes sont réunies :
¾ Des données partagées sont modifiées sur #cores
¾ Plusieurs threads, sur # cores mettent à jour des données qui
se trouvent dans la même ligne de cache.
¾ Ces
C misesi à jjour ontt lilieu ttrès
è ffréquemment
é t ett simultanément
i lt é t
Performances sur architectures
multicoeurs : Le false-sharing (2)
„ Lorsque les données partagées ne sont que lues, cela
ne génère pas de false sharing.

„ En général, le phénomène de false sharing peut être

réduit en :
¾ En privatisant éventuellement des variables
¾ Parfois en augmentant la taille des tableaux (taille
des problèmes ou augmentation artificielle) ou en
faisant du « ppadding
g»
¾ Parfois en modifiant la façon dont les itérations d’une
boucle sont partagées entre les threads (augmenter
la taille des paquets)
p q )
 Performances sur architectures
multicoeurs : Le false-sharing (3)
Integer, dimension(n) :: a
…
!$OMP PARALLEL DO SHARED(nthreads,a) SCHEDULE(static,1)
DO i=0, nthreads-1
a(i) = i
END DO
!$OMP END PARALLEL DO
Nthreads : nombre de thread exécutant la boucle
Supposons que chaque thread possède un copie de a dans son cache local
La taille de paquet de 1 provoque un phénomène de false sharing à chaque
mise à jour

Si une ligne de cache peut contenir C éléments du vecteur a,, on peut

résoudre le problème en étendant artificiellement les dimensions du tableau
( « array padding ») : on déclare un tableau a(C,n) et on remplace a(i) par
a(1,i)
Performances : architecture CC-NUMA

Mé i
Mémoire Mé i
Mémoire

CPU CPU

Cohérence de Cache
Performances : effets du CC-NUMA
„ Comment placer les données pour optimiser les temps
d’accès ?
„ La p
politique
q de p placement dépendp de l’OS
„ Sous linux, solaris : « first touch »

a[0]
[ ]
a[1] Mémoire Mémoire
a[99]

CPU C U
CPU

Cohérence de Cache

For (i=0;i<100; i++)

a[i ] = 0;
 Effet de la politique « First Touch »

a[0] a[50]
a[1] Mé i
Mémoire Mé i
Mémoire a[51]

a[49] a[99]

CPU CPU

Cohérence de Cache

#pragma omp for num_threads(2)

for (i=0;i<100; i++)
a[i[i ] = 0;
0
 Performances sur architectures
multicoeurs : ordonnancer les threads
efficacement
ƒ Maximiser le rendement de chaque CPU fortement
dépendant de la localité des accès mémoire
ƒ Les variables sont stockées dans une zone
mémoire ((et cache)) au moment de leur
initialisation.
paralléliser l’initialisation des éléments (Ex tableau)
de la même façon (même mode et même taille de
paquets) que le travail
ƒ L’idéal serait de pouvoir spécifier des contraintes
d placement
de l td
des ththreads
d en ffonction
ti d de affinités
ffi ité
threads/mémoire
Performances sur architectures
multicoeurs : problématique de la
diversité des architectures
# types de processeurs
# nombres de cœurs
# niveaux de cache
# architecture mémoire

Et # types d’interconnexion des différents

composants t

Des stratégies d’optimisation

d optimisation qui peuvent différer
d’une configuration à l’autre
Affinité threads/mémoire sur
architectures multicoeurs :

Pour l’instant, OpenMP ne fournit pas de support

Pas de spécification,
spécification mais des discussions en
cours.

En attendant :
utiliser les possibilités offertes par l’OS pour
attacher les threads à des cores et pour
contrôler l’allocation de page.
Affinité thread/core avec
l’environnement d’exécution Intel:
Possibilité de lier les threads OpenMP à des
cores
N ti d
Notion de thread
th d affinity
ffi it : le
l lilieu d’
d’exécution
é ti d de
certaines threads est restreint à un sous
ensemble d’unités d’exécution physiques
Avec la librairie intel :
Variable d’environnement KMP_AFFINITY
S SGI : notion
Sur ti ded cpusett
outil « dplace » permet de lier une
application à un ensemble de CPUs
Outil « taskset » sous linux
 Performances : parallélisation
conditionnelle
Utiliser lla clause
Utili l IF pour Program parallel
mettre en place une implicit none
parallélisation integer, parameter :: n=8192
integer :: i,j
conditionnelle
diti ll real, dimension(n,n) :: a,b
ex : ne paralléliser une call random_number(a)
!$OMP PARALLEL DO SCHEDULE(RUNTIME) &
boucle q que si sa taille &!$OMP IF([Link].1024)
est suffisamment do j=2,n-1
do i=1,n
grande b(i,j) = a(i,j+1) – a(i,j-1)
end do
end do
!$OMP END PARALLEL DO
End program parallel
 Fonctions de bibliothèque
Fonctions relatives aux verrous
Un verrou est libre ou possédé par une thread.
„ omp_init_lock(),
omp init lock() omp
omp_set_lock(),
set lock() omp
omp_unset_lock(),
unset lock() omp
omp_test_lock()
test lock()
« omp_test_lock() » permet d’attendre à un point du code la libération d’un
verrou par une autre thread.
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()
„ Tester si le programme est actuellement dans une région parallèle

omp_in_parallel()
„ Combien y a t-il de processeurs reconnus par le système

omp num procs()

omp_num_procs()
Mesure du temps elapsed (temps de restitution) propre à chaque thread :
OMP_GET_WTIME() en double precision
OpenMP
p versus MPI
„ OpenMP exploite la mémoire commune à tous les processus.
Toute communication se fait en lisant et en écrivant dans cette
mémoire (et en utilisant des mécanismes de synchronisation)

„ MPI est une bibliothèques de routines permettant la

communication entre différents processus (situés sur différentes
machines
hi ou non),
) lles communications
i ti se ffontt par d
des envois
i
ou réceptions explicites de messages.

„ Pour le programmeur : réécriture du code avec MPI, simple

ajout de directives dans le code séquentiel avec OpenMP

„ possibilité de mixer les deux approches dans le cas de cluster

d machines
de hi à mémoire
é i partagée
t é

„ Choix fortement dépendant : de la machine, du code, du temps

que veut y consacrer le développeur et du gain recherché.

„ Extensibilité supérieure avec MPI

Références

„ [Link]
„ [Link]
„ [Link]
„ [Link]
„ « Using
U i O OpenMPMP , PPortable
t bl Sh
Shared dMMemory M
Model
d l »,
Barbara Chapman