PARALLEL

COMPUTING

Master 1 Génie Informatique

Par TSHIKUTU Bikengela Anaclet

PhD Student
 OBJECTIFS
2

SPÉCIFIQUES
• Threads (Java, C, Python)
• OpenMP
À la fin du cours, l’étudiant sera capable de : • MPI
• Analyser un problème pour identifier son potentiel de parallélisation • GPU (CUDA / OpenCL - introduction)

• Comparer les modèles de parallélisme (mémoire partagée vs

distribuée) • Synchronisation
• Concevoir des algorithmes parallèles efficaces • Interblocage (deadlock)
• Conditions de course
• Évaluer les performances (speedup, efficacité, scalabilité)
• Utiliser des outils et frameworks modernes :
• Gérer les problèmes classiques :
• Optimiser les performances :
• Développer une application parallèle complète (projet de fin) • Répartition de charge (load balancing)
• Localité mémoire
CONTENU
Chapitre 1 : Rappels et fondements du parallélisme
Chapitre 2 : Architectures parallèles et Modèles de
programmation parallèle
Chapitre 3 : Programmation multi-thread
Chapitre 4 : OpenMP (mémoire partagée) et MPI
(mémoire distribuée)
Chapitre 5 : Performance, Optimisation et Applications
avancées
PRÉREQUIS
- Algorithmique (complexité, structures
de données)
- Programmation (Java, C, Python)
- Notions de base vues en L3 :
• Threads
• Processus
• Synchronisation de base
 CHAPITRE 1 : FONDEMENTS
5

DU CALCUL PARALLÈLE

1. Introduction au calcul parallèle

On ne va pas plus vite en faisant mieux une tâche, mais en faisant

plusieurs tâches en même temps.
2. EXPLOSION DES BESOINS DE CALCUL6

• Avant : augmentation de fréquence

• Aujourd’hui : augmentation du nombre de cœurs
• GPU → milliers de cœurs
3. TYPES DE PARALLÉLISME 7
3.1 Parallélisme de données
Même instruction sur plusieurs
données.
Très utilisé en :
• IA
• traitement d’image

3.2 Parallélisme de tâches

Plusieurs tâches différentes
Exemple : serveur web

3.3 Pipeline TD
• Chaque étape traite une partie
du flux
• Très utilisé en architecture
CPU
 3. TYPES DE PARALLÉLISME 8

Considérons le programme séquentiel suivant qui calcule un

Le parallélisme de données :
vecteur de polynômes
Les instances du corps de la
boucle du problème (VP) peuvent
s’exécuter indépendamment les
unes des autres :

Chaque vv[i] peut être calculé

sur un processeur Pi (i=0, . . ., n-
1)
 3. TYPES DE PARALLÉLISME 9

Considérons le programme séquentiel suivant qui calcule un

Le parallélisme de contrôle :
vecteur de polynômes Chaque processus possède ses
données privées. On évalue le
polynôme du programme (VP)
en parallèle

On obtient trois sous-expressions de

complexité comparable
Chaque sous-expression sera évaluée par
un processeur différent
3. TYPES DE PARALLÉLISME 10

Le problème à résoudre devient

 4. MESURE DES
11

PERFORMANCES
Dans le calcul parallèle, l’objectif n’est pas seulement de :
• paralléliser un programme
• mais de gagner réellement en performance

Donc on doit répondre à :

• Est-ce que le parallélisme est efficace ?
• Combien de temps avons-nous gagné ?
• Est-ce que ça vaut la peine d’utiliser plusieurs
processeurs ?
1. Temps d’exécution (Execution
Time)

C’est le temps nécessaire pour exécuter

un programme.
• Tₛ : temps séquentiel • Si Tₚ < Tₛ → parallélisme utile OK
• Tₚ : temps parallèle • Sinon → mauvaise parallélisation KO
4. MESURE DES
12

