Cycle Ingénieur SICOM, S8, FST, Fès

Pr. Mohammed Talibi Alaoui

AU:2021/2022
Pr. M. Alaoui Talibi 2
 Introduction au parallélisme
 Classification des architectures parallèles.
 Programmation parallèle impérative :
 Notionsde base
 Programmation par variables partagées
 Stratégiesde conception d'algorithmes parallèles.
 Exemples de langages.
 Mesures de performance.
 Programmation parallèle avec mémoire distribuée
et MPI.

Pr. M. Alaoui Talibi 3

Pr. M. Alaoui Talibi 4
 MOTIVATIONS

Pr. M. Alaoui Talibi 5

 Loi de Moore :

Pr. M. Alaoui Talibi 6

 La loi de Moore concerne l’évolution de la
puissance des ordinateurs.

 Selon cette loi :

Le nombre de transistors, c’est-à-dire l’élément
principal qui compose les processeurs des
ordinateurs, double tous les deux ans.

Et parallèlement double également la puissance

des appareils.

Pr. M. Alaoui Talibi 7

 Moore fixa ensuite le cycle non plus sur 2 ans mais dix-
huit mois.

 Donc selon Moore :

Tous les 18 mois, il y a doublement du nombre de

transistors, rendant les ordinateurs rapidement
obsolètes.

Vous l’avez compris, cette loi porte le nom de celui

qui l’a énoncée en 1965, le cofondateur de la société
Intel, Gordon Moore.

Pr. M. Alaoui Talibi 8

 Et Moore avait raison.

 Pourpreuve en 2014, les premières puces gravées

en 14 nanomètres (nm) – environ 5.000 fois plus fin
qu’un cheveu – sont arrivées avec un an de retard.

 Et
celles de 10 nanomètres n’étaient pas prêtes
avant 2017.

Pr. M. Alaoui Talibi 9

 Les 7 nanomètres pas avant 2020.

 Orcomme l’avait dit Moore, à cette taille, certains

éléments du transistor ne sont désormais
constitués que de quelques atomes.

Nous touchons aux limites de la physique.

Pr. M. Alaoui Talibi 10

 Lerecours au parallélisme pour accélérer des calculs
n’est pas une idée récente.

 Cependant, les contraintes matérielles imposèrent

l’utilisation d’un unique processeur.

 L’évolutiontechnologique des années 80 a permis de

réduire les couts de production des divers composants
d’un calculateur,

 Enmême temps qu’elle en augmentait les performances

à la fois en temps de calcul, en volume et en fiabilité.
Pr. M. Alaoui Talibi 11
 Leralentissement du gain en vitesse des circuits
électroniques ( entre 1976 et 1986 ) a conduit à la
recherche de nouvelles techniques pour gagner de la
puissance soit :

- au niveau algorithmique

- soit au niveau architectural

Pr. M. Alaoui Talibi 12

 Leconcept de parallélisme rompt avec l’approche
classique qui consiste à diminuer le temps de calcul
en effectuant plus vite chaque opération.

 Encalcul parallèle, le gain de temps provient de la

réalisation simultanée de plusieurs opérations.

 L’algorithmique
parallèle consiste à réduire la
complexité de certains problèmes parallèles.

Pr. M. Alaoui Talibi 13

 De plus, le niveau technologique atteint est tel
qu’il est maintenant possible de construire des
architectures multiprocesseurs et de les utiliser
efficacement :

Avec quelques processeurs pour des systèmes

généraux ( plusieurs dizaines )
OU
Beaucoup plus pour des systèmes spécialisées (
quelques milliers )

Pr. M. Alaoui Talibi 14

 Afind’atteindre cette objectif, les diverses
architectures parallèles ont poussé les algorithmiciens
à imposer de nouvelles contraintes à leurs modèles
pour les rendre plus proche de la réalité.

 Face aux demandes toujours croissantes en

puissance de calcul, le domaine du parallélisme
s’est considérablement développé depuis 1985.

Pr. M. Alaoui Talibi 15

 La parallélisation d’une méthode requiert plusieurs
phases :

Tout d’abord, il est commode :

 de partir de diverses écritures de la méthode sous

forme algorithmique.
 puis d’en faire une étude théorique de complexité
pour bien saisir le parallélisme intrinséque.
 Après avoir choisi la (les) bonne version, on peut
examiner son implémentation, càd
Pr. M. Alaoui Talibi 16
 Lafaçon d’exécuter les instructions sur une machine
cible.

Cela pose en particulier les problèmes :

- de placement d’instructions,
- de circulation des données,
- d’utilisation efficace des communications, ..

Pr. M. Alaoui Talibi 17

 Pourparalléliser un algorithme, on commence par
partitionner le problème en sous-taches.

 Restealors à affecter les taches aux processeurs,

en respectant les contraintes de précédence ainsi
que les contraintes matérielles liées à l’architecture
de la machine.

 Ces dernières permettent de sélectionner, parmi

toutes les versions parallèles obtenues, celle qui
est la plus efficace pour l’ordinateur utilisé.
Pr. M. Alaoui Talibi 18
 En général, ces contraintes sont de deux types :

 Accès limité aux données

 Et problèmes de synchronisation des processeurs.

Pr. M. Alaoui Talibi 19

 Aujourd’hui, on divise l’évolution de l’informatique
en cinq générations déterminées par :

 un niveau technologique,
 par un mode d’exploitation et de traitements,
 par les langages utilisées
 et par les objets traités.

Pr. M. Alaoui Talibi 20

Du séquentiel au parallèle :

Pr. M. Alaoui Talibi 21

1938 : premier ordinateur électronique analogique
1964 : premier ordinateur électronique digital
ENIAC.
1950 :
 premier ordinateur avec programme enregistré
 Technologie mécanique ou électromécanique
 UAL séquentielle
 Langage binaire

Pr. M. Alaoui Talibi 22

 1954 : premier ordinateur à transistors TRADIC ( 800
transistors)

 Mémoire magnétique
 UAL évoluée
 Langage assembleur, puis fortran et Algol.
 Exécution par batch d’un seul programme

Pr. M. Alaoui Talibi 23

 Utilisationdes circuits intégrés
 Compilateurs intelligents de langages de haut niveau.
 Multiprogrammation
 Processeurs vectoriels
 Temps partagé et multiprogrammation
 Machines virtuelles
 Du traitement des données au traitement l’information.

Pr. M. Alaoui Talibi 24

 Circuit à haute intégration (LSI)
 Mémoire de grande taille
 Langages permettant le traitement vectoriel
 UAL parallèle et pipeline
 Plusieurs processeurs
 Du traitement de l’information au traitement des
connaissances (systèmes experts).

Pr. M. Alaoui Talibi 25

 Circuits spécialisés à très haute intégration (VLSI)

 Multiprocesseurs parallèles

 Parallélisme massif

 Du traitement des connaissances au traitement de

l’intelligence.

Pr. M. Alaoui Talibi 26

 Au plus haut niveau, le traitement parallèle permet
l’exécution simultanée de plusieurs programmes
indépendants.

 Il utilise la multiprogrammation, le temps partagée

et le multitraitement: Mode de fonctionnement d'un ordinateur selon
lequel plusieurs processeurs ayant accès à des mémoires communes
peuvent opérer en parallèle sur des programmes différents.(Anglais:
multiprocessing).

 Il s’emploie dans des systèmes de grande taille

(mainframe) et se traite au niveau du système
d’exploitation.

Pr. M. Alaoui Talibi 27

 L’introduction
du parallélisme à l’intérieur d’un
programme peut se faire au niveau des procédures.

 Ilnécessite la décomposition du programme en

taches, la recherche des relations de dépendance
entre ces taches et la programmation en parallèle
des taches indépendantes.

Pr. M. Alaoui Talibi 28

 Il peut se traiter au niveau du système d’exploitation :

 parallélisation automatique de programmes,

 compilateurs intelligents

 ou au niveau algorithmique.

Pr. M. Alaoui Talibi 29

 Le traitement parallèle d’instructions indépendantes
utilise la technique de vectorisation.

 Ilse traite au niveau du système (vectoriseur), du

langage de programmation (Fortran vectoriel) ou au
niveau algorithmique.

Pr. M. Alaoui Talibi 30

 Latechnique du pipeline permet l’introduction du
parallélisme au niveau d’une instruction. Il s’agit de
décomposer une instruction en plusieurs étapes
successives et de faire exécuter, en même temps,
des étapes différentes de plusieurs instructions.

 Ce
type de parallélisme est traité au niveau du
matériel.

 Lesgrands ordinateurs font appel maintenant tous

à ces techniques.
Pr. M. Alaoui Talibi 31
Le parallélisme dans les
monoprocesseurs

Pr. M. Alaoui Talibi 32

 Les architectures monoprocesseurs ont en général
une structure de base commune :

 Une mémoire principale

 Un processeur centralisé
 Un ensemble de communications

Les relations entre ces 3 unités peuvent être réalisées

de manières diverses, par exemple par l’intermédiaire
d’un bus commun (VAX -11/780) par exemple.
Pr. M. Alaoui Talibi 33
 L’introduction du parallélisme peut se faire de
plusieurs façons :

 UAL parallèle : Plusieurs unités fonctionnelles

 par exemple Fonctionnement simultané des trois
unités
 Multiprogrammation et temps partagé

Pr. M. Alaoui Talibi 34

Exemple :
Les diverses fonctions d’une UAL sont distribuées à des
unités indépendantes opérant en parallèle.

Les CDC 6600 possède 10 unités fonctionnelles (addition,

soustraction, décalage,..) dans son UAL.

L’IBM 360/91 a deux unités arithmétiques parallèles :

l’une pour les opérations en virgule fixe,
l’autre pour les opérations en virgule flottante,
divisée en deux unités fonctionnelles (additions et
multiplications).
Pr. M. Alaoui Talibi 35
 LesUAL possèdent maintenant des additionneurs
parallèles à anticipation de retenue et de multiplieurs
intégrés.

 Leur traitement est pipeline

Pr. M. Alaoui Talibi 36

 L’utilisation
des multiprocesseurs conduit à une
programmation effective de divers processeurs.

 Un ordinateur est donc parallèle dés qu’il dispose

de plus d’un processeur pour effectuer le
traitement d’un seul programme.

 Le Cray 2 possède 4 processeurs très puissants.

Pr. M. Alaoui Talibi 37

 Problème d’optimisation :

Une très grande partie des programmes actuels

n’utilise pas la puissance des multi-cœurs.

Limite théorique : loi d’Amdahl

Pr. M. Alaoui Talibi 38

Soit f la fraction intrinsèquement séquentielle (non
parallèlisable) de l’algorithme à paralléliser.

Alors l’accèleration maximale sur p processeurs de

l’algorithme parallèle correspondant est :

S(n,p)≤1/(f+(1-f)/p)

Pr. M. Alaoui Talibi 39

 Exemple :

20% d’un algorithme n’est pas parallélisable.

L’accéleration est donc limité à 5.

50% d’un algorithme n’est pas parallélisable.

L’accéleration est donc limité à 2.

Pr. M. Alaoui Talibi 40

 En pratique, le (sur)cout dû au parallélisme est dû
aux parties séquentielles, mais aussi aux aspects
suivants :

 Démarrage et terminaison des taches

 Synchronisation
 Communications
 Surcouts logiciels dus aux compilateurs,
bibliothèques, outils, systèmes d’exploitation…

Pr. M. Alaoui Talibi 41

Pr. M. Alaoui Talibi 42
 Comment construire et analyser des algorithmes et
des programmes pour des machines si différentes.

 Peut-on concevoir une méthode de programmation

identique ?

 Existe-ildes outils de parallélisation automatique et

quels sont leur principes ?

Pr. M. Alaoui Talibi 43

 Certains
problèmes sont ils intrinsèquement
séquentiels ?

 Leparallélisme massif a-t-il un avenir et peut-il

être utilisé efficacement?

Voila quelques unes des questions auxquelles nous

nous proposons d’apporter des Réponses.

Pr. M. Alaoui Talibi 44

 Paradigmes de base de la
programmation concurrente

Pr. M. Alaoui Talibi 45

 Permettre d'effectuer plusieurs traitements, spécifiés
distinctement les uns des autres,« en même temps ».

 En général, dans la spécification d'un traitement,

beaucoup de temps est passé à « attendre ».

 Idée : exploiter ces temps d'attente pour réaliser

d'autres traitements, en exécutant en concurrence
plusieurs traitements.

Pr. M. Alaoui Talibi 46

 Laprogrammation concurrente permet à des
processus multiples, de pouvoir partager des
ressources (structures de données, ressources
matériels, CPU, mémoire, dispositifs I/O).

Pr. M. Alaoui Talibi 47

 Utilisation des temps d’attente de saisie :

Pr. M. Alaoui Talibi 48

 Programme concurrent :

programme qui contient plusieurs processus (ou

threads) qui coopèrent.
 coopération Communication, échange
d’information

 Deux principales façons de communiquer :

 par l’intermédiaire de variables partagées.
 par l’échange de messages et de signaux (par ex.
canaux de communications).
Pr. M. Alaoui Talibi 49
 Note: on considère un thread comme étant un
processus léger (lightweight process)

Pr. M. Alaoui Talibi 50

 Processus vs thread :

 Processus :

- Un processus représente un programme en cours

d’exécution.

– Un processus possède un espace mémoire privé,

indépendant de celui des autres processus.

– Parce qu’ils ne partagent aucun espace mémoire

commun, deux processus qui veulent collaborer doivent le
faire en utilisant un mécanisme d’échange de messages .

Pr. M. Alaoui Talibi 51

– Le contexte d’un processus est lourd : code,
registres.

- Créer et activer un processus est donc (très!)

coûteux!

Pr. M. Alaoui Talibi 52

 Thread :
– Un thread représente une fonction en cours
d’exécution.

– Un processus peut contenir un ou plusieurs threads.

- Ces threads partagent alors la mémoire ainsi que

diverses autres ressources.

- Parce qu’ils partagent un même espace mémoire,

deux threads qui veulent collaborer peuvent le
faire par l’intermédiaire de variables partagées.
Pr. M. Alaoui Talibi 53
- Le contexte d’un thread est léger.

- Créer et activer un thread est donc moins coûteux

que dans le cas d’un processus!

Pr. M. Alaoui Talibi 54

 Interaction entre processus : communication

La communication est un échange de données entre processus,

• Soit par messages explicites.

Deux manières d'envoyer un message :

Synchrone : permet autant la synchronisation que la

communication.

Le Processus Emetteur doit attendre que son message soit reçu;

Et il est possible qu'un processus Récepteur doive attendre qu'un
message soit envoyé.

Pr. M. Alaoui Talibi 55

Asynchrone :

L'émetteur poursuit son exécution après l'envoi du

message.

• soit à travers des variables partagées (visibles à

chaque processus; convient aux systèmes à mémoire
commune);

• ou bien par RPC (Remote Procedure Call).

