Chapitre 3

Fondements de la Programmation Parallèle

Plan du cours

1. Introduction

2. Modèles, Environnements et Paradigmes de Programmation 3. Evaluation des performances du parallélisme 4. Bibliothèques scientifiques parallèles

1. Introduction

Dans la décennie précédente, le monde a vécu une des plus excitantes périodes dans le développement des ordinateurs : les améliorations des performances des ordinateurs ont été spectaculaires.

De nouveaux paradigmes de programmation, langages, techniques d’ordonnancement et de partitionnement, et algorithmes sont nécessaires pour exploiter efficacement la puissance de ces machines sophistiquées et pour gagner de la puissance soit au niveau

algorithmique, soit au niveau architectural.

2. Modèles, Environnements et Paradigmes de Programmation

2.1. Principales formes de parallélisme

Il existe fondamentalement deux approches pour la programmation parallèle : implicite et explicite .

Approche implicite

Cette approche se traduit par les langages parallèles et les compilateurs paralléliseurs.

Prendre un langage existant et laisser le compilateur faire tout le travail.

Approche idéale du point de vue de l’utilisateur :

- Codes existants peuvent tourner sans rien changer ni optimiser.

- Economie dans les coûts de développement.

Problèmes de cette approche :

Le plein potentiel parallèle d’un problème ne peut pas toujours être exploité.
Pour l’écriture d’un nouveau programme, il est conseillé que le programmeur ait une certaine connaissance sur les possibilités de détection du parallélisme du compilateur afin d’écrire du code qui s’exécute rapidement.

=> déviation du but original de détection automatique du parallélisme.

Approche explicite

Cette approche est justifiée par le fait que l’utilisateur est souvent le meilleur juge de la façon avec laquelle le parallélisme peut être exploité efficacement pour une application particulière.

Avantages :

Les utilisateurs sont déjà habitués aux langages de base.
Pour que leurs programmes s’exécutent efficacement, seulement un ensemble limité de fonctions supplémentaires a besoin d’être appliqué.

Problèmes :

Le programmeur est responsable d’une grande partie de l’effort de parallélisation.
Manque de portabilité : ces langages sont destinés à des classes spécifiques de machines.
Manque de standardisation : beaucoup d’extensions ont été développées avec des fonctionnalités similaires mais des apparences différentes

2.2. Les sources du parallélisme

Exploiter toute la puissance de calcul d’une machine parallèle est souvent difficile :

Les algorithmes et les applications ne possèdent pas tous le même parallélisme potentiel.
Mettre en évidence le potentiel de parallélisme d’un algorithme et l’exploiter au mieux des capacités de la machine reste un problème difficile.

Problème du choix de l’algorithme pour résoudre un problème donné :
- Plusieurs algorithmes séquentiels possibles.
- Le parallélisme extrait du meilleur algorithme séquentiel n’aboutit pas forcément au meilleur algorithme parallèle.
- Chaque algorithme se prête plus ou moins à une parallélisation.

On identifie trois sources de parallélisme : parallélisme de données, parallélisme de tâches (ou de contrôle) et parallélisme de flux .

Parallélisme de données

Exploite comme source de parallélisme la régularité des données

Applique en parallèle un même calcul à des données différentes

Parallélisme de tâches

Consiste à appliquer des calculs différents sur des données différentes en même temps afin de générer du parallélisme

Parallélisme de flux

Correspond à la technique du travail à la chaîne

Chaque donnée subit une séquence de traitement réalisée en mode pipeline en exploitant une régularité des données

Remarque :

Lorsqu’on combine plus qu’un mode, on parle de parallélisme mixte.

2.3. Grain (ou granularité) et degré de parallélisme

Ces deux paramètres sont importants à étudier lorsqu’on parallélise une application. Ils ont une grande influence sur l’efficacité de la parallélisation.

Grain de parallélisme

Taille moyenne des tâches élémentaires qui ont guidé la parallélisation (en nombre d’instructions, temps d’exécution, …).

Le choix du grain de parallélisme est fortement lié à l’architecture sousjacente.

Ce paramètre a généralement une grande influence sur le paramètre du degré de parallélisme.

Niveau de parallélisation Mode

