École Nationale Supérieure d’Informatique et

d’Analyse des Systèmes

Partie 3:
Modèles de programmation parallèle

M4.3 Systèmes parallèles

Pr. Fatima Zahra Harmouch

2023-2024 1
Plan
• Pourquoi le parallélisme?
• Processeur multi-core moderne
• Modèle de programmation parallèle
• Les bases de la programmation parallèle
• Programmation parallèle avec OpenMP, MPI
• Graphic processing units and CUDA

2
 Un exemple:
Programmation avec les threads

3
Processus vs Threads
• La duplication des processus fonctionnent bien lorsque les
tâches effectuées par chaque processus sont :
(a) ne sont pas liées, ou
(b) nécessitent une communication bien adaptée aux pipes ou sockets
• Une collaboration plus complexe ou plus fine entre des parties
concurrentes simultanées d'une application est souvent
difficile, voire impossible, lorsque plusieurs processus sont
utilisés
• Lorsque le traitement d'une application est réparti entre plusieurs
processus, le changement de contexte d’exécution diminue
généralement les performances
• Le modèle des threads a été inventé pour résoudre ces
problèmes
• Plusieurs threads partageant un espace d'adressage diminuent plusieurs
sources de surcharge

4
Processus vs Threads
• Le partage d'informations importantes sur l'état entre les
processus est problématique parce que :

- L'échange d'informations sur l'état nécessite des mécanismes IPC (inter-

process communication) coûteux et il n'est souvent pas possible d'obtenir une
cohérence totale entre les copies multiples

• Dans le cadre du modèle de thread, le coût lié au contexte

d’exécution est moindre, toutes les variables globales sont
partagées et l'implémentation de mutex est moins coûteuse

5
Processus vs Threads
• Lorsque vous créez un nouveau processus, une copie complète
du bloc de contrôle du processus parent est copiée dans le
processus enfant.
• Lorsque vous créez un nouveau thread, seuls les composants
du bloc de contrôle du processus qui sont nécessaires à la
création et contrôle du thread sont effectivement alloués au
thread
- Un nouveau ID, une image des registres et quelques autres paramètres
sont alloués au nouveau thread.
- Les régions de code et de données de l'espace d'adressage ne sont pas
copiées, mais sont désormais partagées entre le processus et le thread
• Pour ces raisons, les threads sont souvent considérés comme
des processus légers.
- Moins de changements de contexte et moins d'utilisation de la mémoire par
rapport à un ensemble équivalent de processus.équivalent de processus

6
C’est quoi les Threads? (SW non
pas HW)

• « Light weight process »

• Fil d'exécution indépendante
• Sous-ensemble des processus

7
 C’est quoi les Threads?
• Les threads qui appartiennent au même
processus partagent l'espace d'adressage du
processus.

8
 Processus vs Threads
Le partage des ressources entre des processus distincts n'est pas
aussi facile que le partage entre les threads d'un même processus.

Voyons cet exemple: Processus « Préparer le diner »

Thread 2
Thread 1

Shared address
space Instructions
Code

Data and
variables

9
Processus vs Threads
• Le partage des ressources entre des processus distincts n'est
pas aussi facile que le partage entre les threads d'un même
processus.
• Il existe des moyens de communiquer et de partager des
données entre processus, mais cela demande un peu plus de
travail que la communication entre threads.

Processus 2 Processus 1
10
 Processus vs Threads

• En règle générale, si vous pouvez • Si votre application est destinée à

structurer votre programme avec être distribuée sur plusieurs
plusieurs threads, faites-le ordinateurs, vous aurez
probablement besoin de
processus distincts.

11
 Résumé Processus vs Threads

• Les threads sont "légers" par rapport aux processus, qui sont
plus gourmands en ressources.

• La création et l'arrêt d'un thread nécessitent moins de

overhead qu'un processus

• Les systèmes d'exploitation peuvent passer de l'exécution de

threads d'un même processus à l'exécution de threads de
processus différents.

