19/01/2024

Université Tunis El Manar

Institut Supérieur d’Informatique

Architectures
multiprocesseurs
&
algorithmes Mariem FEKI
2ème
parallèles ISEOC

Année Universitaire 2023‐2024

Introduction

Année Universitaire 2023-2024

1
 19/01/2024

Informations concernant le module

 Volume horaire :
22h30 cours 1h30 fixe /semaine
7h30 TD 1h30 par quinzaine (semaine A)

 Période : tout le long du semestre

 Unité d’enseignement : Conception et implémentation des circuits
numériques sur FPGA
 Coefficient : 1
 Evaluation: CC (30%) + Examen(70%)
 Contact :
E‐mail : [Link]@[Link]
Espace de cours sur [Link]
M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 3

Prérequis et objectif du cours

 Prérequis:
‐ Système d’exploitation
‐ Architecture avancée des processeurs
‐ Algorithmique fondamentale et programmation (langage C)

 Objectif :
Acquérir les compétences nécessaires sur les architectures multi‐cœur
et hétérogènes qu'on retrouve sur les systèmes sur puce ainsi que les
modèles de la programmation parallèle en relation étroite avec
l'architecture considérée.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 4

2
 19/01/2024

Motivations
Performances accrues des
plateformes : Les algorithmes
parallèles permettent
d'exploiter efficacement les
ressources matérielles en
exécutant plusieurs tâches
simultanément.
Calcul scientifique (physique, chimie,
Gestion de la complexité : astronomie, météorologie, etc).
Les produits embarqués
modernes deviennent de
plus en plus complexes, IA, ML, Robotique, traitement d’images et de
nécessitant des calculs vidéos etc,
massivement parallèles.

Évolutivité : Les architectures parallèles sont hautement évolutives, ce qui signifie

qu'elles peuvent être étendues pour répondre à des besoins de calcul croissants
M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 5

Plan du cours

 Introduction générale :
‐ Rappeler le parallélisme interne du processeur : pipelining et
processeur superscalaire.
‐ Définir les besoins et les motivations pour l'étude et la
programmation des architectures parallèles.

 Chapitre 1: Architectures parallèles sur puce

‐ Classifier les architectures parallèles (SIMD, MIMD ..). Définir les
différences entre architecture à mémoire partagée et architecture à
mémoire distribuée.
‐ Aborder la marche historique vers le parallèlisme.
‐ Présenter les différentes architectures multi‐coeurs qu'on retrouve sur
les systèmes sur puce
‐ Définir les métriques d'évaluation de performance.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 6

3
 19/01/2024

Plan du cours

 Chapitre 2: Programmation des architectures parallèles à mémoire

partagée ‐ OpenMP ‐
‐ Présenter l’API OpenMP
‐ Détailler la programmation d'architectures avec mémoire partagée
avec l’API OpenMP ( Les directives, clauses et fonctions )
‐ Introduire les fonctions de mesure de temps d’éxécution
‐ Donner des recommandations pour l’optimisation du code

 Chapitre 3: Programmation des architectures parallèles hétérogènes

‐ Présenter l’architecture d’un GPU
‐ Présenter et comparer les Langages de programmation pour les GPU
‐ Introduire l’architecture CUDA
‐ Introduire la programmation CUDA (Grille, bloc, thread etc.).

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 7

Syllabus
Semaine Contenu
S1 (2 séances) Introduction générale

S2 (1 séance) Chapitre 1: Architectures parallèles sur puce

S3 (2 séances)
S4 (1 séance)
S5 (2 séances)
Chapitre 2: Programmation des architectures parallèles à
S6 (1 séance) mémoire partagée ‐ OpenMP ‐
S7 (2 séances)
S8 (1 séance)

S9
S10 (2 séance) DS
S11 (1 séance)
S12 (2 séances) Chapitre 3: Programmation des architectures parallèles
S13 (1 séance) hétérogènes
S14 (2 séances)
S15 (1 séance) 8

4
 19/01/2024

1. Parallélisme interne du processeur

1.1. Pipeline

 Un programme informatique est un flux d'instructions exécuté par un

processeur.

 Un pipeline ou chaîne de traitement d’un processeur est l’élément d’un

