Systèmes et traitements parallèles

Mohsine Eleuldj
Département Génie Informatique, EMI
eleuldj@[Link]

Novembre 2023
 Eclaircissement

Ce support n'est pas un polycopié de cours

De nombreuses explications et illustrations manquent

Les détails seront donnés au tableau et à l'oral pendant le cours magistral

Il est recommandé d'y ajouter vos propres commentaires et de faire les exercices

Ce support peut être consulté pendant le contrôle des connaissances

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 2

 Syllabus du cours
Objectifs
• Etudier les architectures parallèles incluant les systèmes à mémoire distribuée,
et à mémoire partagée, le principe du pipeline et les ordinateurs vectoriels.
• Apprendre à concevoir des algorithmes parallèles et les programmer en utilisant
multithreading, multiprocessing et les bibliothèques MPI et OpenMP.
• Déterminer, anticiper et améliorer les facteurs de performance.
Contenu
I. Introduction au calcul haute performance
II. Architectures parallèles
III. Pipelines et ordinateurs vectoriels
IV. Réseaux d'interconnexion
V. Programmation parallèle
VI. Caractéristiques de la parallélisation
VII Exercices
Evaluation : Quiz (30%) + TP (20%) + Contrôle avec ce support de cours (50%)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 3
 Performance de la parallélisation ?

Ps : Programme séquentiel
+
Parallélisation

Pp : Programme parallèle

performance(Pp) > performance(Ps) ?

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 4

 Eléments de performance
des systèmes parallèles
• Algorithme (complexité, taille de l'exemplaire, nature du problème,…)
• Architecture (mémoire partagée, distribuée,…)
• Processeurs (nombre, fréquence, nombre de cores, GPU, GPGPU,…)
• Mémoire (temps d'accès, cache, niveaux de caches,…)
• Langage de programmation (langage d'assemblage, C, Java, Fortran, Python,…)
• Paradigmes de programmation (procédural, fonctionnel, orienté objet,…)
• Compilateur (optimisation, vectorisation, …)
• Système d 'exploitation (Linux, Windows, macOS,…)
• Protocole de communication (Ethernet, TCP/IP, ATM…)
• Caractéristiques de la parallélisation (équilibre des charges, Granularité,
Ordonnancement, communication bloquante ou non, exclusion mutuelle,…)
• Bibliothèques (multithreading, multiprocessing, MPI, OpenMP,…)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 5

 Chapitre I
Introduction au calcul haute performance
• Unités de mesure de la performance
• Problèmes complexes
• Qu'est ce que c'est que le HPC ?
• Evolution des systèmes d'ordinateurs
• Evolution de la densité des circuits intégrés
• Loi de Moore
• Mesures de performance
• Loi d'Amdahl
• Exemple d'un processeur moderne
• Configuration de votre ordinateur
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 6
 unités de mesure de la performance
(multiples et sous-multiples)
Valeur Désignation Symbole Exemples
1018 exa E taille d'un ensemble de données ou Dataset (1 EB)
1015 péta P puissance de calcul de Summit (148 Pflops)
1012 téra T capacité mémoire d'un disque dur (1 TB)
109 giga G fréquence de mon processeur (2,4 GHz)
106 méga M taille du fichier de cette présentation (5 MB)
103 kilo k taux de transfert (1 kb/s)
100 unité m (meter), s (second), b (bit), B (Byte), Hz (Hertz), ips
(instruction per second), flops (flotting point per s), core
10-3 milli m temps d'accès à un disque dur de TB (10 ms)
10-6 micro µ Technologie des circuits au début des années 80 (3 µs)
10-9 nano n SRAM de 1 MB (1 ns), DRAM 1 GB (50 ns)
10-12 pico p SRAM de 512 KB 1(100 ps)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 7
 Problèmes complexes
Production de données en 2020 (selon intel)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 8

 Problèmes complexes
Domaines du calcul intensif
• Prévision météorologique
• Astrophysique
• Géonomique/bioinformatique
• Intelligence artificielle (réalité virtuelle, réalité augmentée,…)
• Dynamique moléculaire
• Finance
• Cyber sécurité
• Activités géologique et sismique
• Simulation des circuits intégrés
• …

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 9

 Exemples : Problèmes complexes

1) Un missile d'une vitesse de 600 km/h doit atteindre une cible à une distance
de 200 km. Supposons que les calculs de reconnaissance de formes nécessaires
pour son identification prennent 30 minutes.
• Quel est le temps de collision ?
• Que pouvez-vous conclure ?

2) Considérons un ordinateur de fréquence 2,4 GHz. Estimer le temps

d'exécution d'une application de :
• prévision météorologique du lendemain dont l'exécution nécessite 40 T
instructions et où une instruction prend 6 cycles d'horloge.
• Moteur de recherche web dont le Dataset a une taille de 1 PB et où le
traitement de 512 octets prend un cycle d'horloge.

Quelle solution pour ces problèmes complexes ?

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 10
 Problèmes complexes et HPC
Problème complexe :
•Données massives (Big Data)
•Calcul intensif

HPC
(High Performance Computing)

Solution satisfaisante :
•Grande capacité de la mémoire
•Réduction du temps de réponse

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 11

 Qu'est-ce que HPC ?
Ressources de calcul parallèle et de stockage distribué :
• CPU (Central Processing Unit)
• FPGA (Field Programmable Gate Array)
• GPU (Graphics Processing Unit)
• GPGPU (General Purpose GPU)
• RAM (Random Acces Memory)
• Unités de stockage mémoire
Connexion des ressources par un réseau d'interconnexion
Utilisant des techniques optimisées (algorithme, technologie,…)
Résolution des problèmes complexes :
• Traitement d'un ensemble de données massives (BigData) et/ou
• Calcul intensif
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 12
 Evolution des systèmes d'ordinateurs (1/2)
Technologie de fabrication
• Implantation de la commutation : relai mécanique, électromécanique, tube à
vide, transistors (1947), diode, circuit électronique,…
• Mémoire à tore (électromagnétisme), mémoire électronique,…
• Intégration des circuits : SSI (Small Scale Integration), MSI (Medium), LSI
(Large) et VLSI (Very Large), ULSI (Ultra) et WSI (Wafer).

Processeur
• Arithmétique : bit à bit (additionneur à 1 bit), 8 bits, 32 bits et 64 bits.
• Représentation des nombres : entier naturel, relatif, décimal (virgule fixe et
virgule flottante).
• Coprocesseur scientifique, multiprocesseurs, multi-cores,…
• Mémoire cache à plusieurs niveaux (3 à 7).
• GPU, GPGPU,…

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 13

 Evolution des systèmes d'ordinateurs (2/2)

Système d'exploitation : traitement par lot (cartes perforées),

multiprogrammation, temps partagé, mémoire virtuelle, multiprocessing,
multithreading, ...

Langage de programmation : langage machine binaire, langage

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

Bibliothèque (Library) : mathématique, graphique, statistique, apprentissage

automatique, parallélisation (OpenMP, MPI), …

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 14

 Evolution des processeurs intel
Processeur Année Transistors Technologie
4004 1970 2,3 K 6 µm
8088 1980 29 K 3 µm
80286 1983 134 K 2 µm
80386 1985 275 K 2 µm
80486 1989 1,2 M 1 µm
Pentium 1995 3,3M 350 nm
PentiumPro 1996 5,5M 250 nm
Pentium II 1997 7,5 M 180 nm
Pentium III 1999 9,5 M 130 nm
Pentium IV 2003 42 M 90 nm
i7-3770K 2012 1,4 G 22 nm
i9-9980XE 2018 ? 14 nm
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 15
 Circuits intégrés récents
Unités de traitement
Type Circuit intégré Intégration Année Concepteur Technologie Surface
(G transistors) (nm) (mm2)
Processeur Fujitsu A64FX 8,876 2018 Fujitsu 7 -
GC2 IPU 23,6 2018 Graphcore 16 825
Tegra Xavier SoC 9 2018 Nvidia 12 350
GPU TU116 Turing 6,6 2019 Nvidia 12 200
Navi 10 10,3 2019 AMD 7 284
TU117 Turing 4,7 2019 Nvidia 12 251
FPGA Stratix 10GX5500 17 2017 intel /Altera 14 560
Virtex XCVU440 20 2014 Xilinx 20 -
Versal/Everest 50 2018 Xilinx 7 -

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 16

 Circuits intégrés récents
Unités de mémoire
Type Circuit intégré Capacité Année intégration Concepteur Tech. Surface
(transistors) (nm) (mm2)
SDRAM - 8 Gb 2008 8G Samsung 50 -
- 16 Gb 2008 17 G Samsung 50 -
- 32 GB 2016 34 G Samsung 20 -
- 64 GB 2017 68 G Samsung 20 -
- 128 GB 2018 137 G Samsung 10 -
Flash THGBM 256 GB 2008 256 G Toshiba 43 353
THGBM2 1 TB 2010 256 G Toshiba 32 374
KLMCG8GE4A 512 GB 2011 256 G Samsung - 192
KLUFG8R1EM 4 TB 2017 1,365 T Samsung - 150
eUFS (1 TB) 8 TB 2019 2,048 T Samsung - 150

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 17

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 18
 Loi de Moore
Énoncé (régularité empirique) : nombre de transistors dans un circuit
intégré double approximativement tous les deux ans

Remarques :
•Nombre de transistors ≡ Puissance de calcul ⇒ anticipation (concepteur,
développeur d'application, fabriquant, vendeur, …)
•Augmentation de densité ⇒ réduction de la taille du transistor et
augmentation de la fréquence ⇒ limite du processus de fabrication et vitesse
proche de la célérité de la lumière.
•Approches de pérennisation de la loi de Moore :
o HPC
o Hyperscaling comupting (Extension des ressources de calcul,
mémoire, réseau et stockage au besoin : Cloud par exemple)
o Quantum computing : encore à ses débuts
o Nouvelle technologie de fabrication
o …
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 19
 Mesures de performance
Soit t(n,p) le temps d'exécution d'un problème de taille n en utilisant un système
composé de p processeurs

• Performance
P(n,p) = 1/t(n,p)
• Accélération (Speed up)
A(n,p) = t(n,1)/t(n,p)

• Efficacité
E(n,p) = A(n,p) /p
En général 1 ≤ A(n,p) ≤ p et E(n,p) ≤ 1
si A(n,p) > p alors il s'agit d'une sur-accélération
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 20
 Exemple : Traitement d'image
Considérons une image contenant n2 pixels et représentée à l'aide d'une
matrice d'ordre n. Supposons que le traitement d'un pixel prend c secondes et
que le système parallèle est composé de 9 processeurs.
n
…
… …
… …
…
…
… …
… …
…
n …
… …
… …
…
… … …
…
……………
t(n,1) = cn2
En négligeant les temps de communication
t(n,9) = t(n/3,1) = c(n/3)2 = cn2/9
A(n,9) = t(n,1)/t(n,9) = 9 et E(n,9) = A(n,9)/9 = 1 = 100%
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 21
 Exercice : Amélioration des performances

Reprenons l'exemple précédent (traitement d'image).

a) Comment pourriez augmenter l'accélération et l'efficacité ?
b) En pratique, quelle hypothèse faut-il revoir ?
c) Dans quel cas pourriez-vous avoir une sur-accélération ?
c'est à dire A(n,p) > p et par conséquent E(n,p) > 100%

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 22

 Degré moyen de parallélisme
