Cours Prog Parra Seance 5-23-24
Cours Prog Parra Seance 5-23-24
Cours Prog Parra Seance 5-23-24
INTERFACE HOMME-MACHINE
MOTIVATIONS
Et
celles de 10 nanomètres n’étaient pas prêtes
avant 2017.
- au niveau algorithmique
L’algorithmique
parallèle consiste à réduire la
complexité de certains problèmes parallèles.
Afin
d’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é.
- de placement d’instructions,
- de circulation des données,
- d’utilisation efficace des communications, ..
✓ un niveau technologique,
✓ par un mode d’exploitation et de traitements,
✓ par les langages utilisées
✓ et par les objets traités.
Mémoire magnétique
UAL évoluée
Langage assembleur, puis fortran et Algol.
Exécution par batch d’un seul programme
Multiprocesseurs parallèles
Parallélisme massif
L’introduction
du parallélisme à l’intérieur d’un
programme peut se faire au niveau des procédures.
ou au niveau algorithmique.
Ce
type de parallélisme est traité au niveau du
matériel.
L’utilisation
des multiprocesseurs conduit à une
programmation effective de divers processeurs.
Problème d’optimisation :
S(n,p)≤1/(f+(1-f)/p)
Exemple :
✓ Processus :
✓ Un protocole réseau
Exemples :
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.
Exemple :
A:a;b
Z:x;y;z
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...
✓ parallélisme de données,
✓ parallélisme de contrôle
✓ et parallélisme de flux.
Et
ou les différentes phases peuvent évidemment
manipuler des collections différentes.
Définition :
A l’intérieur du processeur :
Multi-processeurs
Les
instructions peuvent être réarrangées afin
d’améliorer le rendement (out of order execution).
Pr. M. Alaoui Talibi 79
MULTI-CŒUR :
Cœur :
Unité exécutant les instructions dans un processeur
Multi-cœur : plusieurs unités exécutant des
instructions en parallèle.
Un concept ancien :
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
Disponibilité et flexibilité :
Internet :
– Web (http)
Calculsindépendants
Modèle plus distribué que parallèle
Application cible
– Applications parallèles dans les systèmes
parallèles :
Communication, synchronisation, … entre les différentes
Introduction
Processus
Appels système
Ordonnancement des processus
Communication et synchronisation des
processus : l’exclusion mutuelle.
Espace d’adressage
Code (instructions du programme)
Pile
Compteur ordinal
Registres
Variables
…
Un programme peut être exécuté par plusieurs processus.
système.
la norme UNIX :
Ordonnancement garanti
…
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.
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.
Processus A
B est
T T2 bloqué T3 T4
1
temps
2018-2019 144
L’EXCLUSION MUTUELLE
Le sommeil et l’activation
Les sémaphores
…
Si le verrou est déjà à 1, ce qui signifie qu’un autre processus se trouve dans la
peuvent se produire
Un processus qui a testé le verrou et le trouve à 0, perd le processeur avant
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
L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :
Alternance stricte
Code d’entrée dans la section critique des deux
processus
Processus 1 Processus 2
Alternance stricte
Problème :
Solution de Peterson
Combine l’alternance stricte et la variable verrou
2éme cas :
Instruction TSL :
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
L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :
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.
➔ interblocage
Moniteurs
➔ L’échange de message
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.
Attendre le dernier
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
✓ Des pipelines,
✓ Des processeurs vectoriels,
✓ Des machines SIMD,
✓ Les PRAM
✓ Et les circuits booléens et arithmétique
Elles
est basée sur le type d’organisation des flots
de données et des flots d’instructions.
Problèmes :
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.
Figure.
Architecture
synchrone
- ILLIAC IV
- BSP
- STARAN
- MPP
- Et plus récemment les DAP de AMT
Thèse d’invariance :
Le modèle PRAM :
Extensions :
Sp = t1/tp
✓ Loi d’Amdahl
✓ Loi de Minsky
✓ Table de Stone
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
COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :
L’expression est simple si chacune des variables
n’est utilisée qu’une seule fois comme opérande.
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.
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.
Elle concerne :
Parallélisme de récursion :
Fonctionnement de Hadoop
Fonctionnement de HDFS
➢ 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.
CONCEPTION DES APPLICATIONS
CONCURRENTES :
Avantages de Hadoop :