Parallélisme

Professeur
M. Hicham. MEDROMI
hmedromi@[Link]

1
 Plan

 Machines parallèles
 Système parallèle

 Architecture Parallèle

H. MEDROMI AS 2
Menu : plat du jour

Définition du parallélisme
 Concurrence versus distribution
 Parallélisme d’exécution
Exemples de systèmes distribués
Modélisation
dynamique
Problèmes emblématiques
 De la concurrence
 De la distribution
Parallélisme,
concurrence et langage
Systèmes réactifs et éléments en Java

3
Définition du Parallélisme

Eninformatique, on dit que deux instructions, deux

actions, deux calculs sont parallèles si elles/ils
ont lieu (leur exécution a lieu) au même instant

 Notion de simultanéité
 Logique / réel
 Notion de non dépendance

4
Modèle flot de données

T0
T4 T9

T2
T5
T3
T1 T8

T6 T7

5
Trois niveaux de parallélisme

Parallélisme du monde réel

 Analyse
Parallélisme de conception
 Concurrence, processus
Parallélisme d’exécution
 Processeurs, circuits, réseaux

6
Introduction(?) au parallélisme

 Parallélisme
 utiliser plusieurs ordinateurs ensemble pour résoudre des problèmes

 plus gros (taille mémoire, espace disque)

 plus rapidement (puissance CPU)

 Mot clé : efficacité

 Différents domaines de recherche

 théoriques

 algorithmique

 ordonnancement

 pratiques

 supports

 modèles

 si on veut de l ’efficacité les deux sont évidemment liées

7
Environnement logiciel parallèle
 Composants nécessaires pour l’exécution
d ’un programme parallèle
Application

Compilateur

Support d ’exécution

Système d ’exploitation

Hardware

8
Modèles de programmation parallèle
 Définies par
 le compilateur

 le support d ’exécution

 Buts
 facilité de programmation

 proche du séquentiel

 proche d ’un modèle de description d’algorithmes parallèles

 PRAM

 BSP

 efficacité = f(algorithme, compilateur, support, système, hardware)

 portabilité = f(support, algorithme)

 scalabilité

 obsolescence du matériel

 utilisation de plusieurs sites pour la même application (meta-

computing)
9
Les débuts du parallélisme
 Multiprogrammation
 notion de processus
 système Multics (~65)
 toujours d’actualité, au cœur des UNIX et de NT
 Programmation concurrente
 les coroutines (Djikstra, 68)
 multiprogrammation à grain plus fin
 problèmes de synchronisation
 Parallélisme simulé
 pas de machine contenant réellement du parallélisme

10
Parallélisme matériel : première époque
 Processeurs vectoriels (Cray, ~1976)
 circuit spécifique

 opérations arithmétiques élémentaires (+, …)

 données manipulées : vecteurs

 calcule n additions en parallèle au lieu d’une

 contient n ALUs au lieu d ’une avec un seul microcontrôleur pour

tous
 Traitement parallèle sur des données
 même opération sur un ensemble de données

 le parallélisme se fait sur les données (par opposition aux instructions)

 « Parallélisme de données »

 fonctionnement « naturellement » synchrone

 Classification traditionnelle
 SIMD : Single Instruction (flow) Multiple Data

11
Modèle à parallélisme de données
 Principe algorithmique
 définir des structures de données (souvent) régulières (vecteurs,

matrices)
 effectuer une suite d ’opérations simples sur ces structures

 Exemple
Vecteur a[100]; a b c
Vecteur b[100];
Vecteur c[100];

for i:= 1 to 100 dopar

c[i]:=a[i]+b[i];
done

12
 Importance de la compilation

 Le compilateur doit être intelligent

a b c
 Découpage de la boucle
Si le processeur vectoriel ne sait calculer
que 50 additions en parallèle

-> 2 cycles au lieu d ’un

13
Caractéristiques

 Modèle simple et naturel

 programmation simple

 passage direct à partir de l ’algorithme séquentiel

 compilateur peu compliqué à écrire

 efficacité à peu près garantie

 pour les architectures vectorielles et SIMD en général

 cas particulier : le pipe-line (processeurs super-scalaires)

 Adapté à un certain type d’applications

 calcul sur des structures régulières

 applications scientifiques et certaines simulations

14
MPL
 Langage data-parallèle
 pour une machine précise : Maspar MP-1

 machine SIMD de 1024 à 16384 processeurs

 architecture : un processeur performant en scalaire qui comma

16384 processeurs scalaires qui font tous la même chose

 chaque processeur a une mémoire locale associée

 topologie des communications : grille 2D torique

commande

15
 Variables parallèles

 Deux types de variables dans le langage

 scalaire : réside dans la mémoire du processeur maître

 parallèle : réside dans la mémoire de tous les processeurs esclaves

 Syntaxe à la C