Considérons un système parallèle composé de p processeurs

• Degré de parallélisme
D(t) = nombre de processeurs utilisés pendant l'instant t

• Degré moyen de parallélisme

1 t2
D= ∫ D(t )dt
t 2 − t 1 t1
où t1 et t2 les temps de début et fin de l'exécution

1 t2
• D(t) est une fonction discrète ⇒ D= ∑ D(t )
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023
t 2 − t 1 t =t1
23
 Exemple : Degré moyen de parallélisme

processeurs
11
10
9
8
7
6
5
4
3
2
1

4 5 6 7 8 9 10 11 12 temps
D = (1 + 4 + 10 + 8 + 5 + 3 + 6 + 3) / (12 – 4) = 40/8 = 5
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 24
 Exercice : Choix du nombre de processeurs

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

a) Quel est le nombre de processeurs qui minimise le temps d'exécution ?
b) Qu'arrive-t-il si on augmente le nombre de processeurs (plus que 10) ?
c) Qu'arrive-t-il si on réduit le nombre de processeurs (moins que 10) ?
d) En supposant que le temps de communication est négligeable devant le
temps de calcul, calculer l'accélération et l'efficacité.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 25

 Loi d'Amdahl (en 1967)
Considérons l'exécution d'une tâche dans un système où les ressources sont
améliorées.
p : pourcentage du temps d'exécution de la partie de la tâche bénéficiant de
l'amélioration des ressources.
s : facteur d'accélération de l'exécution de la partie de la tâche bénéficiant de
l'amélioration des ressources.

Enoncé: L'accélération théorique de l'exécution d'une tâche que l'on peut

attendre d'un système dont on améliore les ressources est :

Remarque : L'accélération théorique est toujours limitée par la partie de la tâche

qui ne peut tirer profit de l'amélioration.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 26

 Exemples de la loi d'Amdahl

Mémoire cache
Un cache a un temps d'accès 20 fois plus court que le temps d'accès à la RAM et
est utilisé pendant 90% du temps.
a)Calculer l'accélération théorique.
b)Recalculer cette accélération si le cache est 1000 fois plus rapide.

Calcul parallèle
Un système multiprocesseurs est composé de s processeurs et le pourcentage du
temps d'exécution du code parallélisable est p.
a)Quelle est l'accélération de la partie parallélisable ?
b)Calculer l'accélération théorique pour p = 50%, 75%, 90%, 95% et 99%
sachant que s = 103.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 27
 Loi d'Amdahl pour le calcul parallèle

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 28

 Processor moderne : Intel Core i7-3770K

Année = 2012, technologie = 22 nm, surface = 160 mm2, nombre de transistors = 1,4 G,
fréquence = 3,4 GHz, cores = 4, RAM Maximale = 32 GB, Cache = 8 MB (L1, L2 et L3),
Bande passante = 25,6 GB/s, GPU = intel HD4000 (16 TMU et 2 ROP) et prix = $342
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 29
 Configuration de votre ordinateur

MS Windows (Microsoft):
• Aller dans ʺPanneau de configuration/Systèmeʺ
• Lancer ʺIndice de la performance Windowsʺ
• Lancer ʺImprimer et afficher des informations détaillées sur les
performances et le systèmeʺ

macOS (Apple):
• Aller dans ʺMenu pommeʺ
• Lancer ʺA propos de ce Macʺ
• Lancer ʺRapport système ʺ

Exercice : Déterminer la configuration de votre ordinateur

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 30
 Chapitre II
Architectures parallèles

• Traitement parallèle
• Parallélisme dans un monoprocesseur
• Classifications des ordinateurs parallèles
• Classification structurelle (mémoires partagées et mémoires distribuées)
• Classification de Flynn (SISD, SIMD, MISD et MIMD)
• Principe général de la parallélisation
• Parallélisation de l'évaluation polynomiale
• Classement des superordinateurs (Top 4, juin 2020)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 31

 Traitement parallèle

Définition du traitement parallèle : Exploitation d'événements concurrents qui

peuvent être en parallèle, simultanés ou en pipeline
• Evénements parallèles : se produisent pendant le même intervalle de temps
• Evénements simultanés : se produisent pendant dans le même instant
• Evénements en pipeline : se produisent pendant des instants chevauchés

Niveaux du traitement parallèle

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

Constatation : de plus en plus le matériel remplace le logiciel

• Miniaturisation et réduction du coût
• Augmentation de la vitesse (temps réel)
• Augmentation de la fiabilité et la tolérance au pannes
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 32
 Evénements concurrents

e2 e2 e2

e1 e1 e1

temps temps temps

Événements en parallèle Événements simultanés Événements en pipeline

(même intervalle) (même instant) (temps chevauchés)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 33

 Parallélisme dans un monoprocesseur
• Multiplicité des unités fonctionnelles (10 UAL dans le CDC-6600)
• Parallélisme et pipeline dans le CPU (processeur)
• Transferts simultanés dans entre les différents niveaux de l'hiérarchie de
mémoire (mémoire virtuelle)
• Multiprogrammation (chevauchement entre le CPU et les E/S)
• Temps partagé (Time sharing) : efficace pour les applications interactives
⇒ temps réel
• Equilibrage des tâches bornées par le calcul (calcul intensif ) et celles
bornées par les E/S (communications intensives)

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 34

 Classifications des ordinateurs parallèles

Classification structurelle
• Système à mémoire distribuée
• Système à mémoire partagée

Classification de Flynn (1966)

• SISD : Single Instruction Single Data stream (ordinateur conventionnel)
• SIMD : Single Instruction Mulitple Data stream (Cray 1: ordinateur
vectoriel)
• MISD : Multiple Instruction Single Data stream (pas d'implémentation)
• MIMD : Multiple Instruction Multiple Data stream (Cray 2, MPP)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 35

 Classification structurelle
Système à mémoire distribuée
E/S
UC
PC
MC
UC : unité de contrôle
PC : processeur de contrôle
ET1 ET2 ET3 ETn
MC : mémoire de contrôle
P P P P ET : élément de traitement
P : processeur
M M M M
M : mémoire locale.

Réseau d'interconnexion

Exemples : Illiac IV et MPP (Massively Parallel Processors)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 36
 Classification structurelle
Système à mémoire partagée

E/S
…..
MM1
MM2 MM : module mémoire
P : processeur
Réseau d'interconnexion
ML : mémoire locale

MMn
Mémoire
partagée P1 ML1 ….. Pp MLp

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 37
 Classification de Flynn
SISD

FI
P : Processeur
M : Mémoire
FI FD FI : Flot d'instructions
UC P M
FD : Flot de données

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 38

 Classification de Flynn
SIMD

FD1
P1 M1
FD2
P2 M1
UC : Unité de contrôle
FI P : Processeur
UC . .
. . M : Mémoire
. . FI : Flot d'instructions
FD : Flot de données
FDn
Pn Mm
FI

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 39
 Classification de Flynn
MISD
FI1
UC1 P1 FD
FI2
UC2 P2

. . M1 M2 ... Mm
. .
. .
FIn
UCn Pn
FD FIn ... FI2 FI1

Architecture ayant moins d'intention, considérée comme impraticable par

certains architectes et aujourd'hui il n'y a pas d'exemple connu.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 40
 Classification de Flynn
MIMD
FI1 FI1 FD1
UC1 P1 M1
DSn
FI2 FI2 FD2
UC2 P2 M2
.
. . . .
. . . .
. . .
FIn FIn FDn
UCn Pn Mm

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 41
 Principe général de la parallélisation
Diviser-pour-régner de la parallélisation
• Décomposition du problème en plusieurs sous-problèmes (processus, threads,
tâches,…)
• Répartition (allocation ou affectation) des sous-problèmes sur les différents
processeurs ou cores selon le modèle maître/esclave, arborescent,...
• Possibilité de partage de la mémoire (mémoire partagée) ou échange de
messages (mémoire distribuée) au cours du traitement
• Combinaison des résultats des sous-problèmes afin de résoudre le problème
de départ

Exemples : Fork/Join et mapReduce

En pratique : Alternance entre le traitement séquentiel et parallèle

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 42

 Exercice :
Parallélisation de l'évaluation polynomiale
Soit un polynôme
p(x) = a4x4 + a3x3 + a2x2 + a1x + a0
Considérons l'évaluation de p(x) en un point donné x0 (c'est-à-dire p(x0)) sur
3 systèmes différents : 1, 2 et 4 processeurs et supposons qu'une addition et
une multiplication prennent 1 et 4τ (τ : cycle d'horloge).
a) Décrire un algorithme du calcul de p(x0) dans le cas d'un seul processeur.
b) Comment allez-vous répartir ce calcul dans le cas de 2 et 4 processeurs ?
c) En supposant que le temps de communication (transfert) est négligeable
devant le temps des opérations arithmétiques, estimez le temps d'exécution de
ce calcul sur les 3 systèmes.
d) En supposant que les processeurs sont interconnectés à l'aide d'un bus et
qu'une communication prend 10τ, estimer le temps d'exécution.
e) Est-il possible de généraliser ces algorithmes pour un polynôme de degré n.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 43
 Classement des superordinateurs
