Chapitre 3 Chapitre 3 Chapitre 3 Chapitre 3

Fondements de la Programmation Fondements de la Programmation Fondements de la Programmation Fondements de la Programmation Parallèèèèlelelele Parall Parall Parall

Plan du cours Plan du cours Plan du cours Plan du cours

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

1. Introduction 1. Introduction 1. Introduction 1. Introduction

(cid:1) 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.

(cid:1) 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 2. Modèèèèles, Environnements et Paradigmes de les, Environnements et Paradigmes de les, Environnements et Paradigmes de 2. Mod 2. Mod Programmation Programmation Programmation Programmation

2.1. Principales formes de parallélisme

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

Approche implicite

(cid:1)

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

(cid:1)

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 développées avec des apparences différentes

: beaucoup d’extensions ont été fonctionnalités similaires mais des

2.2. Les sources du parallélisme

(cid:1)

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.

(cid:1)

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

(cid:1) Exploite comme source de parallélisme la régularité des données (cid:1) Applique en parallèle un même calcul à des données différentes

Parallélisme de tâches

(cid:1) 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

(cid:1) Correspond à la technique du travail à la chaîne (cid:1) 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

(cid:1)

Ces deux paramètres sont importants à étudier lorsqu’on parallélise une la application. parallélisation.

Ils ont une grande

l’efficacité de

influence sur

Grain de parallélisme

(cid:1)

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 sous- jacente. Ce paramètre a généralement une grande influence sur le paramètre du degré de parallélisme.

Niveau de parallélisation Mode Programmes

Gros grain

Sous-Programmes

Instructions

Grain fin

Expressions

Opérateurs

MIMD

SIMD

Degré de parallélisme

(cid:1)

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 :

(cid:1)

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 le nombre optimal de forcément que c’est processeurs!

2.4. Modèles d’abstraction (cid:1)

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.

(cid:1) Ces modèles « idéals » sont utilisés pour déterminer des bornes de

performances et des estimations de complexité.

(cid:1) Pas de modèle unique. (cid:1) Différents aspects à considérer :

• • •

Architecture Logiciel Algorithmes

(cid:1) 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

(cid:1)

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

(cid:1) Machine constituée d’une infinité de processeurs qui exécutent tous le

même calcul en mode synchrone.

(cid:1)

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

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

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

Avantages

(cid:1)

Simplicité

Problèmes

(cid:1)

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

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

(cid:1)

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

Variations sur les PRAM (cid:1) (cid:1)

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!

•

(cid:1)

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

(cid:1)

(cid:1) (cid:1) (cid:1)

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 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) •

(communications

2.5. Paradigmes de programmation parallèle

(cid:1)

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 »

: de multiples processus réalisent chacun un calcul

(cid:1) (cid:1)

Programme = suite d’étapes Étape = 2 phases : calcul + interaction •

Calcul indépendant Interaction entre les processus : • • Inconvénients :

synchronisation communication bloquante, etc.

•

• •

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 »

(cid:1)

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 :

(cid:1)

Réduction du problème à des instances plus petites.

indépendantes

Résolution parallèle récursive des appliquant sous-instances, 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» (cid:1)

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

(cid:1) (cid:1) Maître = goulot d’étranglement (cid:1) Paradigme non-extensible

(cid:1) Des processus esclaves • attendent du travail du maître • exécutent le travail •

retournent le résultat au maître

des performances du //smesmesmesme Evaluation des performances du // 3. 3. 3. 3. Evaluation des performances du // des performances du // Evaluation Evaluation

(cid:1)

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

(cid:1)

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) = T1(n) / Tp(n) => 1<Sp(n)≤p : « normal ». Plus Sp est proche de p,

Sp(n)<1 : on ralentit ! (mauvaise parallélisation)

Sp(n)>p : accélération super-linéaire : analyser et

meilleur est l’algorithme parallèle.

Sp(n)

Accélération super-

linéaire

justifier

Sp(n)=p

Accélération idéale

Accélération

normale

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 : (cid:1) On ne fait plus les bonnes opérations (résultat faux) (cid:1)

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

(cid:1) (cid:1) On a modifié l’algorithme de départ et on converge plus vite (exp de

l’algorithme génétique optimisé)