Gros grain

Grain fin

Programmes	MIMD
Sous-Programmes	Sous-Programmes
Instructions	Instructions
Expressions	SIMD
Opérateurs	Opérateurs

Degré de parallélisme

C’est la mesure du nombre de sous-tâches exécutées simultanément dans un programme parallèle. => indication du nombre de processeurs que l’on pourra utiliser.

Il peut fortement varier dans les différentes parties du programme => on considère souvent le degré maximal, moyen et minimal

Ces degrés peuvent être évalués statiquement à la compilation, ou dynamiquement lors de l’exécution.

Remarque :

Bien que l’exécution d’un programme avec un nombre de processeurs égal au degré maximal de parallélisme soit, en principe, la plus rapide, cela ne signifie pas forcément que c’est le nombre optimal de processeurs!

2.4. Modèles d’abstraction

L’étude de modèles théoriques pour le calcul parallèle est de donner des cadres de travail permettant de décrire et d’analyser des algorithmes. Ces modèles « idéals » sont utilisés pour déterminer des bornes de performances et des estimations de complexité. Pas de modèle unique. Différents aspects à considérer :

- Architecture

- Logiciel

- Algorithmes

De nombreux modèles d’abstraction existent pour des architectures parallèles à mémoire partagée et à mémoire distribuée.

Le modèle PRAM

Caractéristiques

PRAM ( Parallel Random Access Machine ) est un modèle de machine utilisé pour modéliser des machines parallèles idéalisées.

Machine constituée d’une infinité de processeurs qui exécutent tous le même calcul en mode synchrone.

Tous les processeurs partagent la même mémoire globale.

Prend en compte l’accès concurrent aux données.

Même coût pour toutes les instructions (lecture, écriture, traitement, …).

Avantages

Simplicité

Problèmes

Difficilement portable sur machines à mémoire distribuée.

Modèle de coût peu réaliste (durée d’un accès = durée d’un calcul).

Les surcoûts dus aux communications et aux synchronisations sont négligés.

Variations sur les PRAM

L’accès à la mémoire commune peut s’effectuer de diverses manières.

4 variantes sont possibles selon qu’un seul processeur ou plusieurs peuvent lire ou écrire dans la même case mémoire :

Lecture Exclusive ( Exclusive Read, ER ) : un seul processeur peut lire dans une case mémoire à un instant donné.
Lecture Concurrente ( Concurrent Read, CR ) : plusieurs processeurs peuvent lire simultanément le contenu de la même case mémoire.
Ecriture Exclusive ( Exclusive Write, EW ) : un seul processeur peut écrire dans une case mémoire à un instant donné.
Ecriture Concurrente ( Concurrent Write, CW ) : plusieurs processeurs peuvent écrire simultanément dans la même case mémoire => Dans ce cas, les procs peuvent posséder des informations différentes, ce qui entraîne un conflit entre eux!

Plusieurs modèles ont été proposés pour résoudre ce problème :

Modèle commun : toutes les écritures concurrentes enregistrent la même valeur.
Modèle arbitraire : une seule valeur choisie arbitrairement est enregistrée.
Modèle prioritaire .
Max, ( min ) : la valeur écrite par le processeur ayant l’index le plus grand (petit) est enregistrée. Les autres valeurs sont ignorées.
etc.

CREW et CRCW sont les variantes les plus importantes

Le modèle par passage de messages

Un algorithme conçu pour un système à passage de message consiste en une collection de programmes locaux s’exécutant sur les différentes unités de calcul dans un système distribué.

Le passage de message dans un système distribué peut être modélisé en utilisant un graphe de communication.

Le graphe de communication peut être direct (communications unidirectionnelles) ou non direct (communications bidirectionnelles).

Le système peut opérer en mode synchrone ou asynchrone.

La communication et la synchronisation sont explicites.

Exemples de librairies de passage de messages :

MPI (Message Passing Interface)
PVM (Parallel Virtual Machine)

2.5. Paradigmes de programmation parallèle

La conception des applications parallèles se base sur l’adoption de paradigmes de programmation bien définis.

Le choix du paradigme adéquat est déterminé par les ressources de calcul parallèles disponibles et par le type du parallélisme inhérent dans le problème.