processeur dans lequel l’exécution des instructions est découpée en
plusieurs étapes. Le premier ordinateur à utiliser cette technique est
l'IBM Stretch (1961).

 Chaque instruction nécessite plusieurs cycles d‘horloge, l'instruction est

exécutée en autant d'étapes que de cycles nécessaires.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 9

1. Parallélisme interne du processeur

1. Pipeline

 Avec un pipeline, le processeur peut commencer à exécuter une

nouvelle instruction sans attendre que la précédente soit terminée.

 Les microprocesseurs séquentiels exécutent l'instruction suivante

lorsqu'ils ont terminé l’instruction en cours.

Séquence de 3
instructions de 5
étapes chacune

 Si on suppose qu’il faut un cycle d’horloge pour chaque étape. Il faut 15

cycles pour exécuter 3 instructions.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 10

5
 19/01/2024

1. Parallélisme interne du processeur

1. Pipeline
 Dans le cas du parallélisme d'instruction, le microprocesseur peut traiter
plusieurs de ces étapes en même temps pour plusieurs instructions
différentes, car elles ne font pas appel aux mêmes ressources internes
(chaque étape dispose de ses propres ressources matérielles).

 Chacune des étapes d’un pipeline est appelé étage. Le nombre d'étages
d'un pipeline est appelé sa profondeur. Il correspond au nombre maximal
théorique d'instructions exécutées en même temps dans le pipeline.

 En effet, le processeur exécute en parallèle des instructions qui se suivent

à différents stades d'achèvement. Prenons comme exemple le pipeline
RISC classique qui compte 5 étapes:
1. IF (Instruction Fetch): charger l’instruction à exécuter
2. ID (Instruction Decode) : décoder l’instruction et lecture des registres
opérandes
M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 11

1. Parallélisme interne du processeur

1.1. Pipeline

3. EX (Execute) : exécuter l’instruction

4. MEM (Memory): Accès mémoire si nécessaire
5. WB (Write Back): stocker le résultat dans un registre

Séquence des instructions dans un processeur doté d'un pipeline à 5

étages. Il faut 9 cycles pour exécuter 5 instructions. À t = 5, tous les étages
du pipeline sont sollicités, et les 5 opérations ont lieu en même temps.

 Ainsi, le pipeline permet d’accélérer le traitement des instructions et

apporte un gain de temps considérable.
M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 12

6
 19/01/2024

1. Parallélisme interne du processeur

1. Pipeline

 Aujourd’hui, tous les processeurs sont pipelinés

 Pentium 4 Prescott : 31

 Le niveau de profondeur des processeurs actuels:

Processeurs Intel i3, i5, i7,i9 : 14
Processeurs ARM embarqués sur les SoC : 8 ‐ 14

 Nombreux problèmes sont rencontrés en pratique. Un pipeline profond

pose plus de problèmes qu’un pipeline court.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 13

1. Parallélisme interne du processeur

1. Pipeline
1. Les aléas structurels : plusieurs étages du pipeline aient besoin
d’accéder à la même ressource matérielle (mémoire, registre, unité
de calcul..). Exemple :
1 2 3 4 5
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB

Au cycle 4, il faut accéder à la mémoire et charger une instruction au

même temps et ça pose un problème si on a une seule mémoire (et un
accès/ cycle) pour les données et les instructions.
M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 14

7
 19/01/2024

1. Parallélisme interne du processeur

1. Pipeline
2. Aléas de données : une instruction qui a besoin d’un résultat
provenant d’une autre instruction et cette dernière n’a pas encore fini
son exécution. Ces dépendances constituent une des raisons pour
lesquelles les pipelines sont difficiles à concevoir au niveau logiciel et
matériel.
Exemple :

1 2 3 4 5
Sub $2, $1,$3 IF ID EX MEM WB
And $4,$2,$5 IF ID EX MEM WB

Au cycle 3, la 2ème instruction cherche à lire les opérandes et à ce

moment, la 1ère instruction n’a pas fini de calculer l’une de ces
opérandes ( $2)

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 15

1. Parallélisme interne du processeur

1. Pipeline

3. Aléas de contrôle:

If (R1 > 30) inst ①

then R3 = 10 + R1 inst ②
else R3 = 20 + R1 inst ③

En fonction du résultat du test, le contenu du compteur cordinal est