Pr. M. Alaoui Talibi 56

 RPC (remote procedure call) est :

 Un protocole réseau

 Ce protocole est utilisé dans le modèle client-serveur

 Pour assurer la communication entre le client, le serveur et

d’éventuels intermédiaires.

 Permettant de faire des appels de procédures sur

un ordinateur distant à l'aide d'un serveur d’applications.

Pr. M. Alaoui Talibi 57

 Interaction entre processus : Synchronisation

La synchronisation, implique l'échange d'information de

contrôle entre processus.

Exemples :

Un processus dépend des données produites par un autre;

Si les données ne sont pas disponibles, le processus doit
attendre jusqu'à ce qu'elles soient disponibles.

Un processus peut changer son état à "Blocked"(Wait(Pi)),

et peut signaler aux Processus "Blocked" qu'ils peuvent
continuer (signal(Pi)).
Pr. M. Alaoui Talibi 58
 Entrelacement
de threads : C'est un dispositif technique
commode pour étudier l'exécution concurrente de
processus.

 Définition:
Un entrelacement de deux séquences s et t est une
séquence U construite à partir des événements de s
et de t, de telle sorte que les événements de s
préservent leur ordre dans U ainsi que ceux de t.

Pr. M. Alaoui Talibi 59

 Exemple :

Si a et z sont des événements concurrents,

On considère le cas ou a se produit avant z ou bien
z se produit avant a, mais on ignore le cas ou a et z
se produisent en même temps.

Pr. M. Alaoui Talibi 60

 Concurrence comme entrelacement : Exemple
Soient deux Processus :

A:a;b
Z:x;y;z

L'exécution concurrente de A et Z, peut être étudiée en considérant les

entrelacements possibles (10):
 a b x y z
 a x b y z
 .....
 x y z a b

L'entrelacement préserve l'ordre relatif dans le thread:

a doit se produire avant b, mais x y z étant dans un autre thread peuvent se produire
dans n'importe quel ordre relativement à a et b. Il en est de même pour x, y et z...

Pr. M. Alaoui Talibi 61

Une autre façon de classifier
les paradigmes de
programmation parallèle

Pr. M. Alaoui Talibi 62

 Une autre classification intéressante des modèles
de programmation parallèle, qui peut aussi aider à
mieux comprendre certaines notions importantes
de conception d’algorithmes parallèles, est celui
qui distingue entre :

 parallélisme de données,
 parallélisme de contrôle
 et parallélisme de flux.

Pr. M. Alaoui Talibi 63

 Correspond à l’application d’une même opération
sur tous les éléments d’une collection des données
homogènes, (de même type).

 Onparle dans ce cas de structures des données

régulières.

 Paropposition aux structures de données

dynamiques basées sur l’utilisation des pointeurs (
et donnant lieu à des arbres ou des graphes : donc
des structures de formes non régulières ).
Pr. M. Alaoui Talibi 64
 L’ensemble du travail effectué consiste en une
série de phases de calcul.

 Chaque phase est une application d’une opération

sur une collection.

 Et
ou les différentes phases peuvent évidemment
manipuler des collections différentes.

Pr. M. Alaoui Talibi 65

 La forme la plus simple de parallélisme de données
survient lorsque les calculs sur les différents
éléments sont complètement indépendants les uns
des autres.

L’ordre d’exécution n’a aucune importance et, donc,

que tous les calculs peuvent se faire en parallèle.

Pr. M. Alaoui Talibi 66

 Soit
l’opération consistant à multiplier chacun des
éléments d’une collection par l’entier 2.

 L’applicationd’une telle opération sur les éléments

d’un tableau d’entiers a pour obtenir un tableau b
pourrait alors s’écrire comme suit :

int a[n], b[n]

pour i varie de 1 … n
b[n]=2*a[n]

Pr. M. Alaoui Talibi 67

Ici, c’est le compilateur qui s’occupe de générer le
code qui permettra l’exécution en parallèle des
diverses multiplications et affectations.

C’est aussi le compilateur qui s’occupera de

distribuer les données entre les processeurs, en
fonction des directives spécifiés par le programmeur.

Pr. M. Alaoui Talibi 68

 Lafigure suivante illustre les deux principaux
types de décomposition et distribution d’un
tableau à deux dimensions 8*8 sur 4 processeurs, à
savoir distribution par bloc ou distribution
cyclique (ou des combinaisons entre les deux
modes).

Pr. M. Alaoui Talibi 69

Pr. M. Alaoui Talibi 70
 Consiste :

 à décomposer le travail à effectuer en

différentes taches,

 à identifier celles qui peuvent s’exécuter en

parallèle,

 puis finalement à ordonner, à l’aide de

structures de contrôle appropriés, l’exécution
de ces diverses taches.

Pr. M. Alaoui Talibi 71

 Correspond au principe du travail à la chaine.

 Uneséquence d’opérations doit être appliquées en

cascade à une série de données similaires.

 Lesopérations à réaliser sont associées à des

éléments de calculs chainées de façon à ce que
l’entrée d’une opération soit la sortie de
l’opération précédente.
Pr. M. Alaoui Talibi 72
 Leparallélisme de flux n’est donc rien d’autre
qu’un fonctionnement en mode pipeline des
éléments du calcul.

Pr. M. Alaoui Talibi 73

Systèmes parallèles et
distribués

Pr. M. Alaoui Talibi 74

 Définition :

 On dit que deux processus s'exécutent en parallèle

lorsqu'ils s'exécutent sur des CPU différents.

 Ils sont concurrents lorsqu'ils concourent pour

l'obtention d'une même ressource CPU.

Leur exécution est alors entrelacée. Chacun

dispose à son tour d'un quantum de temps calcul.
Pr. M. Alaoui Talibi 75
 Découper un gros problème en de nombreux petits
problèmes :

- Super calculateurs pour le calcul scientifique

- Stations multiprocesseurs
- Grilles :
 SETI@Home
 folding@home
 défi cryptographiques ([Link])
 ....

Pr. M. Alaoui Talibi 76

A l’intérieur du processeur :

 instructions en parallèle (pipeline)

 multi-cœurs

 Multi-processeurs

Pr. M. Alaoui Talibi 77

Le parallélisme au
sein du processeur :

Pr. M. Alaoui Talibi 78

 L’exécutiond’une instruction (multiplication par ex.)
nécessite plusieurs cycles d’horloge).

⇒ On exécute en parallèle les instructions indépenda-

ntes pour gagner du temps.

 Un processeur possède plusieurs Unités Arithmétique

et Logiques.

 Les
instructions peuvent être réarrangées afin
d’améliorer le rendement (out of order execution).
Pr. M. Alaoui Talibi 79
 Cœur :
Unité exécutant les instructions dans un processeur
Multi-cœur : plusieurs unités exécutant des
instructions en parallèle.

 Multi-cœur(tous sur un même circuit) ≠multi-

processeur (circuits différents).

Pr. M. Alaoui Talibi 80

 Une très grande partie des processeurs actuels sont
multi-cœurs (généralement de 2 à 8 cœurs).

 Encore plus de cœurs dans l’avenir :

 Prototype tera-scale (80 cœurs) d’Intel.

 Processeurs multi-cœurs pour les appareils mobiles

(smartphones, tablettes).

Pr. M. Alaoui Talibi 81

Le parallélisme multiprocesseurs :

Pr. M. Alaoui Talibi 82

 Un concept ancien :

 premier ordinateur multi-processeur en 1962,

 premier ordinateur multi-processeur parallèle en

1969.

 Similaire au multi-cœur à l’exception de la

mémoire cache qui n’est pas partagée.

Pr. M. Alaoui Talibi 83

 Supercalculateurs :
- Le plus puissant : Computer K
- 88,128 processeurs 8-cœurs (2GHz)

- Le deuxième : Tianhe-1A
- 14 336 processeurs
- 7 168 processeurs graphiques

Pr. M. Alaoui Talibi 84

Les systèmes distribués :

Pr. M. Alaoui Talibi 85

 Ensemble de processeurs autonomes.

 Qui ne se partagent pas de mémoire primaire.

 Maisqui coopèrent par envoi de messages à travers

un réseau de communication.

Pr. M. Alaoui Talibi 86

 Mise en commun d'un grand nombre de ressources à
faible coûts :
– Bon rapport performance / prix.
– Puissance globale virtuellement illimitée.
- Supérieure à celle des gros calculateurs

 Disponibilité et flexibilité :

– Un élément peut tomber en panne sans bloquer tout

le système.
– Flexibilité : Distribution de la charge permet d’exécuter
un travail sur la machine la plus disponible.
Pr. M. Alaoui Talibi 87
 Distribution naturelle de certaines applications :
- distribution géographique d’agences bancaires.

 Partage de ressources coûteuses entre plusieurs

utilisateurs/machines.
– Accès à distance à une ressource indisponible en
local.
– Accès aux mêmes ressources depuis tous les endroits
du système.

Pr. M. Alaoui Talibi 88

 Problèmes inhérents aux communications
– Si pas de mémoire partagée, communications explicites
(moins de communications).
– Lenteur, saturation, perte de messages.

 Partage et distribution de données impose mécanismes

complexes :
– Synchronisation.
– Sécurité.

Pr. M. Alaoui Talibi 89

Internet :

Contient de nombreux sous-systèmes selon le

protocole considéré :

– Web (http)

– peer-to-peer : permet à plusieurs ordinateurs

de communiquer entre eux via un réseau.

Pr. M. Alaoui Talibi 90

 Seti@home !
– Les machines de tout le monde :

 Puissance virtuellement illimitée

- N Gflop/s par machine, des millions des
machines.

 Calculsindépendants
 Modèle plus distribué que parallèle

Pr. M. Alaoui Talibi 91

 Cray Jaguar à ORNL :

- 20 000 noeuds à six-core

Assemblés par réseau Cray spécifique

- Presqu'un Cluster, mais réseau trop spécifique

- Plus d'1 PetaFlop/s

Pr. M. Alaoui Talibi 92

 Tianhe en Chine :

- 7000 nœuds à 2 processeurs et 2 GPUs.

- Un cluster avec des accélérateurs.
- 2 Petaflop/s.

Pr. M. Alaoui Talibi 93

 Architecture matérielle et/ou logicielle
- Un système parallèle peut être distribué
Si assemblage de machines à mémoires
indépendantes
- ou non
Si une seule grosse machine parallèle.

Application cible
– Applications parallèles dans les systèmes
parallèles :
Communication, synchronisation, … entre les différentes

Pr. M. Alaoui Talibi 94

Pr. M. Alaoui Talibi 2018-2019 95
Pr. M. Alaoui Talibi 2018-2019 96
 Introduction
 Processus
 Appels système
 Ordonnancement des processus
 Communication et synchronisation des
processus : l’exclusion mutuelle.

Pr. M. Alaoui Talibi 2018-2019 97

 Lesordinateurs mono processeur actuels sont capables
d’exécuter plusieurs programmes « simultanément ».

 Multiprogrammation, multi-tâches ou encore pseudo-

parallélisme.
 En réalité ce n’est pas vrai, une machine mono processeur ne
peut exécuter qu’une seule tâche à un instant donné.

 Le processeur est affecté, périodiquement, à chaque programme

en cours d’exécution pour une durée infiniment petite  donne
l’impression d’exécuter tous les programmes en même temps.

Pr. M. Alaoui Talibi 2018-2019 98

 Un processus est un programme en exécution qui a
son propre environnement

 Espace d’adressage
 Code (instructions du programme)
 Pile
 Compteur ordinal
 Registres
 Variables
 …
 Un programme peut être exécuté par plusieurs processus.

Pr. M. Alaoui Talibi 2018-2019 99

Les systèmes d’exploitation ont besoin de savoir que tous

les processus nécessaires existent bel et bien.

Par exemple le contrôleur d’un four à micro-ondes : il

peut être envisageable que tous les processus susceptibles

d’intervenir soient actifs pendant le fonctionnement du

système.

Pr. M. Alaoui Talibi 2018-2019 100

En général, les systèmes d’exploitation ont besoin de
disposer d’une méthode pour créer et arrêter les
processus, selon le cas, au cours de leur activité.

Pr. M. Alaoui Talibi 2018-2019 101

 Création des processus
 Quatre événements sont à l’origine de la création d’un
processus.
 Initialisation du système.

 Exécution d’un appel système de création de processus par un

processus en cours d’exécution.

 Requête utilisateur sollicitant la création d’un nouveau

processus.

 Initiation d’un travail en traitement par lot.

Pr. M. Alaoui Talibi 2018-2019 102

 Sous UNIX, la commande ps sert à afficher la liste
des processus en cours d’exécution.

 Sous windows 95/98/Me, le fait de taper Ctrl+Alt+Del

une seule fois permet de voir les processus en cours.

 Sous Windows 2000/XP, c’est le gestionnaire des

taches qui intervient.

Pr. M. Alaoui Talibi 2018-2019 103

Création des processus :
 La création d’un processus se traduit toujours par
un :
appel système déclenché à partir de :
 Processus utilisateur OU
 Processus système, OU
 Processus gestionnaire de traitements par lots.

Cet appel demande au système d’exploitation de créer un

nouveau processus et indique, directement ou indirectement,
quel programme y exécuter.

 Sous Unix : fork() crée un clone du processus appelant

 Sous Win32 : Create_Process.

Pr. M. Alaoui Talibi 2018-2019 104

 Dans les deux cas, une fois qu’un processus a été
crée, le parent et le fils disposent désormais de leur
propre espace d’adressage.

 S’il arrive que l’un des processus modifie un mot dans

son espace d’adressage, le changement n’est pas
visible par l’autre processus.

Pr. M. Alaoui Talibi 2018-2019 105

 Fin d’un processus :

 Une fois qu’un processus a été créé, il commence à

s’exécuter, quelle que soit sa tache.

 Mais tôt ou tard, le nouveau processus s’arrete pour

diverses raisons :

Pr. M. Alaoui Talibi 2018-2019 106

 Fin d’un processus
 Arrêt normal (volontaire)
 Exécution de toutes les instructions du programme correspondant.
 Arrêt à cause d’une erreur fatale
 Erreur imprévisible (division par 0)
 Par exemple, saisir la commande cc foo.c

Pour compiler le programme foo.c et que le fichier correspondant

n’existe pas, le compilateur s’arrete.

Pr. M. Alaoui Talibi 2018-2019 107

 Arrêt à cause d’une erreur provoquée par le processus :

Souvent due à un bogue du programme.

Par exemple, les erreurs peuvent provenir de l’exécution :

- d’une instruction illégale,

- D’une référence mémoire inexistante

- d’une division par 0

Pr. M. Alaoui Talibi 2018-2019 108

 Le quatrième motif d’ arrêt d’un processus :

Intervient lorsqu’il exécute un appel système indiquant

au SE d’ Arrêter un ou plusieurs autres processus.

Sous UNIX, cet appel est kill.

Pr. M. Alaoui Talibi 2018-2019 109

 Hiérarchie des processus
 Chaque processus a un et un seul processus parent
 Sous Unix le processus « init » est le seul qui n’a pas de