12
Pthreads API
• pThreads = POSICX threads API
Dans les années 80-90, il existait plusieurs API pour la programmation
de threads sous UNIX.
POSIX.1c (1995) a considéré Pthreads ("POSIX threads") comme
l'API standard pour les threads sous UNIX

Principales parties de Pthreads :

• types de données abstraits (pthread_t, pthread_mutex_t, . .
.)
• gestion des threads (création, "wait", annulation, . . . )
• Mutex
• variables de condition
• …
API très vaste et complexe ! nous ne ferons qu'effleurer la
surface. . .
13
Création d’un thread
Pthread_create

• pthread_create crée une nouvelle thread et renvoie son identité à

l’adresse p_tid
• attr définit les attributs du thread
• fonction est un pointeur sur la fonction qui sera exécutée par l’activité
(cette fonction retourne nécessairement un void * et prend nécessairement
un unique argument de type void *)
• arg correspond à l’argument transmis à la fonction fonction

Cette primitive retourne 0 en cas de succès, un code d’erreur sinon.

14
Définition “section critique”

• Une section critique est une partie du code qui

accède à une ressource partagée et qui doit
être exécutée de manière atomique par rapport
aux autres entités accédant à la même
ressource partagée

• entités = threads
• ressources partagées = toutes les variables non
locales sont par défaut partagée

15
Utilisation de mutex

• Un mutex est un verrou d'exclusion mutuelle.

Une seule unité d'exécution peut maintenir le
verrou.
• Les mutex sont utilisés pour protéger les
données ou d'autres ressources contre les
accès simultanés.
• Un mutex possède des attributs qui spécifient
les caractéristiques du mutex.

16
Section critique: Exemple
#include <pthread .h>
#include " helpers .h“

static long glob = 0;

void *t main ( void *arg ) {
long n = ( long ) arg ;
long i , loc ;
for ( i = 0; i < n; i ++) {
loc = glob ;
loc ++;
glob = loc ;
}
return NULL;
}
17
 Utilisation de mutex
• Pour mettre en œuvre des sections
critiques, nous avons besoin d'un
certain nombre de mécanismes
d'exclusion mutuelle.
• L'API Pthreads propose mutex comme
un mécanisme de synchronisation
rapide pour appliquer l'exclusion
mutuelle entre les threads.

• Terminologie et "protocole" :
1. threads lock mutex ("acquérir")
2. section critique
3. threads déverrouillent le mutex (
"release")

18
 Création de mutex

• La création des mutex de Pthread peut être faite par allocation