([Link]/lists/2020/06)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 44

 A propos de Summit et Sierra d'IBM
Two IBM-built supercomputers, Summit and Sierra, installed at the
Department of Energy's Oak Ridge National Laboratory (ORNL) in Tennessee
and Lawrence Livermore National Laboratory in California, respectively, retain
the first two positions on the list. Both derive their computational power from
Power 9 CPUs and NVIDIA V100 GPUs. The Summit system slightly improved
its HPL result from six months ago, delivering a record 148.6 petaflops, while
the number two Sierra system remains unchanged at 94.6 petaflops.

Exercice : Summit est composé de 4 356 noeuds où chacun a 2 CPU Power9

de 22 cores et de 6 GPU NVIDIA Tesla V100.
• Quel est le nombre de CPU et de GPU ?
• Quel est le nombre de cores dans un GPU ?
• Dessiner une architecture de ce superordinateur.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 45

 Chapitre III
Pipelines et ordinateurs vectoriels
Pipelines
• Pipeline unidimensionnel
• Principe général
• Assemblage de voitures
• Exécution d'un programme
• Addition en virgule flottante
• Pipeline bidimensionnel (Produit matriciel)
• Ordinateurs pipelines
Ordinateurs vectoriels
• Architecture de Cray-1
• Exemple du calcul de Cray-1
Vectorisation
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 46
 Principe du pipeline unidimentionnel

Concept : inspiré de la chaîne de montage industriel utilisée depuis le début du

siècle dernier.
Hypothèses :
• on veut effectuer le traitement de n entrées (tâches)
• le traitement est décomposé en k sous-traitements ou étages Ei (1≤ i ≤ k)
• le résultat d'un étage est sauvegardé dans le tampon T
• les entrées et les sorties des tampons sont contrôlées par l'horloge H

entrées … sorties
E1 T E2 T T Ek T

H H H H

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 47

 Accélération du pipeline
Soient :
t(n,1) : temps de traitement de n tâches sans pipeline
t(n,k) : temps de traitement de n tâches avec un pipeline de k étages
τi : temps de traitement de Ei (1≤ i ≤ k)
τ0 : temps d'accès à T (lecture et écriture)
τ : période de l'horloge
A(n,k) : accélération du pipeline de k étages pour le traitement de n tâches

Supposons que t(n,1) = nkτ

Synchronisation des étages Ei ⇒ τ = max{ τi , 1 ≤ i ≤ k} + τ0
t(n,k) = kτ + (n - 1)τ = (k + n - 1)τ
A(n,k) = t(n,1)/t(n,k) = nkτ/ (k + n - 1) τ = nk/(k + n - 1)

Exercice : Que signifient et ?

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 48
 Assemblage de voitures

Considérons une chaîne de montage de voitures composée de 3 postes

d'assemblage (moteur, roues et portes) où nous voulons monter 5 voitures
(Vi, 1 ≤ i ≤ 5).

Poste
3 V1 V2 V3 V4 V5

2 V1 V2 V3 V4 V5

1 V1 V2 V3 V4 V5

1 2 3 4 5 6 7 8 heure

Exercice : Calculer l'accélération de ce processus sachant que le temps de

montage d'une voiture est 3h et que le temps d'assemblage d'un étage est 1h.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 49
 Exécution d'un programme
Exécution d'une instruction :
• CI : Chercher l'instruction de la mémoire
• DI : Décoder l'instruction
• CO : Chercher les opérandes
• EO : Exécuter l'opération

Programme CI DI CO EO Résultats
(instructions) (données)

Inconvénients :
• conflit d'accès à la mémoire (CI et CO et mémoire à une entrée par exemple)
• instructions de branchement ou d'interruption (BR ou INT)
Cas avantageux :
• exécution de la même instruction plusieurs fois (traitement vectoriel)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 50
 Addition en virgule flottante
Etant donné deux nombres représentés en virgule flottante normalisée.
A = a x 2p et B = b x 2q avec 0,1 ≤ a < 1 et 0,1 ≤ b < 1
a et b : mantisses et p et q : exposants.
exposant mantisse
Exemple de représentation à l'aide de 16 bits : 1010 100100000000
4 bits 12 bits

On veut calculer : A + B = c x 2r où r = max(p.q)

= d x 2s et 0,1 ≤ d < 1

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

A + B = 0,101 x 28 + 0,1101 x 29
= 0,0101 x 29 + 0,1101 x 29 réduction au même exposant
= 1,0010 x 29 addition des mantisses
= 0,1001 x 210 normalisation
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 51
 Algorithme de l'addition flottante
A = a x 2p, B = b x 2q et C = A + B = c x 2s

fonction additionFlottante(a,p,b,q)
si p > q alors // r=max(p,q) et t=|p-q|
r ß p, t ß p – q, m1 ß b, m2 ß a // m1:mantisse d'exposant min
sinon // m2: mantisse d'exposant max E0
r ß q, t ß q – p, m1 ß a, m2 ß b
m1 ß m1 >> t // décalage à droite par t bits
m ß m1 + m2 // ajouter les manatisses E1
si m > 1 alors u ß 1 // m est-il normalisé ?
sinon u ß 0 E2
c ß m >> u // normaliser le résultat
sßr+u // exposant du résultat E3

Exercice : Concevoir une implantation pipeline de cet algorithme.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 52
 Additionneur flottant pipeline

E0 E1 E2 E3

r=max(p,q) r r
Comparateur
A = a x 2p

p
d'exposants
Additionneur s
a t=|p–q| des exposants

C = A+B = c x 2s
m2=autre mantisse u
Compteur
de zéros
Additionneur m
des
q
B = b x 2q

Décaleur mantisses
Décaleur c c
Sélecteur de droite gauche
b mantisses m1=mantisse
avec min(p,q)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 53

 Accélération de l'additionneur pipeline
Hypothèses : τ0 = 10 ns, τ1 = 90 ns, τ2 = 70 ns, τ3 = 60 ns et τ4 = 40 ns
τ = 100 ns = 10-7s ⇒ fréquence = 1/ τ = 107 Hz = 10 Mhz
⇒ après l'initialisation, l'exécution d'une opération toutes les 100 ns

t(n,1) = (90 + 70 + 60 + 40) * n = 260 * n

t(n,4) = 410 + 100 * (n - 1) = 310 + 100 * n
⇒ A(n,4) = t(n,1) / t(n,4) = 260 n /(310 + 100 n)

et

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 54

 Pipeline bidimensionnel
Exemple : Produit matriciel
C = A * B où A=(aij) et B=(bij), 1 ≤ i, j ≤ n
soient τ : temps d'exécution d'une multiplication
t(n) : temps d'exécution du produit matriciel

Algorithme classique (SISD)

nombre de multiplications = n3 et t(n) = n3τ

Réseau systolique (SIMD)

nombre de cellules de base = 3n2 -3n +1
nombre de périodes = 3n-2 et t(n) = (3n – 2)τ

Application numérique
n = 103 et τ = 1 µs
SISD ⇒ 1 processeur et t(n) = 103 s ≈ 16 mn
SIMD ⇒ 4M processeurs et t(n) ≈ 4 ms
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 55
 Cellule de base du produit matriciel

a
d

b M b d=a*b+c

c
a
Remarques :
•L'entrée verticale a se propage du bas vers le haut sans changement .
•L'entrée horizontale b se propage de la gauche vers la droite sans changement.
•La sortie diagonale d est calculée en fonction de a, b et c.
•Exemple : si a = 2, b = 3 et c = 4 alors d = 2*3 + 4 = 10.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 56
 Réseau systolique du produit matriciel
t3
t4
t5 c13 c12 c11
t2 t1 t0 t6 c21 c22
t7 c33
M c21
b33 0 0 M M
c32

b23 b32 0 M M M M c31

b13 b22 b31 M M M M M

0
0 b12 b21 M M M M
0
0 0 b11 M M M

0 a11 0 a12 0 a13 0 0

Systèmes et traitements parallèles, M.0Eleuldj, EMI, novembre
a21 2023 a22 a23 0
0 0 a31 a32 a33 57
 Ordinateurs pipelines
Caractéristiques : pipeline du traitement de données dans :
• UAL
• Processeur (ou UC)
• E/S
• Hiérarchie de la mémoire
•…

La performance peut se dégrader de façon significative à cause de la

dépendance des données ⇒ conflit des ressources partagées.

Exemples : Cray-1 (14 étages) et Cyber 205 ( 26 étages)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 58

 Algorithme de Fox
Supposons que m2 processus sont utilisés pour calculer C et que n=km.
a) Considérons un algorithme parallèle du calcul de C où chaque processus
calculera le bloc Cij de la matrice C (0 ≤ i, j < m) à partir des blocs Aij et
Bij (0 ≤ i, j < m) des matrices A et B.
b) Considérons maintenant l'algorithme de Fox pour le calcul de C. Chaque
processus pij (0 ≤ i, j < m) contient initialement les blocs Cij, Aij et Bij.
Dans la première étape de l'algorithme, les processus de la diagonale (pij /
i=j) envoient leur bloc Aii à tous les processus de la ligne i. Par la suite
tous les processus calculent Aij*Bij et additionnent le résultat à Cij. Dans
la seconde étape, une permutation circulaire des blocs de B est effectuée.
Le processus pij envoie son bloc B au processus p(i-1)j. (p0j envoie son
bloc B à p(m-1)j). L'algorithme s'arrête après m itérations. Faire la trace
pour n=m=3.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 59

 Ordinateurs vectoriels
Un ordinateur vectoriel est caractérisé par :
- haute vitesse de calcul
- MP et MS grandes capacités et rapides
- logiciels //

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

- vectoriel
- ou matriciel

utilisé dans les applications scientifiques : prévision météorologique,

recherche nucléaire, intelligence artificielle, …

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 60

 Ordinateur vectoriel : Cray-1 (1/2)
Premier ordinateur vectoriel moderne (1976)

période de l'horloge = 12.5 ns ⇒ fréquence = 80 Mhz.