parent.
 C’est le processus qui initialise le système.
 Un processus peut avoir des processus fils 0,1,2
ou plus.
 Sous Unix, il est possible d’envoyer des signaux à toute
une arborescence de processus
 Demande d’arrêt par exemple
 Le principe de l’hiérarchie n’existe pas sous Windows
 Tous les processus sont égaux

Pr. M. Alaoui Talibi 2018-2019 110

 Etats des processus
 Un processus peut être dans l’un des trois états
 Elu : En cours d’exécution
 C’est lui qui détient la CPU
 Prêt
 A toutes les ressources nécessaires et attend son tour pour la
CPU.
 Bloqué
 Attend une ressource ou un événement
 Ne peut pas être candidat pour obtenir la CPU avant qu’il soit
débloqué

Pr. M. Alaoui Talibi 2018-2019 111

 La transition 1 : rend le processus
bloqué en attente d’une ressource ou
d’un événement.

 La transition 2 : reprend la CPU au

processus et la donne à un autre
processus. Elu
1: réquisition
Notre processus doit attendre son tour. d’une ressource 2: réquisition
de la CPU
3: attribution
 La transition 3 : donne (redonne) la CPU de la CPU
à notre processus.
Bloqué
 La transition 4 : débloque le processus Prêt
ce qui le rend candidat pour obtenir la 4: acquisition
de toutes les ressources
CPU.

 Un processus prêt ne peut pas devenir

bloqué sans passer par l’état « élu ».

 Un processus bloqué ne peut pas

prendre la CPU sans passer par l’état «
prêt ». Pr. M. Alaoui Talibi 2018-2019 112
 Appels systèmes :
 Définissent l’interface entre le SE et les programmes
utilisateurs
 Sorte de bibliothèque de fonctions.
 Environ 100 appels systèmes dans la norme UNIX.
 Analogie avec l’appel de fonctions en langage C.
 Les tâches correspondant aux appels systèmes sont
exécutées en mode noyau.
 Services offerts à travers les appels systèmes :
 Gestion des processus
 Gestion de la mémoire
 Gestions des fichiers
 Gestion des E/S

Pr. M. Alaoui Talibi 2018-2019 113

 Principaux appels système de gestion des processus de

la norme UNIX :

Appel système description

pid = fork() Crée un processus enfant identique au parent

pid = waitpid(pid, &stat, Attend la terminaison d'un fils

options)

exit (statut) Termine l'exécution du processus et renvoie le

statut

Pr. M. Alaoui Talibi 2018-2019 114

 Appels système de gestion des processus
 fork
 Crée une copie conforme du processus appelant
 Même code
 Mêmes descripteurs de fichiers
 …
 Sauf la valeur retournée par fork
 Nulle dans le nouveau processus (fils)
 PID du fils dans le processus père
 Les deux processus évolueront, en général, différemment.
 Le seul moyen de créer les processus.

Pr. M. Alaoui Talibi 2018-2019 115

Pr. M. Alaoui Talibi 2018-2019 116
Lorsqu’un ordinateur est multiprogrammé, il possède
fréquemment plusieurs processus en concurrence pour
l’obtention de temps processeur.

Cette situation se produit chaque fois que deux

processus ou plus sont en état prêt en même temps.

S’il y’a un seul processeur, un choix doit être fait quand

au prochain processus.

Pr. M. Alaoui Talibi 2018-2019 117

 La partie du système d’exploitation qui effectue ce
choix se nomme l’ordonnanceur (sheduler).

 L’algorithme qu’il emploie s’appelle algorithme

d’ordonnancement (sheduling algorithm).

Pr. M. Alaoui Talibi 2018-2019 118

 L’ordonnanceur peut jouer un rôle prépondérant pour
améliorer les performances du système d’exploitation
 Exemple :
 Etant donnés deux processus P1 et P2
 P1 : processus de rafraichissement de l’écran
 P2 : processus d’envoi de courrier électronique
 Retarder P1 (i.e. ralentir le rafraichissement de l’écran) 
l’utilisateur perçoit ce petit retard comme une dégradation du
service.
 Par contre un petit retard de l’envoi du courrier électronique ne
sera pas senti par l’utilisateur.
 L’ordonnanceur doit, normalement favoriser le processus P1.

Pr. M. Alaoui Talibi 2018-2019 119

 Quand ordonnancer ?
Un large éventail de situations nécessitent de
l’ordonnancement.

- lorsqu’un nouveau processus est créé, il faut décider

s’il faut exécuter d’abord le processus parent ou le
processus fils. Etant donné que les deux sont en état
prêt.

- lorsqu’un processus se termine, un autre processus

doit être choisi dans le jeu des processus prêts.
Pr. M. Alaoui Talibi 2018-2019 120
- lorsqu’un processus bloque sur des E/S un autre
processus, un autre processus doit être sélectionné
pour être exécuté.

- lorsqu'une interruption d’E/S se produit, il faut

également prendre une décision d’ordonnancement.

Si l’horloge matérielle fournit des interruptions

périodiques à une fréquence de 50 ou 60 Hz, par
exemple, une décision d’ordonnancement peut être
prise à chaque kéme interruption.
Pr. M. Alaoui Talibi 2018-2019 121
On peut classer les algorithmes d’ordonnancement en
deux catégories selon leur manière de réagir aux
interruptions de l’horloge :

- Un algorithme non préemptif : sélectionne un

processus, puis le laisse s’exécuter jusqu’à ce qu’il
bloque ou qu’il libère volontairement le processeur.
Même s’il s’exécute pendant des heures.

- Par contre un algorithme préemptif, sélectionne un

processus et le laisse s’exécuter pendant un délai
déterminé. Si le processus est toujours en cours à
l’issue de ce délai : il est suspendu.
Pr. M. Alaoui Talibi 2018-2019 122
 Efficacité de l’utilisation du processeur
 Le basculement du processeur d’un processus à un autre
est relativement coûteux

 Basculement en mode noyau

 Sauvegarder l’état du processus en cours
 Charger l’environnement du processus suivant
 Démarrer le processus

  éviter les basculements très nombreux

Pr. M. Alaoui Talibi 2018-2019 123

 Plusieurs algorithmes d’ordonnancement :
 Ordonnancement de type tourniquet (round robin)

 Ordonnancement par priorités

 Ordonnancement garanti

 Ordonnancement par tirage au sort

 …

Pr. M. Alaoui Talibi 2018-2019 124

 Ordonnancement de type tourniquet (round robin)

 Le plus ancien et le plus utilisé

 Tous les processus à ordonnancer sont au même pied
d’égalité.
 Le processeur est attribué, à tour de rôle, à chacun des
processus en lice pour une durée donnée (quantum)
 Un processus, qui n’a pas terminé son exécution au bout
de son quantum, se met de nouveau dans la file
d’attente.

Pr. M. Alaoui Talibi 2018-2019 125

 Le choix du quantum est très déterminant pour les
performances du système.

 Un quantum très petit provoquerait des basculements très

fréquents  dégradation des performances

 Un quantum très grand  temps d’attente est important pour les

processus prêts  atteinte à l’interactivité

Pr. M. Alaoui Talibi 2018-2019 126

 Ordonnancement par priorités
 En réalité, les processus ne sont pas de même niveau
d’importance
 Les processus système sont le pivot du système et par la
suite doivent être les plus prioritaires.
 Un processus d’envoi de courrier n’est pas sensible à un petit
retard.
 Un processus de traitement de texte peut être sensible au
retard d’affichage des caractères saisis au clavier.

  il est important de définir des priorités entre les

processus

Pr. M. Alaoui Talibi 2018-2019 127

 Ordonnancement par priorités
 Principe :
 Attribution d’une priorité à chaque processus
 Parmi les processus prêts, l’ordonnanceur choisit celui qui
a la plus grande priorité

 La priorité peut être :

 Statique : ne change pas le long de l’exécution  un
processus de priorité supérieure est toujours prioritaire
par rapport à un autre de prioritaire moindre.

Pr. M. Alaoui Talibi 2018-2019 128

 Dynamique
 Le niveau de priorité du processus qui détient la CPU

baisse dans le temps jusqu’à ce qu’un autre processus

devient plus prioritaire et lui prend la CPU.

 De même le processus prêt se voit augmenter le niveau

de priorité au fil du temps ce qui lui donne la chance
d’avoir la CPU.

Pr. M. Alaoui Talibi 2018-2019 129

 Ordonnancement par priorités

 Catégories de priorités
 Le système définit plusieurs catégories de priorités
 Regrouper les processus par catégorie
 Les processus de la même catégorie ont le même niveau de
priorité.
 L’ordonnancement adopté entre ces processus est celui de
type Tourniquet.
 Les processus de la catégorie de priorité supérieure sont
toujours prioritaires par rapport aux autres processus des
autres catégories.

Pr. M. Alaoui Talibi 2018-2019 130

 Ordonnancement par priorités :
 Files d’attente multiples
 Définition de plusieurs catégories de priorités
 Le quantum du processeur n’est pas le même pour toutes les
catégories. La catégorie de niveau de priorité inférieure a un
quantum relativement grand que celui de la catégorie de priorité
supérieure.
 Récompenser le retard des processus de priorité inférieure par une
durée de détention de la CPU supérieure.
 Le processus qui termine sa durée et lâche le processeur passe à la
catégorie inférieure.
 les processus interactifs commencent dans la catégorie
supérieure.
 Une interaction (clique, retour chariot) remet le processus dans
la catégorie supérieure.

Pr. M. Alaoui Talibi 2018-2019 131

 Ordonnancement garanti
 Le principe de cet ordonnancement est que les
processus doivent avoir, globalement, le même cumul
des durées de détention du processeur.
 Le système maintient, pour chaque processus, un taux
correspondant à la durée effective d’utilisation de la
CPU par rapport à son quota.

Le processus qui a le taux le plus petit (qui a moins

utilisé la CPU) sera le plus prioritaire.
 Exemple
Un processus de taux ½ (a utilisé la moitié de son quota) est
prioritaire par rapport au processus de taux 1,2 (a dépassé
son quota de 20%).
Pr. M. Alaoui Talibi 2018-2019 132
 Ordonnancement par tirage au sort :

 L’idée de base consiste à donner aux processus des «

billets de loterie » pour différentes ressources du
système et notamment pour le temps processeur.
 L’ordonnanceur effectue, à chaque fois, un tirage au
sort et le processus possédant le billet tiré aura le CPU.
 Possibilité d’instaurer une discrimination positive :
 Pour favoriser certains processus, il suffit de leur attribuer
plus de billets que les autres
 Le processus qui a plus de billets a beaucoup de chance qu’un
de ses billets soit tiré.

Pr. M. Alaoui Talibi 2018-2019 133

 Des processus coopératifs peuvent s’échanger leurs
billets
 Un processus bloqué, en attente d’un autre processus,
préférerait donner ses billets à ce dernier.
  le processus bloquant aura, donc, plus de chance
d’être sélectionné.
 Notre processus pourra récupérer ses billets et éventuellement
ceux de l’autre processus.

Pr. M. Alaoui Talibi 2018-2019 134

 Comment un processus passe des informations à un
autre processus ?

 Comment éviter des conflits entre des processus

concurrents qui s’engagent dans des activités
critiques ?

 Comment synchroniser les processus dépendants ?

Pr. M. Alaoui Talibi 2018-2019 135

 Les conditions de concurrence
 La section critique
 L’exclusion mutuelle avec attente active
 Le sommeil et l’activation
 Les sémaphores
 Les moniteurs
 L’échange de message
 Les barrières
Pr. M. Alaoui Talibi 2018-2019 136
 Exemple : spooler d’impression
 Principe
 Un processus qui veut imprimer un fichier, entre son nom dans
un répertoire spécial : répertoire du spooler
 Le démon d’impression (spooler) inspecte périodiquement son
répertoire, s’il y a un fichier il l’imprime et le supprime du
répertoire.
 Le répertoire du spooler possède un grand nombre d’entrées
numérotées : 0, 1 ,2 … chacune pouvant accueillir un nom de
fichier.
 Le spooler utilise deux variables partagées : out et in
 Out : pointe vers le prochain fichier à imprimer
 In : pointe vers la prochaine entrée libre du répertoire
 Les variables out et in peuvent être stockées dans un fichier
de deux mots, disponible pour tous les processus.

Pr. M. Alaoui Talibi 2018-2019 137

 Problème : deux processus A et B
tentent d’imprimer en même temps
 Le processus A lit la valeur de in, et en stocke
out in
la valeur, 7, dans une variable locale appelée
4 7
next_free_slot.
 A ce moment là, une interruption se 4 [Link]
Processus A
produit. La CPU jugeant que le processus 5 Prog.c
A a bénéficié de suffisamment du temps 6 [Link]
d’exécution, bascule vers le processus B. Processus
7
B
 Celui-çi lit la valeur de in et récupère
également un 7. il stocke cette valeur dans
sa variable locale appelée aussi next_free_slot.
 A ce point, les 2 processus pensent que la
prochaine entrée disponible est la 7.
Pr. M. Alaoui Talibi 2018-2019 138
Le processus B continue de s’exécuter. Il stocke son
nom de fichier dans l’entrée 7 et actualise in qui
prend la valeur 8.

Finalement, le processus A s’exécute à nouveau,

reprenant les choses où il les avait laissées. Il
examine next_free_lost, y trouve un 7, et écrit son
nom de fichier dans le connecteur 7, écrasant le nom
que le processus B venait juste d’y placer. Ensuite, il
calcule next_free_lost+1, ce qui donne 8, et
positionne in à 8.

Pr. M. Alaoui Talibi 2018-2019 139

 Problème : deux processus A et B tentent
d’imprimer en même temps

 Le processus B ne recevra jamais de sortie.

L’utilisateur B va attendre longtemps une impression
qui ne viendra jamais.

 De telles situations, ou deux processus ou plus

lisent ou écrivent des données partagées et ou le
résultat final dépend de quel élément s’exécute à
un instant donné : sont nommées conditions de
concurrence.

Pr. M. Alaoui Talibi 2018-2019 140

 Appelée aussi région critique, c’est l’ensemble
d’instructions d’un processus (par exemple :
accès à la mémoire ou fichiers partagés)
susceptibles de provoquer les conditions de
concurrence avec d’autres processus.
 Pour éviter les conditions de concurrence il faut
éviter que les processus concernés ne se trouvent
en même temps dans la section critique.

L’Exclusion mutuelle

Pr. M. Alaoui Talibi 2018-2019 141

 L’exclusion mutuelle est une méthode qui permet de
s’assurer que si un processus utilise une variable
ou un fichier partagé, les autres processus seront
exclus de la même activité.

La partie du programme à partir de laquelle on accède à

la mémoire partagée se nomme région critique, ou
section critique.

Si l’on pouvait empêcher que deux processus se trouvent

simultanément dans leurs sections critiques, on éviterait les
conditions de concurrence.