int i;
parallel int a,b,c; // définit les variables a,b et c sur tous les processeurs

i=1; // effectué sur le maître seulement

c=a+b; // effectué sur tous les processeurs en même temps
a[0]=12; // effectué sur le processeur 0 seulement
16
Communication entre les processeurs
 Accès à des cases mémoire distantes
 par localisation géographique dans les 8
directions possibles
 N,S,E,W,NE,NE,SE,SW

NW[4].a=12; // accède à la valeur de a d ’un autre processeur

17
Fonctionnement synchrone

 Chaque instruction est décodée par le maître et exécutée par tous les
processeurs
 modèle fondamentalement synchrone

 pas de conflit d ’accès à des variables possible

 Comment est fait a[0]=12 ?

 Chaque processeur a un bit d ’activation

 dit au processeur s ’il doit exécuter l ’instruction ou pas

 activation calculée par le compilateur  complexité

 Programmation de bas niveau

 C-like != fortran par exemple

 découpage des structures par le programmeur

 mais compilateur sophistiqué quand même

 Parallélisme de données sur architecture SIMD

18
Évolution architecturale

 Début 90 : SIMD en perte de vitesse

 composants spécifiques donc chers

 idem pour les réseaux

 dépassé en performances pures par des composants standards

 petit marché donc prix élevé

 rapidement obsolètes

 Réseaux locaux standards deviennent performants

 Fast-Ethernet, Myrinet, etc.

 vous avez vu ça hier

 Les machines parallèles deviennent MIMD

 processeur puissant standard+réseau d ’interconnexion rapide

19
Problèmes du data-parallélisme
 Intelligence du compilateur
 parallélisation automatique des boucles

 calcul des dépendances entre les données

 compliqué, sujet de recherche encore actuelle

 exploitation correcte des machines même non SIMD

 répartition des données sur les processeurs

 problèmes d’alignement, de défaut de cache

 Gestion des structures de données irrégulières

 type liste, arbres, …

 toutes les dépendances complexes entre objets

 le compilateur ne s ’en sort plus!

 Nécessité de langages plus évolués

 HPF ou Fortran 90

20
HPF

 Extension avec modification de la norme Fortran-90

 Défini en 93
 But : avoir rapidement des compilateurs pouvant l ’implanter
 Purement orientés données, ne contient plus de primitives de gestion de
messages ou de synchro
 Vise à l ’efficacité sur architectures distribuées aussi
 Parallélisation non complètement automatique
 directives fournies par le programmeur pour le placement des données

 mais conserve un modèle data-parallèle (boucles FORALL)

21
Le modèle HPF
 Modèle à 4 niveaux
 Objets HPF « normaux » (tableau)

 mappés sur des templates qui représentent des groupes d ’alignement

 définit les contraintes d ’alignement sur et entre les objets

 permet de spécifier aussi la façon de les distribuer sur les

processeurs
 ces templates sont mappés sur des processeurs virtuels (machine

abstraite possédant une topologie), spécification d’une distribution

 les processeurs virtuels sont mappés sur les processeurs physiques

 Intuitivement
 une opération entre deux objets est plus efficace s ’ils sont sur le même

processeur
 ces opérations peuvent être exécutées en parallèle si elles peuvent être

réalisées sur des processeurs différents

22
Fonctionnement de HPF

 Spécification de dépendances entre les objets

 par le mapping sur les templates

 possibilité de lier deux objets pour les aligner de la même manière

 les opérations entre objets alignés à l ’identique sont plus efficaces

 possibilité de réaligner dynamiquement les objets

 Distribution des objets

 définit le mapping des objets sur un ensemble de processeurs abstraits

 but : rapprocher sur la grille des processeurs abstraits les objets qui

interagissent
 deux possibles : BLOCK (suite d ’éléments contigües) et CYCLIC

(pareil mais avec bouclage)

 Instruction FORALL
 ~= au for parallèle mais en plus puissant (description d ’intervalles,…)

23
Fonctionnement de HPF(2)
 Expression d ’indépendance d ’instructions
 par exemple deux instructions dans une boucle

 Spécification de fonctions « locales »

 ne nécessitent pas de communications pour être exécutées -

> efficacité
 Résumons
 langage data-// pour architectures SIMD et MIMD

 alignement/distribution des données

 directives d ’aide au compilateur

 mélange des apports de différents langages

 largement utilisé car disponibilité de compilateurs (Adaptor)

24
Machine Parallèle

25
 Machine Parallèle

Une machine parallèle est essentiellement un ensemble

de processeurs qui coopèrent et communiquent

26
 Processeur

Une machine parallèle est essentiellement un ensemble

de processeurs qui coopèrent et communiquent

27
 Type de parallélisme