(cid:1) On cherche une solution dans un arbre et on stoppe le programme

3.3. Efficacité

(cid:1)

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 (cid:2)(cid:2)(cid:2)(cid:2) 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

(cid:1)

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 ?

(cid:1) Même programme lancé sur un seul processeur ? (cid:1) Même algorithme implanté en séquentiel ? (cid:1) Meilleur algorithme séquentiel connu ?

(cid:1) (cid:1)

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 :

(cid:1)

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 :

(cid:1) (cid:1)

Utilisateur final : SON programme séquentiel sur SA machine séquentielle : même algorithme sur un processeur de la machine Paralléliseur parallèle

3.4. Sources de perte de performances

(cid:1) Sous-optimisation séquentielle

Aspects séquentiels

(cid:1) Fraction séquentielle (cid:1) Surcoût des opérations de gestion du parallélisme (cid:1) Surcoût dû aux communications (cid:1) Déséquilibre de charge (cid:1) ES séquentielles/séquentialisées (cid:1) Sous-optimisation des outils et langages parallèles

Algorithmique et programmation parallèle

Environnement de développement

Remarque

(cid:1)

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

(cid:1)

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 taille est augmentée, par exemple.

lorsque sa

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

(cid:1)

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 (resp. exponentiellement) en fonction de p pour maintenir une efficacité fixe.

linéairement

augmente

nécessite

qu’elle

ques Scientifiques Parallèèèèlesleslesles 4. Bibliothèèèèques Scientifiques Parall 4. Biblioth ques Scientifiques Parall ques Scientifiques Parall 4. Biblioth 4. Biblioth

4.1. Motivation (cid:1)

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 …

(cid:1)

Réduction du temps de développement

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

•

Séquentielle, ou

Parallèle

4.2. Portabilité et efficacité

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

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

(cid:1)

Choix du meilleur algorithme numérique

Assurance de la stabilité numérique

(cid:1) Optimisation fonction de l’architecture de la machine (cid:1) 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:

(cid:1) (cid:1) (cid:1)

BLAS 1 : vecteur/vecteur BLAS 2 : matrice/vecteur BLAS 3 : matrice/matrice

BLAS niveau 1 :

Première bibliothèque de calcul scientifique

(cid:1) (cid:1) Opérations de type z=αx+y (α scalaire, x, y et z vecteurs) (cid:1) (cid:1) Grand succès (cid:1) O(n) opérations sur O(n) éléments

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

BLAS niveau 2 :

(cid:1) Motivés par :

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

•

Augmentation du grain de calcul

Prise en compte des unités vectorielles pipelines

(cid:1) Opération entre matrices et vecteurs

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

• O(n2) opérations sur O(n2) éléments

BLAS niveau 3 :

(cid:1) Motivés par :

• Utilisation maximale des hiérarchies mémoire • Minimisation des mouvements de données entre les mémoires • Meilleure utilisation des caches

(cid:1) Opération entre matrices et matrice

• Opérations de type C= βC+αAB (A, B, C matrices) • O(n3) opérations sur O(n2) éléments

LAPACK (Linear Algebra PACKage) :

(cid:1)

Résolution de systèmes linéaires Résolution des moindres carrés Valeurs propres, valeurs singulières Factorisation de matrices LU, Cholesky, QR, …

Algèbre linéaire de haut niveau • • • • Travail sur des matrices denses ou des matrices bandes : pas de prise en compte de matrices creuses générales Conçue pour 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.

les machines vectorielles. Etendue aux machines

4.4. Bibliothèques parallèles

(cid:1) (cid:1) (cid:1)

(cid:1)

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

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 • • Versions parallèles des algorithmes • 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 ?

Jusqu’à de nouvelles méthodes numériques

(cid:1) Modèle de programmation SPMD d’utilisation des bibliothèques

BLACS (Basic Linear Algebra Communication Subroutines)

(cid:1) (cid:1)

(cid:1)

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)

(cid:1)

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)

(cid:1)

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

(cid:1)

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

(cid:1)

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

(cid:1)

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 •…

Parallélisme en programmation : Approches implicites et explicites

Parallélisme en programmation : Approches implicites et explicites