Pr. M. Alaoui Talibi 2018-2019 142

 Quatre conditions sont nécessaires pour éviter les
conditions de concurrence tout en assurant la
coopération et l’utilisation adéquate des ressources
partagées :
 Deux processus ne doivent pas se trouver simultanément
dans leurs sections critiques (exclusion mutuelle)
 Il ne faut pas faire de suppositions quant à la vitesse ou le
nombre de processeur mis en œuvre.
 Aucun processus s’exécutant à l’extérieur de la section
critique ne doit bloquer d’autres processus.
 Aucun processus ne doit attendre indéfiniment pour
pouvoir entrer dans sa section critique.

Le comportement que nous voulons mettre en œuvre est celui

illustré à la figure suivante.
Pr. M. Alaoui Talibi 2018-2019 143
 A entre dans sa A quitte sa
section critique section critique

Processus A

B tente B entre dans B quitte sa

d’entrer dans sa section section
sa section critique critique
critique
Processus B

B est
T T2 bloqué T3 T4
1
temps

2018-2019 144
 Plusieurs manières d’assurer l’exclusion mutuelle

 L’exclusion mutuelle avec attente active

 Le sommeil et l’activation

 Les sémaphores

 …

Pr. M. Alaoui Talibi 2018-2019 145

 Leprincipe est que lorsqu’un processus se trouve
dans sa section critique, les autres processus ne
peuvent pas y entrer, mais restent actifs et
attendent que le processus en cours termine la
région critique.

 Plusieurs techniques sont utilisées

 Désactivation des interruptions
 Variables de verrou
 Alternance stricte
 Solution de Peterson
 Instruction TSL
Pr. M. Alaoui Talibi 2018-2019 146
 Désactivation des interruptions :

 Le processus qui entre dans sa section critique, désactive les interruptions

  Dans ce cas, l’horloge aussi ne pourrait pas envoyer les interruptions, ce qui
implique que le processeur ne pourrait pas basculer vers un autre processus.
 Le processus en cours est sûr maintenant qu’aucun processus concurrent (ou
autre) ne pourra entrer dans la section critique.
 Les autres processus n’ont même pas la possibilité d’avoir le processeur tant que les
interruptions sont désactivées.
 Le processus en cours doit réactiver les interruptions à la fin de la section critique.
 Attention!!
 Donner aux processus utilisateurs de bloquer les interruptions n’est pas une bonne idée
 Un processus (utilisateur) qui termine sa section critique et oublie de réactiver les
interruptions.
 Un processus (utilisateur) qui, volontairement, ne réactive pas les interruptions pour
s’emparer (l’utiliser tout seul) exclusivement du processeur.
 La désactivation des interruptions peut être intéressante pour les processus en
mode noyau (qui n’impose pas des restrictions sur les instructions exécutées).

Pr. M. Alaoui Talibi 2018-2019 147

 Variables verrou : Solution logicielle
 Le processus qui veut exécuter sa section critique, teste une variable
verrou ( ou lock) partagée dont la valeur initiale est 0.
 Si cette variable est à 0, alors il la remet à 1 et entre dans la section critique

 Si le verrou est déjà à 1, ce qui signifie qu’un autre processus se trouve dans la
section critique  le processus doit attendre que le verrou passe à 0
 Le processus remet le verrou à 0 quand il termine la section critique
 Problème :
 La variable verrou est partagée  pour y accéder, les conditions de concurrence

peuvent se produire
 Un processus qui a testé le verrou et le trouve à 0, perd le processeur avant

de remettre le verrou à 1 (un autre processus s’exécute et le fait à sa place).

 Un deuxième processus teste aussi le verrou (toujours à 0) et le remet à 1
ensuite, il entre dans sa section critique.
 Lorsque le premier processus reprend son exécution, il remet le verrou à 1(il est

déjà à 1) et commence sa section critique.

Résultat : les deux processus se trouvent en même temps dans la section

critique!!
Pr. M. Alaoui Talibi 2018-2019 148
 Alternance stricte
 Deux processus alternent strictement leur entrées dans la
section critique
 Entre deux exécutions de la section critique par l’un des
processus, il est impératif que l’autre processus exécute aussi la
section critique.
 Pratique pour représenter le modèle basique de producteur /
consommateur.
 Principe
 Les deux processus inspectent une variable « turn »
 Le processus 1 entre dans sa section critique si turn est à 0.
Sinon, il entre dans une phase d’attente active.
 A l’inverse du processus 1, le processus 2 entre dans sa section
critique si turn est à 1. Sinon il entre dans une phase d’attente.
 Chacun des deux processus alterne la variable turn à la fin de sa
section critique.
 Le processus 1 : 01
 Le processus 2 : 10
Pr. M. Alaoui Talibi 2018-2019 149
 Alternance stricte
 Code d’entrée dans la section critique des deux
processus

Processus 1 Processus 2

Pr. M. Alaoui Talibi 2018-2019 150

 Quatre conditions sont nécessaires pour éviter les
conditions de concurrence tout en assurant la
coopération et l’utilisation adéquate des
ressources partagées :
1. Deux processus ne doivent pas se trouver
simultanément dans leurs sections critiques (exclusion
mutuelle).
2. Pas de suppositions sur la vitesse ou le nombre de
processeur mis en œuvre.
3. Aucun processus s’exécutant à l’extérieur de la section
critique ne doit bloquer d’autres processus
4. Aucun processus ne doit attendre indéfiniment pour
pouvoir entrer dans sa section critique.

Pr. M. Alaoui Talibi 2018-2019 151

 Alternance stricte
 Problème :

 La démarche proposée entre en conflit avec la troisième

condition :

Le processus 1 peut être bloqué par un processus, hors de sa

section critique.

Par exemple, le processus 1 ne serait pas autorisé à imprimer

un autre fichier, car le processus 2 serait occupé à une autre
tache.

Pr. M. Alaoui Talibi 2018-2019 152

 Solution de Peterson
 Combine l’alternance stricte et la variable verrou

 Un processus peut enchaîner deux (ou plusieurs)

exécutions de la section critique, alors que
l’autre processus n’en a pas exécuté une.

 L’algorithme de Peterson, est composé de deux

procédures développées en C ANSI.

Pr. M. Alaoui Talibi 2018-2019 153

 Code de la solution de Peterson :
#define n 2 /*nb de processus*/
int turn; /* à qui le tour */
int interested[n]; /* toute valeur initialement 0 (FALSE)*/
void enter_region (int process) /* Le processus est 0 ou 1*/
{
int other; /* nb des autres processus */
other = 1 – process; /* l’opposé du processus */
interested[process] = TRUE; /* montre que vous êtes intéressés */
turn = process; /* définit l’indicateur */
while(turn == process && interested[other] == TRUE); /* instruction null */
}

void leave_region(int process) /* processus : qui quitte */

{
inerested[process] = FALSE; /* indique départ de la section critique */
}

Pr. M. Alaoui Talibi 2018-2019 154

 Avantd’utiliser les variables partagées, chaque
processus appelle enter_region avec son propre
numéro de processus, 0 ou 1.

 Cet appel le met en attente, jusqu’à ce qu’il entre

 Unefois qu’il a fini avec les variables partagées, le

processus appelle leave_region pour autoriser un
autre processus à entrer.

Pr. M. Alaoui Talibi 2018-2019 155

 Voyons comment fonctionne cette solution :
 1er cas :
 Aucun des processus ne se trouve dans sa section
critique.
 Le processus 0 appelle enter_region.
 Il montre son intérêt en positionnant turn à 0.
 Si le processus 1 est désintéressé, enter_region
retourne immédiatement.
 Si le processus 1 appelle maintenant enter_region,
il attend jusqu’à ce que interested[0] passe à FALSE.
 Ceci ne se produit que si le processus 0 appelle
leave_region.
Pr. M. Alaoui Talibi 2018-2019 156
 2éme cas :

 Les 2 processus appellent enter_region simultanément.

 Ils vont stocker tous les 2 leur numero de processus dans
turn.
 Supposons que le processus 1 soit stocké en dernier : turn
est à 1.
 Lorsque les 2 processus arrivent, le processus 0 entre en
section critique.
 Le processus 1 n’entre pas en section critique tant que le
processus 0 n’a pas quitté la sienne.

Pr. M. Alaoui Talibi 2018-2019 157

 Instruction TSL :

Etudions maintenant une proposition qui sollicite un

peu d’aide de la part du matériel. De nombreux
ordinateurs, et notamment ceux qui ont été conçus
pour accueillir plusieurs processeurs, prennent en
charge l’instruction :

TSL RX, LOCK

Pr. M. Alaoui Talibi 2018-2019 158

 Elle fonctionne de la manière suivante :

Elle lit le contenu du mot mémoire lock dans le

registre RX, puis stocke une valeur différente de 0 à
l’adresse mémoire lock.

Les opérations qui consistent à lire le mot et à y

stocker une valeur sont absolument indivisibles :
aucun autre processeur ne peut accéder à la
mémoire tant que l’instruction n’est pas terminée.

Le processeur exécutant l’instruction TSL verrouille

le bus mémoire pour interdire aux autres processeurs
d’accéder à la mémoire tant qu’il n’a pas terminé.
Pr. M. Alaoui Talibi 2018-2019 159
 DONC, pour exploiter l’instruction TSL, on fait
appel à une variable partagée, lock, afin de
coordonner l’accès à la mémoire partagée.

Lorsque lock est à 0, n’importe quel processus peut

la positionner à 1 via l’instruction TSL, puis lire ou
écrire dans la mémoire partagée. Cela fait, le
processus repositionne lock à 0 à l’aide d’une
instruction move ordinaire.

Mais comment utiliser cette instruction pour

empêcher deux processus d’entrer simultanément
dans leurs sections critiques ?
Pr. M. Alaoui Talibi 2018-2019 160
La solution est illustré dans les sous-programmes
suivants :

Enter_region :
TSL REGISTER, LOCK |copie lock dans le registre et
|la positionne à 1
CMP REGISTER, #0
JNE enter_region
RET

leave_region :
MOV LOCK, #0
RET
Pr. M. Alaoui Talibi 2018-2019 161
 Limitations
 Toutes les solutions de cette catégorie obligent le
processus en attente d’entrer dans sa section critique
à rester actif.
 Le processus s’installe dans une petite boucle en
attendant l’ouverture.

  Cette approche est très consommatrice du temps

processeur.
 Le processus consomme, inutilement, sa part du
processeur.

Pr. M. Alaoui Talibi 2018-2019 162

 Principe :
 Le processus, en attente d’entrer dans sa section critique,
ne doit pas rester actif.
 N’a pas besoin d’avoir la CPU
  Le processus en attente doit se bloquer (s’endormir)
en attendant que le processus en cours le débloque (le
réveille).
 Deux primitives sont utilisées : sleep et wakeup
 Un processus qui n’est pas autorisé à entrer dans la section
critique se bloque (est suspendu de la liste de l’ordonnanceur
) en appelant la primitive sleep.
 A la fin de la section critique, le processus vérifie si un processus
est bloqué, si c’est le cas il le réveille avec la primitive wakeup.
Pr. M. Alaoui Talibi 2018-2019 163
 Producteur/consommateur
 Deux processus se partagent un tampon (buffer) de taille
fixe. Le premier (producteur) écrit des informations dans le
tampon et le deuxième (consommateur) y récupère les
informations.
 Le producteur se bloque quand le tampon devient plein.
 Le consommateur se bloque quand le tampon se vide.
 Principe :
 N étant la taille fixe du tampon
 Les deux processus se partagent une variable « count »
correspondant au nombre d’éléments dans le tampon
 Consommateur
 Si count = 0  le consommateur entre en sommeil
 Si count = N-1  le consommateur réveille le producteur
 Producteur
 Si count = N  le producteur entre en sommeil
 Si count = N-1  le producteur réveille le consommateur

Pr. M. Alaoui Talibi 2018-2019 164

 Producteur/consommateur
 Problème de conditions de concurrence (qu’on risque
de rencontrer)

 Le consommateur lit la valeur de count qui est à 0 et avant de

se mettre en sommeil on lui retire la CPU.
 Le producteur insère un élément dans le tampon et
incrémente count qui passe à 1. Dans ce cas, il tente de
réveiller le consommateur qui ne s’est pas encore endormi.

 Cette tentative sera ignorée

 Le consommateur reprend la CPU et, croyant que la valeur de
count est 0, se met en sommeil  il y restera à jamais.

Pr. M. Alaoui Talibi 2018-2019 165

 Telleétait la situation, en 1965, lorsque E. W.
Dijkstra suggéra d’utiliser un nouveau type de
variable entière qui devait permettre de
décompter le nombre de wakeup enregistrés pour
un usage ultérieur.

 Danssa proposition, il appelait ce nouveau type de

variable un sémaphore.

Pr. M. Alaoui Talibi 2018-2019 166

 Unsémaphore est une variable entière spéciale sur
laquelle on peut exécuter deux opérations : down
et up
 L’opération down teste si le sémaphore est supérieur à
0. Dans ce cas, elle le décrémente et le processus peut
entrer dans la section critique. Si le sémaphore est nul
alors, le processus entre en sommeil.
 L’opération up incrémente le sémaphore.
 Si un processus se trouve en sommeil sur ce sémaphore, alors
il sera réveillé.
 Les opérations de test, de modification du sémaphore
et de mise en sommeil sont indivisibles
 ceci permet d’éviter les conditions de concurrence.
Pr. M. Alaoui Talibi 2018-2019 167
 Résolution du problème du producteur / consommateur
avec les sémaphores :
 Deux processus se partageant un tampon de taille fixe. Le
premier écrit dans le tampon et l’autre y consomme.

 Trois sémaphores sont utilisés dans la solution

 Full : pour compter le nombre d’emplacements pleins dans tampon

 Empty : le nombre d’emplacements vides

 Mutex : pour assurer l’exclusion mutuelle lors de l’accès au tampon

(afin de s’assurer que le producteur et le consommateur n’accèdent
pas simultanément au tampon).

Pr. M. Alaoui Talibi 2018-2019 168

 Dans la figure suivante, le sémaphore mutex est
employé pour l’exclusion mutuelle. Il est conçu
afin de garantir qu’un seul processus à la fois
accédera en lecture et en écriture au tampon et
aux variables associées.

 Cetteexclusion mutuelle est indispensable pour

éviter tout désordre.

Pr. M. Alaoui Talibi 2018-2019 169

  Solution du Producteur/consommateur

#define n 100 /* nb d’emplacements dans le tampon */