cycle de la mémoire = 50 ms, bipolaire (SECDED)
transfert de (4 mots) /période de l'horloge de ou vers la mémoire.= 320 M mots/s
les canaux ont un taux de transfert = 80 M mots/s
4 canaux opèrent simultanément pour achever le taux maximum de transfert.

266 tampons d'instruction

800 registres
12 unités fonctionnelles pipeline (1 à 14 étages).

Registres adresses (A) 8 x 24 bits

Registres scalaires (S) 8 x 64 bits
Registres vecteurs (V) 8 x 64 x 64 bits
Tampons-adresse (B) 64 x 24 bits
Tampons-scalaire (T) 64 x 64 bits
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 61
 Ordinateur vectoriel : Cray-1 (2/2)
g h i j k m
VL : Vector Lnght 4 3 3 3 3 10
format d'instructions = 16 ou 32 bits
Algorithme LRU de remplacement des tampons d'instruction
P = Program counter 22 bits
NIP = Next Instruction Parcel 16 bits
CIP = Current Instruction Parcel 16 bits
LIP = Lower Instruction Parcel 16 bits
Recip Ap : Inverse approximatif d'un opérande de 64 bits en virgule flottante.
Pop/17 : compter le nombre de "1" dans l'opérande/
compter le nombre de '0' précédant un "1"
Nombres en virgule flottante (64 bits) et en double précision (128 bits)
Dans Cray-1, une opération sur 1 vecteur ayant :
•3 éléments s'exécutent plus rapidement en mode scalaire
•4 éléments au plus s'exécutent plus rapidement en mode vectoriel
la vitesse moyenne Cray-1 est de 24 MFlops au lieu de 160 car les logiciels n'exploitent
pas efficacement (proprement) le matériel (langage, compilation,…).
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 62
 Compilation

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 63

 Réservation des unités et des opérandes
Instructions indépendantes
V0 ß V1 + V2
V3 ß V4 and V5

Réservation de l'unité fonctionnelle

V3 ß V1 + V2
V6 ß V4 + V5

Réservation de l'opérande
V3 ß V1 + V2
V6 ß V1 * V5

Réservation de l'opérande et de l'unité

V0 ß V1 + V2
V3 ß V1 + V5

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 64

 Premier algorithme Cray-1

Calculer C = 5*A + B où A et B sont des vecteurs de 20 éléments

fonction SISD(A,B,C) fonction Cray(A,B,C)

pour i = 1 à 20 faire S0 ß 5
C(i) ß 5*A(i) + B(i) VL ß 20
V0 ß A
V1 ß B
V0 ßS0*V0
V0 ß V0 + V1
C ß V0

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 65

 Deuxième algorithme Cray-1
Calculer C = 5*A + B où A et B sont des vecteurs de longueur n (n > 64).

fonction programmePrincipal(A,B,C)
S0 ß 5 mettre dans le registre scalaire S0 une constante
q ß n div 64 déterminer le nombre de tranches de 64 éléments
r ß N mod 64 déterminer le reste des éléments
pour i = 0 à q-1 faire
Calculer (A,B,C,i,64) calculer une tranche
si r ≠ 0 alors Calculer (A,B,C,q,r) calculer le reste

Fonction Calculer(A, B, C, itération, longueur)

VL ß longueur initialiser la longueur du vecteur
V0 ß A(itération*64) mettre A dans V0 à partir de l'adresse itération*64
V1 ß B(itération*64) mettre B dans V1 à partir de l'adresse itération*64
V0 ß S0 * V0 multiplier V0 par 5
V0 ß V0 + V1 additionner V1 à V0
C(itération*64) ß V0 sauvegarder dans C à partir de l'adresse itération*64
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 66
 Vectorisation (1/2)
Vectorisation : ensemble de transformations apportées à un programme
scalaire conduisant à de bonnes performances lorsqu'il est exécuté sur un
ordinateur vectoriel.

Indépendance des données

pour i=1 à 20 faire X(1) ß X(1) + 5
X(i) ß X(i) + 5 X(2) ß X(2) + 5
X(3) ß X(3) + 5
……

Dépendance des données

pour i=2 à 40 faire Y(2) ß Y(1) + 3
Y(i) ß Y(i-1) + 3 Y(3) ß Y(2) + 3
Y(4) ß Y(3) + 3
……
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 67
 Vectorisation (2/2)
Restructuration du programme
pour i=1 à 20 faire pour j=2 à 40 faire
pour j=2 à 40 faire pour i = 1 à 20 faire
Z(i,j) ß Z(i,j-1) + 7 Z(i,j) ß Z(i,j-1) + 7

Eclatement de la boucle
pour i=1 à 20 faire pour i=1 à 20 faire
X(i) ß X(i) + 5 X(i) ß X(i) + 5
Y(i) ß Y(i-1) + 3 pour i=1 à 20 faire
Y(i) ß Y(i-1) + 3

Instruction conditionnelle
pour i=1 à 20 faire VL ß 20
si (A(i) > 0) alors V0 ß (A > 0)
B(i) = C(i) * 5 si V0 alors B ß C * 5
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 68
 Réalisation de la vectorisation
Vectorisation automatique (compilateur) n'est pas encore une solution
satisfaisante pour optimiser la performance d'un ordinateur vectoriel car :
• réalisation d'un compilateur vectoriel est complexe
• algorithmes sophistiqués

Vectorisation assistée :
• compilateur détecte les zones du programmes requérant le plus de temps
d'exécution.
• utilisateur peut intervenir pour restructurer le code du module.

Outils :
• bibliothèque de sous-programmes vectorisés (écrits par l'utilisateur ou par le
constructeur). Par exemple : opérations matricielles, équations d'algèbre
linéaire, valeurs propres, traitement du signal (TFR), …
• Expérience de l'utilisateur (architecture, compilateur, bibliothèque).

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 69

 Chapitre IV
Réseaux d'interconnexion

• Introduction
• Classifications
• Topologies statiques
• Topologies dynamiques
• Mesures des réseaux d'interconnexion

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 70

 Introduction

A1 A1
A2 . . A2
. .
. Réseau d'interconnexion .

An Am

Ai : Téléphone, Processeur, Module mémoire, Ordinateur, Capteur, Objet (IoT), …

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 71

 Classifications des réseaux d'interconnexion

• Topologie : statique ou dynamique (reconfigurable)

• Commutation : par circuit (TCP/IP) ou par paquet (UDP/IP)
• Contrôle : centralisé ou distribué
• Mode d'opération : synchrone ou asynchrone

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 72

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

a) bus
b) Anneau

c) Etoile d) Graphe complet e) Grille

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 73
 Topologies statiques (2/2) : Hypercube

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

d) dim 3 e) dim 4
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 74
 Topologies dynamiques
Les connexions entre les éléments de traitement sont dynamiques (modifiables
ou programmables). Comme exemple, nous considérons le réseau Baseline nxn

0 0
1 1
2 2
3 n/2 x n/2 3
. .
état 0
. .
. .
. .
n-4 n/2 x n/2 n-4
n-3 n-3
n-2 n-2
n-1 n-1
état 1

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 75

 Programmation du réseau Baseline n=8

0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7

Permutation = ( 01234567
17350462 )
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 76
 Exercice : Réseau Baseline

Considérons un réseau Baseline nxn.

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

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

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

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

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

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 77

 Mesures des réseaux d'interconnexion
Définition :
• Dimension(réseau) : longueur minimale entre les nœuds les plus éloignés
• Connexions(réseau) : nombre de liens du réseau
• Routage (réseau) : algorithme de connexion entre les nœuds

Exercice : Remplir le tableau suivant pour des réseaux ayant n entrées

Réseau d'interconnexion dimension connexion
Bus
Anneau
Etoile
Graphe complet
Matrice
hypercube
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 78
 Chapitre V
Programmation parallèle

• Environnement distribué
• Multithreading
• Multiprocessing
• MPI (Message Passing Interface)
• Installation de MPI
• Présentation de MPI
• Communication (envoi et réception de messages)
• Diffusion
• Réduction
• OpenMP
• Présentation de OpenMP
• Région parallèle
• Exclusion mutuelle
• Réduction
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 79
 Environnement distribué

Réseau de communication
P
Cray J916
(6 processeurs)

P P P P P P P
Réseau local 1 Réseau local 2

P : poste de travail (PC, SIMD, MPP,...) sous un système d'exploitation (Unix,

Linux, Windows, SunOS,…) utilisant des bibliothèque (OpenMP, MPI, …)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 80
 Multithreading(1/2)
import time import time
from threading import Thread # classe
def attente(): def attente():
print('sommeil…') print('sommeil…')
[Link](1) [Link](1)
print('réveil…') print('réveil…')

debut = time.perf_counter() #temps sys. debut = time.perf_counter() #temps sys

attente() t = Thread(target=attente) # création
[Link]() # démarrage
[Link]() # fin
fin = time.perf_counter() fin = time.perf_counter()
print(f' temps = {round(fin-debut,4)} s') print(f' temps = {round(fin-debut,4)} s')

Exercice: Qu'affiche ce script ? Modifier le en faisant 2 appels de la méthode attente.

Pouvez-vous réduire le temps d'exécution ?
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 81
 Multithreading(2/2)
import time
from threading import Thread
def attente(secondes): # la méthode attente avec paramètre
print(f'sommeil de {secondes} s')
[Link](secondes)
print(f'réveil après {secondes} s')
attentes = [5, 4, 3, 2, 1] # tableau des temps d'attente
threads = [] # tableau des threads
debut = time.perf_counter()
for s in attentes:
t = Thread(target = attente, args = [s]) # création du thread avec un paramètre
t .start() # démarrage du thread
[Link](t) # insertion dans le tableau de threads
for t in threads:
[Link]() # fin du thread
fin = time.perf_counter()
print(f'termine à {round(fin-debut,4)} s')
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 82
 Multiprocessing(1/2)
from threading import Thread from multiprocessing import Process
import time import time
def attente(): def attente():
print('sommeil d'une seconde…') print('sommeil d'une seconde…')
[Link](1) [Link](1)
print('réveil…') print('réveil…')
if __name__ == '__main__'
debut = time.perf_counter() debut = time.perf_counter()
t = Thread(target=attente) p = Process(target=attente) # création
[Link]() [Link]() # démarrage
[Link]() [Link]() # fin
fin = time.perf_counter() fin = time.perf_counter()
print(temps = {round(fin-debut,4)} s') print(temps = {round(fin-debut,4)} s')