Quelques paradigmes reconnus.

Un programme = combinaison de plusieurs paradigmes.

Le paradigme « Parallélisme de phases »

Programme = suite d’étapes

Étape = 2 phases : calcul + interaction

Calcul : de multiples processus réalisent chacun un calcul indépendant
Interaction entre les processus :
- synchronisation
- communication bloquante, etc. Inconvénients :
Pas de recouvrement entre l’interaction et le calcul.
Nécessité et difficulté de maintenir l’équilibrage de charge entre les processus.

Le paradigme « Diviser pour Paralléliser »

Découverte dynamique d’un arbre de calculs.

Un processus parent divise le travail entre ses fils.

Les processus fils combinent leurs résultats vers leur père.

Division et regroupement récursifs.

Schéma algorithmique :

Réduction du problème à des instances indépendantes plus petites.
Résolution parallèle récursive des sous-instances, en appliquant récursivement la même technique à chacune des sous-instances.
Construction de la solution du problème initial à partir des solutions de chacune des sous-instances.

Le paradigme « Maître/esclaves »

Un processus maître = coordinateur

exécute le code séquentiel
initie des processus esclaves
transmet du travail à ces processus esclaves
attend les résultats des esclaves
itération de l’assignation de travail

Paradigme simple

Maître = goulot d’étranglement

Paradigme non-extensible

Des processus esclaves

attendent du travail du maître
exécutent le travail
retournent le résultat au maître

3. Evaluation des performances du //sme

L’étude théorique des performances des algorithmes parallèles permet de connaître par exemple

l’efficacité d’un programme,
le gain issu du parallélisme,
son comportement futur dans le cas de l’augmentation du nombre de processeurs,
etc.

Il existe de nombreuses métriques de performances. Les plus utilisées sont les suivantes:

3.1. Terminologie

Soit à résoudre une instance d’un problème de taille n

On note par :

T1(n) le temps d’exécution séquentiel sur un seul processeur
Tp(n) le temps d’exécution parallèle sur p processeurs

3.2. Accélération

On définit le facteur d’accélération, qui permet de mesurer le gain en temps dû à la parallélisation (ou le taux d’utilisation des processeurs), par le rapport :

Sp(n)<1 : on ralentit ! (mauvaise parallélisation) Sp(n) = T1(n) / Tp(n) => 1

Sp(n)

Col1	Accélération Accélération super- idéale linéaire Accélération normale	Col3
ralentissement 1	ralentissement 1	26 p
ralentissement 1	ralentissement	ralentissement

Super-linéaire :

Ce n’est pas magique, et ce n’est pas normal

→ on doit analyser le phénomène et l’expliquer

→ corriger une erreur ou exploiter une optimisation

Exemples d’explications :

On ne fait plus les bonnes opérations (résultat faux)

l’algorithme séquentiel n’est pas le même que l’algorithme utilisé pour la parallélisation, et qu’il est moins efficace.

Les données tiennent dans le cache total des p processeurs

On a modifié l’algorithme de départ et on converge plus vite (exp de l’algorithme génétique optimisé)

On cherche une solution dans un arbre et on stoppe le programme

3.3. Efficacité

On définit l’efficacité, qui est équivalent à un rendement, d’un algorithme parallèle par le rapport :

Ep(n) = Sp(n) / p => 0 (=0%)< Ep(n) <= 1 (=100%)

Ep(n)>1 accélération super-linéaire

Elle permet de mesurer le taux moyen d’utilisation des processeurs.

Plus l’efficacité est proche de 1, plus l’algorithme a de bonnes qualités parallèles.

Exemple (Multiplication de matrices)

Algorithme A Temps en séquentiel = 10 mns Nb procs = 10 Temps en // = 2 mns Accélération = 10/2 = 5 (l’application va 5 fois plus vite) Efficacité = 5/10 = 0.5

Algorithme B Temps en séquentiel = 10 mns Nb procs = 3 Temps en // = 4 mns Accélération = 10/4 = 2.5 < 5 Efficacité = (5/2)/3 = 0.8 > 0.5

Remarque