Typedef int semaphore ; /* les semaphores sont un type de variable int */
semaphore mutex = 1; /* contrôle l’acces à la section critique */
semaphore empty = n; /* compte les emplacements vides dans le tampon */
semaphore full = 0; /* compte les emplacements pleins */
void producer()
{
int item;
while (TRUE) /* TRUE est la constante 1 */
{
item = produce_item(); /* génère qlq chose à placer dans le tampon */
down(&empty); /* décrèmente le décompte des emplacements vides */
down(&mutex); /* entre en section critique */
insert_item(item); /* place un nouvel élément dans le tampon */
up(&mutex); /* quitte la section critique */
up(&full); /* incrémente le décompte des emplacements pleins */
}
}
Pr. M. Alaoui Talibi 2018-2019 170
void consumer()
{
int item;
while (TRUE) /* boucle sans fin */
{
down(&full); /* décrémente le décompte des emplacements pleins */

down(&mutex); /* entre en section critique */

item = remove_item(); /* prélève un élément dans le tampon */
up(&mutex); /* quitte la section critique */
up(&empty); /* incrémente la décompte des emplacements vides */
consomme_item(item); /* fait quelque chose avec l’élément */
}
}

Pr. M. Alaoui Talibi 2018-2019 171

 les sémaphores servent également à faire de la
synchronisation.

Les sémaphores full et empty sont nécessaires pour garantir

que certaines séquences d’événements se produisent ou ne
se produisent pas.

 Dans ce cas de figure, ils font en sorte que le producteur

cesse de s’exécuter lorsque le tampon est plein, et que le
consommateur cesse de s’exécuter quand il est vide.

 Il s’agit d’un usage différent de celui de l’exclusion

mutuelle.

Pr. M. Alaoui Talibi 2018-2019 172

 Version simplifiée des sémaphores
 Prend en charge particulièrement l’exclusion mutuelle
 Un mutex peut prendre deux valeurs
 1 : déverrouillé
 0 : verrouillé
 Deux fonctions pour la gestion des mutex
 Mutex_lock : invoquée pour pouvoir entrer en section
critique
 Si le mutex est à 1 alors, il passe à 0 et le processus pourrait
entrer en section critique.
 Si le mutex est à 0 alors le processus se bloquerait jusqu’à ce que
le mutex sera débloqué par un autre processus (celui qui exécute
sa section critique)
 Mutex_unlock : remet le mutex à 1 à la fin de la section
critique, et réveille éventuellement un processus bloqué.
Pr. M. Alaoui Talibi 2018-2019 173
 L’usage des sémaphores est relativement complexe et la moindre erreur peut avoir
des conséquences fatales sur le fonctionnement global des processus.
 Exemple : producteur/consommateur
 Que se passe-t-il si, par erreur, l’ordre des deux instructions down dans le producteur a été
inversé?

void producer() void consumer()

{ {
int item; int item;
while (TRUE) while (TRUE)
{ {
item = produce_item(); down(&full);
down(&mutex); down(&mutex);
down(&empty); item = remove_item();
insert_item(item); up(&mutex);
up(&mutex); up(&empty);
up(&full); consomme_item(item);
} }
} }

Pr. M. Alaoui Talibi 2018-2019 174

 Exemple : producteur/consommateur (suite)

 Si mutex = 1 et empty = 0  le producteur va pouvoir

réaliser l’opération down(mutex) ce qui signifie que
le mutex passe à 0. Par contre il se bloquera après
l’opération down(empty).
 Le consommateur sera bloqué sur down(mutex) parce
que le producteur n’a pas encore fait l’opération
up(mutex).
 Le consommateur ne pourra jamais incrémenter la
valeur de empty et le producteur ne pourra jamais
incrémenter la valeur de mutex
Pr. M. Alaoui Talibi 175
  interblocage

  utilisation des primitives de synchronisation de haut

niveau fournies par un langage de programmation :

Moniteurs

Pr. M. Alaoui Talibi 2018-2019 176

 Mettre à la disposition des utilisateurs un moyen de
définir et de spécifier une partie du code
nécessitant l’exclusion mutuelle sans se soucier de
la gestion «complexe » de sémaphores.
 Minimiser le risque d’erreur lors de la gestion des
sémaphores.

 utilisation des primitives de synchronisation de

haut niveau fournies par un langage de
programmation : Moniteurs.

Pr. M. Alaoui Talibi 2018-2019 177

 Un moniteur est un module spécial regroupant des
fonctions, des variables et des structures de
données.
 Les processus peuvent appeler les fonctions du
moniteur, mais ils ne peuvent pas accéder
directement à ses structures internes.
 A un instant donné, un seul processus peut être
actif dans le moniteur.
 Le programmeur n’a pas à se soucier de la
manière d’assurer l’exclusion mutuelle :
 Normalement c’est le compilateur qui s’en charge
Pr. M. Alaoui Talibi 2018-2019 178
 Comment synchroniser deux processus qui
s’exécutent sur deux ordinateurs distincts reliés
par internet ?
 Pas de mémoire partagée pour conserver un
sémaphore.
 Les moniteurs eux aussi se basent sur les sémaphores.
 Les autres techniques vues précédemment nécessitent
une zone mémoire partagée.

 L’échange de message

Pr. M. Alaoui Talibi 2018-2019 179

 Lesprocessus distants peuvent se synchroniser en
échangeant des messages avec deux primitives send
et receive (en général présentes sous forme d’appel
système).

 send(destination, &message)
 Envoie un message vers une destination
 receive(source, &message)
 Reçoit un message d’une source donnée.
 En l’absence du message, le récepteur peut se bloquer jusqu’à
ce que celui-ci arrive.

Pr. M. Alaoui Talibi 2018-2019 180

 Problème de perte de messages
 Utiliser la technique d’acquittement et de duplication
de messages.
 Pour chaque message reçu, on doit envoyer un accusé de
réception.
 Si l’émetteur ne reçoit pas l’accusé de réception, il déduit
que son message est perdu  il réémette le message
 Que se passe-t-il si le message est arrivé mais son
accusé de réception est perdu?
 Le message sera réémis et risque d’être pris en compte deux
fois.
  numéroter les messages
 Si un message arrive deux fois, le récepteur peut se rendre
compte qu’il s’agit d’un doublon et l’ignorer.

Pr. M. Alaoui Talibi 2018-2019 181

 Moyen de synchroniser un groupe de processus au
début de chaque « phase »

 Tous les processus doivent arriver à un seuil

(barrière) avant que chacun d’eux ne puisse
poursuivre son exécution
 Point de rencontre

 Attendre le dernier

Pr. M. Alaoui Talibi 2018-2019 182

 A A A

B B B
barrière

barrière

barrière
C C C

D D D

temps
Les processus A, B, C et D doivent tous atteindre la
barrière avant que le groupe puisse poursuivre la suite
de l’exécution

Pr. M. Alaoui Talibi 2018-2019 183

 Classification des
Architectures parallèles

Pr. M. Alaoui Talibi 184

 Dans ce chapitre, nous passons en revue les divers
concepts sous-jacents aux architectures parallèles.
 La distinction entre les architectures synchrones et
asynchrones conduit à une classification qui va :

 Des pipelines,
 Des processeurs vectoriels,
 Des machines SIMD,

 Aux machines MIMD à mémoire partagée et

 Aux réseaux de processeurs.

Pr. M. Alaoui Talibi 185
 Nous définissons deux modèles théoriques importants
pour les études de complexité algorithmique :

 Les PRAM
 Et les circuits booléens et arithmétique

 Nous présentons enfin, les mesures de performances

des ordinateurs parallèles.

Pr. M. Alaoui Talibi 186

1. Présentation informelle des ordinateurs parallèles:

La notion de parallélismes recouvre de nombreux

concepts, allant :

- de la manipulation des bits

à
- Un niveau plus grossier (découpage d’un programme
en procédures complexes indépendantes ).

Pr. M. Alaoui Talibi 187

 Plusieurs classifications ont été proposées dans la
littérature. La plus populaire celle de Flynn.

 Ellesest basée sur le type d’organisation des flots

de données et des flots d’instructions.

Pr. M. Alaoui Talibi 188

 Cependant, cette classification, ne permet pas de
tenir compte de beaucoup de facteurs tels que :

- Le mode de fonctionnement des processeurs,

- L’organisation de la mémoire ou encore

- La granularité des processeurs (taille des éléments

logiques de base des processeurs).

Pr. M. Alaoui Talibi 189

 On peut dégager trois grandes classes de machines
parallèles :

 Les machines généralistes à mémoire partagée.

 Les réseaux de processeurs asynchrones à mémoire

Distribuée.

 Les machines distribuées synchrones massivement

parallèles (machines généralistes ou spécialisées).

Pr. M. Alaoui Talibi 190

Problèmes :

 L’augmentation du nombre des processeurs modifie

énormément la structure de base de l’ordinateur.

 Les problèmes d’accès mémoire deviennent cruciaux

pour pouvoir acheminer des données au rythme du
traitement des processeurs.

 De même, les problèmes de communication entre

processeurs sont importants.

Pr. M. Alaoui Talibi 191

 Denombreuses solutions ont été proposées à ces
problèmes et plusieurs architectures ont vu le jour.

 La plus simple, et la plus utilisée est celle de Flynn.

 Celle-ci,
a pour critère de sélection :
le mode de contrôle des suites d’opérations
élémentaires effectuées par les différents processeurs.

 Leprocessus essentiel dans un ordinateur est

l’exécution d’une suite d’instructions sur un
ensemble de données. Pr. M. Alaoui Talibi 192
 En général, les ordinateurs peuvent être classifiées
selon la multiplicité des flots d’instructions et de
données disponibles matériellement.

 En conservant les initiales anglaises consacrées par

l’usage, on obtient essentiellement les architectures
suivantes :
- SIMD : un seul flot d’instructions, plusieurs flots de
données.(single instruction multiple data)
- SPMD : chaque processeur dispose du même
programme.(single program multiple data)
Pr. M. Alaoui Talibi 193
 MISD : plusieurs instructions successives traitent la
même donnée.
 MIMD : plusieurs flots d’instructions et de données.

 Un flot d’instructions est une suite d’instructions

issues d’une partie contrôle en direction d’un ou
plusieurs processeurs.

 Un flot de données est une suite de données venant

d’une zone mémoire en direction d’un processeur ou
venant d’un processeur en direction d’une zone
mémoire.
Pr. M. Alaoui Talibi 194
 Principe de l’ordinateur séquentiel :
Les instructions sont exécutées séquentiellement
mais peuvent être pipelinées.

Figure.
Architecture
synchrone

Pr. M. Alaoui Talibi 195

 En microarchitecture,

Un pipeline (ou chaîne de traitement1),

est l'élément d'un processeur dans lequel
l'exécution des instructions est découpée
en plusieurs étapes.

Pr. M. Alaoui Talibi 196

Architectures pipeline et vectorielle :
Le principe des architectures pipelines est le suivant :

 Ondivise l’opération à effectuer en étapes de

durées égales qui s’exécutent successivement.

 Lesentrées d’une étape sont constituées par les

sorties de l’étape précédente.

 Lepipeline est une unité matérielle qui reproduit

cette division.
Pr. M. Alaoui Talibi 197
 Ilest donc composé d’étages séparés par des
registres nécessaires au stockage des données
intermédiaires.

 Au sens de la classification de Flynn, ces architectures

révèlent du mode MISD.

 Eneffet, une même donnée est traitée par un flot

multiple d’instructions élémentaires successives.

Pr. M. Alaoui Talibi 198

 Architecture vectoriel :
 Un vecteur est un ensemble ordonnée de n éléments.

 Chaque élément est un scalaire, nombre réel

flottant, entier, booléen ou caractère.

 Un processeur vectoriel est une unité permettant

de traiter des vecteurs.

 Ilest constitué de registres de stockage et d’une

ou plusieurs unités pipelines.

Pr. M. Alaoui Talibi 199

Architecture SIMD :
 Plusieurs unités de traitement sont supervisées par
la même unité de contrôle.

 Toutes les unités de traitement reçoivent la même

instruction ( ou le même programme, auquel cas
on parle d’une structure SPMD ) diffusée par
l’unité de contrôle,

Mais opèrent sur des ensembles de données

distincts, provenant de flots de données distincts.
Pr. M. Alaoui Talibi 200
Figure : Structure SIMD

Pr. M. Alaoui Talibi 201

 Chaque unité de traitement exécutant la même
instruction au même instant, on obtient un
fonctionnement synchrone des processeurs.

 la mémoire partagée peut être subdivisée en

plusieurs modules.

 Dans ce cas, l’accès des unités de traitement aux

différents modules se fait par un réseau
d’interconnexion que nous étudierons après.

Pr. M. Alaoui Talibi 202

 Un calculateur SIMD peut être considéré comme un
monoprocesseur exécutant des instructions sur des
tranches de plusieurs éléments.

 Ilest donc particulièrement bien adapté aux

traitements d’opérations vectorielles.

Pr. M. Alaoui Talibi 203

 Par exemple, les ordinateurs :

- ILLIAC IV
- BSP
- STARAN
- MPP
- Et plus récemment les DAP de AMT

Par contre, OPSILA ou les hypercubes FPS de la série T sont

des machines SIMD/SPMD.

 Notons que la plupart des machines actuelles MIMD peuvent

s’utiliser en mode SPMD.

Pr. M. Alaoui Talibi 204

 Parallélisme partagé :

Les premiers ordinateurs parallèles à avoir

effectivement connu un succès industriel sont les
machines à mémoire partagée.

Considérons p processeurs vectoriels reliés à une grande

Mémoire commune.

Le fonctionnement des processeurs s’effectue en mode

MIMD.
Pr. M. Alaoui Talibi 205
 Càdchaque processeur peut évoluer indépendamment
des autres.

 Leséchanges d’informations entre les processeurs se

font par l’intermédiaire de la mémoire.

 Lesmachines appartenant à cette classe possèdent

un nombre relativement faible des processeurs (une
dizaine), mais chacun assez puissant.

 Ladiminution des temps d’exécution n’est pas le seul

but que les utilisateurs (constructeurs) recherchent.
Pr. M. Alaoui Talibi 206
 Ils voudraient aussi disposer de plus en plus de
mémoire pour pouvoir traiter des problèmes
toujours plus grands.

 Or, l’accès à des mémoires de grandes dimensions

est lent.

 Comme la vitesse de base des unités de traitement

augmente sans cesse, il faut organiser les mémoires
de telle sorte que l’accès soit rapide.

Pr. M. Alaoui Talibi 207

Figure. Structure MIMD
Pr. M. Alaoui Talibi 208
 La grande mémoire est divisée en modules distincts
possédant chacun son propre canal d’entrées-sorties
(les bancs mémoire).

 Ces bancs sont reliées aux processeurs par

l’intermédiaire de bus ou d’un réseau
d’interconnexion.

 la différence entre le SIMD et le MIMD, est que pour

le dernier, chaque processeur possède sa propre
unité de contrôle.
Pr. M. Alaoui Talibi 209
 Lesprocesseurs ont donc un fonctionnement
indépendant : en particulier asynchrone, et
exécutant des programmes différents.

Pr. M. Alaoui Talibi 210

 Architectures MIMD distribuées :

Les difficultés d’accès à la mémoire limitent le

nombre de processeurs :

au-delà de quelques dizaines

de processeurs, les performances du réseau
d’interconnexion se dégradent.