Exercice: Qu'affiche ce script ? Modifier le en faisant 2 appels de la méthode attente

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 83

 Multiprocessing(2/2)
import time
from multiprocessing import Process
def attente(secondes): # attente de
print(f'sommeil de {secondes} s')
[Link](secondes)
print(f'réveil après {secondes} s')
if __name__ == '__main__':
attentes = [5, 4, 3, 2, 1]
processes = []
debut = time.perf_counter()
for s in attentes:
p = Process(target = attente, args = [s])
[Link]()
[Link](p)
for p in processes:
[Link]()
fin = time.perf_counter()
print(f'termine à {round(fin-debut,4)} s')
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 84
 Multithreading vs multiprocessing

Thread : processus léger ou fil d'exécution

Thread Processus

Création dans le processus existant indépendamment des autres

processus
Démarrage rapide lent

Partage de la oui non

mémoire
Exclusion mutuelle Souvent utilisée pour contrôler Non nécessaire à moins que des
l'accès aux variables partagées threads sont dans le processus
Global Interpreter Un GIL pour tous les threads Un GIL pour chaque processus
Lock (GIL)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 85
 Présentation de MPI
• Bibliothèque standard à inclure dans un programme C (#include "mpi.h") ou
Fortran (INCLUDE 'mpif.h')
• Plusieurs implantations : MPI-1(1994), MPICH2(2000) et OpenMPI(2009)
• Autres bibliothèques : OpenMP(2010),…
• Souvent utilisée dans des architectures à mémoire distribuée
• Modèle SPMD (Single Programme Multiple Data)
• Le même programme est installé dans chaque processeur (ou machine)
• Des instances multiples du programme traitent partiellement ou totalement
les données
• Chaque instance a un identificateur unique par rapport à un communicateur
• L'instance exécute la partie du programme selon son identificateur
• Le traitement inclut le transferts de messages et la combinaison des résultats
(Reduce)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 86
 Schéma général d'un programme MPI

rang ß identificateur du processus en cours par rapport à un communicateur

si (rang = identificateur_spécifique) alors
faire un traitement
sinon
faire un autre traitement

p2
p0
p3
p1

Communicateur
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 87
 Quelques fonctions MPI (1/2)

int MPI_Init(int *argc, char ***argv)

int MPI_Finalize()
int MPI_Comm_rank(MPI_Comm comm, int *rank)
int MPI_Comm_size(MPI_Comm comm, int *size)
int MPI_Send(const void *buf, int count, MPI_Datatype datatype, int dest, int tag,
MPI_Comm comm)
int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag,
MPI_Comm comm, MPI_Status *status)
int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm)
int MPI_Comm_group(MPI_Comm comm, MPI_Group *group)
int MPI_Group_incl(MPI_Group group, int n, const int ranks[], MPI_Group *newgroup)
int MPI_Comm_create(MPI_Comm comm, MPI_Group group,MPI_Comm *newcomm)
int MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 88

 Quelques fonctions MPI (2/2)

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

MPI_Datatype datatype, MPI_Op op, int root,MPI_Comm comm)
Int MPI_Allreduce( void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, MPI_Comm comm )
Opérations :
MPI_MAX : maximum MPI_MIN : minimum
MPI_SUM : sum MPI_PROD : product
MPI_LAND : logical and MPI_BAND : bit-wise and
MPI_LOR : logical or MPI_BOR : bit-wise or
MPI_LXOR: logical xor MPI_BXOR : bit-wise xor
MPI_MAXLOC : max value + location MPI_MINLOC : min value + location

Liste complète (≈360 fonctions) : [Link]

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 89
 UNIX vs MPI et OpenMP
• Unix : La majorité des éditions incluent les commandes mpicc
(compilation) et mpirun (exécution) de MPI et l'option de compilation –
fopenmp d'OpenMP ([Link]
• Cygwin : Simulation d'un environnement UNIX sous Windows. Il faudrait
installer mpi et openMP (g++, ssh make, vim, libopenmpi, libopenmpi,
openmpi, libopenmpicxx1) : ([Link]
• VMware : Machine virtualisée permettant l'exécution d'applications sous
des systèmes d'exploitation différents (Windows, Linux, OS,…)
• Bibliothèque mpi4py, Langage python et environnement de développement
Pycharm
• Visual Studio Code ([Link] et WSL
(Windows Subsystem for Linux).

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 90

 Exercice : Programme C sous Unix
// hello.c programme qui affiche ʺHello Worldʺ
#include <stdio.h>
void main() {
printf("Hello World!");
}

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

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

Affichage obtenu:
$ Hello World!

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 91

 Quelques commandes Unix
$pwd
$ls -l
$hostname
$mpirun -n 1 hostname (ou mpiexec -np 1 hostname)
$mpirun -n 7 hostname
$mpirun hostname
$mpirun -n 5 hello
$mpirun -n 12 hello
$mpirun -machinefile [Link] -n 4 hostname

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 92

 Exemple 1 : Algorithme de communication
p ß nombre total de processus
rang ß identificateur du processus
dest ß 0
si (rang ≠ 0) alors
message ß ″Hello world du processus ″ + rang
envoyer(message,dest)
sinon
écrire(″Hello world du processus 0 : nombre de processus ″,p)
pour source=1 à (p-1) faire
recevoir(message,source)
écrire(message) p0

Exemple : p=4
p1 p2 p3
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 93
 Programme de communication (1/3)
/* programme helloMPI.c*/
#include <stdio.h>
#include <string.h>
#include "mpi.h"

int main(int argc, char* argv[]){

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 94

 Programme de communication (2/3)
/* start up MPI */
MPI_Init(&argc, &argv);
/* find out process rank */
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
/* find out number of processes */
MPI_Comm_size(MPI_COMM_WORLD, &p);
if (my_rank !=0){
/* create message */
sprintf(message, "Hello MPI World from process %d!", my_rank);
dest = 0;
/* use strlen+1 so that '\0' get transmitted */
MPI_Send(message, strlen(message)+1, MPI_CHAR,dest, tag,
MPI_COMM_WORLD);
} et traitements parallèles, M. Eleuldj, EMI, novembre 2023
Systèmes 95
 Programme de communication (3/3)

else{
printf("Hello MPI World From process 0: Num processes: %d\n",p);
for (source = 1; source < p; source++) {
MPI_Recv(message, 100, MPI_CHAR, source, tag,
MPI_COMM_WORLD, &status);
printf("%s\n",message);
}
}

/* shut down MPI */

MPI_Finalize();
return 0;
}

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 96

 Exercice : Programme de communication
a) Créer le fichier « exemple1.c » qui correspond au programme C précédent.
b) Compiler le programme :
$mpicc -o [Link] exemple1.c
c) Exécuter le programme :
$mpirun -n 5 [Link]
d) Modifier le programme en créant le programme « exemple2.c » en
supprimant les appels MPI_Send.
e) Exécuter le programme et dites ce qui se passe (utiliser la commande top et
supprimer les processus).
e) Modifier le programme en créant le programme « exemple3.c » en :
- supprimant les appels MPI_Send
- supprimant la boucle lorsque my-rank=0 (processus p0)
- remplaçant sprintf par printf
exécuter le programme à 2 reprises. Que se passe-t-il ?

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 97

 Fonctions MPI_Reduce
MPI_Reduce( void* send_data, void* recv_data, int count, MPI_Datatype
datatype, MPI_Op op, int root, MPI_Comm communicator)

MPI_MAX - Returns the maximum element.

MPI_MIN - Returns the minimum element.
MPI_SUM - Sums the elements.
MPI_PROD - Multiplies all elements.
MPI_LAND - Performs a logical and across the elements.
MPI_LOR - Performs a logical or across the elements.
MPI_BAND - Performs a bitwise and across the bits of the elements.
MPI_BOR - Performs a bitwise or across the bits of the elements.
MPI_MAXLOC - Returns the maximum value and the rank of the process that
owns it.
MPI_MINLOC - Returns the minimum value and the rank of the process that
owns it.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 98
 Exemples MPI_Reduce

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 99

 Fonction MPI_Allreduce
MPI_Allreduce( void* send_data, void* recv_data, int count, MPI_Datatype
datatype, MPI_Op op, MPI_Comm communicator)

The image cannot be displayed. Your computer may not have enough memory to open the image, or the image may have been corrupted. Restart your computer, and then open the file again. If the red x still appears, you may have to delete the image and then insert it again.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 100

 Fonctions MPI_Bcast, MPI_Scatter,
MPI-Gather et MPI_Allgather

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 101

 Exemple 2 : Calcul de Π
Considérons le calcul séquentiel de Π par intégration numérique :
où n est le nombre de pas
i

Algorithme séquentiel
n ß nombre de pas
pas ß 1/n, somme ß 0
pour i=0 à (n – 1) faire 2
x ß (i + 0,5)*pas
somme ß somme + 4/(1 + x*x)
pi ß pas * somme
imprimer(pi)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 1 102

 Programme séquentiel de Π
/* fichier piSéquentiel.c version séquentielle du calcul de Pi par intégration
numérique de la fonction f(x) = 4/(1 + x*x) entre 0 et 1 */
#include <stdio.h>
#define N = 1000; // nombre de points à évaluer
main (){
int i;
double pas, x, pi, somme = 0.0;
pas = 1.0/(double) N; // distance entre deux abscisses
for (i = 0; i < N; i++){ // considérer n points
x = (i + 0.5)*pas; // calculer l'abscisse à évaluer
somme += 4.0/(1.0 + x*x); // accumuler les ordonnées dans
somme
}
pi = pas * somme; // trouver une approximation de pi
printf("Pi=%20.19f ",pi);
}Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 103
Exercice : Précision du calcul et optimisation

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

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

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

4. En prenant n=109, estimer le temps d'exécution en utilisant la fonction
clock() qui retourne le nombre de cycles d'horloge et la constante
CLOCKS_PER_SEC de la bibliothèque <time.h>.
5. Comment pourriez-vous paralléliser ce programme pour 2 et 4 processeurs ?

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 104

 Algorithme parallèle du calcul de Π