On distingue classiquement quatre types principaux
de parallélisme (Taxonomie de Tanenbaum):

SISD SIMD MISD MIMD

De nos jours cette classification peut paraître

un peu artificielle car le moindre micro-processeur
courant inclut lui-même plusieurs formes
de micro-parallélisme.

28
 Micro-Parallélisme
Permet néanmoins d'expliquer les bases
de l'architectures des ordinateurs, séquentiels et
parallèles.
Cette classification est basée sur les notions
de flot de contrôle
(deux premières lettres, I voulant dire ``Instruction'')
et flot de données
(deux dernières lettres, D voulant dire ``Data'').

29
 Description des machines

Machine SISD

Machine SIMD Machine MIMD

Machine MISD

30
 Machine SISD
Une machine SISD (Single Instruction Single Data)
C’est ce que l'on appelle d'habitude une machine de Von Neuman.
Une seule instruction est exécutée et une seule donnée
(simple, non-structurée) est traitée à tout instant.

Le code suivant,
int A[100];
...
for (i=1;100>i;i++)
A[i]=A[i]+A[i+1];
s'exécute sur une machine séquentielle en faisant les additions
A[1]+A[2], A[2]+A[3], etc., A[99]+A[100]
à la suite les unes des autres.
31
 Machine SIMD
Une machine SIMD (Single Instruction Multiple Data)
peut être de plusieurs types, parallèle ou systolique.
En général l'exécution en parallèle de la même instruction
se fait en même temps sur des processeurs différents
(parallélisme de donnée synchrone).
Examinons par exemple le code suivant écrit en
CM-Fortran sur la Connection Machine-5 avec
32 processeurs,

32
 Machine SIMD

Une machine INTEGER I,A(32,1000)

CMF$ LAYOUT A(:NEWS,:SERIAL)
...
FORALL (I=1:32,J=1:1000)
$ A(I:I,J:J)=A(I:I,J:J)+A(I:I,(J+1):(J+1))
Chaque processeur i, 1 £ i £ 32 a en sa mémoire locale une tranche
du tableau A: A(i,1), A(i,2), ..., A(i,1000).
Il n'y a pas d'interférence dans le calcul de la boucle entre les différentes
tranches: tous les processeurs exécutent la même boucle sur leur propre
tranche en même temps

33
 Machine SIMD

Réparation d'un tableau sur les processeurs d'une machine SIMD typique
34
 Machine MISD

Une machine MISD (Multiple Instruction Single Data)

peut exécuter plusieurs instructions en même temps
sur la même donnée. Cela peut paraître paradoxal mais
cela recouvre en fait un type très ordinaire de micro-
parallélisme dans les micro-processeurs modernes :
les processeurs vectoriels et les architectures pipelines.

35
 Machine MISD
Un exemple de ``pipelinage'' d'une addition vectorielle est le suivant.
Considérons le code:

FOR i:=1 to n DO
R(a+b*i):=A(a'+b'*i)+B(a''+b''*i);

A, B et R sont placés dans des registres vectoriels qui se remplissent au

fur et à mesure du calcul.
En ce sens, quand le pipeline est rempli, plusieurs instructions sont
exécutées sur la même donnée

36
 Machine MISD
Temps A ( i ) B ( i ) R ( i )
1 1 . . . 1 . . . . ...
2 21. . 21. . . . ..
3 321 . 321 . . . ..
``
4 43214321 . . ..
5 54325432 1 . ..
6 65436543 21..
etc.

37
 Machine MIMD

Le cas des machines MIMD (Multiple Instruction Multiple Data)

est le plus intuitif.
On a plusieurs types d'architecture possibles :
(1) Mémoire partagée (Sequent)

(2) Mémoire locale avec réseau de communication (Transputer,

Connection Machine, local, par réseau d'interconnexion), ou système
réparti C'est le cas (2) que l'on va voir plus particulièrement avec PVM.
On pourra également simuler le cas (1)

38
Architecture simplifiée d'une machine
à mémoire partagée

39
 Machine MIMD
Une machine MIMD à mémoire partagée (2) est principalement constituée
de processeurs avec des horloges indépendantes, donc évoluant de façon
asynchrone, et communiquant en écrivant et lisant des valeurs dans
une seule et même mémoire (la mémoire partagée).

Une difficulté supplémentaire, que l'on ne décrira pas plus ici, est que
chaque processeur a en général au moins un cache de données, tous
ces caches devant avoir des informations cohérentes aux moments
cruciaux.

40
Interaction monde réel – système
Les acteurs
Système
Humain Vanne

Le monde réel est fait d’Agents particuliers que

l’on appelle acteurs
Le système, que l’on peut décomposer sous
forme d’Agents, interagit avec les acteurs du
monde réel 41