statique (c'est-à-dire dans une variable globale) ou dynamique
(en utilisant Malloc)

• L'allocation statique des mutex est plus facile, il suffit de déclarer

une variable globale :

pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER

Inconvénient : vous obtiendrez un mutex initialisé avec divers

attributs par défaut.

19
 Création de mutex

• L'allocation dynamique de mutex est plus flexible et

est réalisée en utilisant :
#include <pthread.h>
int pthread_mutex_init(pthread_mutex_t *restrict mutex,
const pthread_mutexattr_t *restrict attr);
Returns: 0 on success, positive errno en cas d’erreur

• mutex pointe vers une mémoire dynamique

• attr (lorsqu'il n'est pas NULL) permet de spécifier les attributs
du mutex souhaités

20
 Destruction de mutex
• Le mutex alloué dynamiquement doit être détruit
lorsqu'il n'est plus nécessaire en utilisant:

#include <pthread.h>
int pthread_mutex_destroy(pthread_mutex_t *mutex)
Retourne : 0 en cas de succès, positif errno en cas d'erreur

A noter: ne détruisez un mutex que lorsqu'il est déverrouillé, et

qu'aucun autre thread ne le verrouillera plus à l'avenir.

21
 Verrouillage/déverrouillage de
mutex
• Le verrouillage/déverrouillage du mutex est simple à
utiliser :

#include <pthread.h>
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
Returns: 0 on success, positive errno en cas d’erreur

*_lock et *_unlock ont une sémantique évidente.

*_trylock est l'équivalent non bloquant de *_lock

22
Exercice à faire

• Changer le programme précédent pour gérer la

section critique des pthreads

• #include <pthread .h>

#include " helpers .h“

static long glob = 0;

void *t main ( void *arg ) {
long n = ( long ) arg ;
long i , loc ;
for ( i = 0; i < n; i ++) {
loc = glob ;
loc ++;
glob = loc ;
}
return NULL;
}
23
 Un exemple:
Programmation avec ISPC

24
ISPC

▪ Compilateur de programme Intel SPMD (ISPC)

▪ SPMD : Single Program Multiple Data

▪ http://ispc.github.com/
Rappel : exemple de programme du dernier cours
Calculez sin(x) en utilisant le développement de Taylor :
sin(x) = x - x3/3! + x5/5! - x7/7! + ...
pour chaque élément d'un tableau de N nombres réel

void sinx(int N, int terms, float* x, float* result)

{
for (int i=0; i<N; i++)
{
float value = x[i];
float numer = x[i] * x[i] * x[i];
int denom = 6; // 3!
int sign = -1;

for (int j=1; j<=terms; j++)

{
value += sign * numer / denom;
numer *= x[i] * x[i];
denom *= (2*j+2) * (2*j+3);
sign *= -1;
}

result[i] = value;
}
}
sin(x) en ISPC
Calculez sin(x) en utilisant le développement de Taylor : sin(x) = x - x3/3 ! + x5/5 ! -x7 /7 ! + ...

Code C++ : main.cpp Code ISPC : sinx.ispc

Abstraction de la programmation SPMD :

L’appel à la fonction ISPC génère un « gang » :

« instances de programme » ISPC
Toutes les instances exécutent le code ISPC
simultanément
Au retour, toutes les instances sont terminées
sin(x) en ISPC
Calculez sin(x) en utilisant le développement de Taylor : sin(x) = x - x3/3 ! + x5/5 ! -x7 /7 ! + ...

Code C++ : main.cpp

Exécution séquentielle (code C++)

Appel à sinx()
Commencez à exécuter
programCount instances
de sinx() (code ISPC)

Abstraction de la programmation SPMD : sinx() return.

Achèvement des instances du
L’appel à la fonction ISPC génère un « gang » : programme ISPC.
« instances de programme » ISPC Reprendre l'exécution séquentielle
Toutes les instances exécutent le code ISPC Exécution séquentielle (code C++)
simultanément
Au retour, toutes les instances sont terminées

Dans cette illustration, programCount = 8

 sin(x) en ISPC
Affectation « entrelacée » d'éléments de tableau à des instances de programme

Code C++ : main.cpp Code ISPC : sinx.ispc

Mots-clés ISPC :

programCount : nombre d'instances s'exécutant

simultanément dans le gang (valeur uniforme)
programIndex : identifiant de l’instance actuelle dans le
gang.
uniform : Un modificateur de type. Toutes les instances ont la
même valeur pour cette variable. Son utilisation est
purement une optimisation.
Affectation entrelacée d'instances de programme
aux itérations de la boucle

Éléments du tableau de sortie (resultats)

« Gang » d'instances de programme ISPC

Dans cette illustration : le gang contient quatre instances : programCount = 4

ISPC implémente l'abstraction des gangs en
utilisant les instructions SIMD

Code C++ : main.cpp

Exécution séquentielle (code

C)

Appel à sinx()
Commencez à exécuter
programCount
instances de sinx() (code ISPC)

Abstraction de la programmation SPMD : sinx() return.

Achèvement des instances du
L’appel à la fonction ISPC génère un « gang » d’« instances de programme ISPC.
programme » ISPC
Reprendre l'exécution séquentielle
Toutes les instances exécutent le code ISPC simultanément
Au retour, toutes les instances sont terminées Exécution séquentielle (code C++)

Le compilateur ISPC génère l'implémentation SIMD :

le nombre d'instances dans un groupe correspond à la largeur
SIMD du matériel (ou à un petit multiple de la largeur SIMD).
Le compilateur ISPC génère des fichiers binaires (.o)
avec des instructions SIMD
sin(x) dans ISPC : version 2
Affectation « en bloque » des éléments aux instances

Code C++ : main.cpp Code ISPC : sinx.ispc

Affectation en bloque des instances de programme
aux itérations de boucle
Éléments du tableau de sortie (results)

« Gang » d'instances de programme ISPC

Dans cette illustration : le gang contient quatre instances : programCount = 4
 Affectation entrelacée
« Gang » d'instances de programme ISPC

Le gang contient quatre instances : programCount = 4

Instance 0 Instance 1 Instance 2 Instance 3

(programIndex = 0) (programIndex = 1) (programIndex = 2) (programIndex = 3)
Time

_mm_load_ps1
i =0
0 1 2 3

i =1
4 5 6 7

I =2 8 9 10 11

I =3 12 13 14 15
L'instruction SSE (_mm_load_ps1) single« packed load » ...
implémente d’une manière efficace: // suppose N % programCount=0
for (uniform inti=0;i<N; i+=programCount)
Float value=x[idx] ; {
pour toutes les instances de programme, puisque les Int idx = i + programIndex;
quatre valeurs sont contiguës en mémoire float value = x[idx];
...
 Affectation en bloques
« Gang » d'instances de programme ISPC

Le gang contient quatre instances : programCount = 4

Instance 0 Instance 1 Instance 2 Instance 3

(programIndex = 0) (programIndex = 1) (programIndex = 2) (programIndex = 3)
time

i =0
0 4 8 12 _mm_i32gather

i =1 1 5 9 13

I =2 2 6 10 14

I =3 3 7 11 15
Float value = x[idx];
uniform int count = N / programCount ;
Dans ce cas on a 4 valeurs non contiguës en int start= programIndex * count;
mémoire. for ( uniform int i=0; i < count; i++ ) {
Besoin d'une instruction « gather » pour int idx = start + i ;
implémenter (gather est une instruction SIMD plus float value = x[idx] ;
...
complexe et plus coûteuse : disponible uniquement
depuis 2013 dans le cadre d'AVX2)
Un niveau d’abstraction de plus avec foreach
Calculez sin(x) en utilisant le développement de Taylor : sin(x) = x - x3/3 ! + x5/5 ! -x7 /7 ! + ...

Code C++ : main.cpp Code ISPC : sinx.ispc

foreach : Mot clé du langage ISPC

▪foreach déclare les itérations de boucles

parallèles
▪-Le programmeur indique: ce sont les itérations
que les instances d'un gang doivent effectuer
d’une manière coordonnée
▪l’implementation d'ISPC attribue les itérations
aux instances du gang
▪- L'implémentation actuelle d'ISPC effectuera
une affectation statique entrelacée
ISPC : abstraction et implémentation
▪ Modèle de programmation (SPMD) Single Program Multiple Data

- L'exécution d'un gang consiste à créer des flux d'instructions logiques pour

programCount (chacun avec une valeur différente de programIndex)

- C'est l'abstraction de la programmation

- Le programme est écrit en termes de cette abstraction

▪ Implémentation d'une instruction unique, de données multiples (SIMD)

- Le compilateur ISPC émet des instructions vectorielles (SSE4 ou AVX) qui exécutent la
logique réalisée par un gang ISPC

- Le compilateur ISPC gère le mappage du flux de contrôle conditionnel aux instructions

vectorielles
Discussion ISPC
Calculer la somme de tous les éléments du tableau en parallèle

sum est de type uniform float (une copie de la variable pour toutes les instances du programme)

x[i] n'est pas une expression uniforme (valeur différente pour chaque instance du programme)

Résultat : erreur de type à la compilation

Discussion ISPC
Calculer la somme de tous les éléments du tableau en parallèle

Chaque instance cumule une somme partielle privée (pas de

communication)
Les sommes partielles sont additionnées à l'aide de la primitive de
communication inter-instances reduction_add() . Le résultat est la
même somme totale pour toutes les instances du programme
(reduce_add() renvoie un foat uniforme)

Le code ISPC à droite s'exécutera d'une manière similaire à

l'implémentation manuscrite des intrinsèques C + AVX ci-dessous.
ISPC « Task »

▪ L' abstraction du gang ISPC est implémentée par des instructions SIMD
sur un cœur.

▪ Donc... tout le code que je vous ai montré dans les diapositives

précédentes aurait été exécuté sur un seul des quatre cœurs de la
machine.

▪ ISPC contient une autre abstraction : « task » qui est utilisé pour

réaliser une exécution multicœur.

La seconde section

▪ Trois modèles de programmation parallèle

- Qui diffèrent dans la communication présentées au programmeur

- Les modèles de programmation influencent la façon dont les programmeurs

réfléchissent lorsqu'ils écrivent des programmes

▪ Trois architectures machines

- Abstraction présentée par le matériel aux logiciels de bas niveau

- Reflétent généralement les capacités de mise en œuvre du matériel

Nous nous concentrerons sur les différences en matière de communication et de

coopération
Couches du système : interface, implémentation, ...

Applications parallèles
Exemple : exprimer le parallélisme avec pthreads

Application parallèle
Exemple : exprimer le parallélisme avec ISPC
Applications parallèles
 Trois modèles de communication

1.Espace d'adressage partagé

2.Passage de messages

3.Données parallèles
Modèle de communication avec
espace d'adressage partagé

46
Modèle d'espace d'adressage partagé (abstraction)

▪ Les threads communiquent en lisant/écrivant sur des variables

partagées
▪ Les variables partagées sont comme un grand tableau d'affichage
- N'importe quel thread peut lire ou écrire dans des variables partagées
Modèle d'espace d'adressage partagé (abstraction)

Les primitives de synchronisation sont également des variables partagées : par

exemple, les verrous
Modèle d'espace d'adressage partagé (abstraction)

▪ Les threads communiquent par :

- Lecture/écriture sur des variables partagées

- La communication inter-thread est implicite dans les opérations de mémoire
- Le fil 1 stocke vers X

- Plus tard, le thread 2 lit X (et observe la mise à jour de la valeur par le thread 1)

- Manipulation des primitives de synchronisation

- par exemple, garantir l'exclusion mutuelle via l'utilisation de verrous

▪ Il s'agit d'une extension naturelle de la programmation séquentielle

- En fait, jusqu'à présent, toutes nos discussions en classe ont supposé un espace
d'adressage partagé !

▪ Analogie utile : les variables partagées sont comme un grand tableau

d'affichage
- N'importe quel thread peut lire ou écrire dans des variables partagées
Implémentation HW d'un espace d'adressage partagé
Idée clé : n’importe quel processeur peut référencer directement n’importe quel
emplacement mémoire

Multiprocesseur symétrique (à mémoire partagée) (SMP) :

- Temps d'accès mémoire uniforme : le coût d'accès à une adresse mémoire non
mise en cache est le même pour tous les processeurs
Architectures matérielles d’espace d’adressage
partagé
Exemples de produits x86
SUN Niagara 2 (UltraSPARC T2)
Accès mémoire non uniforme (NUMA)
Tous les processeurs peuvent accéder à n'importe quel emplacement mémoire, mais... le coût de

l'accès à la mémoire (latence et/ou bande passante) est différent selon les processeurs.

• Problème lié à la préservation d'un temps d'accès uniforme dans un système : extensibilité
- Avantage: les coûts sont uniformes, Désavantages: ils sont uniformément mauvais (la mémoire
est uniformément éloignée)

• Les conceptions NUMA sont plus extensible.

- Faible latence et large bande passante vers la mémoire locale

• Le coût additionnel lié à l'effort du programmeur pour l'optimisation des performances.

- La recherche et l'exploitation de la localité sont importantes pour les performances(on veut que la
plupart des accès à la mémoire se fassent dans les mémoires locales)
Accès mémoire non uniforme (NUMA)
Exemple : la latence pour accéder à l'adresse x est plus élevée pour les cœurs 5 à
8 que pour les cœurs 1 à 4
SGI Altix UV 1000
▪ 256 lames, 2 processeurs par lame, 8 cœurs par processeur = 4 096 cœurs

▪ Espace d'adressage partagé unique

▪ Interconnexion : fat tree
Résumé : modèle d'espace d'adressage partagé
• Abstraction de la communication

- Threads lisent/écrivent des variables partagées

- Les threads manipulent les primitives de synchronisation : verrous, mutex, etc.

-Extension logique de la programmation monoprocesseur

• Nécessite un support matériel pour une mise en œuvre efficace

-N'importe quel processeur peut charger et stocker à partir de n'importe quelle

adresse (son espace d'adressage est partagé !)

-Même avec NUMA, la mise à l'échelle est coûteuse

(une des raisons pour lesquelles les supercalculateurs sont chers)

Modèle de passage par messages

57
 Modèle de passage de messages (abstraction)

▪ Les threads fonctionnent dans leurs propres espaces d'adressage privés

▪ Les threads communiquent en envoyant/recevant des messages

-send : spécifie le destinataire, le buffer à transmettre et l'identifiant de message facultatif (« tag »)
-receive : l'expéditeur, spécifie le buffer pour stocker les données et l'identifiant de message
(facultatif)
- L'envoi de messages est le seul moyen d'échanger des données entre les threads 1 et 2
 Modèle de passage de messages (implémentation)

▪Bibliothèque logicielle populaire : MPI (message passing interface)

▪Le HW n'a pas besoin d'implémenter les données et le stockage à l'échelle du système
entier pour exécuter des programmes de passage de messages (il suffit de pouvoir
communiquer par des messages).
- Possibilité de connecter des systèmes différents pour former une grande machine
parallèle (le passage par messages est un modèle de programmation pour les clusters)
La correspondance entre les modèles de
programmation et les types de machines est floue

▪ C’est commun d’implémenter des abstractions de passage de messages sur machines

qui implémentent un espace d'adressage partagé dans le HW

-"Envoi de message" = copie de la mémoire depuis les buffers de la bibliothèque de

messages

-"Réception de message" = copier les données des buffers de la bibliothèque de

messages

▪ Peut implémenter l'abstraction de l'espace d'adressage partagé sur les machines qui ne
la prennent pas en charge dans le matériel (via une solution logicielle moins efficace)

-Marquer toutes les pages avec des variables partagées comme invalides

-Le gestionnaire de défauts de page émet des requêtes réseau appropriées

▪ Gardez à l'esprit : quel est le modèle de programmation (abstractions utilisé pour

implémenter le programme) ? et quelle est la mise en œuvre matérielle ?
Modèle données parallèles

61
Rappel : les modèles de programmation imposent une
structure aux programmes

▪ Espace d'adressage partagé : très peu de structure

- Tous les threads peuvent lire et écrire sur toutes les variables partagées

- Mais : dû à l'implémentation : toutes les lectures et écritures n'ont pas le même

coût (et ce coût n'est pas apparent dans le texte du programme)

▪ Passage de messages : communication très structurée

- Toutes les communications se font sous forme de messages (peut lire le programme
et voir où se trouve la communication)

▪ Data-parallel : structure de calcul très rigide

- Les programmes exécutent la même fonction sur différents éléments de données en
collection
Modèle données-parallèles
▪ Historiquement : même opération sur chaque élément d'un tableau
- Capacités équivalentes aux supercalculateurs SIMD des années 80

- Connection Machine (CM-1, CM-2) : des milliers de processeurs, une unité de décodage
d'instructions

- Supercalculateurs Cray : processeurs vectoriels

- add(A,B,n) ← c'était une instruction sur les vecteurs A, B de longueur n

▪ Matlab est un autre bon exemple : C = A + B (A, B et C sont des vecteurs de même longueur)

• Aujourd'hui : prend souvent la forme d'une programmation SPMD

- map(function,collection)

- Ou ‘function' est appliquée indépendamment à chaque élément de la collection

- 'function' peut être une séquence logique complexe (par exemple, une boucle)

-La synchronisation est implicite à la fin de ‘map’ (‘map’ termine lorsque la fonction a été

appliquée à tous les éléments de la collection)

Parallélisme des données dans ISPC

Considérez la boucle comme 'function' (de la

diapositive précédente)

la construction foreach est une ‘map’

Compte tenu de ce programme, il est

raisonnable de considérer le programme
comme mappant le corps de la boucle sur
chaque élément des tableaux X et Y.

Mais si l’on veut être plus précis : la collection

n’est pas un concept ISPC de premier ordre. Il
est implicitement défini par la manière dont le
programme a implémenté la logique
d'indexation des tableaux.
(Il n'y a pas d'opération dans ISPC avec la
sémantique : « mapper ce code sur tous les
éléments de ce tableau »)
Parallélisme des données dans ISPC

Considérez le corps de la boucle comme

'function'
foreach est 'map’
'collection' est implicitement définie par la
logique d'indexation des tableaux

C'est également un programme ISPC

valide !

Il prend la valeur absolue des éléments de x, puis la

répète deux fois dans le tableau de sortie y

(Il est moins évident de considérer ce code comme

mappant le corps de la boucle sur des collections
existantes.)
Parallélisme des données dans ISPC

Considérez le corps de la boucle comme

'function'
foreach est 'map’
'collection' est implicitement définie par la
logique d'indexation des tableaux

Ce programme est non déterministe !

Possibilité d'écrire plusieurs itérations de la boucle dans
le même emplacement mémoire

Le modèle parallèle aux données (foreach) ne fournit

aucune spécification de l'ordre dans lequel les itérations
se produisent

Le modèle ne fournit aucune primitive pour

l'exclusion/synchronisation mutuelle) . Il n'est pas
destiné à aider les programmeurs à écrire des
programmes avec cette structure
Parallélisme des données : une méthode plus «
appropriée »
Remarque : il ne s'agit pas de syntaxe ISPC

Le parallélisme des données exprimé sous

cette forme fonctionnelle est parfois appelé
modèle de programmation de flux.

Streams: collections d’éléments. Les

éléments peuvent être traités
indépendamment

Noyaux : fonctions sans effets aléatoires ,

opérent sur les collections

Considérez les entrées, sorties et

temporaires du noyau pour chaque appel
comme un espace d'adressage privé
Avantages de la programmation en stream
Les fonctions sont sans effets aléatoires! (ne peut
pas écrire un programme non déterministe)
Le flux de données du programme est connu par
le compilateur :
Les entrées et sorties de chaque invocation sont
connues à l'avance : la pré-extraction peut être
utilisée pour masquer la latence.
L'implémentation peut être structurée de manière à
ce que les sorties du premier noyau soient
immédiatement traitées par le deuxième noyau.
(Les valeurs sont stockées dans des
tampons/caches intégrés et jamais écrites en
mémoire ! Économise de la bande passante !)
Ces optimisations relèvent de la responsabilité du
compilateur du programme de flux. Nécessite une
analyse globale du programme.
Inconvénients de la programmation en stream
Besoin d'une bibliothèque d'opérateurs pour
décrire des flux de données complexes (voir
utilisation de l'opérateur de répétition à gauche
pour obtenir le même comportement que le code
ci-dessous)

Notre expérience : attendons et espérons que le

compilateur est suffisamment intelligent pour
générer le code ci-dessous à partir du
programme de gauche.

C’est le point faible de tous les « bons

» systèmes de programmation de
données parallèles/stream.

Si seulement il y avait un autre

opérateur de plus…
Gather/scatter: deux mots clés de communication
données parallèle
L’instruction Gather
Résumé : modèle données parallèle

▪ Le modèle données parallèle consiste à imposer une structure de

programme rigide pour faciliter une programmation simple et des
optimisations avancées.

▪ Structure de base : mapper une fonction sur une grande collection de données
-Fonctionnel : exécution sans effets aléatoires
-Aucune communication entre les fonctions distinctes
(permettre l’execution planifiées dans n'importe quel ordre, y compris en parallèle)

▪ En pratique, c'est ainsi que fonctionnent de nombreux programmes simples.

▪ Mais... de nombreux langages de données parallèles modernes axés sur les

performances n'appliquent pas strictement cette structure
- ISPC, OpenCL, CUDA, etc.

- Ils choisissent la flexibilité/familiarité d'une syntaxe de style C plutôt qu’une forme

plus fonctionnelle : c'est la clé de leur adoption
Trois modèles de programmation parallèle

▪ Espace d'adressage partagé

• La communication est non structurée, implicite dans les chargements et les enregistrements

• Manière naturelle de programmer, mais:

- Le programme est peut-être correct, mais n’a pas une bonne performance

▪ Passage de message
• Structurer toutes les communications sous forme de messages
• Il est souvent plus difficile d'obtenir le premier programme correct que l'espace d'adressage
partagé

• Structure souvent utile pour parvenir au premier programme correct et extensible

▪ Données parallèles
• Structure se calcul sous forme de ‘map’ sur une collection
• Suppose un espace d'adressage partagé à partir duquel charger les entrées/stocker les résultats,
mais le modèle limite considérablement la communication entre les itérations de 'map’ (objectif :
préserver le traitement indépendant des itérations)

• Les réalisations modernes encouragent, mais n'imposent pas, cette structure

Pratique moderne : modèles de programmation
mixtes
▪ Utiliser la programmation d'espace d'adressage partagé au sein d'un nœud

multicœur d'un cluster et utiliser le passage par message entre les nœuds

- Très, très courant en pratique

- Utiliser la commodité de l'espace d'adressage partagé là où il peut être
implémenté efficacement (au sein d'un nœud), nécessiter une
communication explicite ailleurs

▪ Les modèles de programmation données parallèle prennent en charge les primitives

de synchronisation de style mémoire partagée dans les noyaux
- Autorisent des formes limitées de communication (par exemple, CUDA, OpenCL)

▪ CUDA / OpenCL utilisent un modèle données parallèle pour s'adapter à plusieurs

cœurs, mais adoptent un modèle d'espace d'adressage partagé permettant aux threads
exécutés sur le même cœur de communiquer.
Laboratoire national de Los Alamos : Roadrunner
Ordinateur le plus rapide au monde en 2008 (ce n'est plus vrai) Cluster de 3 240
nœuds. Nœuds hétérogènes.
 Résumé
▪ Les modèles de programmation offrent un moyen de réfléchir à l’organisation des programmes
parallèles. Ils fournissent des abstractions qui permettent de nombreuses implémentations
possibles.

▪ Les restrictions imposées par ces abstractions sont conçues pour refléter les réalités du
parallélisme et des coûts de communication.

-Machines à espace d'adressage partagé : le matériel prend en charge n'importe quel

processeur accédant à n'importe quelle adresse

-Machines de passage de messages : peuvent disposer d'un matériel permettant d'accélérer

l'envoi/la réception/la mise en mémoire tampon des messages.

• En pratique, vous devrez être capable de penser de différentes manières

-Les machines modernes offrent différents types de communication à différentes échelles

-L'optimisation peut nécessiter que vous réfléchissiez aux implémentations, pas seulement
aux abstractions