fonction CalculerPi(k,p) // k: rang du processus et p: nombre de processus
si (k = 0) alors
n ß 1000 // n: nombre d'intervalles
pour d=1 à (p – 1) faire envoyer(n, d)
sinon recevoir(n, 0)
h ß 1/n, somme ß0
pour i = k à n-1 pas p faire
x ß h * (i + 0,5)
somme ß somme + 4/(1 + x2)
monPi = h* somme
si (k ≠ 0) alors envoyer(monPi,0)
sinon
somme ß monPi
pour s=1 à (p – 1) faire
recevoir(pi, s), somme ß somme + pi
écrire(″PI=″, somme)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 105
 Diffusion et réduction
fonction CalculerPi(k, p)
si (k = 0) alors n ß 1000

diffuser(n, 0) // envoi de 0 à tous les processus et réception

h ß 1/n
somme ß 0
pour i = k à n pas p faire
x ß h * (i + 0,5)
somme ß somme + 4/(1 + x2)
monPi = h* somme

reduce(monPi,pi,0,opération=somme) // envoi à 0, réception et addition

si (k = 0) alors écrire(″PI=″, pi)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 106

 Trace du calcul de Π

Hypothèse :

p = 3 (p0, p1 et p2)
n =10 ⇒ h = 0,1 1

p0 calcule les valeurs

x=0,05, x=0,35, x=0,65 et x=0,95
p1 calcule les valeurs
x=0,15, x=0,45 et x=0,75
p2 calcule les valeurs
x=0,25, x=0,55 et x=0,85
p0 p1 p2 p0 p1 p2 p0 p1 p2 p0

1
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 107
 Programme du calcul de Π (1/3)
/* fichier piMPI.c */
#include <mpi.h>
#include <stdio.h>
void calc_pi(int rank, int num_procs){
int i, num_intervals;
double h, mypi, pi, sum, x;

/* set number of intervals to calculate */

if (rank == 0) num_intervals = 1000000000;

/* tell other tasks how many intervals */

MPI_Bcast(&num_intervals, 1, MPI_INT, 0, MPI_COMM_WORLD);

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 108

 Programme du calcul de Π (2/3)

/* now everyone does their calculation */

h = 1.0 / (double) num_intervals;
sum = 0.0;
for (i = rank; i <= num_intervals; i += num_procs) {
x = h * ((double)i + 0.5);
sum += (4.0 /(1.0 + x*x));
}
mypi = h * sum;

/* combine everyone's calculations */

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,
MPI_COMM_WORLD);
if (rank == 0) printf("PI is approximately %.16f\n", pi);
}
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 109
 Programme du calcul de Π (3/3)
int main(int argc, char *argv[]) {
int my_rank; /* rank of process */
int num_procs; /* number of processes */

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

MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); /* process rank */
MPI_Comm_size(MPI_COMM_WORLD, &num_procs); /*process number */
calc_pi(my_rank, num_procs); /* calculate PI */

MPI_Finalize(); /* shut down MPI */

return 0;
}

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 110

 Exercice : Programme du calcul de Π

a) Création de MPIPi1.c à partir du programme Π précédent

b) Compilation et exécution de MPIPi1.c
$mpicc -o [Link] MPIPi1.c –lm
$mpirun -n 4 [Link]
c) Création de MPIPi2.c
augmenter le nombre d'intervalles
1

d) Création de MPIPi3.c tel que Π = 4 * ∫

0
dx/(1 + x2)
e) Quelle est la version qui donne les meilleures précisions relativement à
num_intervals réduit sachant que les 25 chiffres de Π sont :
Pi25 = 3,141592653589793238462643
f) Déterminer le temps d'exécution des deux versions en utilisant MPI_Wtime()
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 111
 Exemple 3 : vote électronique
// retourne le numéro du candidat (1,2,…,candidateNum) et 0 si le vote est null
getVote(candidateNum)
candidate ß valeur aléatoire entre 0 et CandidateNum
retourner candidate

DPoll(candidateNum)
rank ß identificateur du processus
pour i=0 à candidateNum faire
vote[i] ß 0
vote [getVote(candidateNum)] ß1
Allreduce(vote, result, Somme)
pour i=0 à candidateNum faire
afficher (rank,vote[i],result[i])

Exercice : Faire la trace pour candidateNum = 3 et processNum = 9

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 112
 programme de vote électronique (1/2)
#include <stdio.h>
#include <mpi.h>
#include <stdlib.h>

// return random value between 0 and candidateNum

int getVote(int germe, int candidateNum){
int candidate;
srand(germe);
candidate = rand() % (candidateNum + 1);
return candidate;
}

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 113

 programme de vote électronique (2/2)
int main(int argc, char *argv[]) {
const int candidateNum=3;
int i, rank,
vote[candidateNum + 1], // vote du processus
result[candidateNum + 1]; // résultat du vote
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
for (i=0; i <= candidateNum; i++) vote[i]=0;
vote [getVote(rank, candidateNum)]=1;
MPI_Allreduce(&vote, &result, candidateNum+1, MPI_INT, MPI_SUM,
MPI_COMM_WORLD);
for (i=0; i <= candidateNum; i++)
printf("rank=%d vote[%d]=%d result[%d]=%d\n",rank,i,vote[i],i,result[i]);
MPI_Finalize();
return 0;
}
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 114
 Exercice : Référendum
Rependre l'algorithme du vote électronique :
a) Modifier l'algorithme afin de l'utiliser dans un référendum. Votre algorithme
devrait afficher le résultat incluant les nombre de bulletins de votes « oui »,
« non » et « nul ».
b) Faire la trace pour 6 électeurs.
c) Transformer pour un vote à main levée (non confidentiel)
d) Dans un système, élire le processus ayant la plus grande priorité pour accéder
à une ressource critique. Et informer tous les processus

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 115

 Présentation d'OpenMP

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

MPICH2(2000) et OpenMP (1997)
• API (Application Programming Interface) pour les applications multithreads
• Standard composé d'un ensemble de directives au compilateur et de fonction de
la bibliothèque pour les applications parallèles
• Simplifie l'écriture des multitreads pour les langages Fortran, C et C++
• Souvent utilisé dans des architectures à mémoire partagées
• Modèles d'exécution :
• SPMD (Single Programme Multiple Data) : Plusieurs threads exécutent le
même programme tout en traitant partiellement ou totalement les données
dépendamment de leur identificateur
• Constructeur et clauses associées aux directive (for, reduce,…)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 116

 Architecture d'OpenMP

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 117

 Modèle de programmation : Fork/Join
• Un thread maître (en rouge) peut créer un ensemble de threads : bifurquer (Fork)
• Plusieurs threads peuvent se ramener au thread maître : se joindre (Join)
• Alternance entre des régions séquentielles et des régions parallèles
• Le parallélisme peut être imbriqué (nested) : un thread peut créer d'autres threads

Fork Join Fork Join

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

Fork Join
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 118
 Région parallèle
• Exemple de la directive de création de threads dans la région parallèle :
# include <stdio.h>
# include <omp.h>
void main (){
#pragma omp parallel // création de la région parallèle
{ // début de la région parallèle
int N = omp_get_num_threads(); // nombre de threads
int ID = omp_get_thread_num(); // numéro du thread courant
printf("Hello world from thread %d/%d\n", ID, N); // affichage
} // fin de la région parallèle
}
• Chaque thread exécute le bloc de la région parallèle et affiche son numéro ou
rang (ID) qui est une variable privée.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 119
 Exercice
1. Mettre le programme précédent est dans le fichier helloOMP.c et compiler
le à l'aide de :
$gcc –fopenmp helloOMP.c
1. Exécuter le programme.
2. Quel est le nombre total des threads générés ? Est-il le même que pour vos
camarades ?
3. Faire la commande : $export OMP_NUM_THREADS=3.
4. Refaire une autre exécution. Que pouvez-vous constater par rapport à la
première exécution ?
5. Qu'arrive-t-il si vous ajoutez la fonction 'omp_set_num_threads(5)' avant
la directive de la région parallèle ?
6. La directive peut inclure une clause :
#pragma omp parallel num_threads(5)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 120
 Exercice : Calcul parallèle de Π
1. Ecrire le programme piOMP.c qui est une version parallèle de
piSéquentiel.c en utilisant la directive de création de la région parallèle et
faire attention aux variables partagées par les threads ainsi qu'à leurs
variables privées.

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

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

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 121

 Répartition du traitement aux threads
pour i=0 à N-1 faire calcul // algorithme séquentiel
Exemple: N=14 et nb=3
Région parallèle // répartition R1 Itération Thread(R1) Thread(R2)
nbß nombre de threads 0 0 0
k ß numéro du thread 1 0 1
2 0 2
débutß k*N div nb
3 0 0
fin ß (k+1)*N div nb 4 1 1
si k= nb -1 alors fin ß N 5 1 2
pour i=début à fin-1 faire calcul 6 1 0
7 1 1
Région parallèle // répartition R2 8 1 2
nbß nombre de threads 9 2 0
k ß numéro du thread 10 2 1
pour i=k à (N-1) pas=nb faire calcul 11 2 2
12 2 0
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023
13 2 1
122
 Exercice : Calcul parallèle de Π

1. Reprendre le programme piOMP.c et écrire une version où les tâches sont

explicitement réparties aux threads.

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

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 123

 Synchronisation : Exclusion mutuelle
Impose des contrainte d'ordre afin de protéger l'accès aux variables partagées
Plusieurs types : critical, atomic,…
La directive #pragma omp critical permet une exclusion mutuelle : un seul
thread à la fois peut entrer dans la région critique

float res;
#pragma omp parallel
{ float B; int i, id, nthrds;
id = omp_get_thread_num();
nthrds = omp_get_num_threads();
for (i=id; i<niters; i+nthrds){
B = big_job(i);
#pragma omp critical
consume (B, res);
}
}Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 124
 Exercice : Exclusion mutuelle

Reprendre le programme piOMP et ajouter la directive afin de

garantir un accès en exclusion mutuelle à la variable partagée
somme.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 125

 Exercice : Retrait d’un solde

a) Ecrire un programme séquentiel de l’algorithme ci-dessous

b) Introduire dans ce programme la directive de la région parallèle et en
affichant le numéro du Thread.
c) Analyser la sortie de plusieurs exécutions
d) Modifier le programme pour avoir un résultat correct.