L’utilisateur s’intéresse surtout à l’accélération obtenue.

L’acheteur de la machine s’intéresse beaucoup à l’efficacité.

Le développeur s’intéresse aux deux.

Choix de la référence séquentielle : A quels programme et exécution séquentielle se comparer ?

Même programme lancé sur un seul processeur ?

Même algorithme implanté en séquentiel ?

Meilleur algorithme séquentiel connu ?

Compilation séquentielle avec le même compilateur ?

Compilation avec le meilleur compilateur séquentiel ?

Optimisations séquentielles autorisées par la parallélisation ?

Optimisations séquentielles maximales ?

Exécution sur un seul processeur de la machine parallèle ?

Exécution sur la meilleure machine séquentielle ?

Tous les choix sont plausibles :

Chaque choix de référence séquentielle correspond à :

Un point de vue différent,

Une préoccupation différente,

Un objectif d’analyse différent

L’important est de faire le choix correspondant à sa problématique

Exemple de choix :

Utilisateur final : SON programme séquentiel sur SA machine séquentielle

Paralléliseur : même algorithme sur un processeur de la machine parallèle

3.4. Sources de perte de performances

Sous-optimisation séquentielle

Fraction séquentielle

Surcoût des opérations de gestion du parallélisme

Surcoût dû aux communications

Déséquilibre de charge

Algorithmique et programmation parallèle

ES séquentielles/séquentialisées Environnement de

développement Sous-optimisation des outils et langages parallèles

Remarque

L’approche précédente est raisonnable pour les machines parallèles à mémoire partagée. Cependant, sur des machines parallèles à mémoire distribuée, elle est insuffisante. Une autre définition du facteur d’accélération a été proposée par Gustafson qui est basée sur la loi d’Amdahl.

3.5. Scalabilité des architectures parallèles

Une architecture // est dite scalable si elle peut être étendue (resp. réduite) à un système plus large (resp. petit) avec une augmentation (diminution) linéaire en sa performance (coût).

La scalabilité est utilisée comme une mesure de la capacité du système à fournir des performances augmentées lorsque sa taille est augmentée, par exemple.

Autrement dit, la scalabilité est une réflexion de la capacité du système à utiliser efficacement l’augmentation des ressources de calcul.

En pratique, la scalabilité d’un système peut être exprimée en différentes formes, incluant la vitesse, l’efficacité, la taille, les applications, la génération et l’hétérogénéité.

Dans un système fortement (resp. faiblement) scalable, la taille du problème nécessite qu’elle augmente linéairement (resp. exponentiellement) en fonction de p pour maintenir une efficacité fixe.

4. Bibliothèques Scientifiques Parallèles

4.1. Motivation

Calcul scientifique – calcul numérique

Algèbre linéaire dense ou creuse
Résolution linéaire directe ou itérative
Résolution non-linéaire
Calcul de valeurs et de vecteurs propres
Transformées de Fourier rapides …

Réduction du temps de développement

Indépendance vis-à-vis de l’implantation

Séquentielle, ou
Parallèle

4.2. Portabilité et efficacité

Généricité (indépendance vis-à-vis du type des données)

Indépendance vis-à-vis de la représentation des données

Choix du meilleur algorithme numérique

Assurance de la stabilité numérique

Optimisation fonction de l’architecture de la machine

Optimisation fonction des paramètres (nombre de colonnes/lignes)

4.3. Bibliothèques monoprocesseurs (séquentielles)

BLAS (Basic Linear Algebra Subroutines) Elle est divisée en trois sections:

BLAS 1 : vecteur/vecteur

BLAS 2 : matrice/vecteur

BLAS 3 : matrice/matrice BLAS niveau 1 :

Première bibliothèque de calcul scientifique

Opérations de type z=αx+y (α scalaire, x, y et z vecteurs)

Traitement élément par élément des éléments des vecteurs

Grand succès

O(n) opérations sur O(n) éléments

BLAS niveau 2 :

Motivés par :

 - Diminution du nombre d’accès mémoire

 - Augmentation du grain de calcul

 - Prise en compte des unités vectorielles pipelines

Opération entre matrices et vecteurs

 - Opérations de type z= βy+αAx (A matrice)

 - O(n [2] ) opérations sur O(n [2] ) éléments