modifié avec l'adresse de la prochaine instruction (② ou ③).
Problème : Il faut connaitre le résultat du test pour savoir quelle est
l'instruction suivante à exécuter

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 16

8
 19/01/2024

1. Parallélisme interne du processeur

1. Pipeline

Conclusion:
 Avantage d'un pipeline long :
‐ Plus d'instructions en exécution parallèle
‐ Donc gain en nombre d'instructions exécutées en un temps donné

 Inconvénient d'un pipeline long :

‐ Plus d'opérations en cours d'exécution à annuler

 Solution globale :
‐ Trouver le bon compromis entre gain d'un coté et perte de l'autre

 C’était une technique clé dans les années 80 pour améliorer les
performances mais elle a atteint rapidement ses limites.
M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 17

1. Parallélisme interne du processeur

2. Processeur superscalaire

 La question qui se posait : Comment peut on encore améliorer les

performances?

‐ Utiliser non plus un mais plusieurs pipelines en parallèle

‐ C’est une technique qui a été développée dans les années 90 :
* Approche superscalaire
* Approche VLIW (Very Long Instruction Word)

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 18

9
 19/01/2024

1. Parallélisme interne du processeur

2. Processeur superscalaire
 Prcoesseur scalaire (pipeliné) :

 Processeur superscalaire :

Séquence des instructions

dans un processeur
superscalaire de degré 2. Il
faut 9 cycles pour exécuter 10
instructions. À t = 5, toutes
les unités sont sollicitées.
M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 19

1. Parallélisme interne du processeur

2. Processeur superscalaire

 Architecture superscalaire de degré n : n instructions par cycle, n unités

de traitement par étage.

 Cette approche augmente la complexité et la consommation d'énergie

du matériel, ce qui limite les processeurs actuels à quelques instructions
par cycle.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 20

10
 19/01/2024

1. Parallélisme interne du processeur

3. VLIW

 Sur ces processeurs, chaque instruction peut faire 128, 256 bits de long,
voire plus.

 Concept du VLIW:

 Une instruction que l’on appelle mot est composée d’un certain nombre
d’instructions élémentaires et le processeur est capable d’exécuter
toutes ces instructions élémentaires en parallèle (grâce aux différentes
unités de calcul disponibles)

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 21

1. Parallélisme interne du processeur

3. VLIW

4 opérations

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 22

11
 19/01/2024

2. Architectures parallèles
1. Limites technologiques sur le monoprocesseur

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 23

2. Architectures parallèles
1. Limites technologiques sur le monoprocesseur

 Améliorer le jeu d’instructions : atteint ses limites

 Améliorer l’accès mémoire en rajoutant différents niveaux de cache : il

s’avère non suffisant vu la complexité des calculs .

 Plus la fréquence d’horloge augmente, plus le processeur exécute des

instructions par seconde.

 La fréquence d’horloge détermine la durée d’un cycle et chaque

opération utilise un certain nombre de cycles.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 24

12
 19/01/2024

2. Architectures parallèles
1. Limites technologiques sur le monoprocesseur

 La fréquence d’horloge est fonction de :

‐ la technologie des semi‐conducteurs,
‐ le packaging,
‐ les circuits.

 Les limites technologiques relatives à la fréquence: En plus du fait

qu’augmenter la fréquence d’horloge est une solution coûteuse, la
consommation électrique et la dissipation thermique d’un processeur
sont fonction de sa fréquence d’horloge.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 25

2. Architectures parallèles
2. Présentation

 Pour améliorer le parallélisme, on utilise des processeurs multi‐cœur,

voir une architecture multi‐processeur.

 Architecture parallèle : utiliser un ensemble de processeurs/coeurs

capables de communiquer et de coopérer dans le but d’accélérer la
résolution d’un problème.

 Mettre plusieurs cœurs sur la même puce

‐ jusqu’à 128 cœurs avec le AMD EPYC
‐ mais plus couramment 8, 16…

 Division d’un algorithme/ problème en tâches pouvant être exécutées

en même temps sur des processeurs/coeurs différents.

26

13
 19/01/2024

2. Architectures parallèles
2. Présentation

 Architecture Multi‐processeur :
c’est une architecture qui
comprend plusieurs processeurs
(CPU) distincts. Chaque processeur
est une entité indépendante avec
son propre jeu d'instructions, ses
registres et sa mémoire cache. Ces
CPUs peuvent être connectés via
un bus et peuvent travailler en
parallèle pour exécuter des tâches
simultanément.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 27