PERFORMANCES
2. Speedup (l'accélération)

C’est le gain obtenu avec le parallélisme :

Exemple
• Tₛ = 10 secondes
• Tₚ = 2 secondes
Donc, S = 5
Alors, le programme est 5 fois plus rapide

• S > 1 → amélioration
• S = p (idéal) → parfait
• S=1 : Aucun gain
4. MESURE DES
13

PERFORMANCES
3. Efficacité

Valeur Signification
E≈1 excellente utilisation
E<1 pertes (overhead)

Où: Exemple
• p = nombre de processeurs • S=4
• p=8

E = 0.5 (50%)
Donc, seulement la moitié des ressources est
utilisée efficacement
4. MESURE DES
14

PERFORMANCES
4. Scalabilité (Scalability)

Définition
Capacité d’un système à rester performant
quand on augmente les ressources
• Bonne scalabilité → performance
stable
Types • Mauvaise → saturation
Strong Scaling
• Taille du problème fixe
• On augmente les processeurs
Weak Scaling
• Taille du problème augmente avec les
processeurs
4. MESURE DES
15

PERFORMANCES
5. Coût du parallélisme

Définition

𝐶 = 𝑝 × 𝑇𝑝

• Coût = ressources utilisées

• Objectif : coût minimal
 16
5. LOI D’AMDAHL
Rappel théorique

Amdahl considère qu’un

programme comporte une
fraction séquentielle (1 – P)
et une fraction parallélisable
(P).

𝟏
𝑺=
𝑷
𝟏−𝑷 +𝑵

• P : partie parallélisable
• N : nombre de processeurs
 17
5. LOI D’AMDAHL

Nota:
Même avec beaucoup de
processeurs :
• la partie séquentielle bloque la
performance
Exemple :
• 90% parallèle → limite ≈ 10x
 18
6. LOI DE GUSTAFSON
Principe

Contrairement à Amdahl :
• on augmente la taille du
problème
La loi de Gustafson (ou Gustafson's Formule
Law) est un principe de calcul 𝑆=𝑁− 1−𝑃 𝑁−1
parallèle formulé par John L.
Gustafson en 1988. Elle propose une
vision alternative à la loi d'Amdahl
pour évaluer la performance des
systèmes parallèles, soulignant que
les gains de vitesse dépendent de la
taille du problème, pas seulement de
la fraction séquentielle du
programme.
 19
COMPARAISON AMDAHL VS GUSTAFSON

courbe de Gustafson

Plus de processeurs = plus de travail

possible

courbe d’Amdahl

• Au début : croissance rapide

• Ensuite : la courbe ralentit puis se
stabilise
 20

Définition
Taille des tâches parallèles
GRANULARITÉ DU PARALLÉLISME 21

Types Exemple simple

Type Description Somme d’un tableau de 1 000 000 éléments

Fine petites tâches Cas 1 : granularité fine
Grossière grandes tâches • 1 élément par tâche
• 1 000 000 tâches
Imaginez que vous avez un travail à Résultat :
partager : • trop de gestion → lent
• Si vous divisez en trop petites tâches:
beaucoup de gestion Cas 2 : granularité moyenne
• Si vous divisez en grosses tâches: • 1000 éléments par tâche
moins de gestion Résultat :
Donc : • bon équilibre
Il faut trouver un équilibre optimal
Cas 3 : granularité grossière
• 250 000 éléments par tâche
Résultat :
• très efficace
 22
8. OVERHEAD DU PARALLÉLISME
Définition

Coût supplémentaire introduit par

le parallélisme :
• communication
• synchronisation
• création de threads

Impact
Trop de parallélisme ⇒ inefficacité

Formulation mathématique

𝑂𝑣𝑒𝑟ℎ𝑒𝑎𝑑 = 𝑝 × 𝑇𝑝 − 𝑇𝑠
•𝑇𝑠 :temps séquentiel
•𝑇𝑝 :temps parallèle
•𝑝: nombre de processeurs
 23
9. DÉCOMPOSITION D’UN PROBLÈME
 24
9. DÉCOMPOSITION D’UN PROBLÈME
Étapes

• Partitionnement
• Communication
• Synchronisation
• Agrégation des résultats
 25
9. DÉCOMPOSITION D’UN PROBLÈME
Aider le compilateur à
paralléliser

Voici quelques conseils qui peuvent Pensez à utiliser les instructions sum, product, etc quand c'est
aider le compilateur: possible. Par exemple, écrivez
somme = sum(a)
1. Utilisez des instructions globales plutôt que
plutôt que des sommes sur les somme = 0 ;
indices. for (i = 1 ; i<= n ; i++) {
somme = somme + a(i);
Par exemple, écrivez : }
s = a + b ;
plutôt que

for (i = 1; i<= n ; i++) {

s(i) = a(i) + b(i);
}
 26
9. DÉCOMPOSITION D’UN PROBLÈME
Aider le compilateur à
paralléliser

Voici quelques conseils qui peuvent

aider le compilateur:

2. Evitez d'encombrer vos boucles avec

des instructions qui peuvent laisser le
compilateur penser que les itérations
ne sont pas indépendantes. Par
exemple, évitez ceci:
for (i = 1 ; i<= n ; i++)
{ num = num + 1 ; /*dépend ici des itérations
précédentes*/
. . . int souspr(int num) ;
/* On ne sait pas comment souspr affecte num ou
d'autres variables. En cas de doute, compilateur
préfère ne pas paralléliser. */ }
 27
9. DÉCOMPOSITION D’UN PROBLÈME
Répartir les données à
traiter

Si votre parc informatique vous permet de Comment faire si toutes les machines ne sont pas
lancer plusieurs exécutables en même identiques?
temps, vous pouvez paralléliser votre
problème en confiant à chaque machine Il faut éviter de confier aux machines les plus
les calculs correspondant à une partie de lentes trop de travail sous peine de devoir
ce problème. L'idée ici est de finalement les attendre. L'idée est de confier à
paralléliser la tâche à réaliser plutôt chaque machine la bonne quantité de travail,
que le programme lui-même. Ce afin qu'elles terminent toutes en même temps.
dernier en effet ne doit subir aucune
modification. Notons que l’affectation
des tâches aux processeurs pose un
problème d’ordonnancement.
 28
9. DÉCOMPOSITION D’UN PROBLÈME
Répartir les données à
traiter
Comment faire si toutes les machines a. Modèle de distribution continue
ne sont pas identiques?
Pour fixer les choses, supposons que nos ayons 10 machines
Nous pouvons considérer les modèles supplémentaires, 3 fois plus lentes que les 20 premières. Nous
d’ordonnancement suivants : avons 100 calculs à réaliser, qui prennent une minute chacun
sur les machines les plus rapides et donc 3 minutes sur les
plus lentes. Soient N=100 le nombre de calculs à réaliser,
N1=20 le nombre d'ordinateurs rapides, N2=10 le nombre
d'ordinateurs lents. Appelons v1=3 la vitesse des machines
rapides et v2=1 la vitesse des machines lentes. On cherche le
nombre n1 de calculs à confier à chaque machine rapide et le
nombre n2 de calculs à confier à chaque machine lente.

On doit alors satisfaire: n1.N1 + n2*N2=N n1=4.2857...

n1/v1= n2/v2 n2=1.4285...
 29
9. DÉCOMPOSITION D’UN PROBLÈME
Répartir les données à
traiter
Nous pouvons considérer les modèles b. Modèle de distribution discrète
d’ordonnancement suivants :
L'algorithme est donc:
1. Classer les processeurs par ordre
décroissant de rapidité
2. Distribuer les tâches une par une:
- en commençant par la gauche
- en se décalant d'une case vers la
droite si ni/vi (ni+1+1)/vi+1
- en revenant à la première case si
cette condition n'est pas vérifiée ou si on
arrive tout à droite
 30
9. DÉCOMPOSITION D’UN PROBLÈME
Répartir les données à
traiter
Nous pouvons considérer les modèles b. Modèle de distribution discrète
d’ordonnancement suivants :
L'algorithme est donc:
1. Classer les processeurs par ordre
décroissant de rapidité
2. Distribuer les tâches une par une:
- en commençant par la gauche
- en se décalant d'une case vers la
droite si ni/vi (ni+1+1)/vi+1
- en revenant à la première case si
cette condition n'est pas vérifiée ou si on
arrive tout à droite
 31
9. DÉCOMPOSITION D’UN PROBLÈME
Modèle d’exécution avec OpenMP

• Attention aux conflits.

• Très peu de surcoût de
parallélisation.
• Le plus souvent nombre de
processeurs < 32.
• Architecture coûteuse.
 32
9. DÉCOMPOSITION D’UN PROBLÈME
Modèle de communication avec MPI

Le dernier modèle est celui où les

processeurs n'ont pas accès à une
zone mémoire commune, mais
possèdent uniquement une mémoire
privée, visible par eux seul
(distributed memory).
 33
10. ÉTUDE DE CAS SIMPLE
Somme d’un tableau
Séquentiel :
s = 0
for i in range(n):
s += T[i]

Parallèle :
• division du tableau
• calcul partiel
• fusion
 34
EXERCICES
Somme d’un tableau

Exercice 1 Exercice 2
Un programme a : Comparer :
• 80% parallélisable • parallélisme de données
• 4 processeurs • parallélisme de tâches
Calculer le speedup (Amdahl) avec exemples concrets

Exercice 3
Donner un exemple réel en RDC où le
calcul parallèle est utile
 35
TRAVAUX PRATIQUES (TP)

Mesure du speedup en Python

1. implémenter :
• version séquentielle
• version parallèle (threading / multiprocessing)
2. comparer les temps
 CHAPITRE 2 :
36

ARCHITECTURES PARALLÈLES

parallèles
1. Introduction aux architectures
Définition avancée

Une architecture parallèle est un

système informatique conçu pour
exécuter simultanément plusieurs
flux d’instructions ou de données,
en exploitant plusieurs unités de
calcul.

Objectifs fondamentaux

• Accélération des traitements (HPC)

• Traitement de grandes masses de
données (Big Data)
• Simulation scientifique (climat,
médecine)
• Intelligence artificielle
 CHAPITRE 2 :
37

ARCHITECTURES PARALLÈLES

2. Architectures parallèles
2.1 Classification de Michael J. Flynn

Principe

Classification basée sur :

• flux d’instructions
• flux de données
 CHAPITRE 2 :
38

ARCHITECTURES PARALLÈLES

2. Architectures parallèles
2.1 Classification de Michael J. Flynn

SISD: Single Instruction Single Data

Une seule instruction traite une seule

donnée

Exemple :
Programme classique (séquentiel)

TD: Algo – Pseudo code

Somme et moyenne d’un vecteur de

100 notes saisies au clavier
 CHAPITRE 2 :
39

ARCHITECTURES PARALLÈLES

2. Architectures parallèles
2.1 Classification de Michael J. Flynn

SIMD: Single Instruction Multiple Data

Une instruction traite plusieurs données en

parallèle

Exemple :
• traitement d’image (pixels)
• GPU
 CHAPITRE 2 :
40

ARCHITECTURES PARALLÈLES

2. Architectures parallèles
2.1 Classification de Michael J. Flynn

MISD: Multiple Instruction Single Data

Plusieurs instructions appliquées à une

seule donnée

Rare :
• systèmes critiques (aéronautique)
 CHAPITRE 2 :
41

ARCHITECTURES PARALLÈLES

2. Architectures parallèles
2.1 Classification de Michael J. Flynn

MIMD: Multiple Instruction Multiple Data

Plusieurs instructions sur plusieurs données

Exemple :
• multi-core
• clusters
 CHAPITRE 2 :
42

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.2 Architecture à mémoire partagée (SMP: Symmetric MultiProcessing)
les processeurs sont connectés
par l’intermédiaire d’un RI à
une même mémoire qu’ils
partagent.

Types
• UMA: Uniform Memory
Access
• NUMA: Non-Uniform
Memory Access

Programmation simple
 CHAPITRE 2 :
43

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.2 Architecture à mémoire partagée (SMP: Symmetric MultiProcessing)

Rôle du réseau d’interconnexion (RI)

• Le réseau d’interconnexion (RI) relie
les processeurs à la mémoire.
Il permet :
• le transfert rapide des données entre
CPU et mémoire,
• la gestion de la cohérence du cache
(pour que chaque processeur voie la
même version des données),
• la coordination entre les accès
concurrents.
Si le bus est saturé ou lent, cela peut devenir
un goulot d’étranglement.
 CHAPITRE 2 :
44

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.3 Architecture à mémoire distribuée (MPP: Massively Parallel
Processing).

Dans les architectures à mémoire

distribuée chaque processeur ne peut
accéder qu'à sa propre mémoire.
 CHAPITRE 2 :
45

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.3 Architecture à mémoire distribuée (MPP: Massively Parallel
Processing).

Avantages

• Évolutivité : facile d’ajouter des

processeurs sans saturer la
mémoire.
• Tolérance aux pannes : une
défaillance sur un nœud n’affecte
pas directement les autres.
• Haute performance : adaptée
aux calculs massifs et aux grandes
bases de données.
 CHAPITRE 2 :
46

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.3 Architecture à mémoire distribuée (MPP: Massively Parallel
Processing).

Inconvénients

• Programmation complexe : il
faut gérer explicitement l’échange
de données entre processeurs.
• Temps de communication : les
échanges par le réseau sont plus
lents que l’accès à la mémoire
locale.
• Synchronisation difficile : il
faut s’assurer que les messages
arrivent au bon moment et dans
le bon ordre.
 CHAPITRE 2 :
47

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture Hybride

Principe
• combinaison des deux modèles

Exemple
• cluster de machines multi-core

Chaque machine possède plusieurs cœurs partageant Message clé pour les étudiants :
une mémoire locale, et plusieurs machines sont Une architecture hybride combine
reliées entre elles par un réseau. OpenMP + MPI.
 CHAPITRE 2 :
48

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture Hybride

Avantages de l’architecture hybride

• Haute performance
• Très bonne scalabilité
• Réduction du trafic réseau
• Flexibilité
• Adaptée aux grands volumes de
données
 CHAPITRE 2 :
49

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture Hybride

Inconvénients de l’architecture hybride

• Complexité de programmation
• Synchronisation complexe
• Débogage difficile
• Gestion mémoire complexe
• Coût matériel élevé
• Consommation énergétique
 CHAPITRE 2 :
50

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture GPU (CUDA / OpenCL)

Un GPU (Graphics
Processing Unit) est un
processeur spécialisé conçu
pour exécuter un très grand
nombre d’opérations en
parallèle.

Contrairement au CPU, il
contient :
des centaines à des
milliers de cœurs
optimisés pour calcul
parallèle massif
 CHAPITRE 2 :
51

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture GPU (CUDA / OpenCL)

Rôle initial du GPU

Au départ, le GPU servait

pour :
• affichage graphique
• rendu d’images
• jeux vidéo

Aujourd’hui, il est utilisé

pour :
• intelligence artificielle
• simulation scientifique
• Big Data
• traitement d’image
 CHAPITRE 2 :
52

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture GPU (CUDA / OpenCL)

Critère CPU GPU

Nombre de cœurs faible très élevé
Type de calcul complexe répétitif
Performance parallèle moyenne très élevée
Mémoire RAM VRAM
 CHAPITRE 2 :
53

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture GPU (CUDA / OpenCL)

Architecture interne du GPU

Structure générale

Un GPU contient :
• Streaming Multiprocessors (SM)
• Mémoire partagée
• Mémoire globale
• Cache
 CHAPITRE 2 :
54

ARCHITECTURES PARALLÈLES

3. Architectures mémoire
3.4 Architecture GPU (CUDA / OpenCL)

TP pour demain

Etude approfondie entre

l’architecture CUDA et OpenCL
 CHAPITRE 3 : 55

PROGRAMMATION MULTI-
THREAD

1. Introduction aux threads

Définition

Un thread est une unité

d’exécution légère appartenant à
un processus.

Un processus peut contenir un

ou plusieurs threads
Exemple simple

Navigateur Web :
• Thread 1: chargement page
• Thread 2: lecture vidéo
• Thread 3: téléchargement
 CHAPITRE 3 : 56

PROGRAMMATION MULTI-
THREAD

2. Processus vs Thread
Définition Processus

Un processus est un
programme en cours
d’exécution.

Différences principales

Critère Processus Thread

Mémoire séparée partagée
Création coûteuse rapide
Communication lente rapide
 CHAPITRE 3 : 57

PROGRAMMATION MULTI-
THREAD

3. Création des threads

1. Namespace utilisé en multithreading

using [Link];

Rôle

Permet d’accéder aux classes nécessaires

pour :
• créer des threads
• synchroniser des threads Classes principales disponibles
• gérer la concurrence
• Thread
• Mutex
• Monitor
• Semaphore
• AutoResetEvent
 CHAPITRE 3 : 58

PROGRAMMATION MULTI-
THREAD

3. Création des threads

1. Namespace utilisé en multithreading

using [Link];

Exemple
using System;
using [Link];

class Program
{
static void Main()
{
[Link]("Multithreading
activé");
}
}
 CHAPITRE 3 : 59

PROGRAMMATION MULTI-
THREAD

3. Création des threads

1. Namespace utilisé en multithreading
Méthodes importantes
1.1. Classe Thread Méthode Rôle
Start() démarre thread
(C’est la classe la plus importante)
Sleep() pause thread
Définition Join() attendre thread
La classe Thread permet de créer, Abort() arrêter thread (obsolète)
contrôler et exécuter un thread.
Syntaxe
Thread t = new Thread(methode);
 CHAPITRE 3 : 60

PROGRAMMATION MULTI-
THREAD

3. Création des threads

using System;
Exemple using [Link];

class Program
{
static void Travail()
{
[Link]("Thread actif");
}

static void Main()

{
Thread t = new Thread(Travail);

[Link]();

[Link]("Main actif");
}
}
 CHAPITRE 3 : 61

PROGRAMMATION MULTI-
THREAD

3. Création des threads

Classe ThreadStart
Syntaxe
Définition ThreadStart ts = new ThreadStart(methode);
Thread t = new Thread(ts);
Représente une méthode sans
paramètre, sans valeur retournée,
utilisée pour démarrer un thread.

Exemple
ThreadStart ts = new ThreadStart(Travail);
Thread t = new Thread(ts);
[Link]();
 CHAPITRE 3 : 62

PROGRAMMATION MULTI-
THREAD
Exemple

3. Création des threads

Classe ParameterizedThreadStart
static void Travail(object obj)
{
Définition
[Link](obj);
Permet de passer des paramètres à un }
thread.
Thread t = new Thread(
new
Syntaxe ParameterizedThreadStart(Travail)
);
Thread t = new Thread(new
ParameterizedThreadStart(metho [Link]("Thread avec paramètre");
de));
 CHAPITRE 3 : 63

PROGRAMMATION MULTI-
THREAD
Syntaxe

3. Création des threads

Classe Mutex
Mutex m = new Mutex();
Définition
Permet d’assurer un accès unique
Exemple
entre plusieurs threads ou plusieurs
processus. Mutex m = new Mutex();

Méthodes importantes [Link]();

Méthode Rôle [Link]("Accès

sécurisé");
WaitOne() demander accès
ReleaseMutex() libérer accès [Link]();
 CHAPITRE 3 : 64

PROGRAMMATION MULTI-
THREAD
Syntaxe

3. Création des threads

Classe Semaphore
Semaphore s = new Semaphore(2, 2);
Définition
Permet de limiter le nombre de Exemple
threads accédant à une ressource.
Semaphore s = new Semaphore(2, 2);

[Link]();

[Link]("Thread
autorisé");

[Link]();
 CHAPITRE 3 : 65

PROGRAMMATION MULTI-
THREAD
Syntaxe

3. Création des threads

Classe Monitor [Link](obj);
[Link](obj);
Définition Exemple
Permet de contrôler l’accès à
une ressource partagée. object verrou = new object();

[Link](verrou);

[Link]("Section
critique");

[Link](verrou);
 CHAPITRE 3 : 66

PROGRAMMATION MULTI-
THREAD

3. Création des threads

Classe Rôle
Thread créer thread
Mutex accès unique
Semaphore limiter accès
Monitor synchronisation
ThreadPool réutilisation
Timer exécution périodique
AutoResetEvent synchronisation
ManualResetEvent synchronisation multiple
Interlocked opérations atomiques
SpinLock verrou rapide
 CHAPITRE 3 : 67

PROGRAMMATION MULTI-
THREAD

4. Cycle de vie des threads

 CHAPITRE 3 : 68

PROGRAMMATION MULTI-
THREAD

4. Cycle de vie des threads

 CHAPITRE 3 : 69

PROGRAMMATION MULTI-
THREAD

5. Multithreading et performance
 CHAPITRE 3 : 70

PROGRAMMATION MULTI-
THREAD

5. Multithreading et performance
Déterminisme d’un système de tâches

Soit, par exemple, deux processus qui accèdent sans contrôle à une même
cellule mémoire M, contenant la valeur 10, le premier pour y ajouter 5, le
deuxième pour doubler la valeur contenue dans M.

Suivant l’ordre d’accès à M des deux processus, on obtient

comme valeur finale soit :
(10 + 5) * 2 = 30,
soit :
(10 * 2) + 5 = 25.
 CHAPITRE 3 : 71

PROGRAMMATION MULTI-
THREAD

5. Multithreading et performance
 CHAPITRE 3 : 72

PROGRAMMATION MULTI-
THREAD

5. Multithreading et performance
 CHAPITRE 3 : 73

PROGRAMMATION MULTI-
THREAD

5. Multithreading et performance
 CHAPITRE 3 : 76

PROGRAMMATION MULTI-
THREAD
using System;
Exemple applicatif

5. Multithreading et performance
using [Link];
Somme parallèle d’un tableau class Program
{
static void Main()
{
int[] tab = {1,2,3,4,5};

int somme = 0;

[Link](0, [Link], i =>

{
lock(tab)
{
somme += tab[i];
}
});

[Link](somme);
}
}
 CHAPITRE 3 : 77

PROGRAMMATION MULTI-
THREAD
Exemple applicatif

5. Multithreading et performance
Simulation de téléchargement

static void Download()

{
[Link]("Téléchargement...");
}

Thread t1 = new Thread(Download);

Thread t2 = new Thread(Download);

[Link]();
[Link]();
 CHAPITRE 4 :
PROGRAMMATION AVEC
78

OPENMP
1. Définition

OpenMP (Open Multi-Processing) est une API (Application

Programming Interface) qui permet de programmer en parallèle
sur des machines à mémoire partagée (comme les processeurs
multicœurs).

Elle repose sur des directives de compilation intégrées dans le

code C, C++ ou Fortran à l’aide de pragma (#pragma omp ...).

2. Principe de base
OpenMP divise l’exécution d’un programme en plusieurs threads
(lignes d’exécution parallèles) qui partagent la même mémoire.
 CHAPITRE 4 :
PROGRAMMATION AVEC
79

OPENMP
Modèle d'exécution

OpenMP utilise le modèle Fork-Join. Le programme commence

par un thread unique appelé Master Thread. Lorsqu'une directive
parallèle est rencontrée, il crée ("fork") une équipe de threads
esclaves. À la fin du bloc, les threads se synchronisent et s'arrêtent
("join"), laissant le Master Thread continuer seul.
 CHAPITRE 4 :
PROGRAMMATION AVEC
80

OPENMP
3. Étapes du développement parallèle avec OpenMP
Étape Description
Identifier les parties parallélisables du
1. Analyse du problème
code.
Déterminer les variables partagées et
2. Définition des données
privées.
3. Ajout des directives Utiliser #pragma omp pour activer le
OpenMP parallélisme.
Utiliser les mécanismes de verrouillage
4. Synchronisation
et de réduction.
5. Vérification & Comparer les performances
optimisation séquentielles et parallèles.
 CHAPITRE 4 :
PROGRAMMATION AVEC
81

OPENMP
4. Directives de base OpenMP
• Directive #pragma omp parallel

Crée une région parallèle : plusieurs

threads exécutent le bloc de code.

#include <stdio.h>
#include <omp.h>
int main() {
#pragma omp parallel
{
int id = omp_get_thread_num(); // Récupère l'ID du thread
printf("Hello depuis le thread %d\n", id);
}
return 0;
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
82

OPENMP
4. Directives de base OpenMP

• Directive #pragma omp for

Distribue les itérations d’une boucle entre threads.

#pragma omp parallel for

for (int i = 0; i < N; i++) {
A[i] = B[i] + C[i];
}

Ici, si vous avez 4 threads, le thread 0 traitera les indices 0-249,

le thread 1 les indices 250-499, etc.
 CHAPITRE 4 :
PROGRAMMATION AVEC
83

OPENMP
4. Directives de base OpenMP
• Directive #pragma omp sections

Permet d’exécuter plusieurs blocs indépendants en parallèle.

#pragma omp parallel sections

{
#pragma omp section
fonction1();

#pragma omp section

fonction2();
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
84

OPENMP
4. Directives de base OpenMP
• Directive #pragma omp single
Exécute un bloc par un seul thread.

#pragma omp parallel

{
#pragma omp single
printf("Initialisation faite par un seul
thread\n");
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
85

OPENMP
Le Problème des Conditions de Course (Race Conditions)

Si deux threads tentent d'incrémenter la même variable somme en même temps,

le résultat sera faux. OpenMP propose deux solutions majeures :

A. La Clause reduction
(La plus performante)
int somme = 0;
Elle crée une copie privée #pragma omp parallel for
par thread, puis combine reduction(+:somme)
les résultats à la fin de for (int i = 0; i < 100; i++) {
manière sécurisée. somme += i;
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
86

OPENMP
A. La Clause reduction (La plus performante)

• Directive #pragma omp reduction

Combine automatiquement les résultats des threads.

#pragma omp parallel for reduction(+:somme)

for (int i = 0; i < N; i++) {
somme += A[i];
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
87

OPENMP
B. La Directive critical

• Directive #pragma omp critical

Protège une section critique (accès à une ressource partagée).

#pragma omp parallel for

for (int i = 0; i < N; i++) {
#pragma omp critical
somme += A[i];
}
#pragma omp critical
{
// Un seul thread à la fois
ici
global_counter++;
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
88

OPENMP
5. Gestion des variables
Les variables sont définies comme privée, globale, etc. comme
nous le démontrons ci-après:

Syntaxe Signification
shared(var) Variable partagée entre tous les threads
private(var) Chaque thread possède sa copie locale
firstprivate(var) Copie initialisée à la valeur du maître
reduction(op:var
Combine les résultats (somme, min, max, etc.)
)
 CHAPITRE 4 :
PROGRAMMATION AVEC
89

OPENMP

5. Gestion des variables

Les clauses s'ajoutent à la fin d'une directive pour préciser le comportement

des variables ou l'organisation du travail.
#pragma omp parallel for reduction(+:moyenne) shared(tab)
 CHAPITRE 4 :
PROGRAMMATION AVEC
90

OPENMP #include <omp.h>

#include <stdio.h>

Exemple Récapitulatif : int main() {

Calcul d'une Moyenne int i;
double moyenne = 0;
double tab[1000];
Voici un exemple qui combine
directives et clauses pour // Initialisation
illustrer leur rôle : for(i=0; i<1000; i++) tab[i] = i * 1.5;

// DIRECTIVE: parallel for (création threads + partage de boucle)

// CLAUSE: reduction (pour sommer en sécurité)
// CLAUSE: shared (le tableau est le même pour tous)
#pragma omp parallel for reduction(+:moyenne) shared(tab)
for (i = 0; i < 1000; i++) {
moyenne += tab[i]; // Chaque thread travaille sur sa partie
}

moyenne /= 1000;
printf("Moyenne = %f\n", moyenne);
return 0;
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
91

OPENMP
6. Contrôle du parallélisme
Les variables sont définies comme privée, globale, etc. comme
nous le démontrons ci-après:

• Fixer le nombre de threads: omp_set_num_threads(4);

• Obtenir des informations:
int id = omp_get_thread_num(); // Numéro du thread
int n = omp_get_num_threads(); // Nombre total de
threads
 CHAPITRE 4 :
PROGRAMMATION AVEC
92

OPENMP
7. L'Ordonnancement (Scheduling)

La clause schedule détermine comment les itérations sont

distribuées.
static : Les itérations sont divisées en blocs de taille égale au début.
Très peu de "surcoût" (overhead), mais sensible au déséquilibre
de charge.
dynamic : Les threads demandent de nouveaux blocs dès qu'ils
finissent les leurs. Idéal si les itérations n'ont pas toutes le même
temps de calcul.
 CHAPITRE 4 :
PROGRAMMATION AVEC
93

OPENMP
Exercice d'Application : Produit Matrice-Vecteur
Voici comment structurer un calcul complexe :
#pragma omp parallel for private(j) shared(A, x, y, n)
for (i = 0; i < n; i++) {
y[i] = 0.0;
for (j = 0; j < n; j++) {
y[i] += A[i][j] * x[j];
}
}

Analyse technique :

• La boucle externe i est parallélisée.

• La variable j doit être privée pour chaque thread afin d'éviter que le thread 1
ne modifie l'indice de boucle du thread 0.
 CHAPITRE 4 :
PROGRAMMATION AVEC
94

OPENMP
Compilation et Exécution
#include <stdio.h>
1) Préparer le test (code #include <omp.h>

source) int main() {

Crée un nouveau fichier #pragma omp parallel
{
source (ou projet) dans int id = omp_get_thread_num();
Dev-C++ et colle ce code int n = omp_get_num_threads();
#pragma omp critical
test_openmp.c : printf("Hello from thread %d /
%d\n", id, n);
}

printf("omp_get_max_threads() = %d\n",
omp_get_max_threads());
return 0;
}
 CHAPITRE 4 :
PROGRAMMATION AVEC
95

OPENMP
Compilation et Exécution

2) Ajouter l’option OpenMP

dans Dev-C++
Important : OpenMP s’active
via l’option -fopenmp et la
bibliothèque libgomp. Si la
chaîne GCC incluse dans Dev-
C++ contient libgomp, tout ira
bien. Sinon il faudra installer
une distribution MinGW
 CHAPITRE 4 :
PROGRAMMATION AVEC
96

OPENMP
Compilation et Exécution
Étapes :
[Link] Dev-C++.
[Link]ée un Nouveau → Project → Console Application → C Project (ou C++ si tu veux).
Donne un nom et enregistre.
[Link] le fichier source et écris ton code sources.
[Link] dans le menu Project → Project Options... (ou Project → Parameters selon la version).
[Link] Parameters (Paramètres) :
1. Dans la zone Compiler (ou Compiler Options → Add to command line), ajoute
exactement :
2.-fopenmp
3. Dans la zone Linker (Linker Options), normalement rien d’autre à ajouter ; -
fopenmp suffit généralement (le compilateur ajoute automatiquement -lgomp au
linking). Si tu as un lien manquant, ajoute :
4.-lgomp
[Link] sur OK
 CHAPITRE 4 :
PROGRAMMATION AVEC
97

OPENMP
Compilation et Exécution
Compiler et exécuter
Dans Dev-C++ clique Compile → Compile & Run (F9) ou l’icône de compilation.

Si tu obtiens une erreur de compilation ou d’édition de liens

Erreurs possibles :
•undefined reference to 'omp_get_thread_num' ou cannot find -
lgomp : cela signifie que la distribution MinGW/GCC utilisée n’inclut pas la
bibliothèque OpenMP (libgomp) ou n’est pas correctement configurée dans
Dev-C++.
Dans ce cas, passe à l’installation de la distribution MinGW.
 CHAPITRE 4 :
PROGRAMMATION AVEC
98

OPENMP
Exemple #include <stdio.h>
#include <omp.h>
Ecrire un programme
int main() {
parallèle en C qui fait
long N = 1000000;
la somme d’un vecteur double sum = 0.0, data[N];
contenant les entiers.
for (long i = 0; i < N; i++)
data[i] = i;

#pragma omp parallel for reduction(+:sum)

for (long i = 0; i < N; i++)
sum += data[i];

printf("Somme totale = %.0f\n", sum);

}
 CHAPITRE 4 : PROGRAMMATION 99
AVEC OPENMP
Exercices
Exercice 1 : Analyse de la Portée des Variables (Scope)
Énoncé : Soit le fragment de code C suivant utilisant OpenMP :
int a = 10, b = 20, c = 30;
#pragma omp parallel private(a) firstprivate(b) shared(c)
{
int id = omp_get_thread_num();
a = a + id;
b = b + id;
c = c + id;
printf("Thread %d: a=%d, b=%d, c=%d\n", id, a, b, c);
}
printf("Final: a=%d, b=%d, c=%d\n", a, b, c);

Questions :
1. Si le programme est exécuté avec 2 threads (ID 0 et 1), quelles seront les valeurs affichées par chaque
thread pour a et b ? Justifiez.
2. Pourquoi l'utilisation de la variable c dans ce bloc est-elle dangereuse ? Quel phénomène risque de se
produire ?
3. Quelle sera la valeur finale de a après la zone parallèle ?
CHAPITRE 4 : PROGRAMMATION100
AVEC OPENMP
Exercices
Exercice 2
On souhaite calculer le produit scalaire de deux vecteurs U et V de
taille N. Le produit scalaire est défini par :

1. Écrivez le code séquentiel en C.

2. Proposez une version parallélisée avec omp parallel for en utilisant une
clause critical.
3. Proposez une seconde version utilisant la clause reduction.
4. Analyse : Laquelle des deux versions (2 ou 3) sera la plus performante
sur un processeur multi-cœurs ? Pourquoi ?
CHAPITRE 4 : PROGRAMMATION101
AVEC OPENMP
Exercices
Exercice 3 : Dépendances de Données
Toutes les boucles for ne sont pas parallélisables. Analysez les deux boucles suivantes :
Boucle A :
for (i = 0; i < N; i++) {
A[i] = B[i] + C[i];
}

Boucle B :
for (i = 1; i < N; i++) {
A[i] = A[i-1] + B[i];
}
Questions :
1. Laquelle de ces boucles peut être parallélisée directement avec #pragma omp parallel for ?
2. Expliquez pourquoi l'autre boucle pose problème en termes de dépendance de données (RAW - Read
After Write).
3. Que se passerait-il si on forçait quand même la parallélisation de la boucle B ?
CHAPITRE 4 : PROGRAMMATION102
AVEC OPENMP
Exercices
Exercice 4

Vous devez traiter une boucle où le temps de calcul de chaque itération est très
variable.
Par exemple :
• L'itération i=0 prend 1ms.
• L'itération i=100 prend 500ms.
#pragma omp parallel for schedule(______)
for (i = 0; i < N; i++) {
calcul_tres_long_et_variable(i);
}
Questions :
1. Si vous utilisez schedule(static), quel problème de performance risquez-vous de
rencontrer (phénomène d'équilibrage de charge) ?
2. Quelle option de schedule serait la plus appropriée ici pour maximiser l'utilisation des
cœurs ?
3. Expliquez le fonctionnement du mode dynamic.
MERCI
TSHIKUTU Bikengela Anaclet
PhD Student
attshituku@[Link]
TBA International