Pr. M. Alaoui Talibi 211

 Chaque processeur doit disposer d’une mémoire
locale à accès rapide et n’est connecté qu’a un
certain nombre de processeurs voisins.

 nous avons deux modèles :

1.
 Les processeurs travaillent en partageant des
données de la mémoire commune.
 Chaque processeur lit en mémoire les données dont
il a besoin, effectue son traitement, puis écris les
résultats en mémoire.
Pr. M. Alaoui Talibi 212
2.
 Les processeurs travaillent en échangeant des
messages.

 Chaque processeur lit sur un ou plusieurs canaux de

communications les données dont il a besoin en
provenance d’autres processeurs, effectue son
traitement, puis transfère les résultats en direction
des processeurs qui les demandent.

Pr. M. Alaoui Talibi 213

 Cherchent à exploiter au maximum le parallélisme
d’un algorithme en s’affranchissant des contraintes
liées à l’ordre d’exécution des instructions.

 Le principe de base est d’autoriser l’exécution

d’une instruction dés que ses opérandes sont
disponibles.

 Le début d’une instruction ne dépend alors que de

la disponibilité des données et non pas de sa
position dans le programme.
Pr. M. Alaoui Talibi 214
 Explication
: L’exécution du programme est liée
aux contraintes de dépendance entre données.

Pr. M. Alaoui Talibi 215

 Elle comporte :
 Une unité mémoire contenant les opérandes et les
instructions non actives,

 Une unité de recherche des instructions actives

 Une file des instructions actives en attente d’exécution.

 Une unité de traitement avec plusieurs processeurs,

 Une unité de mise à jour dont le rôle est d’affecter

leurs valeurs aux opérandes à l’issue du traitement.
Pr. M. Alaoui Talibi 216
Pr. M. Alaoui Talibi 217
 Présentation générale :

L’étude de la complexité algorithmique parallèle nécessite

que soit défini un modèle de calcul, que nous appelons un
modèle de machines, pour exécuter des algorithmes.

 Cependant, de nombreux modèles existent pour les

ordinateurs parallèles.

 Suivant le modèle utilisé, Il existe des notions différentes

de complexité algorithmique.

Pr. M. Alaoui Talibi 218

 Dans ce paragraphe, nous allons étudier deux
d’entre eux :

 les PRAM, Parallel Random Access Machines,

 Et les circuits booléens et arithmétiques.

Pr. M. Alaoui Talibi 219

 Thèse du calcul parallèle :

Se fonde sur l’idée intuitive d’une relation entre le

temps de calcul des machines parallèles et l’espace
de calcul (taille de la mémoire) des machines
séquentielles.

Tout problème qui peut être résolu sur un ordinateur

séquentiel (raisonnable) en utilisant un espace de
taille mémoire (polynomiale) peut être résolu en temps
Polynomial sur un ordinateur parallèle (raisonnable)
et vice versa.
Pr. M. Alaoui Talibi 220
Définir des ordinateurs raisonnables, aussi bien séquentiel que
parallèle n‘est pas une tache simple.

Un consensus s’est établi entre théoriciens qui repose sur la

« thèse de l’invariance ».

 Thèse d’invariance :

Des machines raisonnables peuvent se simuler entre elles avec

au plus un accroissement polynomial en temps et une
multiplication constante de l’espace.

Pr. M. Alaoui Talibi 221

 Le modèle PRAM :

Un Parallel Random Access Machine PRAM est un

ensemble de processeurs séquentiels indépendants,
des RAM, qui possèdent donc chacun une mémoire
privée (ou locale) et qui communiquent entre eux en
utilisant une mémoire globale qu’ils se partagent.

Pr. M. Alaoui Talibi 222

 Opérations fondamentales :

Considérons une PRAM composée de :

p processeurs numérotées de P0 à Pp-1

m positions mémoires M0 à Mm-1

Chaque processeur peut effectuer des opérations

atomiques, en une unité de temps :
Lire(Mi)
Ecrire(Mi)
Calculer(f)
Pr. M. Alaoui Talibi 223
 Toutes
ces opérations atomiques s’effectuent de
manière synchrone,

 Autrement dit, au même instant, tous les processeurs

lisent, écrivent et calculent.

 Extensions :

Le modèle PRAM doit être modifié pour prendre en

compte les accès mémoire dans le cas d’une mémoire
distribuée.
Pr. M. Alaoui Talibi 224
 Définition:
Une DRAM ( Distributed RAM ) est un ensemble de p
processeurs Pi, de p zones mémoires Mi et d’une
famille de couples X=(i,j).

Nous noterons Xi l’ensemble des couples (i,.).

Le processeur Pi ne peut accéder qu’aux zones

mémoire Mj quel que soit j appartenant à Xi.

X est le réseau d’interconnexion de la DRAM.

Pr. M. Alaoui Talibi 225
 Pour lire une donnée située dans une case mémoire
à laquelle il n’est pas directement connecté :

Un processeur doit donc obtenir l’aide d’autres

processeurs qui, en lisant et en écrivant, déplaceront
la donnée de la case mémoire initiale à une case
accessible par le processeur intéressé.

Pr. M. Alaoui Talibi 226

 Le facteur d’accélération :

Considérons un algorithme qui s’exécute sur un

ordinateur parallèle comportant p processeurs
(identiques) en un temps tp, et soit t1 son temps
d’exécution séquentiel (sur un ordinateur avec un
seul processeur).
On définit le facteur d’accélération par le rapport :

Sp = t1/tp

Théorème : quel que soit p, 1 ≤ Sp ≤ p (A démontrer).

Pr. M. Alaoui Talibi 227
 Limitations du facteur d’accélération :

Divers auteurs ont essayé de préciser les bornes du

facteur d’accélération suivant l’architecture (à
chercher):

 Loi d’Amdahl
 Loi de Minsky
 Table de Stone

Pr. M. Alaoui Talibi 228

 Dansce chapitre, nous introduisons les principales
notions de complexité parallèle.

 Lemodèle utilisé est principalement le modèle PRAM

et ses dérivées.

 Nousétudions la complexité parallèle de plusieurs

algorithmes de base.

Pr. M. Alaoui Talibi 229

 Description des hypothèses :
 La structure de l’ordinateur est de type SIMD ou
MIMD avec une mémoire commune partagée.

 Nous supposerons que notre modèle peut admettre

un nombre illimité de processeurs.

 L’unité de base est le temps d’exécution d’une

opération arithmétique

 Nous négligeons les temps de communication entre

la mémoire et les processeurs.
Pr. M. Alaoui Talibi 230
 Objectifs de l’étude de la complexité parallèle :

 Il s’agira de trouver dans l’algorithme les opérations

susceptibles d’être exécutées simultanément.

 Considérons un problème donné : calcul du produit

scalaire de deux vecteurs de taille n.

 Une question classique : chercher la complexité

séquentielle de ce problème.

 Càd le temps de calcul minimum pour résoudre le

problème.
Pr. M. Alaoui Talibi 231
 On procède généralement en deux étapes :

 Recherche d’une borne inferieur.

 Ensuite, construction d’un algorithme séquentiel

dont le temps d’exécution est égal à cette borne.

Un tel algorithme est dit optimal

Pr. M. Alaoui Talibi 232

 Lesalgorithmes que nous étudierons s’exécutant
en un nombre fini d’opérations,

 2n-1 (nb d’opérations) pour le cas du produit scalaire,

 Cecirevient à supposer que le nombre de processeurs

est égal à ce nombre d’opérations.

Pr. M. Alaoui Talibi 233

 Evaluation d’une expression arithmétique :

Dans une première partie, nous étudions les relations

entre algorithmes d’évaluation d’une expression et
arbres binaires étiquetés.

Définition :
1. Une expression de taille n est un problème
possédant n données (variables ou atomes) et
fournissant un seul résultat, et dont toutes les
opérations sont binaires.
Pr. M. Alaoui Talibi 234
 L’expression est simple si chacune des variables
n’est utilisée qu’une seule fois comme opérande.

 E est une expression simple si E satisfait une des

conditions suivantes :

1. E = xi où xi est une variable

2. E = o G où G est une expression simple et où o
appartient {+,-}.
3. E = G o D où G et D sont des expressions simples
portant sur des ensembles de variables disjoints
et où o appartient à {+,-,*,/}.
Exemple.
Pr. M. Alaoui Talibi 235
 Nousdéfinissons maintenant les arbres binaires
étiquetés.

 Ladéfinition dépend d’un entier p qui représente

le nombre de processeurs.

 L’arbre
étiqueté conduit à un algorithme d’évaluation
avec p processeurs : chaque nœud représente une
opération et l’étiquette du nœud la date d’exécution
de cette opération.

Pr. M. Alaoui Talibi 236

 Définition :

Soit p un entier positif. Nous appelons A(p) l’ensemble des

arbres binaires étiquetés construits de la manière suivante :

1. l’arbre avec un seul nœud étiqueté 0 appartient à A(p) et

a une profondeur égale à 0.

2. Pour d≥0, un élément de A(p) de profondeur d+1 est

obtenu à partir d’un élément de A(p) de profondeur d en
ajoutant 1 à toutes les étiquettes et en remplaçant au plus
p de ses feuilles par l’arbre binaire à trois sommets dont
les feuilles sont étiquetées 0 et la racine 1.

Pr. M. Alaoui Talibi 237

 L’arbrebinaire à trois sommets dont les feuilles
sont étiquetées 0 et la racine 1 est appelé arbre de
base.

Exemple : prenons p=3;

Pr. M. Alaoui Talibi 238

 Relationsentre évaluation des expressions et arbres
binaires étiquetés :

Lemme :
1. Tout algorithme parallèle d’évaluation d’une
expression de taille n avec p processeurs peut être
représenté par un élément de A(p) admettant au
moins n feuilles.

Pr. M. Alaoui Talibi 239

2. Toute expression simple de taille n peut être
représentée par un élément de A(p) possédant n feuilles.
Cet arbre détermine un algorithme parallèle d’évaluation
de l’expression avec p processeurs.

 Pour tout arbre de A(p), de profondeur d et possédant n

feuilles, il existe une expression simple de taille n et un
algorithme parallèle d’évaluation de cette expression,
représenté par cet arbre.
Exemple1
Exemple2

Pr. M. Alaoui Talibi 240

Stratégies de conception
d'algorithmes parallèles :

Pr. M. Alaoui Talibi 241

 Le but est de :
 résoudre plus rapidement un problème donné ;
 résoudre un problème plus gros pour une même
durée de calcul.

Elle concerne :

 le calcul scientifique en cherchant à modéliser

et à simuler des phénomènes naturels, et les grands
défis :

 Réchauffement climatique, un nouveau médicament...

Pr. M. Alaoui Talibi 242
 La cosmologie, l’imagerie médicale, la prédiction
des tremblements de terre, le climat.

Ces programmes sont exécutés sur des architectures

parallèles avec souvent autant de processus que de
processeurs.

Pr. M. Alaoui Talibi 243

 On distingue deux grandes classes de programmes
parallèle :

 Parallélisme de données : chaque processeur

réalise un même traitement sur une partie des
données ;

 Parallélisme de contrôle : chaque processeur

réalise un traitement différent.

Pr. M. Alaoui Talibi 244

 Les différents processus d'une même application
ont besoin :

 d'interagir entre eux,

 de communiquer,
 de se synchroniser,

et suivant leur localisation entre les différents

processeurs :

Pr. M. Alaoui Talibi 245

 En multi-programmation : utilisation de variable
partagée ;

 En distribué : échange de message

 En parallèle : soit l'un, soit l'autre, soit les deux en

fonction du matériel utilisé.

Pr. M. Alaoui Talibi 246

 Parallélisme itératif :

 Il est utilisé lorsque le programme est décomposé en

différents processus souvent identiques,

 Chacun contenant une ou plusieurs boucles.

 Ces processus travaillent ensemble pour résoudre un

seul problème.

 Ils communiquent et se synchronisent par variables

partagées et envoi de messages.

Essentiellement : du calcul scientifique exécuté sur

plusieurs processeurs.
Pr. M. Alaoui Talibi 247
 Parallélisme de récursion :

Il peut être utilisé lorsque il existe une ou plusieurs

procédures récursives et que ces appels sont
indépendants entre eux.

Pr. M. Alaoui Talibi 248

La récursion est utilisée pour résoudre des problèmes
combinatoires : tri, ordonnancement (problème du
voyageur de commerce), jeu (échec).

Pr. M. Alaoui Talibi 249

 Producteur/Consommateur :

Ce sont des processus communiquants qui sont

souvent organisés en pipeline à travers lequel les
données circulent.

Chaque processus est un filtre qui utilise la sortie

de son prédecesseur et produit la sortie pour son
successeur.

Cette forme de pipeline est utilisée au niveau de l'OS

pour un shell Unix, par exemple.
Pr. M. Alaoui Talibi 250
 Client/Serveur : c'est le modèle dominant qui
s'applique du réseau local au réseau global.

Un client fait appel à un service et attend la réponse.

Un serveur attend une requête et travaille à la réception.

Un serveur peut être implémenté par :

 un seul processus gérant un client à la fois,
 ou bien comme un multi-programme (plusieurs
processus) pour traiter simultanément les requêtes de
plusieurs clients.
Pr. M. Alaoui Talibi 251
Lorsque client et serveur sont sur des machines
différentes :

il est nécessaire d'utiliser la notion de

rendez-vous et d'appel à distance.

Ce schéma peut être facilement automatisé, mais il

faut faire attention à son efficacité.

Pr. M. Alaoui Talibi 252

 Modèle Map/Reduce :

Pr. M. Alaoui Talibi 253

 Modèle Map/Reduce :

 Est un paradigme dédié pour exécuter un problème

large et complexe d’une manière distribuée.

 Les programmes adoptant ce modèle sont

automatiquement parallélisés et exécutés sur
des clusters (grappes) d’ordinateurs.
Fonctionnement de MapReduce :

Un programme MapReduce se compose des trois parties

suivantes :
 Le driver, qui s’exécute sur une machine client,
est responsable :
 d’initialiserle job
 puis de le soumettre pour exécution.
 Le mapper est responsable :
 de lire les données stockées sur disque
 et les traiter.
 Le reducer est responsable de :
 consolider les résultats issus du mapper
 puis de les écrire sur disque.
Pr. M. Alaoui Talibi 255
 Unebonne compréhension de MapReduce implique
la maitrise du fonctionnement de Hadoop et HDFS.

Pour cela, ces deux notions sont obligatoires pour

mieux appréhender la suite.

 Fonctionnement de Hadoop
 Fonctionnement de HDFS

Pr. M. Alaoui Talibi 256

 Hadoop :

 est une plateforme « framework » open source.

 destiné aux traitements distribués des données

massives de l’ordre de plusieurs pétaoctets.

 Elle permet de faciliter la création d’applications

distribuées.

 Est un environnement Big Data typique.

 L’écosystème Hadoop est un :

 produit de la fondation Apache basé pour sa