2. Architectures parallèles
2. Présentation

 Multi‐cœur : C’est architecture qui comprend un processeur unique qui

intègre plusieurs cœurs de traitement indépendants sur une seule puce.
Chaque cœur dispose de son propre ensemble de registres, mais ils
partagent généralement certaines ressources, telles que certains la
mémoire cache, le bus système et la mémoire principale.
Les cœurs de traitement d'un processeur
multi‐cœurs peuvent travailler en parallèle
pour exécuter des tâches simultanément.
Cela permet d'augmenter les performances
globales du processeur en tirant parti du
parallélisme au niveau de l'instruction, du
parallélisme des données et du parallélisme
des threads.
Procsseur AMD quad‐core

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 28

14
 19/01/2024

2. Architectures parallèles
2. Présentation

Architecture multi‐processeur Architecture multi‐coeur

(+) puissance de traitement élevée (+) meilleure utilisation des
ressources
(+) séparation des tâches (meilleure (+) coût moins élevée
sécurité pour certaines applications)
(+) Programmation plus facile
(‐) coût élevée (‐) limitations de bande passante *
(‐) Consommation d’énergie élevée (‐) Diminution des performances en
cas de surcharge**
(‐) Complexité de la programmation
* les cœurs se partagent une même mémoire cache et un même bus système, ce qui peut créer des limitations de
bande passante lorsque plusieurs cœurs tentent d'accéder simultanément aux mêmes ressources.

** Si les tâches exécutées sur les différents cœurs nécessitent toutes des ressources intensives en calcul ou en
mémoire M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 29

2. Architectures parallèles
3. Les challenges

 Les architectures parallèles posent de nombreuses questions et un

certain nombre de challenges à relever.

 Un ensemble de cœurs/ processeurs mais :

‐ Combien ?
‐ Quelle est la taille de leur mémoire associée ?
‐ mémoire partagée ou distribuée?
‐ Quelle est l’organisation des différents cœurs/ processeurs ?
‐ le nombre assure‐t‐il une bonne autonomie du système embarqué?

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 30

15
 19/01/2024

2. Architectures parallèles
3. Les challenges

 Et pour la communication:
‐ Comment sont‐ils reliés les uns aux autres ?
‐ Comment synchronisent‐ils leurs efforts ?

 Comment exploiter au mieux les performances offertes?

‐ améliorer les algorithmes/ optimisation du code (voir d’autres
cours )
‐ techniques de programmation parallèle adaptées à l’architecture
parallèle de notre système embarqué.

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 31

3. Quiz
Q1

Supposons un processeur superscalaire de degré 4 sans pipeline.

Combien d'instructions seront simultanément en exécution dans le
processeur?

2 à 8 instructions

 8 instructions

 4 instructions

4 à 8 instructions

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 32

16
 19/01/2024

3. Quiz
Q2

Supposons un processeur superscalaire de degré 2 avec un pipeline

de 5 étapes qui ne contient aucun aléa. Combien d'instructions
seront simultanément en exécution dans le processeur?

 2 instructions

 2 à 10 instructions

 5 instructions

 10 instructions

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 33

3. Quiz
Q3

Un aléa structurel ait lieu quand :

 2 instructions doivent être exécutées au même temps et sur la

même ressource

 Une instruction a besoin d’un résultat provenant d’une instruction

qui n’a pas encore finie son exécution

 L’instruction suivante à exécuter dépend du résultat d’un test

 il y a un problème de conception matérielle sur le processeur

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 34

17
 19/01/2024

3. Quiz
Q4

Quelles sont les caractéristiques d’une architecture multi‐coeur

 Une meilleure utilisation des ressources matérielles

 Plus coûteuse que les architectures multi‐processeur

 faible consommation d’énergie (par rapport à l’architecture multi‐

processeur).

 Chaque cœur dispose de son bus système et de sa mémoire

globale

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 35

3. Quiz
Q5

Quelles sont les caractéristiques d’une architecture multi‐processeur

 faible consommation d’énergie

 Puissance de calcul élevée

 mémoire cache commune à tous les processeurs

 programmation facile

M. FEKI – Architectures multiprocesseurs & algorithmes parallèles 36

18