solde ß1000, retrait ß 1000, tentatives ß 7

pour i=1 à tentatives faire
si solde ≥ solde alors
solde ß solde – montant
afficher(tentative, solde , ”retrait accepté”))
sinon
afficher(tentative, solde, ”retrait refusé”)
afficher(”retrait final=”, solde)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 126
Constructeur de partage de traitement d'une
boucle (loop worksharing construct)
for (i=0; i<N; i++) a[i] = a[i] + b[i]; // séquentiel

#pragma omp parallel // région parallèle

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

#pragma omp parallel // région parallèle et constructeur

#pragma omp for // de boucle
{ for(i=0; i<N; i++) { a[i] = a[i] + b[i];}
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 127
 Clause de réduction
Clause de réduction : reduction (op : list)
Inside a parallel or a worksharing construct:
• A local copy of each list variable is made and initialized depending on the
“op” (e.g. 0 for “+”).
• Compiler finds standard reduction expressions containing “op” and uses
them to update the local copy.
• In C “op” : +, *, -, &, |, ^, && et ||
• Local copies are reduced into a single value and combined with the original
global value.

Exemple :
double ave = 0.0, A[MAX]; int i;
#pragma omp parallel for reduction (+ : ave)
for (i = 0; i < MAX; i++) ave + = A[i];
ave = ave/MAX;
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 128
 Programme OpenMP du calcul de Π
#include <stdio.h>
#include <omp.h>
static long N = 100000000; // nombre d'étapes
int main(){
int i; double x, pi, somme = 0.0, pas, start_time, run_time;
start_time = omp_get_wtime();
pas = 1.0/(double) N;
#pragma omp parallel for reduction (+:somme)
for (i=0; i<N; i++){
x = (i + 0.5)*pas;
somme += 4.0/(1.0 + x*x);
}
pi = pas * somme;
run_time = omp_get_wtime() - start_time;
printf("Pi=%f temps écoulé=%f",pi, run_time);
}Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 129
 Chapitre VI
Caractéristiques de la parallélisation

• Complexité des algorithmes

• Equilibre des charges
• Granularité
• Ordonnancement
• Extensibilité
• Communication bloquante
• Sources d'interblocage

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 130

 Complexité des algorithmes

• Notion d'ordre
O(f(n)) = {t:N ⎯> R*/ (∃c ∈ R+)(n0 ∈ N)( ∀n> n0 ) [t(n)<cf(n)]}
t(n) est de l'ordre de f(n)

• Soit t(n) le temps d 'exécution d'un algorithme sur un exemplaire de taille n

t(n) ∈O(log n) ⇒ algorithme est logarithmique
t(n) ∈O(n) ⇒ linéaire
t(n) ∈O(n2) ⇒ quadratique
t(n) ∈O(p(n)), où p polynôme ⇒ polynomial
t(n) ∈O(f(n)), où f exponentielle ⇒ exponentiel

• Classes des problèmes : P, NP, NP-complet

• Problèmes indécidables : Exemple du problème d'arrêt

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 131

 Parallélisation du produit matriciel
A=(aij) et B=(bij) 1 ≤ i, j ≤ n C=(cijj) où cij= aik*bkj 1 ≤ i, j, k ≤ n

Algorithme SISD Eclatement de la 2ème boucle

pour i = 1 à n faire pour i = 1 à n faire
pour j = 1 à n faire pour j = 1 à n faire
c(i,j) ß 0 c(i,j) ß 0
pour k = 1 à n faire pour j = 1 à n faire
c(i,j) ß c(i,j) + a(i,k)*b(k,j) pour k = 1 à n faire
c(i,j) ß c(i,j) + a(i,k)*b(k,j)
Restructuration de 2ème et 3ème boucles Algorithme SIMD
pour i = 1 à n faire pour i = 1 à n faire
Par pour j = 1 à n faire c(i,j) ß 0 Par pour j = 1 à n faire c(i,j) ß 0
pour k = 1 à n faire pour k = 1 à n faire
pour j = 1 à n faire Par pour j = 1 à n faire
c(i,j) ß c(i,j) + a(i,k)*b(k,j) c(i,j) ß c(i,j) + a(i,k)*b(k,j)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 132
 Trace de l'algorithme SIMD avec n=3
M1 M2 M3 i k en parallèle (j=1, 2 et 3)
.. .. ..
1 c11=0, c12=0, c13=0
.. .. .. 1 c11+=a11b11, c12+=a11b12, c13+=a11b13
.. .. ..
2 c11+=a12b21, c12+=a12b22, c13+=a12b23
a11 a12 a13
A 3 c11+=a13b31, c12+=a13b32, c13+=a13b33
a21 a22 a23
a31 a32 a33 2 c21=0, c22=0, c23=0
b11 b12 b13 1 c21+=a21b11, c22+=a21b12, c23+=a21b13
B
b21 b22 b23
2 c21+=a22b21, c22+=a22b21, c23+=a22b23
b31 b32 b33
c11 c12 c13 3 c21+=a23b31, c22+=a23b32, c23+=a23b33
C
c21 c22 c23 3 c31=0, c32=0, c33=0
c31 c32 c33 1 c31+=a31b11, c32+=a31b12, c33+=a31b13
.. .. .
.. .. . 2 c31+=a32b21, c32+=a32b22, c33+=a32b23
.. .. .
3 c31+=a33b31, c32+=a33b32, c33+=a33b33
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 133
 Algorithme SPMD

j ß rang du processus
n ß nombre des processus
pour i=1 à n faire
somme ß 0
pour k=1 à n faire
somme ß somme + a(i,k)*b(k,j)
afficher ('C(', j ,',', i, ')=', somme)

Exercice
a)Programmer cet algorithme en utilisant la bibliothèque MPI.
b)Exécuter le programme pour deux matrices d'ordre 3.
c)Modifier le programme pour que le processus 0 affiche la matrice produit.
d)Que constatez vous lorsque vous exécutez le programme ?
e)Corriger le programme en utilisant l'instruction MPI_Gather
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 134
 Exercice : Calcul du produit matriciel

Considérons le calcul du produit matriciel de matrice d'ordre n sur un

système SIMD composé de 3 ET.
a)Analyser la complexité de l'algorithme.
b)Proposer un réseau d'interconnexion pour relier les ET.
c)Comment allez-vous programmer ce réseau ?

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 135

 Exercice : Calcul du produit matriciel 2
int main(int argc, char **argv){
int A[ORDRE][ORDRE]={{0,1,2},{3,4,5},{6,7,8}},
B[ORDRE][ORDRE]={{1,-1,2},{3,-4,-5},{6,-7,8}};
int k, i, j, n, m, myC, C[ORDRE][ORDRE];
MPI_Init (&argc, &argv);
MPI_Comm_rank (MPI_COMM_WORLD, &k);
MPI_Comm_size (MPI_COMM_WORLD, &n);
for (i=0; i<n; i++){
myC = 0;
for (j=0; j<n; j++) myC += A[i][j]*B[j][k];
C[i][k]=myC;
}
if (k==0){
for (i=0; i<n; i++) for (j=0; j<n; j++) printf("\n");
}
}
MPI_Finalize();
return
Systèmes 0; parallèles, M. Eleuldj, EMI, novembre 2023
et traitements 136
}
 Calcul des sommes partielles
Problème : Soit v = (v(0),v(1),…v(n-1)) un vecteur de n éléments.
Les sommes partielles S(i) (0 ≤ i < n) sont définies par :

Exercice
a)Décrire un algorithme séquentiel pour calculer S(i) pour 0 ≤ i < n.
b)Déterminer le nombre d'additions de ce calcul.
c)Déduire la complexité de l'algorithme.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 137

Algorithmes séquentiels des sommes partielles
Algorithme 1 : Calcul direct Algorithme 2 : Calcul non répétitif
pour i = 0 à (n-1) faire S(0) ß v(0)
S(i) ß v(0) pour i = 1 à (n-1) faire
pour j = 1 à i faire S(i) ß S(i-1) + v(i)
S(i) ß S(i) + v(j)

Nombre d'additions = n(n – 1)/2 Nombre d'additions = n – 1

⇒ Algorithme 1 ∈ O(n2) ⇒ Algorithme 2 ∈ O(n)

Exercice : Supposons que n = 8 et que le nombre de processeurs k = 2.

a) Comment allez-vous répartir les calculs de Algorithme 1 et Algorithme 2
et les affecter aux processeurs ?
b) Quel est l'algorithme qui ne se prête pas à la parallélisation (ne réduit pas
le temps d'exécution) ?
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 138
 Equilibre des charges

Pour paralléliser le calcul de n sommes partielles considérons p processeurs (Pk

pour 0 ≤ k < p).

Soient
a(Pk) : nombre d'additions effectuées par Pk appelé tâche ou charge de Pk
t(Pk) : temps d'exécution du processeur Pk qui est proportionnel à a(Pk)
a(p) : nombre d'additions effectuées par les p processeurs
t(p) : temps d'exécution total sur le système composé des p processeurs

t(p) = Maximum(t(P0),t(P1),…,t(Pp)) et

⇒ pour réduire t(8), les charges des processeurs devraient être équilibrées.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 139

 Charge des processus de Affectation 1

Affectation 1
p0 exécute les itérations i = 0 à 31 c'est-à-dire S(0) à S(31)
p1 ʺ i = 32 à 63 ʺ S(32) à S(63)
…
pk ʺ i = 32k à 32k+31 ʺ S(32k) à S(32k+31)
…
p7 ʺ i = 224 à 255 ʺ S(224) à S(255)

p0 p1 p2 p3 p4 p5 p6 p7
0 32 64 96 128 150 192 224 256

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 140

 Première parallélisation du calcul direct

Algorithme 3 : Affectation 1
Par pour k=0 à 7 faire
pour i = 32k à (32k + 31) faire
S(i) ß v(0)
pour j = 1 à i faire
S(i) ß S(i) + v(j)

Exercice
Montrer que :
a) a(pk) = 16 x (64k + 31) pour (0 ≤ k < 8 ) a(pk) = 32k + 31
b) Temps(Affectation 1) = 7664 x c où c est le temps d'exécution d'une
addition.
c) a(8) = 32640
Retrouver ce dernier résultat à l'aide de l'exercice de la page 83.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 141
 Charges des processeurs de Affectation 1
