Introduction sur la programmation
parallèle et distribuée
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Situation actuelle
Les anciens processeurs possèdent Les processeurs modernes en
seulement un cœur pour exécuter possèdent 4 ou plus pour
les instructions. exécuter les instructions.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Situation actuelle
Quand on exécute un programme séquentiel:
Les instructions sont exécutées sur un seul cœur.
Les autres cœurs sont au repos (idle)
Gaspillage des ressources disponibles.
Problématique: nous voulons que tous les
cœurs soient utilisés pour exécuter ce
programme. Mais comment ?
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Principaux modèles de parallélisation
Architectures à mémoire partagée
Intrinsics instructions vectorielles assembleur (Intel SSE2,
ARM NEON) très bas niveau
Posix Threads bibliothèque standardisée, bas niveau
OpenMP(Open Multi-Processing) API
CUDA plateforme propriétaire pour accélérateurs
OpenCL API
Architectures à mémoire distribuée
Sockets: bibliothèque standardisée, bas niveau
MPI (Message Passing Interface): bibliothèque standard pour les architectures
à mémoire distribuée.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Introduction sur OpenMP
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Introduction
OpenMP(Open Multi-Processing) API
(Application Programming Interface)
standard pour la programmation
d’applications parallèles sur architectures
à mémoire partagée:
Programmation basée sur les threads
Directives pour les opérations vectorielles
(OpenMP 4.x)
Directives pour les accélérateurs matériels
(OpenMP 4.x
Standard industriel mature et répandu
Bonne performance
Effort de programmation minimal
Portable
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Concepts généraux
Un programme OpenMP est exécute par un processus unique.
Ce processus active des processus légers (threads) à l’entrée d’une région
parallèle.
Chaque processus léger exécute une tâche composée d’instructions
Pendant l’exécution d’une tâche, une variable peut être lue et/ou modifiée en
mémoire:
Elle peut être définie dans la pile (stack) (espace mémoire local) d’un
processus léger: on parle alors de variable privée.
Elle peut être définie dans un espace mémoire partagé par tous les processus
légers ; on parle alors de variable partagée.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Concepts généraux
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Concepts généraux
Un programme OpenMP est une alternance de régions séquentielles et de
régions parallèles:
Une région séquentielle est toujours exécutée par la tâche maître dont le rang
vaut 0.
Une région parallèle peut être exécutée par plusieurs tâches à la fois.
Les tâches peuvent se partager le travail contenu dans la région parallèle.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Concepts généraux: Partage de travail
Le partage du travail consiste essentiellement à :
exécuter une boucle par répartition des itérations entre les tâches ;
exécuter plusieurs sections de code mais une seule par tâche;
exécuter plusieurs occurrences d’une même procédure par différentes tâches
(orphaning).
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Concepts généraux: Synchronisation
La synchronisation entre les tâches concurrentes peut être nécessaire pour
éviter, par exemple la modification de la valeur d’une variable partagée (cas
des opérations de réduction).
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Concepts généraux
Les tâches sont affectées aux processeurs par le système d’exploitation.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
OpenMP API
Directives et clauses de compilation:
servent à définir le partage du travail, la
synchronisation et le statut privé ou
partagé des données
sont considérées par le compilateur
comme des lignes de commentaires à
moins de spécifier une option adéquate
de compilation pour qu’elles soient
interprétées.
Fonctions et sous-programmes : pour
des fonctionnalités spécifiques
(informations dynamiques, actions sur
le runtime...). Ils font partie d’une
bibliothèque chargée à l’édition de liens
du programme.
Variables d’environnement : pour
influer sur le programme à exécuter
(nombre de threads, stratégies
d’ordonnancement...)
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Modèle d’exécution OpenMP
Le programmeur introduit des directives
établissant des régions parallèles
Durant l’exécution, leur comportement
respecte le modèle fork-join :
Le thread maître crée des threads
travailleurs et forme une équipe avec
eux
Les threads travailleurs se terminent
avec la région parallèle
Le thread maître continue son exécution
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Modèle mémoire OpenMP
Tous les threads ont accès à la même
mémoire partagée
Chaque thread possède sa propre
mémoire privée
Les données partagées sont accessibles
par tous les threads
Les données privées sont accessibles
seulement par le thread correspondant
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Principales directives OpenMP
Construction de régions parallèles
parallel : crée une région parallèle sur le modèle fork-join
Partage du travail
for : partage des itérations d’une boucle parallèle
sections : définit des blocs à exécuter en parallèle
single : déclare un bloc à exécuter par un seul thread
Synchronisation
master : déclare un bloc à exécuter par le thread maître
critical : bloc à n’exécuter qu’un thread à la fois
atomic : instruction dont l’écriture mémoire est atomique
barrier : attente que tous les threads arrivent à ce point
Gestion de tâches
task : déclaration d’une tâche fille
taskwait : attente de la fin des tâches filles
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Structure d’un programme openMP
#include <omp.h>
...
#pragma omp parallel [options]
{
...
}
options:
num_threads(expression) permet de définir le nombre de threads.
if (expression) va s'exécuter en parallèle si expression évaluée est vraie.
shared(liste_de_variables) liste de variables partagées par tous les threads
private(liste_de_variables) liste de variables privées à chaque thread.
default(none|shared|private) comportement par défaut de toutes les
variables.
reduction(operation: var) à la fin de la section parallèle, tous les threads vont
appliquer opération sur la variable var et la stocker dans la copie globale
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Compilation d’un programme OpenMP avec gcc
Utiliser le compilateur GNU gcc en spécifiant l'option de compilation fopenmp
afin de lui permettre d'interpréter les directives OpenMP.
La compilation d'un code code.c se fera donc de la manière suivante:
$ gcc code.c -o executable -fopenmp
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Exemples de code openMP
Exemple -1:
int main(){
#pragma omp parallel
// bloque 1
#pragma omp parallel num_threads(2)
// bloque 2
#pragma omp parallel if(0)
// bloque 3
}
Explications:
Bloque 1 sera exécuté par tous les threads
Bloque 2 sera exécuté par une équipe de 2 threads
Uniquement le thread principal va exécuter le Bloque 3. Si on met 1 ça serait
équivalent au premier pragma
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Exemples de code openMP
Exemple -2:
#include <omp.h>
#include <stdio.h>
int main()
{
# pragma omp parallel
{ /* Fork threads */
printf("This is thread %d\n", omp_get_thread_num());
} /* Join */
printf("Done.\n");
return 0;
}
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Partage de travail avec openMP
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Introduction
En principe, la construction d’une région parallèle et l’utilisation de quelques
fonctions OpenMP suffisent pour paralléliser une portion de code.
dans ce cas, à la charge du programmeur de répartir aussi bien le travail que
les données et d’assurer la synchronisation des tâches.
OpenMP propose trois directives (FOR, SECTIONS) qui permettent facilement
de contrôler la répartition du travail et des données en même temps que la
synchronisation au sein d’une région parallèle.
Il existe d’autres constructions OpenMP qui permettent l’exclusion de toutes
les tâches à l’exception d’une seule pour exécuter une portion de code située
dans une région parallèle.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Bibliothèque openMP
Fonctions Région séquentielle Région parallèle
call omp_set_num_threads (integer) Modifie le nombre de threads --------
void omp_set_num_threads (int) à utiliser dans l’équipe
integer omp_get_num_threads () 1 Retourne le
int omp_set_num_threads (void) nombre de threads
int omp_get_thread_num(void) 0 Retourne l’id des
threads
int omp_get_max_threads(void) Retourne le nombre max de threads
(OMP_NUM_THREADS)
int omp_get_num_procs(void) Retourne le nombre de CPUs
logical omp_in_parallel () FALSE TRUE
int omp_in_parallel (void)
call omp_set_dynamic (logical) Contrôle dynamiquement ------
void omp_set_dynamic (int) l’ajustement du nombre de
threads
logical omp_in_parallel () FALSE TRUE
int omp_in_parallel (void)
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Régions parallèles: Nombre de threads dans l’équipe
Remarques:
Le # threads par défaut est égal à 1 lorsqu’on utilise les compilateurs Sun
OpenMP.
Le # threads par défaut est égal au # CPUs lorsque on utilise les compilateurs
GCC.
=> Utiliser la variable OMP_NUM_THREADS.
Si l’ajustement dynamique du nombre de threads est activé, le système
d'exécution est autorisé à modifier le nombre de threads d'une région
parallèle à une autre
Compilateurs Sun OpenMP ont l'ajustement dynamique activée par défaut!
Mais le # threads est ajusté qu'une seule fois au début: Le # threads est
réduite, si le système est surchargé.
Compilateurs GCC ont l'ajustement dynamique désactivée par défaut.
Attention! La modification du # threads d'une région parallèle à une autre,
peut produire des résultats erronés, lors de l'utilisation threadprivate.
=> Utiliser omp_set_dynamic(0)
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Régions parallèles: Nombre de threads dans l’équipe
Utiliser la variable d’environnement OMP_NUM_THREADS avant l’exécution
du programme. Par exemple: $ export OMP_NUM_THREADS=5
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Partage de travail: Principe
CPUs RAM
for(i=0; i< 25; i++){ a[0]
a[i] = b[i] + c[i];
Travail à partager }
a[99]
for(i=25; i< 50; i++){
for(i=0; i< 100; i++){
a[i] = b[i] + c[i];
a[i] = b[i] + c[i];
} a[0]
}
for(i=50; i< 75; i++){
a[i] = b[i] + c[i]; b[99]
}
c[0]
for(i=75; i< 100; i++){
a[i] = b[i] + c[i];
}
c(99)
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Partage de travail: avec omp _get_thread_num
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Partage de travail: Boucles parallèles
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Partage de travail: sections parallèles
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Partage de travail: single
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Portée d’une variable
Dans le modèle de programmation partagé, tous les variables sont
partagées(shared).
Les variables globales sont partagées(shared): en C, variables avec attributs static
ou extern.
Exception: variables d’itération de la boucle sont privées
Variables locales d’un sous-programme appelées dans une région parallèle sont
placées dans le stack. Elles sont privées(private).
Variables statiques d’un sous-programme appelées dans une région parallèle sont
partagées(shared)en C/C++
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Portée d’une variable: defaults
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Portée d’une variable: private
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Portée d’une variable: firstprivate
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Synchronisations
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Synchronisations: Introduction
La synchronisation devient nécessaire dans les situations suivantes :
pour s’assurer que toutes les tâches concurrentes aient atteint un même
niveau d’instruction dans le programme (barrière globale) ;
pour ordonner l’exécution de toutes les tâches concurrentes quand celles-ci
doivent exécuter une même portion de code affectant une ou plusieurs
variables partagées dont la cohérence en mémoire (en lecture ou en écriture)
doit être garantie (exclusion mutuelle).
pour synchroniser au moins deux tâches concurrentes parmi les autres
(mécanisme de verrou).
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Région critique
CPUs RAM
for(i=0; i< 25; i++){
s = s + a[i];
Travail à partager }
for(i=0; i< 100; i++){ for(i=25; i< 50; i++){
s = s + a[i]; s = s + a[i];
} }
for(i=50; i< 75; i++){
s = s + a[i]; a[0]
}
for(i=75; i< 100; i++){ a[99]
s = s + a[i];
}
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Région critique: directive critical
Un et un seul processeur est autorisé à accéder la région critique à un instant
t. => Performance lente.
La région critique est extraite en dehors de la boucle
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Région critique: directive critical
La région critique peut être nommée. Ceci est utile si les régions critiques
multiples sont utilisées.
Le nom de la région critique est un nom global.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Région critique: directive atomic
Si la région critique est constituée d’une simple instruction seulement, par
exemples:
var= var op expression (ou var= intrinsic( var,expression))
var binop= expression
var++; var--; ++var;--var
=> La directive atomic pourrait être utilisée.
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Réductions: directive reduction
Une réduction est une opération associative appliquée à une variable
partagée.
La directive est de la forme: reduction({op|intrinsic}:list) avec
op= { + | * | -| .and. | .or. | .eqv. | .neqv.}
ou op= { + | * | -| & | ^ | | | && | || }
intrinsic= { max, min, iand, ior, ieor}
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Synchronisations : directive barrier
La directive BARRIER synchronise l’ensemble des tâches concurrentes dans
une région parallèle.
Chacune des tâches attend que toutes les autres soient arrivées à ce point de
synchronisation pour reprendre, ensemble, l’exécution du programme.
Les constructeurs suivants ont une barrière implicite sauf qu’elle a été
désactivée par la directive nowait: fin de for, fin de sections, fin de single, fin
de workshare
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018
Références
[1] - [Link]
[2] - [Link]
[3] - [Link]
[4] - [Link]
[5] – [Link]
05/09/2018 Cours M1 - ENI 2015 - Mise à jour 2018