création sur le langage java.

 Hadoop se positionne aujourd’hui avec plus de

42000 nœuds chez Yahoo.

 Plusieurs fondations mondiales utilisent Hadoop tel

que : Ebay, Facebook, Amazon, Google, Microsoft,
LinkedIn, Twitter…
 Avantages de Hadoop :

 Parallélisme des données:

un même traitement et calcul peut être effectué
sur toutes les données.

 Performance :
Hadoop délivre à travers le critère de parallélisme
un support de traitement de grands volumes de
données et d’énormes data sets.
 Avantages de Hadoop :

 Économie : les coûts lors de l’utilisation de

Hadoop sont mieux contrôlés grâce à l’utilisation
de matériel de calcul de type standard.
 Le fonctionnement de Hadoop repose sur :

 HDFS (Hadoop Distributed File System) :

 Est un système de fichiers distribués de Hadoop

 Destiné pour le stockage distribué des données.
 Ce composant est distribué,
 tolérant aux pannes,
 portable,
 et également extensible.
 L’interet de MapReduce est de simplifier la vie du
programmeur, en lui masquant le fonctionnement
interne de Hadoop (parallélisation , tolérance aux
pannes,…etc).

 Ainsi, le modèle de programmation permet au

développeur de ne s’intéresser qu’à la partie
algorithmique.

 Il transmet alors son programme MapReduce développé

dans un langage de programmation au framework
Hadoop pour l’exécution.

Pr. M. Alaoui Talibi 262

Exemples de langages de programmation
paralléle:

Ruby/PRuby, C/OpenMP, C++/Threading

Building Blocks, C/OpenCL, C/MPI, Python.

Pr. M. Alaoui Talibi 263

Programmation parallèle en

mémoire distribué

Message Passing Interface

(MPI)

Pr. M. Alaoui Talibi 264

 le modèle pour les machines parallèles à mémoire
distribuée :

Comment avoir la parallélisation explicite ?

 L’utilisateur doit coder le parallélisme dans son

programme.

 AFIN DE exprimer :
 le rôle de chaque processeur dans les phases de
lecture ou
 de lecture/écriture de données distribuées.
Pr. M. Alaoui Talibi 265
Pr. M. Alaoui Talibi 266
 Asynchrone ou faiblement synchrone :

 Il est adapté pour des programmes asynchrones :

 Tous les processeurs effectuent des tâches

concurrentes sans s’occuper des autres participants.

 ou faiblement synchrones

 Les étapes de lecture/écriture des données

synchronisent les processeurs
 mais les tâches s’effectuent de manière asynchrone.
Pr. M. Alaoui Talibi 267
 Remarque :

 Les programmes respectent l’approche SPMD

(Single Program Multiple Data)

 où le plus grand nombre de processeurs effectuent

les mêmes tâches sur des données différentes.

 Seuls quelques processeurs peuvent effectuer des

tâches différentes.

Pr. M. Alaoui Talibi 268

 Les opérations Send/Receive :

 Les opérations de lecture/écriture nécessitent un moyen de

partager des données distribuées.

 La base de ce modèle de programmation s’appuie sur les

opérations élémentaires :

 d’envoi de messages :

send(void *sendbuf, int size, int dest)

 de réception de messages :

receive(void *recvbuf, int size, int source)

Pr. M. Alaoui Talibi 269

 La garantie des données :

Le processeur P1 reçoit 0 ou 100 ?

Pr. M. Alaoui Talibi 270

 Caractéristiques :

 Négociation entre l’émetteur et le récepteur avant la

transmission.

 Reprise des tâches à la fin de la transmission (fin envoi

/ fin réception).

 Les inconvénients :

 Un taux d’attente important pour l’émetteur ou le

récepteur.

 Des situations d’interblocage entre processus.

Pr. M. Alaoui Talibi 271
 Caractéristiques :

 L’émetteur et le récepteur disposent d’un buffer pour

stocker le message.

 Une opération send est décomposée en :

1- une bufferisation du message à transmettre (les données

peuvent être modifiées sans altérer la transmission).

2- un envoi du buffer de manière asynchrone ou non selon

le mode de communication sous jacent.
Pr. M. Alaoui Talibi 272
3- Une opération receive ne copie pas directement
le message mais utilise également une bufferisation
et :

 elle vérifie si le buffer contient le message à lire.

 ou attend jusqu’à réception du message dans ce

buffer.

Pr. M. Alaoui Talibi 273

 Avantages/Inconvénients :

 La bufferisation peut régler des temps d’attente et

certains interblocages.

 Si la taille des buffers n’est pas suffisante, des

coûts supplémentaires d’attente vont diminuer les
performances.

Si le programme est très synchrone :

- les opérations lecture/écriture ont lieu au même moment et
- On peut se passer du coût de la bufferisation.
Pr. M. Alaoui Talibi 274
 Introduction :

1. Concepts de l’échange de Messages

2. Mémoire distribuée
3. Historique

Pr. M. Alaoui Talibi 275

 Parallélisme :

L’intérêt de faire de la programmation parallèle est :

 De réduire le temps d’exécution;

 D’effectuer de plus gros calculs;
 D’exploiter le parallélisme des processeurs modernes
(multi-coeurs, multithreading).

Mais pour travailler à plusieurs, la coordination est

nécessaire.

Pr. M. Alaoui Talibi 276

MPI est une bibliothèque permettant de
Coordonner des processus en utilisant le
Paradigme de l’échange de messages.

Pr. M. Alaoui Talibi 277

 Les implémentations de MPI sont fournies sous
forme de bibliothèques libres ou commerciales.

 Les deux principales: MPICH2, OpenMPI.

 Langage supportés: C/C++, Fortran, python, java,

perl ....

Pr. M. Alaoui Talibi 278

 l’environnement d’exécution
 les communications point à point (Send, Recv)
 les communications collectives (Bcast, Reduce,
Scatter,...).
 les groupes de processus et les communicateurs.
 la topologie d’inter-connexion des processus
(grilles, arbres,...).
 des types de données dérivés.
 etc

Pr. M. Alaoui Talibi 279

 Distributions :

[Link]
[Link]

Documents, Forums et tutoriaux :

[Link]
[Link]
[Link]
[Link]
[Link]
Pr. M. Alaoui Talibi 280
 Concepts de l’échange des messages :

Modèle de programmation séquentiel :

 le programme est exécuté par un et un seul processus;

 Toutes les variables et constantes du programme sont

allouées dans la mémoire allouée au processus;

 Un processus s’exécute sur un processeur physique

de la machine.

Pr. M. Alaoui Talibi 281

 Concepts de l’échange de messages :

Modèle de programmation séquentiel

Pr. M. Alaoui Talibi 282

 Concepts de l’échange de messages :
 Modèle de programmation par échange de messages

 Le programme est écrit dans un langage classique

(Fortran, C, C++, etc.);

 Toutes les variables du programme sont privées et

résident dans la mémoire locale allouée à chaque
processus;

 Chaque processus exécute éventuellement des

parties différentes d’un programme;
Pr. M. Alaoui Talibi 283
 Concepts de l’échange de messages :

 Une donnée est échangée entre deux ou plusieurs

processus via un appel, dans le programme, à des
sous-programmes particuliers.

Modèle de programmation par échange de messages

Pr. M. Alaoui Talibi 284
 Concepts de l’échange de messages :

Si un message est envoyé à un processus, celui-ci doit

ensuite le recevoir.

Échange d’un message

Pr. M. Alaoui Talibi 285

 Concepts de l’échange de messages :

Constitution d’un message

 Unmessage est constitué de paquets de données

transitant du processus émetteur au(x) processus
récepteur(s).

 Enplus des données (variables scalaires, tableaux,

etc.) à transmettre, un message doit contenir les
informations suivantes :

Pr. M. Alaoui Talibi 286

 Concepts de l’échange de messages :

 l’identificateur du processus émetteur;

 le type de la donnée;

 sa longueur;

 l’identificateur du processus récepteur.

Pr. M. Alaoui Talibi 287

 Concepts de l’échange de messages :

Constitution d’un message

Pr. M. Alaoui Talibi 288

 Concepts de l’échange de messages :

Environnement :

 Les messages échangés sont interprétés et gérés

par un environnement qui peut être comparé à la
téléphonie, à la télécopie, au courrier postal, à la
messagerie électronique, etc.

 Le message est envoyé à une adresse déterminée.

Pr. M. Alaoui Talibi 289

 Concepts de l’échange de messages :

Environnement :

 Le processus récepteur doit pouvoir classer et

interpréter les messages qui lui ont été adressés.

 L’environnement en question est MPI (Message

Passing Interface).

Pr. M. Alaoui Talibi 290

 Concepts de l’échange de messages :

Environnement :

 Une application MPI est un ensemble de processus

autonomes.

 Exécutant chacun leur propre code.

 et communiquant via des appels à des sous-programmes

de la bibliothèque MPI.
Pr. M. Alaoui Talibi 291
Mémoire distribuée :

Architecture des supercalculateurs :

 La plupart des supercalculateurs (clusters) sont des

machines à mémoire distribuée.

 Ils sont composés d’un ensemble de nœud,

 À l’intérieur d’un nœud la mémoire est partagée.

 Cluster : ensemble logique de ressources ( processeurs, mémoire, disques,
matériels réseaux, etc... ) généralement distribuées sur plusieurs machines
(noeuds).
Pr. M. Alaoui Talibi 292
Mémoire distribuée :

Architecture des supercalculateurs

Pr. M. Alaoui Talibi 293

Ada :

 332 nœuds de calcul.

 4 processeurs Intel SandyBridge
(8-cœurs) à 2,7 GHz par nœud.
 10 624 cœurs.
 192 Tflop/s (linpack)(nb d’opérations par seconde).
 (flop : unité de mesure de vitesse de calcul)
 LINPACK (puissance) : Un des tests de performance les plus communs employés
pour mesurer le nombre de FLOPS.

 244 kWatt.
 786 MFLOPS/watt.
 Mflops/watt : mesure la puissance de calcul délivrée par un ordinateur pour
chaque watt consommé. Pr. M. Alaoui Talibi 294
 Turing :

 6 144 nœuds
 16 processeurs POWER A2 à 1,6 GHz par nœud
 98 304 cœurs
 393 216 cœurs logiques
 96 Tio ( 16 Go par nœud)
 1 073 Tflop/s (linpack)
 493 kWatt
 2 176 MFLOPS/watt

Pr. M. Alaoui Talibi 295

 Les
cœurs physiques sont le nombre de cœurs
physiques, les composants matériels réels.

 Lescœurs logiques sont le nombre de cœurs

physiques multiplié par le nombre de threads
pouvant s’executer sur chaque cœur
grâce à l’utilisation de l’hyperthreading.

 Parexemple, mon processeur à 4 cœurs execute

deux threads par cœur. J’ai donc 8 processeurs
logiques.

Pr. M. Alaoui Talibi 296

Mémoire distribuée :

OpenMP utilise un schéma à mémoire partagée,

tandis que

pour MPI la mémoire est distribuée.

Pr. M. Alaoui Talibi 297

Pr. M. Alaoui Talibi 298
Mémoire distribuée :

 Un schéma que l’on rencontre très souvent avec

MPI est la décomposition de domaine.

 Chaque processus possède une partie du domaine

global,

 et effectue principalement des échanges avec ses

processus voisins.

Pr. M. Alaoui Talibi 299

Pr. M. Alaoui Talibi 300
Introduction
Historique :
 Version 1.0 : en juin 1994, le forum MPI (Message Passing Interface
Forum), avec la participation d’une quarantaine d’organisations, aboutit à
la définition d’un ensemble de sous-programmes concernant la
bibliothèque d’échanges de messages MPI.

 Version 1.1 : juin 1995, avec seulement des changements mineurs

 Version 1.2 : en 1997, avec des changements mineurs pour une meilleure
cohérence des dénominations de certains sous-programmes

 Version 1.3 : Mai 1997, avec des clarifications dans MPI 1.2, en
fonction des clarifications elles-mêmes apportées par MPI-2.1

 Version 2.0 : apparue en juillet 1997, cette version apportait des

compléments importants volontairement non intégrés dans MPI 1.0
(gestion dynamique de processus, copies mémoire à mémoire, entrées-
sorties parallèles, etc.).
Pr. M. Alaoui Talibi 301
 Version 2.1 : juin 2008, avec seulement des
clarifications dans MPI 2.0 mais aucun changement.

 Version 2.2 : septembre 2009, avec seulement de

« petites » additions.

 Version 3.0 : septembre 2012 changements et

ajouts importants par rapport à la version 2.2;

Pr. M. Alaoui Talibi 302

 Communications collectives non bloquantes;
 Révision de l’implémentation des copies mémoire à
mémoire;
 Fortran (2003-2008) interface;
 Suppression de l’interface C++;
 Interfaçage d’outils externes (pour le débogage et les
mesures de performance);
 etc.

 Version 3.1 : juin 2015

 Correction de l’interface Fortran (2003-2008);
 Nouvelles fonctions pour les écritures collectives non
bloquantes;
Pr. M. Alaoui Talibi 303
Environnement

Pr. M. Alaoui Talibi 304

 Description :

 Touteunité de programme appelant des sous-

programmes MPI doit inclure un fichier d’en-têtes.

 Lesous-programme MPI_INIT() permet d’initialiser

l’environnement nécessaire :

Pr. M. Alaoui Talibi 305

Réciproquement, le sous-programme MPI_FINALIZE()

désactive cet environnement :

Pr. M. Alaoui Talibi 306

Différence entre le C et Fortran :

Concernant le c/c++ :

 Ilfaut inclure le fichier mpi.h ;

 Uniquement le préfixe MPI ainsi que la première
lettre suivante sont en majuscules;
 Hormis MPI_Init(), les arguments des appels sont
identiques au Fortran.

Pr. M. Alaoui Talibi 307

Différence entre le C et Fortran :

Concernant le C/C++ :

 Parameters :
argc[in] Pointer to the number of arguments.
argv[in] Pointer to the argument vector.

Pr. M. Alaoui Talibi 308

MPI sous language C :

Pr. M. Alaoui Talibi 309

 Fichier mpi.h :

 Il doit être inclus en entête de tous les programmes

MPI. A pour but la :

 Déclaration des prototypes de toutes les routines MPI.

 Déclaration de l’ensemble des constantes MPI.

 Déclaration de toutes les structures de données.

Pr. M. Alaoui Talibi 310

Routines MPI :

Les routines MPI (en C) sont sous deux formes :

1- MPI_Xxxx(),
2- MPI_Xxxx_xxx().

Il y a six routines MPI de base :

1- MPI_Init, 2- MPI_Finalize, 3- MPI_Comm_size,

4- MPI_Comm_rank, 5- MPI_Send, 6- MPI_Recv.

Pr. M. Alaoui Talibi 311

Pr. M. Alaoui Talibi 312
 Routine MPI_Init :

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

 C’est la première routine MPI exécutée par tous les