BLAS niveau 3 :

Motivés par :

 - Utilisation maximale des hiérarchies mémoire

 - Minimisation des mouvements de données entre les mémoires

 - Meilleure utilisation des caches

Opération entre matrices et matrice

 - Opérations de type C= βC+αAB (A, B, C matrices)

 - O(n [3] ) opérations sur O(n [2] ) éléments

LAPACK (Linear Algebra PACKage) :

Algèbre linéaire de haut niveau

Résolution de systèmes linéaires
Résolution des moindres carrés
Valeurs propres, valeurs singulières

Factorisation de matrices LU, Cholesky, QR, …

Travail sur des matrices denses ou des matrices bandes : pas de prise en compte de matrices creuses générales

Conçue pour les machines vectorielles. Etendue aux machines parallèles à mémoire partagée.

Utilise des algorithmes par blocs pour utiliser au mieux la hiérarchie mémoire.

Implantée au dessus des BLAS 3.

4.4. Bibliothèques parallèles

Nécessité de versions parallèles des bibliothèques de calcul numérique

Prise en compte de la localité des données

Bonne répartition des données

Equilibrage de la charge de calcul
Recouvrement des accès aux données distantes par des calculs

Versions parallèles des algorithmes

Jusqu’à de nouvelles méthodes numériques

Proposer une bibliothèque parallèle

Paralléliser chacune des fonctions de la bibliothèque
Quel algorithme parallèle ?
Quelle répartition des données ?

Modèle de programmation SPMD d’utilisation des bibliothèques

BLACS (Basic Linear Algebra Communication Subroutines)

Bibiliothèque de communications

Communications spécialisées

Échange de vecteurs/matrices
Lignes/colonnes de matrices : blocs de matrices
Diffusion et réduction
Contexte de la communication : isoler les communications de la bibliothèque et d’autres communications.

BLACS :

Portabilité (versions PVM et MPI)
Efficacité (versions optimisées pour nombres de machines)
Ce n’est pas une bibliothèque générale de communications

PBLAS (Parallel BLAS)

Ce sont les BLAS parallèles

Interface aussi proche que possible de celle des BLAS

Implantée au dessus de BLAS + BLACS

BLAS : calculs locaux
BLACS : communications

Considérée comme un noyau pour d’autres bibliothèques numériques parallèles

ScaLAPACK (Scalable LAPACK)

La référence en terme d’algèbre linéaire dense pour machines à mémoire distribuée.

C’est une bibliothèque domaine public

Implantée au dessus de LAPACK, PBLAS et BLACS

D’autres bibliothèques sont implantées au dessus de ScaLAPACK

Succès de ScaLAPACK

Extensibilité

Garantir les performances quand le nombre de processeurs augmente
Équilibrage de la charge via des distributions cycliques 2D
- Équilibrage de charge pour des petits blocs (grain de distribution)
- Faible coût de communication pour des gros blocs (diminution du nombre de messages)
- Taille de blocs qui soit le bon compromis entre équilibrage de la charge et la latence des communications

Stratégie d’un succès

Code source (Fortran 77 et C), donc portabilité
Structure hiérarchique (BLAS, BLACS, …)
Évolution continue des bibliothèques de base
- Meilleurs algorithmes
- Optimisation pour la majorité des machines (assembleur)
- Rejaillit de suite sur ScaLAPACK

IBM PESSL

PESSL : Parallel Engineering and Scientific Subroutines Library

Bibliothèque mathématique d’IBM : calcul numérique haute performance sur IBM SP et clusters d’IBM RS/6000

Algèbre linéaire, FFT, génération de nombres aléatoires, …

Fondements du Parallélisme

Formes	Sources	Granularité	Modèles	Paradigmes	Performances	Bibliothèques
•Implicite •Explicite	•Données •Tâches •Flux	•Grosse •Moyenne •Fine	•PRAM •Passage de msgs •…	•//me de phases •diviser pour //er •maître/esclaves •…	•Accélération •Efficacité •Scalabilité	•BLAS •LAPACK -------------- •BLACS •PBLAS •ScaLAPACK •PESSL •…