Nombre d'additions

processeurs

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 142

 Charge des processus de Affectation 2

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

p0 p1 p2 p3 p4 p5 p6 p7 p7 p6 p5 p4 p3 p2 p1 p0
0 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 256

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 143

 Deuxième parallélisation du calcul direct

Algorithme 4 : Affectation 2
Par pour k=0 à 7 faire
pour i=16k à 16k+15 et i=(240 - 16k) à (255 - 16k) faire
S(i) ß v(0)
pour j=1 à i faire
S(i) ß S(i) + v(j)

Exercice :
a)Montrer que a(pk) est indépendant de k et qu'il est égal à 4080
b)Que représente 4080 par rapport à a(8) c'est-à-dire au nombre
total d'aditions du calcul ?
c)Déterminer le temps d'exécution de cet algorithme.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 144

 Charges des processeurs de Affectation 1 et 2
Nombre d'additions

processeurs

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 145

 Degré moyen de parallélisme
de Affectation 1 et 2
processeurs
10 Affectation 1
9 Affectation 2
8
7
6
5
4
3
2
1

t0 t1 t2 t3 t4 t5 t6 t7 t8 temps

Exercice : montrer que le degré moyen de parallélisme de l'Affectation 1 et

l'Affectation 2 sont 4,5 et 8 respectivement.
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 146
 Autre parallélisation des sommes partielles
étape t0 t1 t2 t3

p0 v0 v0 v0 v0 S(0)

p1 v1 v0+v1 v0+v1 v0+v1 S(1)

p2 v2 v1+v2 v0+…+v2 v0+…+v2 S(2)

p3 v3 v2+v3 v0+…+v3 v0+…+v3 S(3)

p4 v4 v3+v4 v1+…+v4 v0+…+v4 S(4)

p5 v5 v4+v5 v2+…+v5 v0+…+v5 S(5)

p6 v6 v5+v6 v3+…+v6 v0+…+v6 S(6)

p7 v7 v6+v7 v4+…+v7 v0+…+v7 S(7)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 147
 Exercice : Calcul des sommes partielles
Considérons la troisième parallélisation du calcul des sommes partielles.
a)Calculer le degré de parallélisme pour n=8 en négligeant le temps des
communications.
b)En vous inspirant de l'exemple précédent, décrire un algorithme parallèle
pour un système composé de n processeurs. Trouver la complexité de cet
algorithme.
c)Montrer que le nombre de communications est nlogn - (n - 1).
d)Modifier l'algorithme en utilisant un seul puis 2 processeurs.
e)En supposons que n = 8 :
•Quelles sont les interconnexions qu'il faudrait réaliser dans chaque étape
pour effectuer les calculs de cet algorithme ?
•Quel réseau d'interconnexion allez-vous utiliser : Bus, Baseline ou
l'hypercube ?
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 148
 Granularité
Granularité = taille de la tâche affectée (allouée) à un processeur (ou processus)
temps d 'exécution = temps de calcul + temps de communication

Hypothèse : temps de communication d'un message de taille s est a + b * s

où a est b sont deux constantes (a : latence et b : débit)

Exemple : Calcul du produit matriciel C = AB où A et B deux matrices d'ordre n.

version 1 : monoprocesseur pour i=1 à n faire

processus : matrice x matrice pour j=1 à n faire
nombre de mult/processus = n3 C(i,j) ß 0
nombre de processus = 1 pour k=1 à n faire
nombre de communications = 0 C(i,j) ß C(i,j)+A(i,k)*B(k,j)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 149

 Granularités des processus pour le
produit matriciel
version 2 : granularité grosse pour i=1 à n faire
processus : vecteur x matrice pour j=1 à n faire
nombre de mult/processus = n2 C(i,j) ß 0
nombre de processus = n pour k=1 à n faire
nombre de communications = n C(i,j) ß C(i,j)+A(i,k)*B(k,j)

version 3 : granularité moyenne pour i=1 à n faire

processus : vecteur x vecteur pour j=1 à n faire
nombre de mult/processus = n C(i,j) ß 0
nombre de processus = n2 pour k=1 à n faire
nombre de communications = n2 C(i,j) ß C(i,j)+A(i,k)*B(k,j)

version 4 : granularité fine pour i=1 à n faire

processus : scalaire x scalaire pour j=1 à n faire
nombre de mult/processus = 1 C(i,j) ß 0
nombre de processus = n3 pour k=1 à n faire
nombre de communications = n3 C(i,j) ß C(i,j)+A(i,k)*B(k,j)
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 150
 multiplications et communications
du produit matriciel pour n = 3

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 151

 Ordonnancement

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

• Alternance entre les phases de calcul et de communication
• Ordonnancement des processus de telle sorte que lorsque certains
calculent les autres communiquent

Exemple : 2 processeurs + 1 DMA (Direct Memory Access)

Calcul
p1 Communication
p2
Calcul
Calcul
p3 Communication
p4 Calcul
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 152
 Extensibilité (scalability)
temps

100

80

60

40

20

0 processeurs
1 2 3 4 5 6 7 8

Exercice : Déterminer le nombre optimal de processeurs pour ce calcul

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 153
 Communication bloquante
Quand p0 envoie un message à p1, p0 ne peut continuer son exécution
(traitement) que lorsqu'il reçoit un accusé de réception de p1

Envoyer (message)

Recevoir
Attendre (message)
Envoyer (accusé)
(accusé)

Traitement

p0 p1
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 154
 Interblocage des communications bloquantes

Envoyer (message) Occuper

le canal
Envoyer (message) Occuper
s'il est libre Envoyer (message)
le canal
Attendre s'il est libre
(accusé) Recevoir
Attendre
Attendre Envoyer (accusé) (message)
(accusé)
(accusé)
Occuper
le canal
Envoyer (message)
s'il est libre
Recevoir
(message) Attendre
Envoyer (accusé)
(accusé)

p0 p1 p0 p1
(1) Interblocage (2) Exclusion mutuelle
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 155
 Chapitre VII
Exercices
• Produit matriciel
• Sommes partielles
• Produit scalaire

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 156

 Exercice 1

Considérons le produit de deux matrices d'ordre n.

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

b) Pour chaque cas trouvez :

• Le nombre de processeurs

• Le temps de calcul

• Le degré moyen de parallélisme

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 157

 Exercice 2
Considérez l'algorithme de Affectation 1 du calcul des sommes partielles :
Par pour k=0 à 7 faire
pour i = 32k à (32k + 31) faire
S(i) ß v(0)
pour j = 1 à i faire S(i) ß S(i) + v(j)
a) Traduire cet algorithme en un programme SPMD en utilisant les fonctions MPI
où n ) 16 et v = (2,3,6,9,4,7,0,2,2,6,8,9,11,0,2,4).
b) Afficher les calculs des processus selon la forme suivante :
<numéro du processus> : S(<indice>) = <valeur calculée>
c) Modifier le programme pour qu'il puisse être exécuté sur 1, 2, 4, 8 et 16
processus.
d) Afficher le temps de traitement des processus sachant que v est un vecteur de
100 000 éléments tel que v(i)=i. Que pouvez-vous dire des temps d'exécution ?
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 158
 Exercice 3

Reprenez les mêmes questions que l'exercice précédent et cette fois-ci pour
l'algorithme de la deuxième parallélisation (Affectation 2) :

Par pour k=0 à 7 faire

pour i=16k à 16k+15 et i=(240 - 16k) à (255 - 16k) faire
S(i) ß v(0)
pour j = 1 à i faire
S(i) ß S(i) + v(j)

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 159

 Exercice 4
Soit l'algorithme suivant :
p ß nombre de processus // n = p (autant de processus que d'éléments)
rang ß identificateur du processus
somme ß v(rang) // v = (v(0), v(1),…, v(n-1)
pour i = 0 à (log(p) – 1) faire
pas ß 2**i
si (rang < p – pas) alors
envoyer(somme, rang + pas)
si (rang >= pas) alors
recevoir(A, rang - pas)
somme ß somme + A
écrire(" Somme partielle du processeur :", rang, " = " ,somme)

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

algorithme en utilisant MPI. Que calcule cet algorithme ?
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 160
 Exercice 5 (1/2)
a) Corriger le programme de la page suivante.

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

c) Que calcule-t-il ?

d) Expliquer le type de granularité.

e) Modifier le programme pour augmenter la granularité.

f) Estimer le temps d'exécution.

Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 161

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

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

sum = 0;
for (k=0; k<order; k++) sum = sum + (row + k) * (k - column);
printf("[processus : %d]: c(%d,%d) = %d\n",myrank,row,column,sum);
MPI_Finalize();
}
Systèmes et traitements parallèles, M. Eleuldj, EMI, novembre 2023 162
 Exercice 6
Soient deux vecteurs a=(a0,a1,…,an-1) et b=(b0,b1,…,bn-1) avec n=2m (m ∈ N+). Nous
voulons calculer le produit scalaire S = a0* b0 + a1* b1 + … + an-1* bn-1

a) Ecrire un algorithme SPMD où le processus pk calcule le produit ak * bk et l'envoie à p0

qui calcule la somme S et l'affiche.
b) Récrire l'algorithme en remplaçant les envois et réceptions par Reduce.
c) Afin d'augmenter la granularité et en ayant m processus, réécrire l'algorithme selon
l'affectation suivante :
p0 calcule le produit scalaire partiel : de l'indice 0 à l'indice 1.
pk calcule le produit scalaire partiel : de l'indice 2k à l'indice 2k+1 – 1 (0 < k <
m).
d) Faire la trace pour n=16 de ce dernier algorithme et calculer le degré moyen de
parallélisme sachant que le temps d'exécution est proportionnel au nombre de
multiplications (temps d'addition et de transfert sont négligeables devant la
multiplication).
e) Tout en ayant m processeurs, trouver une affectation qui permet l'équilibrage de
charge. Quel est le degré moyen de parallélisme ?
f)Systèmes
Ecrire un programme SPMD de cette deuxième affectation et faire la trace pour n=16.
et traitements parallèles, M. Eleuldj, EMI, novembre 2023 163