processus.

 Elle permet de débuter l’exécution parallèle.

 Elle renvoie MPI_SUCCESS si l’appel n’a eu aucun

problème.
Pr. M. Alaoui Talibi 313
 int MPI_Finalize(void);

 Elle termine proprement l’exécution parallèle et

doit être appelée par tous les processus.

 Elle renvoie MPI_SUCCESS si l’appel n’a eu aucun

problème.

Pr. M. Alaoui Talibi 314

 MPI_COMM_WORLD :

MPI définit la notion de communicateur (MPI_Comm).

 MPI_Init initialise le communicateur par défaut :

MPI_COMM_WORLD

Pr. M. Alaoui Talibi 315

 int MPI_Comm_size(MPI_Comm comm, int* nprocs);

 Cette routine retourne dans nprocs le nombre total

de processus du communicateur comm.

int MPI_Comm_rank(MPI_Comm comm, int* pid);

 indique le pid d’identifiant relatif au communicateur

comm du processus appelant.
 pid est un nombre entier unique dans le
communicateur comm.
Pr. M. Alaoui Talibi 316
 Initialement,
chaque processus a un identifiant
unique pid ∈ [0,nprocs −1] dans MPI_COMM_WORLD.

Pr. M. Alaoui Talibi 317

Pr. M. Alaoui Talibi 318
 Installation Ubunbtu – Package

$ sudo apt-get install openmpi

openmpi-common
libopenmpi-dev

 Compilation habituelle avec mpicc :

mpicc exemple.c –o exemple

mpirun –np N exemple
Pr. M. Alaoui Talibi 319
 Voir la version ubuntu :

[Link]

Pr. M. Alaoui Talibi 320

 MPI_Send :

Pr. M. Alaoui Talibi 321

Pr. M. Alaoui Talibi 322
 statut
reçoit des informations sur la
communication :

rang_source, etiquette, code,…

Pr. M. Alaoui Talibi 323

 Types de base :

Pr. M. Alaoui Talibi 324

 Communicateurs :

 Toutesles opérations effectuées par MPI portent

sur des communicateurs.

 Lecommunicateur par défaut est MPI_COMM_WORLD

qui comprend tous les processus actifs.

Pr. M. Alaoui Talibi 325

Communicateur MPI_COMM_WORLD

Pr. M. Alaoui Talibi 326

 Arrêt d’un programme :

 Parfoisun programme se trouve dans une situation

où il doit s’arrêter sans attendre la fin normale.

 C’esttypiquement le cas si un des processus ne

peut pas allouer la mémoire nécessaire à son
calcul.

 Dans
ce cas, il faut utiliser le sous-programme
MPI_ABORT().
Pr. M. Alaoui Talibi 327
 comm : tous les processus appartenant à ce
communicateur seront stoppés,

 il est donc conseillé d’utiliser MPI_COMM_WORLD ;

 erreur : numéro d’erreur retourné à l’environnement

UNIX.
Pr. M. Alaoui Talibi 328
 Rang et nombre de processus :

On peut connaître le nombre de processus gérés par

un communicateur par le sous-programme :

MPI_COMM_SIZE() :

Pr. M. Alaoui Talibi 329

 De même, le sous-programme MPI_COMM_RANK()
permet d’obtenir le rang d’un processus

 i.e. son numéro d’instance,

 qui est un nombre compris entre 0 et la valeur

renvoyée par :

MPI_COMM_SIZE() – 1

Pr. M. Alaoui Talibi 330

Pr. M. Alaoui Talibi 331
 Communications point à point :

 Notions générales

 Opérations d’envoi et de réception bloquantes

 Types de données de base

Pr. M. Alaoui Talibi 332

 Notions générales :

 Une communication dite point à point a lieu entre

deux processus,

 l’un appelé processus émetteur et

 l’autre processus récepteur (ou destinataire).

Pr. M. Alaoui Talibi 333

Notions générales :

Communication point à point

Pr. M. Alaoui Talibi 334

 Notions générales :

 L’émetteur et le récepteur sont identifiés par leur

rang dans le communicateur.

 Ce que l’on appelle l’enveloppe d’un message est

constituée :
 du rang du processus émetteur;
 du rang du processus récepteur;
 de l’étiquette (tag) du message;
 du communicateur qui définit le groupe de processus
et le contexte de communication.
Pr. M. Alaoui Talibi 335
 Les données échangées sont typées (entiers, réels,
etc ).

 Ilexiste dans chaque cas plusieurs modes de

transfert, faisant appel à des protocoles différents.

Pr. M. Alaoui Talibi 336

– Opérations d’envoi et de réception bloquantes :

Opération d’envoi MPI_SEND :

Pr. M. Alaoui Talibi 337

– Opérations d’envoi et de réception bloquantes :

 Envoi,à partir de l’adresse message,

 d’un message de taille longueur,
 de type type_message,
 étiqueté etiquette,
 au processus rang_dest dans le communicateur
comm.

Remarque :
Cette opération est bloquante : l’exécution reste bloquée jusqu’à ce
que le contenu de message puisse être réécrit sans risque d’écraser
la valeur qui devait être envoyée.

Pr. M. Alaoui Talibi 338

- Opérations d’envoi et de réception bloquantes :
Opération de réception MPI_RECV :

Réception, à partir de l’adresse message,

d’un message de taille longueur,
de type type_message,
étiqueté etiquette,
du processus rang_source.

Pr. M. Alaoui Talibi 339

Opérations d’envoi et de réception bloquantes :
 Remarques :

 statut reçoit des informations sur la communication :

rang_source, etiquette, code,…

 L’appel MPI_RECV ne pourra fonctionner avec une

opération MPI_SEND que si ces deux appels ont la même
enveloppe (rang_source, rang_dest, etiquette, comm).

 Cette opération est bloquante : l’exécution reste bloquée

jusqu’à ce que le contenu de message corresponde au
message reçu. Pr. M. Alaoui Talibi 340
Opérations d’envoi et de réception bloquantes :

Pr. M. Alaoui Talibi 341

 Types de données de base :

Types de données de base Fortran :

Principaux types de données de base (Fortran)

Pr. M. Alaoui Talibi 342

 Types de données de base :

Types de données de base C :

Principaux types de données de base (C)

Pr. M. Alaoui Talibi 343
Notions générales :

 Les communications collectives permettent de

faire en une seule opération une série de
communications point à point.

 Une communication collective concerne toujours

tous les processus du communicateur indiqué.

Pr. M. Alaoui Talibi 344

 Notions générales :

 Pourchacun des processus, l’appel se termine

lorsque la participation de celui-ci à l’opération
collective est achevée, au sens des communications
point-à-point.

 Lagestion des étiquettes dans ces communications

est transparente et à la charge du système.

Pr. M. Alaoui Talibi 345

Notions générales :

Types de communications collectives

Il y a trois types de sous-programmes :

1- celui qui assure les synchronisations globales : MPI_BARRIER().

2- ceux qui ne font que transférer des données :

 diffusion globale de données : MPI_BCAST() ;

 diffusion sélective de données : MPI_SCATTER() ;
 collecte de données réparties : MPI_GATHER() ;
 collecte par tous les processus de données réparties : MPI_ALLGATHER() ;
 collecte et diffusion sélective, par tous les processus, de données
réparties : MPI_ALLTOALL().

Pr. M. Alaoui Talibi 346

Notions générales :

3- ceux qui, en plus de la gestion des communications,

effectuent des opérations sur les données transférées
:

 opérations de réduction (somme, produit, maximum,

minimum, etc.) : MPI_REDUCE() ;

 opérations de réduction avec diffusion du résultat

(équivalent à un MPI_REDUCE() suivi d’un MPI_BCAST())
: MPI_ALLREDUCE().
Pr. M. Alaoui Talibi 347
 Synchronisation globale : MPI_BARRIER()

Pr. M. Alaoui Talibi 348

 Diffusion générale : MPI_BCAST()

Pr. M. Alaoui Talibi 349

 Diffusion générale : MPI_BCAST()

1- Envoi, à partir de l’adresse message, d’un message

constitué de longueur élément de type type_message,
par le processus rang_source, à tous les autres
processus du communicateur comm.

2- Réception de ce message à l’adresse message pour

les processus y compris le processus de rang_source.
Pr. M. Alaoui Talibi 350
 Diffusion générale : MPI_BCAST()

Pr. M. Alaoui Talibi 351

 Diffusion sélective : MPI_SCATTER()

Pr. M. Alaoui Talibi 352

 Diffusion sélective : MPI_SCATTER()

1- Distribution, par le processus rang_source, à partir de l’adresse

message_a_repartir, d’un message de taille longueur_message_emis,
de type type_message_emis, à tous les processus du communicateur
comm;

2- Réception du message à l’adresse message_recu, de longueur

longueur_message_recu et de type type_message_recu par tous les
processus du communicateur comm.
Pr. M. Alaoui Talibi 353
 Diffusion sélective : MPI_SCATTER()

Remarques :

 Les couples (longueur_message_emis, type_message_emis) et

(longueur_message_recu, type_message_recu) doivent être tels
que les quantités de données envoyées et reçues soient égales.

 Les données sont distribuées en tranches égales, une tranche étant

constituée de longueur_message_emis éléments du type
type_message_emis.

 La ième tranche est envoyée au ième processus.

Pr. M. Alaoui Talibi 354

 Diffusion sélective : MPI_SCATTER()

Pr. M. Alaoui Talibi 355

 Collecte : MPI_GATHER()

Pr. M. Alaoui Talibi 356

 Collecte : MPI_GATHER()

1- Envoi de chacun des processus du communicateur comm, d’un message

message_emis, de taille longueur_message_emis et de type
type_message_emis.

2- Collecte de chacun de ces messages, par le processus rang_dest,

à partir l’adresse message_recu, sur une longueur longueur_
message_recu et avec le type type_message_recu.

Pr. M. Alaoui Talibi 357

 Remarques :

 Lescouples (longueur_message_emis,
type_message_emis) et (longueur_message_recu,
type_message_recu) doivent être tels que les
quantités de données envoyées et reçues soient
égales.

 Lesdonnées sont collectées dans l’ordre des rangs

des processus.

Pr. M. Alaoui Talibi 358

 Collecte : MPI_GATHER()

Pr. M. Alaoui Talibi 359

 Collecte générale : MPI_ALLGATHER()

Pr. M. Alaoui Talibi 360

 Collecte générale : MPI_ALLGATHER()

Pr. M. Alaoui Talibi 361

 Collecte générale : MPI_ALLGATHER()

1- Envoi de chacun des processus du communicateur

comm, d’un message message_emis, de taille
longueur_message_emis et de type
type_message_emis.

2- Collecte de chacun de ces messages, par tous les

processus, à partir de l’adresse message_recu, sur
une longueur longueur_message_recu et avec le type
type_message_recu.
Pr. M. Alaoui Talibi 362
Collecte générale : MPI_ALLGATHER()

Remarques :

 Lescouples (longueur_message_emis,
type_message_emis) et (longueur_message_recu,
type_message_recu) doivent être tels que les
quantités de données envoyées et reçues soient
égales.

 Lesdonnées sont collectées dans l’ordre des rangs

des processus.
Pr. M. Alaoui Talibi 363
 Collecte générale : MPI_ALLGATHER()

Pr. M. Alaoui Talibi 364

– Collecte : MPI_GATHERV()

Pr. M. Alaoui Talibi 365

Pr. M. Alaoui Talibi 366
 Leième processus du communicateur comm envoie
au processus rang_dest, un message depuis
l’adresse message_emis, de taille
longueur_message_emis, de type
type_message_emis, avec réception du message à
l’adresse message_recu, de type
type_message_recu, de taille nb_elts_recus avec
un déplacement de deplts.

Pr. M. Alaoui Talibi 367

Remarques :

Les couples (longueur_message_emis,

type_message_emis) du ième processus et
(nb_elts_recus(i), type_message_recu) du
processus rang_dest doivent être tels que les
quantités de données envoyées et reçues soient
égales.

Pr. M. Alaoui Talibi 368

Pr. M. Alaoui Talibi 369
Pr. M. Alaoui Talibi 370
 Collectes et diffusions sélectives : MPI_ALLTOALL()

Pr. M. Alaoui Talibi 371

 Collectes et diffusions sélectives : MPI_ALLTOALL()

Pr. M. Alaoui Talibi 372

 Correspond à un MPI_ALLGATHER() où chaque
processus envoie des données différentes : le ième
processus envoie la jème tranche au jème processus
qui le place à l’emplacement de la ième tranche.

Remarque :

Les couples (longueur_message_emis,

type_message_emis) et (longueur_message_recu,
type_message_recu) doivent être tels que les
quantités de données envoyées et reçues soient égales.
Pr. M. Alaoui Talibi 373
Pr. M. Alaoui Talibi 374
Pr. M. Alaoui Talibi 375
 Réductions réparties :

Une réduction est une opération appliquée à un

ensemble d’éléments pour en obtenir une seule
valeur.

Des exemples typiques sont la somme des éléments

d’un vecteur SUM(A(:)) ou la recherche de l’élément
de valeur maximum dans un vecteur MAX(V(:)).

Pr. M. Alaoui Talibi 376

 MPIpropose des sous-programmes de haut-
niveau pour opérer des réductions sur des
données réparties sur un ensemble de processus.

 Lerésultat est obtenu sur un seul processus

(MPI_REDUCE()) ou bien sur tous MPI_ALLREDUCE(),
qui est en fait équivalent à un MPI_REDUCE() suivi
d’un MPI_BCAST()).

Pr. M. Alaoui Talibi 377

 Réductions réparties :

Principales opérations de réduction prédéfinies (il existe

aussi d’autres opérations logiques)

Pr. M. Alaoui Talibi 378

 Réductions réparties :

Réduction répartie : MPI_REDUCE() avec l’opérateur somme

Pr. M. Alaoui Talibi 379

 Réductions réparties : MPI_REDUCE()

1. Réduction répartie des éléments situés à partir

de l’adresse message_emis, de taille longueur,
de type type_message, pour les processus du
communicateur comm,

2. Ecrit le résultat à l’adresse message_recu pour

le processus de rang rang_dest.
Pr. M. Alaoui Talibi 380
 Réductions réparties :

Pr. M. Alaoui Talibi 381

 Réductions réparties :

Réduction répartie avec diffusion du résultat :

MPI_ALLREDUCE (utilisation de l’opérateur produit)
Pr. M. Alaoui Talibi 382
 Réductions réparties : MPI_ALLREDUCE()

1. Réduction répartie des éléments situés à partir

de l’adresse message_emis, de taille longueur,
de type type_message, pour les processus du
communicateur comm,

2. Ecrit le résultat à l’adresse message_recu pour

tous les processus du communicateur comm.
Pr. M. Alaoui Talibi 383
 Réductions réparties : MPI_ALLREDUCE()

Pr. M. Alaoui Talibi 384

 Réductions réparties : MPI_ALLREDUCE()

Pr. M. Alaoui Talibi 385